2023/3/6

Rate-Limit Algorithm

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

系統有可能會遇到的攻擊

  1. brute force attacks

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

  2. Dos, DDos

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

  3. 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 的優點,且實作並不困難。

References

實作 API Rate limiter George's blog

System Design Concept: Rate limiting

Rate limiting - Wikipedia

沒有留言:

張貼留言