四种常见服务限流算法解析

什么是服务限流

限定固定请求数量访问服务端，保护服务接口

常用限流框架

常见的限流方式有：nginx 限流、guava 限流、sentinel、Redis 等实现方式。他们的本质算法都是基于 漏桶、令牌桶、滑动窗口来实现的。

常见的经典限流有计时器限流、滑动窗口限流、漏桶限流、令牌桶限流四种。

计数器限流算法

定义

1. 定义一个单位时间(如 1 秒钟)的阈值，每收到一次请求，增加一次计数。

2. 判断 请求总数 <= 当前单位时间内的阈值，则执行正常流程

3. 如果请求总数 > 当前单位时间内的阈值， 则触发限流处理

4. 进入到下一个单位时间，计数清零，开始新一轮的计数

缺点

计数器限流算法相对简单那，但是它的弊端还是很明显的，也就是临界点问题。假设 1 秒钟 100 的阈值，如果 0-0.9 秒都没有请求，最后 0.9 秒到 1 秒收到 100 个请求，下一秒 1 到 1.1 秒又收到 100 个请求，那么服务器所承受的压力就非常大了。(如果是 0.99 秒到 1 秒,0.999 秒到 1 秒呢？tps 暴增)

滑动窗口限流算法

定义

1. 将单位时间划分为多个时间区间

2. 每个时间区间内，每有一次请求计数就加 1

3. 单位时间内的所有时间区间的请求计数之和，就是整个滑动窗口的请求总数

4. 滑动窗口每经过一个时间区间，则抛弃最左区间，并加入最右区间

5. 当滑动窗口的请求总数超过阈值，则新的请求就会被限流

弊端

滑动窗口和计数器算法都没有办法很好的处理瞬时流量的情况，假设限流是 10 万，那么 0.1 秒内收到 10 万个请求，就有可能击穿我们的服务。

总结

滑动窗口算法将时间窗口划分为多个小区间，按照时间滑动。相比之下，计数器算法就类似于固定窗口。滑动窗口算法可以避免临界值带来的流量翻倍的情况，但是时间区间的精度越高，算法所需的空间容量就越大，缺点就是无法处理瞬时流量。

漏桶算法

定义

漏桶算法经常用来处理流量整形或速率限制时常用的一种算法。主要用来控制数据注入到网络的速率，平滑网络上的突发流量。通过漏桶算法，我们可以将瞬时流量整形成为稳定的流量。

实现原理

1. 每个请求到达时，都会先经过一个队列，就像水龙头里面的水先流到桶里面。

2. 当进水速率（请求总数） <= 流出的速率（限流数量），请求可以正常执行

3. 当进水速率（请求总数） > 流出的速率（限流数量）,桶里的水会慢慢变满，当桶里面的水满了之后，会以固定速率向外流出。

4. 当桶满时，后面的水会溢出，也就是后面的请求被限流了。

缺点

使用漏桶算法后，请求有可能在漏桶里面等待处理，这样的话就会导致整体的处理速率比较慢。

令牌桶算法

定义

令牌桶算法经常用来处理流量整形或速率限制时常用的一种算法。相对漏桶算法而言，令牌桶允许突发数据的发送。

实现原理

• 生产令牌

假设我们设置的发送速率为 r,那么每隔 1/r 秒，就生产一个令牌放入桶中。

• 令牌上限

假设令牌桶的上限为 N，如果令牌桶已经满了，那么放进来的令牌就会被丢弃

• 消耗令牌

每当收到一个请求，就消耗掉 1 个令牌

• 突发流量

因为桶的上限为 N，那么最多就允许 N 个请求的突发流量

• 限流处理

因为生产令牌的速率是固定的，所以请求的处理也是限定的

和漏桶算法比较

漏桶算法限制的是流出速率，用来平滑处理突发流入速率。令牌桶算法限制的是流入速率，允许一定程度的突发流量。

总结

计数器相对简单，存在临界值流量缺陷，不推荐使用。滑动窗口将时间窗口划分为多个小区间，按照时间滑动，虽然解决了计数器算法的缺点，但是无法很好的应对突发流量。漏桶算法和令牌桶算法弥补了滑动窗口的缺点，漏桶算法限制了流出速率，令牌桶算法限制了流入速率。具体要使用哪种算法，就需要大家根据实际情况来定了。

作者：越走越远的风

链接：https://juejin.cn/post/7219095104040075301

来源：稀土掘金