Algorithm

速率限制

速率限制依使用者或 IP 限制單位時間內的請求數，防止過載與濫用。本文介紹令牌桶、滑動視窗、漏桶，以及以 Redis 實作的分散式限流。

速率限制器（rate limiter）用來控制一段時間內接受的請求數量。先決定鍵、上限與時間視窗，例如「每位使用者每分鐘 100 次」，超出的請求會被拒絕或延後處理。經典演算法有固定視窗、滑動視窗日誌、滑動視窗計數器、令牌桶與漏桶，它們在精確度、記憶體用量與突發流量的處理方式上各有不同。

幾乎所有對外開放的功能，從公開 API 到登入、付款與訊息發送，都放在速率限制器之後。它保護伺服器免受流量暴增與失控的重試迴圈衝擊，避免單一使用者獨占共用資源，並拖慢暴力破解攻擊。速率限制也是系統設計面試的常見題目，需要能說明各演算法的取捨以及在多台伺服器上的實作。

建議先動手寫一個固定視窗計數器，觀察它在視窗邊界放行兩倍上限的問題，再用滑動視窗與令牌桶加以改善。接著學習注入時鐘進行測試、回傳 HTTP 429 與 Retry-After，以及用 Redis 的 INCR、EXPIRE 與 Lua 指令碼讓多台伺服器共用同一個限額。

特色

令牌桶

令牌以固定速率補充，每個請求消耗一個；既維持平均速率，又允許不超過桶容量的突發流量。

滑動視窗

透過時間戳日誌，或對前後兩個視窗的計數加權估算，統計最近一段時間的請求數，避免固定視窗的邊界突波。

鍵與公平性

依使用者 ID、API 金鑰、IP 位址或端點分別計數，避免單一用戶端獨占資源。

分散式限流

藉由 Redis 的原子 INCR 與 Lua 指令碼，多台伺服器能在沒有競爭條件的情況下共用同一個限額。

適用情境

公開 API 依方案劃分的呼叫配額
限制登入與重設密碼的嘗試次數
控制付費第三方 API 與簡訊發送成本
Web 伺服器與 API 閘道的流量保護

參考實作

令牌桶實作

TokenBucket 每秒補充 rate 個令牌，最多容納 capacity 個。allow() 會一次補上自上次呼叫以來應得的令牌（延遲補充），令牌足夠時消耗一個並回傳 True。執行後，前 5 次呼叫以突發流量通過，接下來 3 次被拒絕；暫停 1.1 秒後又有 2 次通過。時間以不會倒退的 time.monotonic() 量測。

token_bucket.py

import time


class TokenBucket:
    """Allow bursts of up to `capacity` requests, refilled at `rate` tokens per second."""

    def __init__(self, rate: float, capacity: float) -> None:
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity
        self.updated = time.monotonic()

    def allow(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
        self.updated = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False


if __name__ == "__main__":
    bucket = TokenBucket(rate=2, capacity=5)   # 2 requests per second, bursts of 5
    print([bucket.allow() for _ in range(8)])  # 5 x True, then 3 x False
    time.sleep(1.1)                            # about 2.2 tokens come back
    print(bucket.allow(), bucket.allow(), bucket.allow())  # True True False

python token_bucket.py

逐步指南

共六章，帶你從安裝一步步認識速率限制的核心概念。

官方文件與參考資料

討論

發起討論

在這裡提問、分享經驗，交流關於速率限制的看法。

還沒有討論。來發起第一則吧。