3、速率限制基础：令牌桶、漏桶、固定窗口、滑动窗口算法的原理与对比

在分布式系统尾延迟压测中，速率限制（Rate Limiting）是防止系统过载、保障服务质量的核心手段。不同的速率限制算法在突发处理能力、内存开销、边界平滑度上存在显著差异。本节将深入剖析四种经典算法的原理，并通过对比表格和流程图帮助建立直观理解。

3.1 令牌桶算法（Token Bucket）

令牌桶算法是最常用的速率限制算法之一，它允许一定程度的突发流量，同时保证长期平均速率不超过阈值。

• 核心原理：系统以固定速率向桶中放入令牌，每个请求消耗一个令牌。桶有最大容量，超出部分令牌丢弃。
• 关键参数：rate（令牌生成速率，即平均 QPS）、burst（桶容量，即最大突发请求数）。
• 行为特征：当桶中有令牌时，请求可立即通过（允许突发）；当桶空时，请求被拒绝或排队等待。
• 适用场景：允许短时间流量尖峰的网络接口、API 网关、微服务限流。

3.2 漏桶算法（Leaky Bucket）

漏桶算法与令牌桶相反，它强制将请求流整形为恒定速率输出，不允许任何突发。

• 核心原理：请求进入桶中，桶底部以固定速率“漏出”请求进行处理。桶满时新请求被丢弃。
• 关键参数：leak_rate（漏出速率，即处理速率）、bucket_size（桶容量，即最大排队长度）。
• 行为特征：输出速率严格恒定，输入突发被缓冲或丢弃。没有“借令牌”或“预支”机制。
• 适用场景：需要严格平滑输出流量的场景，如数据库写入限流、消息队列消费速率控制。

3.3 固定窗口算法（Fixed Window）

固定窗口算法实现简单，将时间划分为固定长度窗口，每个窗口内限制请求总数。

• 核心原理：以固定时间间隔（如 1 秒）划分窗口，每个窗口维护一个计数器。请求到达时计数器加 1，超过阈值则拒绝。
• 关键参数：window_size（窗口大小，如 1s）、limit（窗口内最大请求数）。
• 行为特征：实现简单，内存开销极低（仅需一个计数器+时间戳）。但存在“边界突刺”问题：窗口切换瞬间可能允许两倍于阈值的请求通过。
• 适用场景：对精度要求不高、资源受限的简单限流场景。

3.4 滑动窗口算法（Sliding Window）

滑动窗口算法通过将窗口细分为更小的子窗口（slot），解决了固定窗口的边界突刺问题。

• 核心原理：将时间窗口划分为 N 个等长子窗口（如 1s 窗口划分为 10 个 100ms slot）。每个 slot 独立计数，滑动窗口的总请求数为当前窗口内所有 slot 计数之和。
• 关键参数：window_size（总窗口大小）、slot_count（子窗口数量）、limit（窗口内最大请求数）。
• 行为特征：边界平滑，精度随 slot 数量增加而提升。内存开销为 O(N)，N 为 slot 数量。
• 适用场景：需要精确限流、防止边界突刺的生产环境，如 API 网关、负载均衡器。

3.5 四种算法对比总结

3.6 压测场景下的算法选择建议

• 模拟突发流量：使用令牌桶算法，设置 burst 参数模拟瞬间流量尖峰，观察后端系统的排队和降级行为。
• 模拟恒定过载：使用漏桶算法，设置 leak_rate 低于压测发送速率，观察请求排队延迟和丢弃率。
• 生产环境限流：优先选择滑动窗口算法，兼顾精度和实现复杂度。固定窗口仅用于资源受限或精度要求不高的场景。
• 压测工具实现：大多数压测工具（如 wrk、vegeta、locust）内置令牌桶限流器。如需精确控制，可自行实现滑动窗口限流器。