这是一个非常重要且常用的流量整形和速率限制算法。它的核心思想非常直观和优雅。
- 核心概念
想象一个桶，这个桶有固定的容量。系统会以一个恒定的速率向这个桶里放入“令牌”。每当一个请求（或数据包）到来时，它需要从桶中取出一个（或多个）令牌才能被处理。
桶的容量 (Capacity)：桶最多能存放的令牌数量。这决定了在短时间内能允许的突发流量最大值。
令牌放入速率 (Rate)：系统每隔多久向桶中放入一个令牌。这个速率决定了长期来看的平均请求处理速率。
- 算法工作原理
初始化：桶开始时是满的，里面有 capacity 个令牌。
添加令牌：系统以一个固定的时间间隔（例如，每 1/rate 秒）向桶中添加一个令牌。如果桶已经满了，新添加的令牌会被丢弃。
处理请求：当一个请求到达时：
如果桶中有足够数量的令牌（比如需要 1 个），则取出相应数量的令牌，请求被立即放行处理。
如果桶中没有足够的令牌，那么这个请求会被等待（排队）或直接丢弃/拒绝（取决于具体的实现策略），直到桶中有新的令牌加入。
- 一个简单的例子
假设我们有一个令牌桶，其参数如下：
速率 (Rate)：每秒 2 个令牌 → 即每 0.5 秒加一个令牌。
容量 (Capacity)：10 个令牌。
情景模拟：
时间 0s：桶是满的，有 10 个令牌。
时间 0s：突然来了 5 个请求。每个请求消耗 1 个令牌。桶里还剩 5 个令牌。所有 5 个请求都被立即处理。这体现了处理突发流量的能力。
时间 0.5s：系统添加一个令牌，桶里有 6 个令牌。
时间 1.0s：系统添加一个令牌，桶里有 7 个令牌。
时间 1.5s：系统添加一个令牌，桶里有 8 个令牌。
…
时间 5.0s：此时桶已经被重新加满到 10 个令牌（因为添加令牌的速率大于消耗速率）。
时间 6.0s：突然又来了 15 个请求。
前 10 个请求可以立即被处理，消耗掉所有令牌。
剩下的 5 个请求无法立即得到令牌，它们必须等待。由于每 0.5 秒才会产生一个新令牌，这些请求将根据新的令牌产生速率被逐个处理（大约每 0.5 秒处理一个）。
从这个例子可以看出：
长期平均速率被限制为每秒 2 个请求。
短期突发流量最多可以处理 10 个请求（桶的容量）。
- 算法实现（伪代码/Python风格）
在实际编程中，我们通常不会真的启动一个定时器来添加令牌，而是采用“惰性计算”的方式，在请求到来时计算自上次检查以来应该产生多少新令牌。
python
import time
class TokenBucket:
def init(self, capacity, rate):
self.capacity = capacity # 桶的容量
self.rate = rate # 令牌放入速率 (个/秒)
self.tokens = capacity # 当前令牌数量
self.last_time = time.time() # 上次更新时间戳
def consume(self, tokens_needed=1):
now = time.time()
elapsed = now - self.last_time # 计算经过的时间
# 计算这段时间内应该添加多少令牌
new_tokens = elapsed * self.rate
# 更新当前令牌数量（不能超过桶容量）
self.tokens = min(self.capacity, self.tokens + new_tokens)
self.last_time = now
# 判断是否有足够的令牌
if self.tokens >= tokens_needed:
self.tokens -= tokens_needed
return True # 获取令牌成功
else:
return False # 获取令牌失败（请求被限流）- 优点
允许突发流量：这是相对于另一种漏桶算法的主要优点。因为桶有容量，它可以应对短时间内的流量高峰。
平滑流量：长期来看，输出速率是稳定的，等于令牌生成的速率，不会对下游系统造成巨大压力。
易于实现：概念简单，实现起来也不复杂。
- 应用场景
令牌桶算法广泛应用于网络和系统中：
API 速率限制：例如，规定每个用户每秒只能调用某个 API 10 次。使用令牌桶（capacity=10, rate=10/s）可以允许用户在前 100 毫秒内快速调用 10 次，之后就必须每秒一次地调用。
网络流量整形：限制网络接口发送数据的速率，防止网络拥堵。
CPU 调度：限制进程的 CPU 使用率。
- 与漏桶算法的区别
这是一个常见的对比点：
特性 令牌桶 漏桶
核心概念 拿令牌放行请求 水（请求）从漏孔中匀速流出
速率限制 平均速率 + 突发流量 严格的恒定速率
实现关键 令牌生成 请求队列
灵活性 更灵活，适合需要一定突发量的场景 更严格，保证绝对平滑的输出
简单来说，令牌桶允许一定程度的突发，而漏桶强制要求输出绝对平滑。在大多数互联网速率限制的场景下，令牌桶因其灵活性而更受欢迎。