月份: 2021 年 8 月

最近剛好公司某個專案需要將資料傳輸到遠端的某個服務上，而那個服務可能會有頻寬上的限制，所以我們的資料傳送端必須加入Rate limit這功能，以免瞬間的資料流造成資料被丟棄的問題；也趁這個機會多整理一點 Rate limit相關的知識…

rate limiting vs throttling

這兩個名詞常分別或一起出現在討論rate limiting 的相關文章中，而我也常搞混這兩個詞的意義，所以稍微再整理一下它們所代表的意思：

Rate limiting 指的是，限制requests在某個時間區間內，其可允許執行requests的數量。

Throttling 指的是，控制requests在特定的時間區間內出現時，允許可執行requests的 一種流程。

一個簡單的例子是，當我們限制某個API 每秒只能執行 100次，這是一個Rate limiting的流程；而當我們再把時間看得更細時，平均我們每100 ms 可以服務10個requests。
在這 100 reqs/s的情境下，控制requests 可以被服務的頻率的一個程序就是throttling。
* 這邊我們可以控制當requests 超過 10 reqs/100ms，就被丟棄 或是可以允許requests 最多到burst 20 reqs/100ms)
* 另一種Throttling的情境是，在某一秒的requests數量為105，那超過的這5個requests 我們可以允許它們被服務(soft throttling)或直接丟棄那5個requests(hard throttling)

簡而言之，Rate limiting比較偏向資源服務在大方向的一個規範，而Throttling責聚焦在實作上一些情境下的處理流程。

Rate limiting 相關演算法

Token bucket

Token bucket 主要的概念是，想像我們有一個水桶，裡面最多可以放到n 個token；每使用者需要使用某個資源時，他就必須到水桶中取走一個token，而如果水桶中沒有任何的token時，則使用者無法使用他想要用的資源。

而水桶中的token 會依照 1/n second的速率補充到水桶中，當水桶補滿n個token時，就不再補充任何的token了。

特色：

• 如果水桶中的token是滿的，其會允許使用者瞬間可以同時索取n個token，也就是允許requests 最多同時burst到n個。
• 可能會導致某個時間區間下，各個時間點request量不平均。
• Golang 有內建的lib 原生支援這個演算法。
• 主要的應用在於，如果我們必須限制我們的requests在固定區間下是有限的，但區間下的每個時間點是允許突然暴增的requests。

Leaky bucket

Leaky bucket 是常用來與Token bucket比較的一個演算法；其概念上是，我們會有一個水桶，並且我們有定義好這個水桶可以往下流出的速率，當我們的requests的量大於可允許流出的速率時，則會被queue起來；而同時間我們也會定義水桶中最多可允許queue起來的量，如果超過時，則這些新的requests 則會被丟棄。

特色：

• 概念上對於burst requests的限制較嚴，主要是用來維持每個時間點下的requests流量是固定的。
• Golang 中可以參考uber-go/ratelimit 這套 open source solution。
• 比較適合像是，網路頻寬或流量控制的相關應用。

相關文章：

• https://www.geeksforgeeks.org/leaky-bucket-algorithm/

Fixed window counter

這個演算法的概念是，我們定義每個時間區間下可以允許的requests 量是n，而這個區間間是固定的。(例如 [12:00:01-12:00:02), [12:00:02, 12:00:03) )
每個區間會有個counter，每當有新的request時，我們就會有個計算目前這個區間下已count的量，如果加入這個request會導致count > n，則我們會丟棄這個新的request。

特色：

• 實作上相對簡單，且對burst的限制較不嚴。
• 如果requests 量剛好發生的時間在，前一個區間的下半段與下一個區間的上半段時，則可能發生這段跨區間的requests量是我們原本定義的n的2倍。
  (e.g. 假設我們每個區間的允許的量是n ，而有n個requests發生在[12:01:30, 12:02:00)，另外n個requests發生在[12:02:00, 12:02:30)，則如果我們單看區間[12:01:30, 12:02:30)時，會發現requests量可能暴增到2n。)

Sliding window logs

這個演算法類似於Fixed window counter，會針對每一個request記錄其發生的時間，所以當一個新的request出現時，演算法會去比較目前時間點回推到過去的某個時間點下，這段時間區間中的request數量，再來衛量這個新的request是否允許，如果不允許的話，則這個新的request則會被丟棄。

隨著時間的流動，已經過期的request 記錄也會被清除…

特色：

• 解決了Fixed window counter演算法可能會遇到的request burst問題。
• 實作上，可能計算會相對較秏資源；因為每次要確認一個新的request是否允許時，需要從目前時間點往回計算，而且過期的記錄要刪除也會是額外要做的事。

Sliding window counter

這個演算法是整合了Fixed window counter + Sliding window log的演算法的作法；概念上也是使用Fixed window counter的概念，只是每個時間區間又再切成多個子區間，所以每次在比對某個request是否可以服務時，就是比對目前時間點下的子區間再加上過去發生過的多個子區間之count 總合，如果低於某個值rate limit最初設定的值的話，那就代表這個新的request 是可以被服務的，反之則丟棄這個request。

舉例來說，我們定義某個API 的 rate limit 為每秒n個，則在實作上，我們可以多切10個子區間， 所以每個子區間的間隔會是100ms，以12:00:01這個區間為例，實際上記錄的子區間有12:00:01.1, 12:00:01.2 … 12:00:01.9 等等。
所以當一個新的request發生時，演算法會去計算目前這個子區間所有的count數量以及過去9個子區間count 數量的總合，再來比對加入這個新的request是否還是小於 n，如果是的話則允許服務這個api request。

特色：

• 整合了Fixed window counter 與Sliding window log的優點，且實作上也不難實現。

在分散式系統上的一些實務上作法

使用Central Storage – Redis/memcached

這是一個蠻常見的作法，透過一個高效的儲存db來存放一些狀態資料，每當一個新的request發生時，就先去儲存db獲取先前儲存的狀態(token/count… etc)來判定目前的request是否可以被服務。

特色：

• 效能瓶頸會是在redis/memcached本身，不過對大多數的應用來說應該是夠用了。
• 網路上可以找到蠻多資源的，相關的教學文或已經寫好的open source library。
• 若單存使用Redis/Memcached所提供的一般API時，可能在大量request發生時要小心處理race condition的問題。(或許要額外引入distributed lock之類的機制)
• 如果使用Redis + Lua時，則可以實現atomic operation，解決race condition的問題。

相關文章：

• https://redis.io/commands/incr#pattern-rate-limiter
• github 使用Redis rate limiting 的經驗
• 透過Stripe 透過redis +Lua來做 rate limiting?
• Figma 的相關rate limiting實作
• https://github.com/wallstreetcn/rate
• https://medium.com/@justin.graber/rate-limiting-in-golang-f3ed2c62df36
• https://medium.com/analytics-vidhya/custom-rate-limiting-in-golang-using-redis-with-docker-e4a7be96f7dc
• Go redis的實作

使用client based rate limiting

概念上是rate limit 的管理是放在client service 那邊管理的，而所有的client service 會透過一個central storage 來獲取某個API/Resource的total rate limiting與client rate limiting 。

舉例來說，我們可以在etcd上設定某個API的rate limiting為n，並且也記錄了目前註冊過的client service數量m，所以每個client service 相對於這個API的rate limit就會是n/m, 這樣每次client service在服務request時就只需要直接參考目前本機上的rate limit (n/m)就可以了。
而在這個例子下，我們還可以透過ectd的watch 機制來讓所有的client service即時的獲取更新後的n 與 m值。

特色：

• 效能可以到非常好，因為rate limit是實作在client 端，所以特別適合超大流量的應用。
• 有個先決條件為，流量必須很平均的分散在所有的client端，這樣才會更有效的使用到所有分配到rate。
• 作為取捨，對於rate limit的控制會相對沒那麼精準，畢境如果有client端的service 掛掉了，會有段時間差，之後所有的client才會獲取得最新的資訊。

相關文章：

• https://engineering.linecorp.com/en/blog/high-throughput-distributed-rate-limiter/

自行設計的rate limit cluster

mailgun這間公司有open source了一套Go的distributed rate limit service – guberator，其概念上是把micro services的概念應用到rate limit service上，每個client端的機器，都會另外在佈署這個gubernator peer，而gubernator之間是靠grpc來溝通的。

每個gubernator都會管理不同resource的rate limit，所以每當某個client service要服務某個request時，它會需要與本機端的gubernator詢問request 相關的limit，而本機端的gubernator 則會知道相對應的資訊是存在本機或是其它的gubernator上。

由於資訊還是由某個gubernator管理，所以理論上也會受限於單機可以處理的上限，但在這邊gubernator有透過一個自行實作的batch機制來提高機器處理的上限值。

這個機制也蠻容易理解的，主要就是再處理rate limit request之前，先把收到的requests 打包起來再送出去成一個單一的batch request。從文章上有提到，batch機制的預設是每當收到對於某個resource的第一個request時，會再等500 micro seconds來收集更多對同一個resource的請求，當時間到了以後，再處理這一包batch過的rate limit request；
假設在這段時間內，收到3000 個對於某個resource的rate limit requests，則只需要某個gubernator送出一個rate limit request，其request quota量為3000，接下來就只需要看收到request的gubernator它那邊會允許多少quote是可以被執行的。

相關文章：

• https://www.mailgun.com/blog/gubernator-cloud-native-distributed-rate-limiting-microservices/
• https://github.com/mailgun/gubernator

Reference:

• https://helpx.adobe.com/coldfusion/api-manager/throttling-and-rate-limiting.html
• https://en.wikipedia.org/wiki/Leaky_bucket
• https://en.wikipedia.org/wiki/Generic_cell_rate_algorithm
• https://baike.baidu.com/item/token%20bucket/4315253
• https://github.com/mennanov/limiters
• https://github.com/ulule/limiter
• How to Design a Scalable Rate Limiting Algorithm
• https://github.com/youtube/doorman
• https://hansliu.com/posts/2020/11/what-is-token-bucket-and-leaky-bucket-algorithms.html