限流器 (Rate Limiter) 是什麼? 有哪些限流策略?

過去一周在推特上，看到許多人在討論 Upstash 的開源限流器 (Rate Limiter) 套件(GitHub 連結)，讓人可以非常輕鬆地做限流(連結)，因此這篇來聊聊限流器。

限流器 (Rate Limiter)是什麼？

限流器 (Rate Limiter) 顧名思義，是用來限制流量的。在全端的世界中，限流器可能是用來限制來自客戶端的請求，或者服務對其他服務發送請求時，也可以用限流器來限流。舉例來說，可以從 IP 的角度，限制每個 IP 每天的請求數；或者以使用者為維度，來限每個使用者在某段時間的請求數量。

限流器的好處:

一來可以阻擋像是 DoS (Denial of Service) 攻擊，避免伺服器過載；
二來可以降低成本，特別是如果你有用第三方 API，流量大起來帳單費也會變很可觀。

限流器多半不會在客戶端實作，因為請求在客戶端比較容易被偽造；所以一般可能會放在伺服器端，或者是放在 API Gateway；或者像是 Upstash 的這個開源套件，是放在 Edge 上。

限流有幾種策略，一般常見做法包含：

令牌桶（Token Bucket）
漏桶（Leaky Bucket）
固定窗口（Fixed Window）
滑動窗口（Sliding Window）

限流器三種策略

而 Upstash 的開源限流器，提供了令牌桶、固定窗口，以及滑動窗口三種策略，同時分析了這三種策略的優缺點。

令牌桶（Token Bucket）

首先來談令牌桶（Token Bucket），可以想像一個裝滿 {maxTokens} 個令牌的水桶，它會以每隔 {interval} 時間以 {refillRate} 速率，自動補充相對應的令牌。每次請求都會從水桶中取走一個令牌，如果水桶中沒有令牌，則請求會被拒絕。

這種做法的優點在於能夠讓突發性的請求高峰變平滑，讓系統可以用穩定的速率處理請求。如果將 maxTokens 設置得比 refillRate 更高，可以允許系統在一開始承擔更高的請求。而缺點則是運算成本比較高。

固定窗口 (Fixed Window)

固定窗口 (Fixed Window) 的做法是，將時間劃分為固定窗口。例如，每個窗口為 10 秒。當有新的請求進入時，將使用當前時間來判斷所屬窗口，並增加一個計數器。如果計數器超過設定的限制，該請求就會被拒絕。

固定窗口的優點包含，在數據量和計算成本上節省、較新的請求不會因為過去的高流量突發而延遲。但也有一些缺點，例如可能會導致窗口邊界處的高流量突發，以及如果許多用戶試圖在一個新窗口開始時，訪問你的伺服器，就會引發請求堵塞。

滑動窗口 (Sliding Window)

而滑動窗口 (Sliding Window)，是建立在固定窗口的基礎上，但與固定窗口不同的是，它採用了滑動的窗口機制。舉例來說，我們設定每分鐘 10 個請求的限流。如同固定窗口的作法，我們將時間切分為 1 分鐘的區間。第一個窗口將從 00:00:00 到 00:01:00。假設當前時間為 00:01:15，並且在第一個窗口中收到了 4 個請求，在當前窗口中收到了 5 個請求。用來判斷請求是否該通過的近似計算方法如下：

limit = 10

// 4 個請求來自舊的窗口，把它們放入權重，同時加上當前的窗口
rate = 4 * ((60 - 15) / 60) + 5 = 8

return rate < limit // True 代表我們會讓請求通過

滑動窗口的優點在於，解決了固定窗口演算法中因窗口邊界導致的問題。但同時會造成存儲和運算耗費更大。並且因為這做法，假設先前窗口中的請求流是均勻的，因此雖然滑動，實際上是近似而非完全準確 (但在大多數情況下這並不會構成大問題)。