實作 API Rate limiter

最近剛好公司某個專案需要將資料傳輸到遠端的某個服務上,而那個服務可能會有頻寬上的限制,所以我們的資料傳送端必須加入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 則會被丟棄。

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) )
每個區間會有個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.212: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的問題。

相關文章:

使用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即時的獲取更新後的nm值。

特色:

  • 效能可以到非常好,因為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: