CodeFarmer 技術週報 #10 - Rate Limiter (2)
簡單筆記學習下限流演算法中的令牌桶 (Token bucket) 與漏桶 (Leaking bucket)
嗨嗨大家，歡迎閱讀第 10 期的 CodeFarmer 技術週報，上週的週報聊到限流器 (Rate Limiter) 的基礎知識與演算法 (連結)，這一期就繼續來學習限流器的其他進階演算法。
限流器演算法
稍微複習一下，上一期提到實作限流器時可以使用下列幾種演算法，並介紹了前面三種，本期就接續來把 Token bucket 與 Leaking bucket 學完：
固定窗口計數器 (Fixed window counter)
滑動窗口日誌記錄 (Sliding window log)
滑動窗口計數器 (Sliding window counter)
令牌桶 (Token bucket)
漏桶 (Leaking bucket)
令牌桶 (Token bucket)
簡介：廣泛被採用的限流演算法，像是 Amazon API Gateway、Stripe、OpenAI 等知名服務都有使用，以 Stripe 內文說明他們使用 Redis 來實現限流器。
白話版工作原理說明
參考上圖，令牌桶顧名思義就是可以想像一個水桶裡面裝了固定數量的令牌 (token)
每一個請求在經過這個水桶時，會需要拿到一個令牌才可以通過，如果水桶裡的令牌被拿完了，則這個請求就會被捨棄
這些令牌另外會有一個補充器 (Refiller) 定時補充到水桶裡，補到滿為止
令牌桶演算法會使用到兩個參數：
bucket size：桶子裡最多可以放入的令牌數量
refill rate：定期補充令牌的速率
在系統實作中會需要多少桶子呢，實際案例：
如果有一個社群平台針對不同 API 做不同數量限制，像是每秒發 1 篇貼文、每天增加 150 個朋友、每秒只能按 5 則貼文讚，以這個狀況來說每個使用者就會各需要 3 個桶子
如果目標是對 IP 做限流，則每個 IP 位址都會需要一個桶子
如果對系統整體 API 做限流，像是每秒只限制一萬個請求，則就會讓所有請求共用 1 個桶子
優點：
演算法實作容易，且記憶體使用率佳
能接受短時間爆量的狀況，只要桶子內還有令牌就可以通過
可以較有彈性且精確地控制請求速率
缺點：
針對經常連續出現爆量請求時相對不適合，可能導致後端系統短時間內承受過高負載，會更建議採用 Leaky Bucket 的策略
效能取決於關鍵兩個參數，要根據實際狀況做出適當的調整。如果桶子過小或補充率過慢可能反而限制正常使用者的請求；桶子過大或補充率太快可能無法有效防止惡意攻擊。
漏桶 (Leaking bucket)
演算法工作原理：
跟令牌桶一樣可以想像是以水桶概念來實作，不同之處在於水桶內部是用一個 Queue 的方式先進先出來處理請求
當一個請求進來水桶，系統去檢查 Queue 是否已經滿了，滿了就捨棄、沒滿就加進來
而另外定義一個流出速率 (outflow rate)，系統會定期從 Queue 中取出請求來處理
漏桶演算法會使用到兩個參數：
bucket size：Queue 的大小
outflow rate：固定時間間隔內處理請求的數量
優點：
Queue 的大小是固定的，因此可提高記憶體使用效率
請求是以固定速率來處理，適合需要穩定限流的系統
缺點：
如果有瞬間爆量的狀況，如果流出速度過慢，可能會影響新請求的使用體驗
與令牌桶一樣需要對兩個參數做適當調整來適應系統需求
補充：Shopify API 採用此種限流演算法
參考資料
System Design Interview – An Insider's Guide 中譯本《內行人才知道的系統設計面試指南》
原本想連系統設計部份一起講完，但最近工作較多時間吃緊本週就先筆記到這 (跪)，下一期將繼續完成這個主題。若內容有什麼錯誤、問題、討論也都歡迎透過以下管道與我交流，或直接留言與回覆這封電子信我也能收到：
Email：codefarmer.tw@gmail.com