最近剛好公司某個專案需要將資料傳輸到遠端的某個服務上，而那個服務可能會有頻寬上的限制，所以我們的資料傳送端必須加入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。10 reqs/100ms，就被丟棄 或是可以允許requests 最多到burst 20 reqs/100ms)
簡而言之，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 則會被丟棄。
https://en.wikipedia.org/wiki/Leaky_bucket 特色：
概念上對於burst requests的限制較嚴，主要是用來維持每個時間點下的requests流量是固定的。 Golang 中可以參考uber-go/ratelimit 這套 open source solution。 比較適合像是，網路頻寬或流量控制的相關應用。
相關文章：
Fixed window counter
這個演算法的概念是，我們定義每個時間區間下可以允許的requests 量是n，而這個區間間是固定的。(例如 [12:00:01-12:00:02), [12:00:02, 12:00:03) )count > n，則我們會丟棄這個新的request。
特色：
實作上相對簡單，且對burst的限制較不嚴。 如果requests 量剛好發生的時間在，前一個區間的下半段與下一個區間的上半段時，則可能發生這段跨區間的requests量是我們原本定義的n的2倍。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 等等。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的問題。 相關文章：
使用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)就可以了。n 與 m值。
特色：
效能可以到非常好，因為rate limit是實作在client 端，所以特別適合超大流量的應用。 有個先決條件為，流量必須很平均的分散在所有的client端，這樣才會更有效的使用到所有分配到rate。 作為取捨，對於rate limit的控制會相對沒那麼精準，畢境如果有client端的service 掛掉了，會有段時間差，之後所有的client才會獲取得最新的資訊。 相關文章：
自行設計的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是可以被執行的。
相關文章：
Reference:
