CodeFarmer 技術週報 #9 - Rate Limiter (1)
初探什麼是限流器、限流器在系統中的擺放位置，以及筆記下幾個較基本的限流器演算法
嗨嗨大家，歡迎閱讀第 9 期的 CodeFarmer 技術週報，上週的週報聊到後端系統設計面試框架 (連結)，這一期實際來看一個常考題 — 如何設計一個限流器 (Rate Limiter)。
但實際開始學這個知識點後，認為在套用面試框架前，需要具備一些前導知識，全部塞在同一篇應該會很可觀，所以為了提升文章可讀性 (以及筆者的可用性)，這期就先來談談這些主題：
什麼是限流器？
使用限流器有什麼好處？
限流器要放在哪裡？
限流器的基礎演算法
固定窗口計數器
滑動窗口日誌
滑動窗口計數器
什麼是限流器？
網路限流器 (限速器) 可以用來限制使用者在指定時段內對 server side 發送請求的數量，當請求數量超過門檻，額外的請求會被擋下來。
以基本的網頁、App 應用上，這些偏前端的情境中，會限制某個功能在固定時間內不能送出過多請求，像是遊戲實況中的洗頻、Discord 的慢速模式、防止惡意建立帳號、防止多次嘗試登入後的上鎖、每週最多領取獎勵點數等功能。
而對於使用第三方 API 服務的後端伺服器來說，也會需要確認文件的限流次數去實作對應的 Message Queue 或對客戶端限流來實作，否則可能會遇到 429: Too Many Requests 而導致服務產生錯誤。舉例：
Twitter API 針對不同使用者等級、功能有不同的請求數量限制，像是每個免費使用者在 1 天內只能做 17 次的貼文 (連結)
GitHub API 對於每個認證的使用者每小時只容許 5000 個請求 (連結)
OpenAI API 對串接服務的使用者依照不同等級、token 數量、圖片上傳數量等功能在每分鐘、每天都有對應不同的限流機制 (連結)
使用限流器有什麼好處？
避免 DoS (Denial of Service) 這樣的惡意機器人攻擊，造成伺服器資源不足無法服務正常使用者。
降低成本
針對特定過多的請求設限，一方面可以降低 server 負擔，另一方面也可以將更多資源分配給有更高優先等級的 API
舉例當你今天有個串接第三方付費 API 服務的產品，每次只要功能上有用上這些付費 API，檢查該帳號的使用額度、付款紀錄等，就能有效控管服務所收費的成本
想到一個例子是像 Cursor 這樣的產品，每個免費使用者每月都有一定的使用不同等級 AI 語言模型的額度。對於 Cursor 而言，因為串接不同家 AI 模型 API 的服務也需要付費，因此在不同等級的訂閱用戶給予不同額度的使用權才能確保服務的品質
為了增加伺服器穩定性，也可以用限流器來過濾掉網路機器人，或阻擋使用者不當操作所引起的過多請求。
限流器要放在哪裡？
client side：在前端實作雖然可行但不可靠，因為 client side 的請求相對容易被惡意使用者繞過直接對 server 攻擊
server side：能根據業務需求有彈性地設計自己期待的限流演算法
API gateway：
隨著最近雲端微服務的流行，限流的功能也常能直接在第三方的 API gateway 服務中實現
可以理解為擋在 API server 前的一道牆，若使用者請求還沒超過流量限制，則可以被正確轉到 server；反之就會被擋下來回應 429。
在 API server 中直接實作或使用第三方的 API gateway 都可以，取決於團隊現有技術與架構、工程資源、優先順序等：
目前團隊擅長使用的語言是否能在 server side 有效實作限流器？
是否需要彈性的商業邏輯來調整限流演算法？因為第三方 API gateway 限制可能較多。
如果已經採取微服務架構，使用 API gateway 可能較快
是否有工程資源或找到現成套件來自己建造限流器？
限流器演算法
另一個在限流器設計中會聊到的就是演算法，但這裡就先以較高階的角度理解即可，對於如何在系統設計面試中挑選適合的演算法組合更有幫助：
固定窗口計數器 (Fixed window counter)
滑動窗口日誌記錄 (Sliding window log)
滑動窗口計數器 (Sliding window counter)
令牌桶 (Token bucket)
漏桶 (Leaking bucket)
本期剩下的篇幅就先來介紹比較基本的前面三種。
固定窗口計數器 (Fixed window counter)
演算法工作原理：
將時間分成多個固定大小的時間窗口，並指定一個計數器給每個窗口使用。舉例像是每分鐘限制最多 2 個請求，則一小時內就有 60 個固定的時間窗口，每個窗口最多計數 2 次。
每一個請求都會讓計數器加一
一但當前窗口的計數器已達門檻值，則其他請求會被丟棄，直到下一次時間窗口開始，計數器歸零才能重新接受新的請求
優點：記憶體使用上較有效率，且實作容易
缺點：在窗口邊界切換處可能會造成流量激增，而超過系統允許的負載能力
滑動窗口日誌記錄 (Sliding window log)
為了解決固定窗口流量激增的缺點的改良演算法
演算法工作原理：
額外追蹤每個請求的時間戳，將時間戳資料存在 log 中，可能會存在快取上像是 Redis Sorted Sets 中
當有新請求進來，刪除 log 中過期的時間戳，並將新請求時間戳記錄下來
若當前 log 中數量多於門檻，則新請求就會被擋下來
舉個例子參考下圖如果限制每分鐘 2 個請求：
01:00:01 時有 1 個請求，檢查當前窗口 00:59:01-01:00:01 為空，可通過，記到 log 中
01:00:30 時有 1 個請求，檢查當前窗口 00:59:30-01:00:30 有 1 個請求，沒超過 2 可通過，記到 log 中
01:00:50 時有 1 個請求，檢查當前窗口 00:59:50-01:00:50 已滿，被擋下來，並記到 log 中
01:01:40 時有 1 個請求，檢查當前窗口 00:00:40-01:01:40，有兩個時間戳超過開始時間的 00:00:40 所以先刪除，刪除後 log 數沒超過 2 可通過，並記到 log 中
優點：限流效果準確，任何滾動的時間區間流量不會激增造成系統不穩定
缺點：額外用上大量記憶體，即時請求被拒絕，該請求的時間戳還是被記錄下來
補充：什麼是 Redis Sorted Sets：
是 Redis 中較有效率的排序資料結構，適合用於排行榜、速率限制這些場景
內部使用 Skip List 和 Hash Table 的結構，確保每個操作能平均在 O(log(n)) 的時間複雜度
滑動窗口計數器 (Sliding window counter)
融合上述兩個演算法的改良做法，在記憶體的使用上更有效率
演算法工作原理，直接參考一個實際例子來理解：
假設每分鐘限制 7 個請求，前一分鐘有 5 個請求，目前這一分鐘已有 3 個請求
若今天有一個新的請求進來，則計算滑動窗口的請求數公式為「目前窗口請求數 + (前窗口請求數 * 滑動窗口與前窗口的重疊比例)」
假設今天滑動窗口的位置 prev : curr = 7 : 3，則可以算出當前滑動窗口已有的請求數為 3 + (5 * 0.7) = 6.5 個，依照實際的商業邏輯可以採取無條件捨去或進位
假設這裡採用捨去的話就是 6 個，則還可再容納 1 個請求，因此這個新請求就可以通過，但如果這時候再加入另一個新請求的話就會被擋下來
可參考這張圖示意，與上圖範例數字不太一樣，只是因為懶得畫圖：
參考資料
System Design Interview – An Insider's Guide 中譯本《內行人才知道的系統設計面試指南》
本週先筆記與學習到這邊，下一期將繼續學習限流器的其他進階演算法，以及實際看看在系統設計面試中該如何實作這樣的系統。若內容有什麼錯誤、問題、討論也都歡迎透過以下管道與我交流，或直接留言與回覆這封電子信我也能收到：
Email：codefarmer.tw@gmail.com