題幹與適用場景
請實作一個按使用者隔離的 Token Bucket 限流器。每個桶有最大容量 capacity、每秒補充速率 refillRate 和目前 token 數；請求攜帶使用者 ID、時間戳和消耗量 cost。如果補充後 token 足夠，扣除成本並允許請求，否則拒絕。需要說明介面設計、複雜度、時間精度、並發安全和測試。
這道題適合後端、平台和基礎設施程式設計面試。AWS 文件把 token bucket 描述為「token 代表請求、按速率補充、每次請求消耗 token」的限流模型，並強調容量和補充速率要透過測試驗證。
面試官考察點
- 是否能寫出惰性補充公式，而不是用計時器逐桶加 token。
- 是否使用單調時間，避免牆上時鐘回撥造成 token 增發。
- 是否限制 token 不超過容量，且拒絕請求時不錯誤扣減。
- 是否明確單機記憶體狀態與分散式共享狀態的邊界。
- 是否能覆蓋並發、浮點精度、超大時間間隔和無效參數。
回答前需要釐清的問題
先確認：
cost是否始終為正整數，還是支援按 token 計費的浮點成本？- 時間戳由呼叫方傳入用於測試，還是限流器自行讀取時鐘？
- 只要求單程序實作，還是多個實例必須共享同一使用者配額？
- 拒絕時是否需要返回預計可重試時間或剩餘 token？
若沒有補充，可以假設單程序、非負整數成本、奈秒級單調時鐘，允許突發但不能超過桶容量。
30 秒回答框架
我會為每個使用者保存 tokens 和 lastRefillAt，在請求到達時按經過的單調時間惰性補充：min(capacity, tokens + elapsed * refillRate)。確認補充後的 token 不小於 cost 才扣減並返回允許，否則保持狀態並返回拒絕。單機版本用每使用者鎖或原子臨界區保證讀改寫不可分割；分散式版本把同一公式放在支援原子腳本的共享儲存中。參數、時鐘回撥、邊界時間和並發請求都用模型測試驗證。
分步驟深入解答
1. 資料結構與不變量
每個使用者記錄 tokens、lastRefillAt 和可選的版本號。狀態必須滿足 0 <= tokens <= capacity，且 lastRefillAt 不倒退。容量和補充速率在建立時驗證為正值；成本必須大於零且不超過容量，否則直接返回參數錯誤，不改變桶狀態。
2. 惰性補充
設目前時間為 now，經過時間為 elapsed = now - lastRefillAt。補充量是 elapsed * refillRate，新 token 為 min(capacity, tokens + refill)。當桶已滿時，仍把 lastRefillAt 推進到 now，避免下一次重複計算同一段時間。使用整數奈秒和有理數計算可減少浮點誤差；若實作使用浮點數，要規定捨入方式並測試長期漂移。
3. 允許與拒絕
補充後若 tokens >= cost，扣除成本並返回允許；否則不扣 token，返回拒絕和可選的 retryAfter。估算重試時間可以用 (cost - tokens) / refillRate，但要向上取整，並處理速率為零或成本超過容量的情況。拒絕結果不應偽造為成功，也不應更新成比目前時間更早的游標。
4. 並發與狀態儲存
單機實作必須把讀取、補充、判斷和寫回放在同一臨界區；按使用者分片鎖可以減少全域鎖競爭。多程序共享配額時，應用內鎖不足，需要 Redis Lua、資料庫行鎖或其他原子交易，把整段狀態轉換作為一次操作。網路重試要攜帶請求 ID，避免客戶端在回應遺失時重複消費業務 token。
5. 過期與容量控制
長期不活躍的使用者狀態應按 lastRefillAt 和租約過期清理，清理不能影響新請求的正確初始化。高基數使用者要有最大狀態數、分片和淘汰策略；淘汰後新桶從滿容量開始可能形成突發，因此生產策略要明確是否允許這種行為。不要用無限 map 讓攻擊者透過偽造使用者 ID 耗盡記憶體。
6. 測試與可觀測性
測試至少覆蓋初始滿桶、連續拒絕、恰好補足、成本等於容量、時間不前進、時間回撥、超長閒置、並發爭用和重複請求。用可控時鐘跑性質測試，持續驗證 token 不越界、成功扣減總量不超過補充總量加初始容量。指標包括允許率、拒絕率、目前 token 分布、狀態數、鎖等待、原子腳本錯誤和記憶體佔用。
高品質示範回答
我會把核心操作定義成 allow(userId, now, cost)。使用者狀態只有 tokens 和 lastRefillAt，每次請求在同一臨界區計算經過時間、補充 token、截斷到容量，再判斷是否足夠。成功時扣除成本並把游標推進到 now；失敗時保留補充後的 token，但不扣除成本。整個過程使用單調時間，狀態不允許回退。
單機用按使用者分片鎖；分散式場景把相同轉換放到 Redis Lua 或資料庫原子交易，不能先讀後寫多個網路往返。請求 ID 只解決重試冪等，不能把限流器誤稱為業務操作的 exactly-once。狀態需要過期清理和高基數保護，避免偽造使用者鍵消耗記憶體。
測試用可控時鐘覆蓋零時間、恰好補足、成本等於容量、超長閒置、時鐘回撥和並發。用性質斷言 token 始終在零到容量之間，允許請求的累計成本不超過初始容量加補充量。上線後觀察拒絕率、token 分布、狀態增長、鎖等待和儲存腳本錯誤；AWS 的實踐也要求先測試擬定限額，再逐步提高。
常見錯誤
- 為每個桶啟動計時器，導致使用者數增長時執行緒和排程開銷失控。
- 用牆上時間計算 elapsed，NTP 回撥後產生額外 token。
- 補充後忘記
min(capacity, ...)，讓桶無限增長。 - 拒絕請求仍扣除 token，造成使用者配額被虛假消耗。
- 把應用內鎖當成跨實例原子性。
- 允許
cost > capacity，讓請求永遠等待或返回錯誤的重試時間。 - 使用浮點數卻不說明捨入與長期漂移。
- 只測順序呼叫，不測同一使用者的並發讀改寫。
追問及應對
為什麼不用固定視窗計數？
固定視窗實作簡單，但邊界可能允許短時間雙倍突發。Token Bucket 用容量表達允許的突發，用補充速率表達長期速率；如果業務不允許任何突發，再比較滑動視窗或漏桶。
如何返回 Retry-After？
根據缺口除以補充速率並向上取整；速率為零或成本超過容量時返回不可重試或設定錯誤，不返回無限等待的時間戳。
Redis 不可用時怎麼辦？
按介面風險選擇 fail-closed、受限的本地預算或明確降級，並記錄原因。不能讓每個實例都無限放行，也不能把故障偽裝成普通業務拒絕。
修改容量和速率時如何遷移？
先按舊參數補充到變更時刻，再按策略截斷或換算 token，記錄設定版本。降低容量時必須處理現有 token 超過新上限的情況，並保證變更原子化。
如何證明實作沒有超發？
用模型狀態機和隨機時間序列做性質測試，斷言每個時間區間的累計允許成本不超過初始 token 加該區間理論補充量；再用並發壓力測試驗證原子臨界區。