限頻三大算法對比與選型建議

維度	漏桶算法	令牌桶算法	滑動窗口算法
流量平滑性	強（固定速率）	中（允許突發）	弱（依賴窗口粒度）
實現復雜度	簡單	中等（需處理令牌生成）	中等（需處理窗口滑動）

一、漏桶算法（Leaky Bucket Algorithm）

1.核心原理

漏桶算法的核心是恒定速率輸出，無論輸入流量如何波動，輸出始終保持穩定。其工作機制可類比為一個底部有固定孔徑的水桶：

• 輸入：請求以任意速率流入桶中（如突發流量）。
• 輸出：桶以固定速率（如100請求/秒）處理請求，超出桶容量的請求直接丟棄。

2.實現

• 實現：使用隊列存儲請求，通過定時任務以固定速率從隊列中取出請求處理。若隊列滿則拒絕新請求。

在非單節點場景下，可使用消息隊列中間件，或者Redis模擬隊列，來實現這個算法。

3.為什么要限制漏桶容量

有容量限制 vs 無容量限制：對比分析

場景	有容量限制（標準漏桶）	無容量限制（無限漏桶）
流量平滑效果	? 穩定輸出，突發請求被緩存或丟棄	? 穩定輸出（但突發請求全部緩存）
內存/緩沖區占用	🟡 有限占用（取決于桶容量）	? 可能無限占用，導致OOM（內存溢出）
突發流量處理	🟡 超過容量的請求被丟棄，保護下游系統	? 緩存所有請求，下游可能被持續高負載拖垮
適用場景	真實系統（如API接口限頻、網絡流量控制）	理論場景（無實際意義，無法用于生產環境）

4.優缺點分析

• 優點：
  • 絕對平滑：嚴格控制輸出速率，適合對穩定性要求極高的場景（如金融交易接口）。
  • 實現簡單：只需維護隊列和固定速率處理器，無需復雜邏輯。
• 缺點
  • 資源浪費：突發流量會被直接丟棄，無法利用系統空閑資源。
  • 靈活性差：無法區分請求優先級，所有超額請求同等處理。

二、令牌桶算法（Token Bucket Algorithm）

1.核心原理

令牌桶算法通過令牌生成與消耗實現限流，允許一定程度的突發流量：

• 令牌生成：系統以固定速率（如100令牌/秒）向桶中添加令牌，桶容量上限為burst_size（如200令牌）。
• 請求處理：每個請求需消耗一個令牌，無令牌則拒絕。若桶滿，新生成的令牌會被丟棄。

2.實現

（1）單機實現

Guava的RateLimiter采用令牌桶算法，支持動態調整速率和突發容量。

RateLimiter rateLimiter = RateLimiter.create(100.0); // 每秒生成100令牌
if (rateLimiter.tryAcquire()) { // 嘗試獲取令牌// 處理請求
} else {// 限流
}

（2）分布式實現

在分布式系統中，可以利用 Redis 的原子操作和 Lua 腳本來實現一個線程安全的令牌桶。

• 使用 Redis 實現令牌桶的關鍵在于：
  • 使用原子操作保證令牌增減的線程安全
  • 實現令牌的自動生成邏輯
  • 高效地判斷是否允許請求通過

3.優缺點分析

• 優點：
  • 支持突發流量：允許短時間內消耗桶內累積的令牌，提升資源利用率（如電商秒殺）。
  • 參數靈活：可通過調整rate（平均速率）和burst_size（突發容量）平衡平滑性與突發性。
• 缺點：
  • 實現復雜度較高：需維護令牌生成、存儲和消耗邏輯。
  • 流量尖刺風險：突發流量可能瞬間耗盡令牌，導致后續請求被拒絕。

三、滑動窗口算法（Sliding Window Algorithm）

1.核心原理

滑動窗口算法通過時間窗口劃分與計數實現限流，精度隨窗口細分而提升：

• 窗口劃分：將時間軸劃分為多個固定長度的子窗口（如1秒劃分為10個0.1秒的子窗口）。
• 計數與滑動：統計當前窗口內的請求數，當窗口滑動時，舊子窗口的計數逐漸過期。

2.實現

在分布式系統中，可以利用 Redis 的原子操作和 Lua 腳本來實現一個這個算法。

3.優缺點分析

• 優點：
  • 時間敏感性強：可精確控制時間維度的請求頻率（如“每分鐘最多100次”）。
  • 動態調整窗口：支持秒級、分鐘級等不同粒度的限流規則。
• 缺點：
  • 臨界問題：窗口切換時可能出現雙倍請求（如0.9秒和1.1秒各發100次）。
  • 分布式同步成本：需依賴Redis等分布式緩存，引入額外延遲。