API Rate Limiting 有哪些演算法？如何實作分散式限流？

Rate Limiting 演算法

1. Fixed Window（固定視窗）

每分鐘重置計數器（如：100 req/min） ❌ 視窗邊界可瞬間承受 2x 流量

2. Sliding Window Log（滑動視窗日誌）

記錄每筆請求時間戳，計算過去 N 秒內請求數 ✅ 精確，無邊界突刺 ❌ 記憶體消耗高（需儲存每筆時間戳）

3. Sliding Window Counter（滑動視窗計數）

加權計算跨視窗近似值 ✅ 記憶體效率高，精度可接受

4. Token Bucket（令牌桶）

固定速率補充 token，請求消耗 token ✅ 允許短暫突發流量

5. Leaky Bucket（漏桶）

請求排隊，以固定速率流出 ✅ 輸出絕對平滑，適合串流場景

分散式實作（Redis）

• INCR + EXPIRE：簡單計數器
• Lua Script：保證原子操作
• Sorted Set：實作 Sliding Window Log

回應 Header

X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After（429 時）