令牌桶Token bucket
以固定速率补充令牌，请求消耗令牌，桶容量限制可积累突发量。
- 核心约束
- 令牌不超过桶容量；获准请求消耗对应配额。
- 适用问题
- 允许一定突发的速率限制与流量整形。
- 边界与取舍
- 补充精度、请求成本、等待或拒绝规则需要单独设计。
常见操作#
r 为补充速率，B 为桶容量，k 为独立桶数量。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 按时间补充 / 消耗令牌 | 按经过时间惰性补充并截断到 B，固定宽度算术；无需为每个令牌设置定时器。 | |
| 查找桶 / 并发更新 | 由键索引及同步方式决定 | 哈希定位、锁或 CAS 重试不包含在桶算术的常数成本内。 |
时间与空间#
- 时间复杂度
- 已定位桶的策略算术
- 辅助空间
- 每桶 ，k 个桶
允许消耗积攒令牌形成突发。令牌单位可为请求或字节，必须与补充速率一致；令牌桶本身不自动产生排队系统。
工程中的应用#
1 个案例 · 附源码Envoy 本地限流按单调时钟补充令牌，用原子更新协调同一桶的并发扣减。桶容量决定可积累的突发量。
附源码片段 · 通信与流量
基础原理参考资料
RFC 3290 · Token-bucket model速率、容量、突发容许量和流量计量。
Envoy 1.32 · TokenBucketImpl按单调时钟计算补充和消耗的具体实现。