限流器的工作，是在昂貴的業務邏輯開工之前便宜地說「不」。設計它要先回答四個問題，選演算法只是其中一個。

面試題 Design a Rate Limiter 很容易被答成「用 Redis INCR 數一下」。INCR 只是儲存層的一個原子操作，它回答不了這幾件事：限流器放在請求路徑的哪裡？用什麼當計數的鍵？「每秒 10 次」指的是哪一段時間裡的 10 次、允不允許瞬間衝一下？很多台機器時，這個數字怎麼仍然只有一份？

限流判定排在身份辨識之後、業務邏輯之前。被拒絕的請求在第三個盒子就返回，不會碰到資料庫；判定本身也必須比它保護的工作便宜，否則限流器自己就成了新的熱點。

把題目拆開，設計一個限流器要回答四個維度的問題：

四個維度互相獨立：同一個 Token Bucket 可以放在閘道數 API key，也可以放在服務內數使用者。面試時先把四格填完，再談演算法。

鍵只要做到「認得出是誰」就夠了，不要等整個業務邏輯跑完才計數——否則超額的請求已經把資料庫打過一輪。不同端點的成本可以不同：上傳扣 5 點、讀取扣 1 點。Token Bucket 用「這次扣幾個許可」表達加權最自然；視窗計數器通常仍是一筆算 1。

流量形狀是演算法的戰場。本篇的五種演算法（外加一個常被誤認為第六種的 GCRA）分成兩個家族，各有一條演化主線：

上排三種都在數「一段時間放行了幾筆」，每往右一步都在修前一種的缺點，也付出新的代價（第 2、3 節）。下排不數視窗，改用速率與容量描述流量（第 4 節）。中間那條雙箭頭是最常被誤解的一點：漏桶只當計量器時，放行與拒絕跟 Token Bucket 一模一樣；只有加上佇列，才會把突發排成等距。

把時間切成等寬的格子，每格一個計數器。好寫、好原子化；代價是相鄰兩格的邊界兩側，可以各吃滿一次上限。

規則很短。請求時刻 t、窗寬 W、上限 L，視窗編號是 floor(t / W)。該編號的計數加一後不超過 L 就放行，否則拒絕。熱路徑只需要一個帶編號的 key 與它的到期時間：

key   = "rl:" + 規則 + ":" + 使用者 + ":" + floor(now / W)
count = INCR key                    -- 這一格第一次被打會得到 1
if count == 1 then PEXPIRE key W    -- 讓這一格自己過期，下一格自然換新 key
放行 ⇔ count ≤ L

每個身份每一格一個整數。這兩行命令拆開送有一個經典的坑，第 6 節會把它們合進同一支腳本。

代價出現在格子邊界。設 W = 1000 ms、L = 3。請求在 820、880、940 ms 到達，落在視窗 0，三筆都放；960 ms 那筆因為視窗 0 已滿被拒。1000 ms 起算視窗 1，計數從 0 重來，1000、1060、1120 ms 又放了三筆。從演算法的角度，每個格子都守住了「最多 3 筆」——但只要把尺換成「任意連續 1000 ms」，820 到 1120 這短短 300 ms 裡就進去了 6 筆。

上排是演算法看到的世界：兩個格子各放行 3 筆，都守住上限；960 與 1850 兩筆因所在格子已滿而被拒。下排把同一批放行換成任意擺放的 1000 ms 尺——820 到 1120 這 300 ms 裡進了 6 筆。這組數字就是第 5 節實驗室的「跨邊界突刺」劇本。

突刺不是實作 bug，是「格子」這個定義本身。常見的變形是不把視窗編號放進 key，而在第一次 INCR 時把 TTL 設成 W：key 過期就等於重新開窗。邊界從「所有人共用的整點」變成「這個身份自己的第一筆」，不同使用者的歸零時刻因此被打散，整點那一刻全站一起解封的尖峰消失了。但單一身份仍然可以在過期前、過期後各吃滿一次 L，所以對單一攻擊者而言，2 倍還在。

另一個細節是時鐘。若各台應用自己算 floor(t / W)，機器之間歪 200 ms，在 60 秒的窗裡無所謂，在 1 秒的窗裡會讓相鄰兩台把同一時刻的請求算進不同格。要對齊，就用計數器那台機器的時間算編號——第 6 節的腳本示範怎麼做。

Fixed Window 的毛病出在「格子」。要守住「任意一段 W 內不超過 L」，有兩條路：把每一筆記下來，或用上一格的總數去估。

Sliding Window Log：記下每一筆

最直接的做法是保留這個身份在窗內每一次放行的時間戳。新請求到達時，先丟掉年齡已經達到 W 的舊戳（年齡剛好等於 W 算窗外），剩下的筆數小於 L 才放行，並把自己的時間戳推進去。在 Redis 上通常用一個 sorted set，分數就是時間戳，整段放進同一支 Lua 腳本裡原子執行：

cutoff = now − W
ZREMRANGEBYSCORE key -inf cutoff    -- 丟掉年齡 ≥ W 的時間戳
n = ZCARD key                       -- 窗內還剩幾筆
if n < L then
  ZADD key now member               -- member 要唯一：時間戳 + 序號
  PEXPIRE key W
放行 ⇔ n < L

分數是時間，所以「丟掉窗外的」就是一次範圍刪除。member 若直接用時間戳，同一毫秒的兩筆會被 sorted set 合併成一筆，計數就少了。

它的好處是絕對不超發：任意一段長度為 W 的區間都不會超過 L，邊界突刺消失。痛點是記憶體隨上限線性成長：若規則是「每小時 10,000 次」，一個活躍的身份就得存 10,000 個時間戳，每次判定還要在腳本裡刪舊的、數剩下的。低頻、上限小、又不能超發的端點（登入、OTP、寄信）用它很舒服；每秒幾萬筆的熱鍵會把腳本與記憶體一起撐大。

還有一個實作分歧：被拒絕的請求要不要也記進日誌？有些實作會記，這樣持續濫用的客戶端只要不停打，就永遠出不了窗——比較嚴，但也可能讓一個重試迴圈把自己永久鎖死。本篇與實驗室採「只記放行」。

Sliding Window Counter：兩個整數的面積近似

Sliding Counter 用兩個整數換掉整份日誌。它只留上一格的放行總數 prev 與這一格已經放行的 curr。請求落在這一格的偏移是 elapsed，此時滑動窗 [now − W, now) 還蓋住上一格的最後 (W − elapsed) 毫秒。假設上一格的請求沿時間均勻鋪開，被蓋住的那部分大約就是 prev 乘上這個比例：

estimate 小於 L 才放行，然後 curr 加一。熱路徑只有格號、prev、curr 三個數字，和 Fixed Window 一樣是 O(1)。下圖把這個公式畫成面積：

三列都是同一個時刻 now = 1300（elapsed = 300）、同一個估計值 2.1。藍框是滑動窗，它蓋住上一格的 70%。Sliding Counter 只記得上一格共有 3 筆，不知道它們落在格子的哪裡：擠在格頭時它們早已滑出窗外，估計偏高；擠在格尾時它們全都還在窗內，估計偏低。

近似的代價：兩個算例

同樣 W = 1000 ms、L = 3，把上一格的 3 筆分別擠到格頭與格尾，逐筆算一次：

左欄是誤拒（False Reject），右欄是超發（Overshoot）。兩欄的數字就是第 5 節實驗室「前窗擠在開頭」與「前窗擠在末端」兩個劇本，可以逐筆對照。

誤差是雙向的，但在大量、彼此獨立的流量上通常不大：Cloudflare 的邊緣限流就公開說明採用這個加權近似，用兩個計數器換掉每筆時間戳，讓每個限流鍵在數百萬個網域上都只佔固定大小。它適合「要比 Fixed Window 平滑得多、又存不起時間戳」的場合；不適合拿來當「絕對不能超過」的契約。

視窗家族在數「這段時間放了幾筆」。桶家族換一個問法：長期速率是多少、瞬間最多能衝多少。兩種桶的差別，在於桶裡裝的是什麼。

Token Bucket：桶裡裝的是許可

Token Bucket 記兩個數：桶裡還有幾個許可（token）、上次補充的時刻。桶以固定速率補充，最多補到容量 capacity。請求到達時先把這段時間該補的許可補上，餘額夠付這次的成本就扣掉並立刻轉發上游，否則拒絕。

兩個參數各管一件事：每秒補充是長期速率，容量是突發的寬度。閒置夠久之後桶是滿的，下一波突發可以一口氣花掉整桶——放行的當下請求就進了上游，桶並不幫你排隊。因為「扣幾個」可以不是 1，它也是表達加權成本最自然的演算法。

要注意它守的不是「任意窗寬不超過 L」。容量 3、每秒補 3，看起來和「每秒 3 筆」對齊：0 ms 連發 3 筆把桶花光，334 ms 與 667 ms 又各補回 1 個許可、各放 1 筆，同一個 1000 ms 內共放了 5 筆。一般化來說，任意窗寬 W 內最多約 capacity + 每秒補充 × W 筆。這是設計上允許的突發，不是 bug，但要說得出來。

Leaky Bucket 的兩種面貌

「Leaky Bucket」這個名字在文獻與實作裡指兩種不同的東西，面試最常在這裡混淆。

當佇列用（Traffic Shaping）：桶裡裝的是排隊中的請求。桶底有一個洞，以固定間隔 1 / 每秒補充 把請求漏向上游；桶深 capacity 是最多能有幾筆在桶裡，最晚那筆會比到達晚 (capacity − 1) 個間隔才出發。滿了就拒絕。瞬間的突發不會打進上游，而是被轉換成排隊延遲，上游看到的是平滑的等距流水。

當計量器用（Policing，也就是 GCRA）：沒有實體佇列，只記一個時刻 TAT（Theoretical Arrival Time，下一筆理論上最早可出發的時刻），當場決定放或拒：

間隔 T = 1 / 每秒補充        容忍 τ = (capacity − 1) × T
請求在 now 到達：
  TAT = max(TAT, now)
  若 TAT − now > τ   → 拒絕（TAT 不動）
  否則               → 放行並立刻轉發，TAT = TAT + T

佇列版只差一行：放行的請求不是現在送出，而是等到 TAT 那一刻才送出。判斷「要等多久、超不超過桶深」的算式完全一樣。

關鍵在這裡：把 TAT − now 換算成「欠了幾個許可」，TAT − now ≤ τ 恰好等價於 Token Bucket 的「餘額 ≥ 1」。同樣的容量與速率下，GCRA 放行與拒絕的請求和 Token Bucket 一模一樣，它不會把任何突發排開；它只是用一個時刻代替「餘額＋上次補充時刻」兩個數字，記帳方向相反。真正改變上游所見形狀的，只有佇列版。

用同一組數字看兩種形狀：容量 3、每秒補 2，四筆請求在 0、10、20、30 ms 到達。

兩邊都放行前三筆、拒絕第四筆，放行數相同。差在最下面那條線：左邊上游在 20 ms 內收到三筆；右邊收到的是 0、500、1000 ms 三個等距脈衝，代價是後兩筆各多等了 490 與 980 ms。若右邊換成 GCRA，決策不變，但三筆會像左邊一樣立刻送出。

所以選擇不在「哪個比較先進」，而在你有沒有地方讓請求等。同步的 HTTP 中介層通常只能現在放或現在拒，Token Bucket 或 GCRA 跟這個模型一致，突發會真實打進上游——上游要另有容量或別的保護才接得住。Envoy 的本地限流設定直接就是 token bucket（max_tokens、tokens_per_fill、fill_interval）。前面若有佇列，Leaky Bucket 用延遲換平滑的輸出。

nginx 的 limit_req 是三種行為都能切的漏桶，正好拿來對照：沒設 burst 時佇列深度為 0，超過速率的請求立刻被拒（預設回 503，可用 limit_req_status 改成 429）；設了 burst=N 就是佇列版，多出來的請求排進深度 N 的佇列、按速率放出；再加上 nodelay，突發內的請求立刻轉發、只佔用額度，超過才拒絕——這就變回計量器，行為等同 Token Bucket。

把窗寬、上限、容量、補充速率鎖成同一份預算，差異就只來自演算法，而不是你偷偷換了一組數字。

這裡只用一把量尺：上游在任意一段窗寬內最多收到幾筆，拿去和視窗上限比。這正是 Sliding Log 的契約，所以 Sliding Log 在這把尺下永遠不會超出；其他演算法若超出，時間軸上會用紅框圈出是哪一段。Leaky · 佇列的請求要排隊，所以量的是它真正送出的時刻，而不是到達時刻。

每條時間軌分兩行：上面是請求到達的時刻，圓圈裡的數字對應下方表格的第幾筆；下面是上游真正收到的時刻。綠色是立刻放行，藍色是排隊後才送出（虛線箭頭從到達指向送出），白底橘框是拒絕——拒絕是限流器在履行職務，不是故障；紅框才是相對契約多放的部分。淡灰直虛線是對齊視窗的邊界，只有 Fixed Window 與 Sliding Counter 會在那裡換格。把滑鼠停在圓圈上，可以看到這一筆當下的狀態。

建議的玩法：先看預設的「跨邊界突刺」，左欄紅框圈住 6 筆、超出 3；右欄 Sliding Log 一筆都沒超。再點「前窗擠在末端」與「前窗擠在開頭」，對照第 3 節兩個算例裡 Sliding Counter 何時多放、何時誤拒。接著點「瞬間突發」，比較兩條「上游收到」線的形狀，再把右欄換成 GCRA，看決策與送出時刻是否與 Token Bucket 完全重合。最後在「瞬間突發」裡把桶容量從 3 拉到 6：Token Bucket 的紅框出現（4 筆擠在 30 ms 內），佇列那一欄只是排得更長，上游仍是每 500 ms 一筆。

演算法在單機上很好寫。多台無狀態服務一起數同一個鍵時，要依序解決四件事：共用、原子、熱鍵，以及計數器掛掉時怎麼辦。

各台自己數，上限就乘上台數

服務通常是 N 台無狀態副本，前面有負載平衡把同一個使用者的請求散到各台。若每台在自己的記憶體裡數，每台都以為自己守住了上限，全域實際放行的是 N 倍。所以計數必須放到所有副本共用的地方，最常見的是一組 Redis。

左邊三台各自守「每秒 10 筆」，總和變成 30；右邊所有節點扣同一個計數器，上限才是全域的 10。代價是每筆判定都多一趟網路往返，這是本節後半要處理的事。

集中計數的兩個坑：讀改寫競態與漏設到期

坑一：讀、算、寫拆成三步。Token Bucket 最容易踩：先讀餘額、在應用裡算補充與扣減、再寫回。兩台同時處理同一個身份時，會讀到同一個餘額、各扣一次、各自寫回，最後一個許可被花了兩次：

sequenceDiagram
    participant A as 節點 A
    participant R as Redis
    participant B as 節點 B
    A->>R: 讀餘額
    B->>R: 讀餘額
    R-->>A: 1
    R-->>B: 1
    A->>R: 寫回 0，放行
    B->>R: 寫回 0，放行
    Note over A,B: 一個許可花兩次
  

兩次寫回都成功、也都「正確」地寫了 0——錯的是兩邊都基於同一個舊值做決定。用 WATCH／MULTI 樂觀鎖也行，但熱鍵上重試會很多；限流通常直接把整段搬進一支腳本。

解法是把讀、算、寫放進同一支 Lua 腳本。Redis 執行腳本時不會穿插其他命令，整段就是一次原子讀改寫，而且只花一趟往返：

-- KEYS[1]：這個身份的桶；ARGV：容量、每秒補充、這次要扣幾個許可
local cap  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2]) / 1000              -- 每毫秒補多少
local cost = tonumber(ARGV[3])
local t    = redis.call('TIME')                    -- 用 Redis 的時鐘，不信任應用機器
local now  = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local s    = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or cap                 -- 第一次見到這個鍵：滿桶
local ts     = tonumber(s[2]) or now
tokens = math.min(cap, tokens + math.max(0, now - ts) * rate)
local ok = 0
if tokens >= cost then
  tokens = tokens - cost
  ok = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate))  -- 閒置到補滿就可以丟掉
return ok

補充、比較、扣減、寫回與設到期全在同一支腳本裡。到期時間設成「從空桶補到滿」所需的時間：閒置超過這麼久的鍵，下次出現時當成滿桶即可，不必一直佔記憶體。

坑二：INCR 成功、PEXPIRE 沒送到。第 2 節的 Fixed Window 若把兩條命令分開送，行程在兩者之間崩潰或網路斷掉，key 就沒有到期時間。這個身份之後每一筆都加在同一個永不歸零的計數上，等於被永久封鎖，而且不會有任何錯誤日誌。修法同樣是一支腳本：加一之後若發現沒有 TTL（PTTL 小於 0）就補上。

local t = redis.call('TIME')
local ms = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local wid = math.floor(ms / tonumber(ARGV[1]))
local key = KEYS[1] .. ':' .. wid
local c = redis.call('INCR', key)
if redis.call('PTTL', key) < 0 then
  redis.call('PEXPIRE', key, ARGV[1])
end
return c

檢查 PTTL < 0 而不是 c == 1：即使某一次設定 TTL 失敗，下一筆請求也會把它補上。視窗編號用 Redis 的時間算，應用機器的時鐘歪了也不會把同一時刻的請求算進不同格。

兩支腳本都用 redis.call('TIME') 取時間，這同時解決了多機時鐘偏移（Clock Skew）：所有判定都以同一台 Redis 的時鐘為準。Redis 5 起腳本預設以「效果」複製到副本，先取 TIME 再寫入是允許的；更早的版本要在寫入前呼叫 redis.replicate_commands()。叢集模式下，腳本用到的 key 必須在同一個 slot，一條規則一個 key 天然滿足。Sliding Log 的刪舊、計數、條件寫入也是同樣的道理，整段放進一支腳本即可。

熱鍵：不拆 key，改成本地預取

集中計數讓每筆請求都多一趟往返。對大多數鍵這不是問題——不同身份落在不同 key，Redis 叢集本來就把它們分散到不同分片。麻煩的是單一熱身份：一個大客戶每秒幾萬筆，全部打在同一個 key、同一個分片上。

直覺的解法是把它拆成 user:42:0 到 user:42:3 四片再加總，但這會讓上限失準：每片各有一份上限，總和就超了；若把每片上限調成四分之一，流量在片之間一不均勻，某片先滿就提早拒絕。限流的上限是一個全域數字，硬拆只是把「多節點各數各的」的問題搬進 Redis。

正確的降壓手段是本地預取（Local Quota Prefetch）：節點手上沒有餘額時，向中央一次原子借走 min(批次, 剩餘) 個額度，然後在本地花。借到 0 就記住這一窗已經空了，不要每筆再打一次。全域放行數不會超過上限，因為借走的當下已經從中央扣掉；吃虧的是額度會卡在借走它的那台機器上（Stranded Quota）。

兩個節點、全域上限 6、一次借 4：節點 A 借走 4、用掉 2、手上還留 2；節點 B 只借得到剩下的 2，兩筆都用掉。此時若第 5 筆打到 B，中央已經是 0、B 手上也是 0，請求被拒絕——額度明明還在 A 手上，卻搬不過去。這就是預取的代價：提早誤拒（False Reject）。

下面把同一批請求同時送給兩種共用方式。請求以輪替順序打到各節點；集中式每筆都打一次中央，預取只在本地沒餘額時借一批。每個節點一條配額條：綠色是已放行、橘色是已從中央扣掉卻卡在手上的額度、紅色是被拒絕的請求。橘色與紅色同時出現在不同節點上，就是「額度在 A，請求在 B」。

預設 4 個節點、各 2 筆、上限 20、一次預取 8：前三個節點借走全部 20 個額度，各自只用掉 2 個；節點 4 一個都借不到，兩筆被拒，而別人手上還握著 14 個。把批次收到 1，卡額與誤拒都消失，往返次數回到與集中式相同；把節點數拉高，同一份上限被更多人同時預借，誤拒更早出現。

計數器掛掉時：Fail-open 還是 Fail-closed

限流器多了一個依賴，就多了一種失敗。Redis 逾時或失聯時要事先選邊，而且不同端點的選擇不一樣：

Fail-open 不等於「不限流」：本地保底上限讓中央失聯時的最壞情況仍是有界的。

另外兩件事一起做：呼叫 Redis 的逾時要設得很短（幾毫秒），否則限流器自己成了延遲來源；對一個已經失聯的 Redis 也不要每筆都去碰，熔斷、艙壁隔離與降級那篇的熔斷器正好適用。

不要從 Redis 命令開始。先鎖契約，再選演算法，再講多節點，最後講失敗與回應。

1. 釐清契約與規模（約 3 分鐘）：鍵是使用者、API key 還是 IP？上限是「任意窗」還是「速率＋突發」？允不允許突發、多大？有幾台應用、多少個活躍鍵、尖峰 QPS？不同端點成本是否不同？
2. 選演算法與狀態結構（約 5 分鐘）：用下表選一列，說出它放棄了什麼（邊界突刺、近似誤差、突發打進上游、排隊延遲），以及每個鍵在熱路徑上要存什麼。
3. 分散式與原子性（約 4 分鐘）：共用計數、一支 Lua 腳本完成讀改寫與設到期、用 Redis 的時鐘；熱身份不拆 key，改本地預取並承認卡額。
4. 失敗、監控與回應（約 3 分鐘）：計數器失聯時哪些端點 Fail-closed、哪些 Fail-open 加本地保底；監控每條規則的 429 比例與 Redis 延遲；拒絕時回 429 與 Retry-After，標頭與本體的格式指到 API 設計風格與演進那篇談速率與配額的段落，不要在這裡發明。

選型先看契約，再看熱路徑放得下幾個數字。同一張表也能用來檢查現成元件：它實作的是哪一列，而不是它叫不叫 rate limit。

真實系統很少只有一層限流。邊緣、閘道、服務內各自擋一種粒度，AWS 的 WAF 與 API Gateway 各管其中一層，都不能取代服務內部那一層。

每一層看得到的身份不同，能擋的流量也不同。越外層越便宜、越粗；越內層越貴、越精細：

客戶端的流量由左往右穿過三層。WAF 擋 DDoS 與爬蟲的 IP 洪峰，被擋的請求根本到不了你的服務；API Gateway 管合作夥伴的 API key；服務內那一層才認得資料庫裡的使用者與每個端點的真實成本。三層缺一層，就有一種流量沒人管。

API Gateway 的 usage plan 把 throttle 與 quota 拆開。throttle 的 rate 是穩態每秒請求數，burst 是桶容量，也就是 token bucket：閒置時可以一次打進 burst 筆，然後回到 rate。quota 是另一個計數，按日、週或月歸零，屬於固定視窗，不負責抹平秒級突發。計劃綁在 API key 與 stage 上；就算計劃寫得很寬，stage 與帳號層還有自己的 throttle，請求可能先死在那兩層。AWS 的文件也明說 usage plan 的 throttle 與 quota 是盡力而為，不是硬上限，不該拿它來控制成本或阻擋存取。超限時請求已經到達閘道，回應是 429。

WAF 的 rate-based rule 粗得多。評估視窗可以是 1、2、5 或 10 分鐘，預設 5 分鐘，依來源 IP、轉送過來的 IP，或你指定的自訂鍵計數。超過門檻就對該鍵執行動作，直到速率掉回門檻以下。門檻下限以帳號當下的限制為準：文件上的下限曾是每視窗 100，後來改成 10。它適合擋邊緣上的大量濫用，不適合「每個使用者每秒 5 次」這種契約——視窗最短 1 分鐘，而且被擋下的請求到不了你的應用，你的 429 本體不會出現。

兩套都叫限流。一個是合作夥伴的秒級 token bucket，一個是邊緣上以分鐘計的視窗。內部使用者的毫秒級預算仍然要自己數。