大多数情况下，我们不需要自己实现一个限流系统，但限流在实际应用中是一个非常微妙、有很多细节的系统保护手段，尤其是在高流量时，了解你所使用的限流系统的限流算法，将能很好地帮助你充分利用该限流系统达到自己的商业需求和目的，并规避一些使用限流系统可能带来的大大小小的问题。

# 令牌桶算法

令牌桶（token bucket）算法，指的是设计一个容器（即“桶”），由某个组件持续运行往该容器中添加令牌（token），令牌可以是简单的数字、字符或组合，也可以仅仅是一个计数，然后每个请求进入系统时，需要从桶中领取一个令牌，所有请求都必须有令牌才能进入后端系统。当令牌桶空时，拒绝请求；当令牌桶满时，不再往其中添加新的令牌。 令牌桶算法的架构如图1所示：

令牌桶算法的实现逻辑如下：

首先会有一个定义的时间窗口的访问次数阈值，例如每天1000人，每秒5个请求之类，限流系统一般最小粒度是秒，再小就会因为实现和性能的原因而变得不准确或不稳定，假设是T秒内允许N个请求，那么令牌桶算法则会使令牌添加组件每T秒往令牌桶中添加N个令牌。

其次，令牌桶需要有一个最大值M，当令牌添加组件检测到令牌桶中已经有M个令牌时，剩余的令牌会被丢弃。反映到限流系统中，可以认为是当前系统允许的瞬时最大流量，但不是持续最大流量。例如令牌桶中的令牌最大数量是100个，每秒钟会往其中添加10个新令牌，当令牌满的时候，突然出现100 TPS的流量，这时候是可以承受的，但是假如连续两秒的100 TPS流量就不行，因为令牌添加速度是一秒10个，添加速度跟不上使用速度。

因此，凡是使用令牌桶算法的限流系统，我们都会注意到它在配置时要求两个参数：

• 平均阈值（rate或average）
• 高峰阈值（burst或peak）

通过笔者的介绍，读者应该意识到，令牌桶算法的高峰阈值是有特指的，并不是指当前限流系统允许的最高流量。因为这一描述可能会使人认为只要低于该阈值的流量都可以，但事实上不是这样，因为只要高于添加速度的流量持续一段时间都会出现问题。

反过来说，令牌桶算法的限流系统不容易计算出它支持的最高流量，因为它能实时支持的最高流量取决于那整个时间段内的流量变化情况即令牌存量，而不是仅仅取决于一个瞬时的令牌量。

最后，当有组件请求令牌的时候，令牌桶会随机挑选一个令牌分发出去，然后将该令牌从桶中移除。注意，此时令牌桶不再做别的操作，令牌桶永远不会主动要求令牌添加组件补充新的令牌。

令牌桶算法有一个同一思想、方向相反的变种，被称为漏桶（leaky bucket）算法，它是令牌桶的一种改进，在商业应用中非常广泛。

漏桶算法的基本思想，是将请求看作水流，用一个底下有洞的桶盛装，底下的洞漏出水的速率是恒定的，所有请求进入系统的时候都会先进入这个桶，并慢慢由桶流出交给后台服务。桶有一个固定大小，当水流量超过这个大小的时候，多余的请求都会被丢弃。

漏桶算法的架构如图所示：

漏桶算法的实现逻辑如下：

• 首先会有一个容器存放请求，该容器有一个固定大小M，所有请求都会被先存放到该容器中。
• 该容器会有一个转发逻辑，该转发以每T秒N个请求的速率循环发生。
• 当容器中请求数已经达到M个时，拒绝所有新的请求。

因此同样地，漏桶算法的配置也需要两个值：平均值（rate）和峰值（burst）。只是平均值这时候是用来表示漏出的请求数量，峰值则是表示桶中可以存放的请求数量。

注意：漏桶算法和缓冲的限流思想不是一回事！

同样是将请求放在一个容器中，漏桶算法和缓冲不是一个用途，切不可搞混，它们的区别如下：

• 漏桶算法中，存在桶中的请求会以恒定的速率被漏给后端业务服务器，而缓冲思想中，放在缓冲区域的请求只有等到后端服务器空闲下来了，才会被发出去。
• 漏桶算法中，存在桶中的请求是原本就应该被系统处理的，是系统对外界宣称的预期，不应该被丢失，而缓冲思想中放在缓冲区域的请求仅仅是对意外状况的尽量优化，并没有任何强制要求这些请求可以被处理。

漏桶算法和令牌桶算法在思想上非常接近，而实现方向恰好相反，它们有如下的相同和不同之处：

• 令牌桶算法以固定速率补充可以转发的请求数量（令牌），而漏桶算法以固定速率转发请求；
• 令牌桶算法限制数量的是预算数，漏桶算法限制数量的是实际请求数；
• 令牌桶算法在有爆发式增长的流量时可以一定程度上接受，漏桶算法也是，但当流量爆发时，令牌桶算法会使业务服务器直接承担这种流量，而漏桶算法的业务服务器感受到的是一样的速率变化。

因此，通过以上比较，我们会发现漏桶算法略优于令牌桶算法，因为漏桶算法对流量控制更平滑，而令牌桶算法在设置的数值范围内，会将流量波动忠实地转嫁到业务服务器头上。

漏桶算法在Nginx和分布式的限流系统例如Redis的限流功能中都有广泛应用，是目前业界最流行的算法之一。

# 时间窗口算法

查看更多