限流算法令牌桶：平滑流量控制

什么是令牌桶算法

令牌桶算法是一种经典的流量整形与速率限制技术，旨在平滑突发流量，同时限制长时间的平均传输速率。其核心思想是通过一个固定容量的“桶”，以恒定速率生成“令牌”，每个请求需要消耗一个或多个令牌才能被处理；若桶中令牌不足，请求将被延迟或拒绝。

该算法最早用于网络流量控制，后来广泛应用于API网关、分布式系统、消息队列等场景，用于保护后端服务免遭过载。

核心机制与原理

关键组件

• 令牌桶：一个虚拟容器，存储令牌，具有最大容量 capacity。
• 令牌生成速率：桶以恒定速率 r（个/秒）产生令牌，例如每秒向桶中添加 r 个令牌。
• 消耗规则：每个请求到达时，尝试从桶中取出 n 个令牌（通常为1）。若桶中令牌数 ≥ n，则移除 n 个令牌并放行请求；否则拒绝或阻塞等待。

平滑特性

令牌桶的“平滑”体现在：它允许短期突发流量超过平均速率，只要桶内有积攒的令牌即可。当长时间空闲时，桶会被填满，后续流量可获得最大 capacity 的突发能力；而当持续高负载时，请求速率则被限制在令牌生成速率 r 附近。这种效果类似于“先存后花”的信用模型。

与漏桶算法的区别

算法工作流程

1. 初始化：桶中令牌数 tokens 设为 capacity（满桶），记录上次补充令牌的时刻 last_time。
2. 请求到达时：
   • 计算当前时间 now，根据经过的时间 delta = now - last_time 补充令牌：
     tokens = min(capacity, tokens + delta * r)
   • 更新 last_time = now。
   • 若 tokens >= 1：消耗1个令牌（tokens -= 1），放行请求。
   • 否则：拒绝请求或使其等待（具体处理取决于应用策略）。
3. 补充逻辑：仅在每次请求到来时惰性计算令牌补充量，避免后台线程开销。

伪代码实现

class TokenBucket:
    capacity      // 桶最大令牌数
    rate          // 令牌生成速率（个/秒）
    tokens        // 当前令牌数
    last_time     // 上次补充时间

    function constructor(capacity, rate):
        this.capacity = capacity
        this.rate = rate
        this.tokens = capacity
        this.last_time = current_time()

    function allow_request():
        now = current_time()
        elapsed = now - last_time
        // 计算补充令牌数
        tokens_to_add = elapsed * rate
        tokens = min(capacity, tokens + tokens_to_add)
        last_time = now

        if tokens >= 1:
            tokens = tokens - 1
            return true   // 允许请求
        else:
            return false  // 拒绝请求

多令牌消耗场景

在某些系统中，一个请求可能代表不同“重量”，例如上传大文件消耗更多令牌。只需将判断条件改为 if tokens >= n，并执行 tokens -= n 即可。

参数调优指南

确定速率 r

• 平均QPS限制：若需将API限制在100 QPS，设置 r = 100。
• 精确控制：r 应为float类型，支持小数速率（如0.5代表每2秒一个请求）。

确定容量 capacity

• 允许的突发大小：容量大小直接决定系统能承受的最大瞬时突发。例如，capacity = 200，r = 100，则系统最多可支持200个令牌的瞬时突发，随后回到100 QPS。
• 常见取值：capacity = r * burst_time，burst_time 是期望容忍的突发秒数。如果API限流100 QPS，且希望允许最多2秒突发，则 capacity = 200。
• 特殊案例：若 capacity = 1，则令牌桶退化为严格的1个令牌消费模式，近似固定间隔限制。

补充精度处理

使用浮点数计算令牌数时，需要注意浮点累加误差。生产环境常采用整数化：将 tokens 表示为“毫令牌”或“微令牌”，速率也相应放大，避免小数运算。

应用场景详解

• API网关限流：对每个客户端或每个接口分配独立的令牌桶，实现差异化流控。
• 消息队列消费：控制消费者拉取消息的速率，防止下游处理能力不足。
• 爬虫控制：限制每秒请求网站的次数，但允许在获取 robots.txt 等场景时短暂加速。
• 网络流量整形：路由器使用令牌桶调度数据包，保障带宽利用率并控制突发。

常见问题与优化

令牌预填充？

系统冷启动时，桶为空，第一个请求可能被直接拒绝。解决方案：初始化时将 tokens 设为 capacity，或采用“预热”模式逐步增加令牌生成速率。

分布式令牌桶

单实例令牌桶不适用于多节点服务。需引入分布式存储（如Redis）配合Lua脚本原子性完成令牌补充与扣减。基本思路：

1. 使用Redis Hash存储桶状态：tokens, last_time。
2. 编写Lua脚本：获取当前时间、计算补充、判断并扣减，一次原子执行。

分层限流

将令牌桶与漏斗、滑动窗口结合，对服务整体设置总速率先用令牌桶整形，内部再对用户分别限流，提供更精细的灰度控制。

总结

令牌桶算法通过恒定的令牌生成速率控制长期平均流量，同时利用桶容量吸收突发请求，天然适合需要平滑突发的系统保护方案。实现简单、理解直观，是限流工具库中最常用、最成熟的算法之一。掌握其原理和调参方法，可以灵活应对从单体到分布式的大部分流量防护需求。