限流算法探秘

在资源有限的情况下，遇到突发流量（如双十一）或系统 RT 剧增，为了保证系统不被拖垮引起更大规模的雪崩，必须进行限流。也就是说限流是系统的自我保护。限流本质上是根据系统处理能力，限制单位时间内处理的请求数量。

滑动窗口

这里的窗口是一个时间窗口，比如把一分钟划分为 6 个窗口，则每个窗口的时间范围是 10 秒。通过移动窗口，统计窗口期内流量，可以实现窗口期的限流。但是滑动窗口存在精度问题，在精度范围内统计到的窗口期流量可能在限流范围内，但进一步细分就会看到仍有突增流量。

滑动窗口时间范围越小，就越平滑，限流的效果越精确，但时间细分的粒度受到客观限制。

漏桶算法

漏桶算法，英文名 Leaky Bucket，是网络中流量整形（Traffic Shaping）和速率限制（Rate Limiting）常用的一种算法。漏桶算法调控了访问流量，使得突发流量可以被整形、去毛刺，为系统提供稳定的访问流量。如果漏桶溢出，请求就会被丢弃。

桶以固定的速率流出流量，无论水龙头进入的流量是多少，都不改变流出速率。上图中，水龙头处存在突发流量，一共进入 30Mb 数据，分布不均匀，对系统有冲击。经过漏桶算法处理，漏桶以 3 Mbps 速率持续流出数据，为系统做了很好的缓冲。

漏桶算法中，如果桶未满，可以持续接收流量；如果桶已满，流量溢出，后续的流量将无法入桶，会被丢弃。漏桶算法限制的是流出速率，无论流入是多少，都能保证后续系统的请求是平稳的。后续系统感知的流量相对固定，但可能在系统仍有能力处理更多流量的时候，也会被漏桶限制住。

令牌桶算法

令牌桶算法，英文名 token bucket，也是网络中流量整形或速率限制常用的一种算法。令牌桶算法以一个恒定的速率向桶里放入令牌，如果有新的请求进来希望进行处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。令牌桶算法限制的是流入速率，允许一定规模的突增流量，最大速率受限于桶的容量和令牌生成速率。可以支持一定程度的突发流量，更适合具有突发特性的流量。

令牌桶算法的简单描述如下：

• 每隔 1/r 秒向桶中增加一个 token；
• 桶最多只能存放 b 个 token。如果放置 token 时桶已经满了，丢弃这个 token；
• 当一个包含 n 个字节的数据包进来的时候，

• 如果桶中有足够的 token，将从桶中移除 n 个 token，然后把这个数据包发送出去；
• 如果桶中没有足够的 token，不会移除任何 token，返回拒绝服务；

自适应限流阈值

使用自适应阈值可以动态调整限流，通过运行中不断试探，最终可以在系统处理能力和限流之间找到一个动态平衡。既能最大限度利用系统处理能力，又能确保系统稳定性。目前比较简单的自定义算法是参考 TCP 拥塞算法的斜率算法。斜率算法设置一个基准值，可以结合应用的 Load、CPU 使用率、总体平均 RT、入口 QPS 和并发线程数等几个维度的监控指标评估系统负载，负载高了降低限流阈值，负载低了提高限流阈值。

目前比较简单的方案是使用平均 rt 计算斜率，公式为

gradient =（RTTnoload / RTTactual）

newLimit = currentLimit×gradient + queueSize

其中，RTTnoload 表示无负载时的 rt，RTTactual 表示当前实际 rt。gradient 小于 1 表示负载偏高，大于 1 表示负载偏低。经过一段时间的试探，就能把系统流量控制在合理范围。

分布式限流

现代网络服务通常都有多台机器，需要对集群做限流。目前使用比较广泛的方案是 Redis 。滑动窗口可以使用 Redis 记录时间和访问次数；Redis-Cell 是一个实现漏桶算法的分布式限流扩展模块，使用非常方便。