一站式了解四种限流算法

引言

对于后端开发（Java/Go）来说，限流（Rate Limiting）是高可用架构中的核心环节。本文讨论一下关于四种限流常见方案以及对应的一些问题。

固定窗口

这里的窗口是指在一个时间段中，每一个时间段都是已经预设好的静态窗口。这是最简单的实现方式，通常作为初级方案或在性能要求极高的底层系统中使用。

• 原理：维护一个计数器，在固定的时间窗口（如每秒）内，请求进来就自增。超过阈值就拒绝，进入下一个周期计数器清零。
• 缺点（致命伤） ：临界突刺问题。如果在第一秒的最后 100ms 进入了 100 个请求，又在第二秒的最初 100ms 进入了 100 个请求。从固定窗口看都没超限（100qps），但在 200ms 的短时间内系统承受了 200 个请求，可能直接宕机。

我们一般不使用这个。

滑动窗口

滑动窗口是固定窗口的进化版。它将时间划分为多个小格子（Bucket），随着时间推移，最老的格子被丢弃，最新的格子被加入。

优点

• 平滑性优于固定窗口：通过细分时间槽，解决了固定窗口在“临界点”流量翻倍的问题。
• 内存开销可控：相比令牌桶，它不需要维护令牌生成逻辑，只需要维护一个计数数组。
• 实现直观：在 Java 的 Sentinel 或 Go 的一些流控库中应用广泛。

缺点

• 无法应对突发流量：它是一个“严格限制”的算法。如果窗口内额度用完，后续请求会被立即拒绝，缺乏弹性。
• 精度权衡：格子划分得越细，限流越精准，但占用的内存和计算开销也会随之增加。

由于滑动窗口无法应对突发流量，我们一般也不使用这个方案。

漏桶算法 (Leaky Bucket)

如果说令牌桶是控制“进水的速率”，那么漏桶控制的就是“出水的速率”。漏桶这种方案主要是用于固定流量速率场景的，有一定的适用场景

• 原理：所有的请求（水）先进入桶中，桶以固定的速率向外排水（处理请求）。如果桶满了，新进来的水直接溢出（拒绝请求）。

• 特点：

  • 极致平滑：无论流入流量多大，流出速度永远恒定。
  • 无突发处理能力：这是它与令牌桶最大的区别。即使系统现在很闲，请求也必须按部就班地排队出去。

• 适用场景：主要用于网络流量整形（Traffic Shaping） ，或者当你下游的服务非常脆弱，绝对不能承受任何瞬时波动时。

令牌桶 (Token Bucket)

令牌桶算法是我们最常用的限流方案之一，接下来我来详细介绍这种算法。

系统以恒定的速率往桶里放令牌，桶满则溢出。请求进来时必须先拿到令牌，否则被限流。

优点

• 支持突发流量 (Burst) ：这是它最大的优势。如果一段时间没请求，桶里攒满了令牌，瞬间涌入大量请求时可以快速消化。
• 流量平滑：它将请求处理的速率平滑化，非常适合保护下游资源（如数据库）。
• 业界标准：Guava 的 RateLimiter 和 Go 标准库的 golang.org/x/time/rate 均采用此方案。

缺点

• 实现较复杂：相对于窗口计数，令牌桶需要考虑令牌生成的频率和时钟精度。
• 配置复杂：除了 QPS，你还需要额外考虑“桶大小”这个参数，配置不当可能导致瞬时并发压力过大冲垮后端。

桶溢出

上面我们说到，系统以恒定的速率往桶里放令牌，桶满则溢出。溢出会有什么后果吗？

在令牌桶算法的设计中， “桶满则溢出”是一个预期的保护机制，并不会导致系统崩溃或逻辑错误。 简单来说，溢出的后果就是“令牌被作废”

1. 限制了“突发流量”的最大上限

令牌桶的一大优势是允许突发（Burst）。如果系统有一段时间没有请求，桶里会攒满令牌。

• 如果不溢出（桶无限大）： 那么系统在闲置很久后，可能会攒下几万个令牌。当流量瞬间涌入时，几万个请求会同时通过，这会瞬间冲垮你的下游数据库或依赖服务。
• 溢出的后果： 溢出确保了桶内令牌数永远不会超过 $Capacity$。这意味着无论系统闲置多久，它能应对的最大瞬时并发量被严格锁定在 $Capacity$。

2. 维持了平均 QPS 的稳定性

令牌放入的速率（Rate）决定了长期的平均吞吐量。

• 当桶满溢出时，说明当前的生产速率 > 消费速率。
• 溢出掉多余的令牌，本质上是在重置系统的“信用额度”，强制让系统回到预设的平均速率轨道上，而不是无限累积。

延迟计算

桶的容量其实就是系统能接受的最大冲击流量。

在 Java (Guava RateLimiter) 或 Go (x/time/rate) 的底层实现中，并不会真的有一个线程在不停地“放令牌”然后看它溢出，因为那样太浪费 CPU 了。

它们通常采用 延迟计算 (Lazy Evaluation) 的方式：

当一个请求进来时，根据 当前时间 - 上次请求时间 计算出这段时间内应该产生多少令牌。

$NewTokens=(CurrentTime-LastTime)\times Rate$

$TokensInBucket=\min (Capacity,CurrentTokens+NewTokens)$

这里的 min 函数就是“溢出”的数学表现。 超过 $Capacity$ 的部分直接被舍弃，不参与计算

总结

这里给出四种方案的对比表格，每种方案都有其使用场景，可以按需选择