Maxkit: Rate-Limit Algorithm

2023/03/06

Rate-Limit Algorithm

rate-limit 是在某個時間區間內，能夠被執行的次數限制。在大型分散式系統，必須要內建這個限制，避免系統因為短時間內收到大量的 requests 造成問題。

系統有可能會遇到的攻擊

brute force attacks

攻擊者可能針對 login 及忘記密碼，用亂數帳號進行暴力的攻擊，試圖取得可以登入系統的帳號
Dos, DDos

攻擊者利用大量的 requests 癱瘓系統運作，導致系統無法接受並處理正常的使用者的 requests
Web Scraping

這是網頁抓取的方法，攻擊者可透過工具，分析網頁的內容，並抓取整個網站的所有可能的連結資料。

Rate Limit

限制 requests 在某段時間區間內，允許執行的數量
Throttling

控制 request 可被服務的頻率，ex: 控制 requests 每 100ms 可處理 10 個 requests，如果超過這個頻率的 request，可以允許另一個 threshold 的數量被處理，ex: 15/100ms，直到超過這個 threshold，就會被拒絕服務

Token Bucket

想像有一個水桶，裡面放 n 個 token，當使用者發出 request，必須要先到水桶取得一個 token，取得 token 後，就能繼續執行，如果無法取得 token，就會被拒絕。

水桶中的 token 會依照 1/n second 的速度，補充 token 到水桶中，直到補滿 n 個 token。

當水桶裡面有 n 個 token，可允許瞬間發生 n 個 requests，也就是同時被取走 n 個 tokens，也就是允許系統突然暴增的 requests。

Leaky Bucket

跟 Token Bucket 很相近，一樣想像有個水桶，預先設定了該水桶可流出 token 的速度，如果收到 requests 的速度超過允許流出的速度，就會累積在水桶裡面 (queue)，如果水桶裡面超過了 n 個 tokens，後續的 requests 會被丟棄。

系統不允許發生突然暴增的 requests。

Fixed Window Counter

預先定義每個時間區間下允許執行的 request 數量 n，時間區間是固定的 (ex: 00:00:01 ~ 00:00:02, 00:00:02 ~ 00:00:03)，每個時間區間都有一個 counter，當發生了新的 requests，就會計算這個時間區間的 counter，如果新增的 request 讓 counter 超過 n，就必須丟棄這個 request。

這個方法可能會遇到的問題是，如果時間區間 (00:00:01.500 ~ 00:00:02.000) 及 (00:00:02.000 ~ 00:00:02.500) 都產生了 n 個 requests，就等於在時間區間 (00:00:01.500 ~ 00:00:02.500) 發生了 2n 個 requests。

Sliding Window Logs

類似 Fixed Window Counter，記錄每一個 reuqest 發生的時間店，當有新的 request 發生時，會去比較目前的時間點到先前某一個時間點，這個時間區間的 requests 數量，用這個數量來衡量是否允許執行這個 request，如果超過了預先定義的數量，就會丟棄這個 request。

Sliding Window Counter

這個方法整合了 Fixed Window Counter 及 Sliding Window Log 的方法，概念上也是用 Fixed Window Counter，但將每個時間區間，又再切割了多個子區間。再比對某個 requst 是否允許執行時，就是比對目前這個時間點到先前多個子時間區間的 counter 總和，如果超過預先定義的值，就會丟棄該 request。

有了 Fixed Window Counter 及 Sliding Window Log 的優點，且實作並不困難。