漏桶Leaky bucket
按固定速率消减积压，按突发规则处理新增请求。
- 核心约束
- 积压随时间衰减，请求到来时增加。
- 适用问题
- 请求限速与突发控制。
- 边界与取舍
- 不同实现的延迟、拒绝和突发语义需要单独解释。
常见操作#
k 为独立限流键数量；以按时间衰减 excess 的 nginx 请求限流实现为例。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 更新单个桶的欠账 | 固定宽度时间算术，按 elapsed × rate 衰减，再加入本次请求。 | |
| 查找限流键 | nginx 1.26.3 使用红黑树；长键比较、锁竞争另计。 | |
| 延迟 / 拒绝请求 | 由队列和定时器策略决定 | 整形器以等待平滑输出；监管器也可直接拒绝超限请求。 |
时间与空间#
- 时间复杂度
- 桶算术 ，键索引和等待另计
- 辅助空间
- 桶状态，加上被延迟请求的状态
“漏桶”有排队整形和计量等不同用法。nginx 的 burst、delay、nodelay 会改变超额请求的处理，不意味着始终匀速发送。
工程中的应用#
1 个案例 · 附源码limit_req 把漏桶计算、红黑树查状态与队列回收组合起来，按配置的 key 管理请求速率。
附源码片段 · 通信与流量
基础原理参考资料
RFC 3290 · Token and leaky buckets区分令牌桶计量和漏桶整形的语义。
nginx · limit_req module漏桶、burst、延迟与拒绝选项。
nginx 1.26.3 · limit_req implementation红黑树定位、excess 衰减和请求延迟。