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

什么是服务限流

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

欢迎关注个人公众号【好好学技术】交流学习

常用限流框架

常见的限流方式有：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个请求的突发流量
• 限流处理 因为生产令牌的速率是固定的，所以请求的处理也是限定的

和漏桶算法比较

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

总结

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