当前位置：首页 > backend >正文

漏桶算法（Leaky Bucket）和令牌桶算法（Token Bucket）的详细介绍

backend 2025/5/14 7:21:18

一、漏桶算法（Leaky Bucket）
核心原理
流量整形：无论请求流入速度多快，系统以恒定速率处理请求。

容量限制：桶的最大容量为 Capacity，超过容量的请求会被拒绝。

适用场景：需要严格限制处理速率的场景（如支付接口、消息队列消费）。

C# 实现示例

using System;
using System.Threading;public class LeakyBucket
{private readonly object _lock = new object();private readonly double _capacity;      // 桶容量（最大请求数）private readonly double _leakRate;      // 流出速率（请求/秒）private double _water;                  // 当前水量（待处理的请求数）private DateTime _lastLeakTime;         // 上次漏水时间public LeakyBucket(double capacity, double leakRatePerSecond){_capacity = capacity;_leakRate = leakRatePerSecond;_water = 0;_lastLeakTime = DateTime.UtcNow;}public bool TryProcessRequest(int requests = 1){lock (_lock){// 计算自上次漏水后流出的水量var now = DateTime.UtcNow;var elapsedSeconds = (now - _lastLeakTime).TotalSeconds;var leakedWater = elapsedSeconds * _leakRate;// 更新当前水量和漏水时间_water = Math.Max(0, _water - leakedWater);_lastLeakTime = now;// 检查是否有足够容量处理新请求if (_water + requests <= _capacity){_water += requests;return true; // 允许处理}return false;    // 拒绝请求}}
}// 使用示例
var bucket = new LeakyBucket(10, 2); // 容量10，每秒处理2个请求
for (int i = 0; i < 20; i++)
{Thread.Sleep(200); // 模拟请求间隔200msConsole.WriteLine($"请求{i + 1}: {(bucket.TryProcessRequest() ? "处理" : "拒绝")}");
}

二、令牌桶算法（Token Bucket）
核心原理
突发流量允许：系统定期生成令牌放入桶中，请求需要获取令牌才能被处理。

容量限制：桶的最大令牌数为 Capacity，令牌不足时拒绝请求。

适用场景：允许突发流量但需整体限速的场景（如秒杀系统、API网关）。

C# 实现示例

using System;
using System.Threading;public class TokenBucket
{private readonly object _lock = new object();private readonly double _capacity;      // 桶容量（最大令牌数）private readonly double _refillRate;    // 令牌生成速率（令牌/秒）private double _tokens;                 // 当前令牌数private DateTime _lastRefillTime;       // 上次生成令牌时间public TokenBucket(double capacity, double refillRatePerSecond){_capacity = capacity;_refillRate = refillRatePerSecond;_tokens = capacity; // 初始满令牌_lastRefillTime = DateTime.UtcNow;}public bool TryConsumeToken(int tokens = 1){lock (_lock){// 计算自上次生成后新增的令牌var now = DateTime.UtcNow;var elapsedSeconds = (now - _lastRefillTime).TotalSeconds;var newTokens = elapsedSeconds * _refillRate;// 更新令牌数和生成时间_tokens = Math.Min(_capacity, _tokens + newTokens);_lastRefillTime = now;// 检查是否有足够令牌处理请求if (_tokens >= tokens){_tokens -= tokens;return true; // 允许处理}return false;    // 拒绝请求}}
}// 使用示例
var tokenBucket = new TokenBucket(10, 2); // 容量10，每秒生成2个令牌
for (int i = 0; i < 20; i++)
{Thread.Sleep(200); // 模拟请求间隔200msConsole.WriteLine($"请求{i + 1}: {(tokenBucket.TryConsumeToken() ? "处理" : "拒绝")}");
}

三、算法对比
在这里插入图片描述

四、实际应用场景

漏桶算法场景
消息队列消费控制：确保消费者以固定速率处理消息。

var bucket = new LeakyBucket(100, 5); // 每秒处理5条消息
while (true)
{var message = queue.Receive();if (bucket.TryProcessRequest()){ProcessMessage(message); // 处理消息}else{RequeueMessage(message); // 重新入队或等待}
}

令牌桶算法场景
API 突发请求限流：允许短时高并发，但限制长期平均速率。

var tokenBucket = new TokenBucket(100, 10); // 每秒生成10个令牌，允许突发100次
[HttpGet("data")]
public IActionResult GetData()
{if (!tokenBucket.TryConsumeToken())return StatusCode(429, "请求过多");// 处理请求...return Ok();
}

五、优化与扩展

动态参数调整
允许运行时修改容量或速率：

// 漏桶算法扩展方法
public void UpdateLeakyBucket(double newCapacity, double newLeakRate)
{lock (_lock){_capacity = newCapacity;_leakRate = newLeakRate;}
}// 令牌桶算法扩展方法
public void UpdateTokenBucket(double newCapacity, double newRefillRate)
{lock (_lock){_capacity = newCapacity;_refillRate = newRefillRate;}
}

分布式限流
结合 Redis 实现跨多台服务器的全局限流：

// 使用 Redis 存储令牌桶状态（示例代码）
var database = redis.GetDatabase();
var script = @"local key = KEYS[1]local capacity = tonumber(ARGV[1])local refillRate = tonumber(ARGV[2])local tokensRequested = tonumber(ARGV[3])local now = tonumber(ARGV[4])local data = redis.call('HMGET', key, 'tokens', 'lastRefillTime')local tokens = tonumber(data[1]) or capacitylocal lastRefillTime = tonumber(data[2]) or nowlocal elapsed = now - lastRefillTimelocal newTokens = elapsed * refillRatetokens = math.min(capacity, tokens + newTokens)if tokens >= tokensRequested thentokens = tokens - tokensRequestedredis.call('HMSET', key, 'tokens', tokens, 'lastRefillTime', now)return 1elsereturn 0end
";
var allowed = database.ScriptEvaluate(script, new { key = "token_bucket", capacity = 100, refillRate = 5, tokensRequested = 1, now = DateTime.UtcNow.Ticks });