限流演算法 (Rate Limiting)

引言：「吵鬧的鄰居」

想像你提供一個免費 API。某個使用者寫了一個腳本，結果不小心每秒發送了 10,000 個請求。你的資料庫瞬間癱瘓，導致其他所有正常使用者都無法訪問。

限流 (Rate Limiting) 指的是限制一個使用者（或服務）在給定時間內可以發送的請求數量。她是防禦 DDoS 攻擊、暴力破解登入以及防止「豬隊友」腳本跑飛的第一道防線。

演算法要解決什麼問題？

• 輸入： 來自不同使用者的請求流。
• 輸出： 接收 (Accept) 或 拒絕 (Reject / 429 Too Many Requests)。
• 承諾： 公平性（單個使用者不能霸佔所有資源）和穩定性（即使在高負載下，系統也能存活）。

核心演算法

1. 令牌桶 (Token Bucket)

• 邏輯： 想像一個裝「令牌」的桶。每個請求消耗一個令牌。系統以固定速率（如 10 個/秒）向桶裡放入令牌。如果桶空了，請求就被拒絕。
• 優點： 允許 突發流量 (Bursts)。如果使用者一段時間沒發請求，桶裡的令牌會攢起來，允許她們瞬間發出一小波請求。
• 適用： 最流行；被 AWS, Stripe 和 Spring Cloud 廣泛採用。

2. 漏桶 (Leaky Bucket)

• 邏輯： 想像一個底部有個小孔的桶。請求像水一樣以任意速度進入，但只能以 固定的速度 從底部漏出。如果桶滿了，多出來的水就會溢出（請求被丟棄）。
• 優點： 完美平滑流量。不允許任何突發，處理速度極其穩定。
• 適用： 網路路由器的流量整形。

3. 固定窗口計數 (Fixed Window Counter)

• 邏輯： 將時間劃分為固定窗口（如 1 分鐘）。每個窗口設一個計數器。
• 缺點： 「臨界點問題」。如果使用者在 00:59 發 100 個，01:01 發 100 個，雖然每分鐘沒超 100，但在 2 秒內發了 200 個，可能瞬間壓垮系統。

4. 滑動窗口日誌/計數 (Sliding Window)

• 邏輯： 記錄每個請求的精確時間戳。
• 優點： 最準確；解決了臨界點問題。
• 缺點： 記憶體開銷大（需要儲存每個時間戳）。

典型業務場景

• ✅ API 分級計費： 限制「免費版」每天 100 次，「專業版」每天 10,000 次。
• ✅ 登入保護： 防止駭客每秒嘗試 1,000 次密碼（暴力破解）。
• ✅ 外部服務保護： 如果你調用 OpenAI 的 API，你會限制自己的發送速率以匹配對方的配額。

性能與複雜度總結

• 時間： $O(1)$ (令牌桶可以透過簡單的數學計算實現，無需定時器)。
• 空間： 每個使用者 $O(1)$。

小結：一句話記住它

「限流是 API 的『安全閥』。令牌桶給系統留了一點『衝動』的空間（突發），而漏桶則追求絕對的『冷靜』與『平滑』。」