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

骑猪看日落 2023-09-25 22:21 22阅读 0赞

## 什么是服务限流 ##

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

## 常用限流框架 ##

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

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

## 计数器限流算法 ##

### 定义 ###

1.  定义一个单位时间(如1秒钟)的阈值，每收到一次请求，增加一次计数。
2.  判断 请求总数 <= 当前单位时间内的阈值，则执行正常流程
3.  如果请求总数 > 当前单位时间内的阈值， 则触发限流处理
4.  进入到下一个单位时间，计数清零，开始新一轮的计数

![format_png][]

### 缺点 ###

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

![format_png 1][]

## 滑动窗口限流算法 ##

### 定义 ###

1.  将单位时间划分为多个时间区间
2.  每个时间区间内，每有一次请求计数就加1
3.  单位时间内的所有时间区间的请求计数之和，就是整个滑动窗口的请求总数
4.  滑动窗口每经过一个时间区间，则抛弃最左区间，并加入最右区间
5.  当滑动窗口的请求总数超过阈值，则新的请求就会被限流

![format_png 2][]

### 弊端 ###

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

### 总结 ###

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

## 漏桶算法 ##

### 定义 ###

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

![format_png 3][]

### 实现原理 ###

1.  每个请求到达时，都会先经过一个队列，就像水龙头里面的水先流到桶里面。
2.  当进水速率（请求总数） <= 流出的速率（限流数量），请求可以正常执行
3.  当进水速率（请求总数） > 流出的速率（限流数量）,桶里的水会慢慢变满，当桶里面的水满了之后，会以固定速率向外流出。
4.  当桶满时，后面的水会溢出，也就是后面的请求被限流了。

### 缺点 ###

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

## 令牌桶算法 ##

### 定义 ###

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

![format_png 4][]

### 实现原理 ###

*  生产令牌  
    假设我们设置的发送速率为r,那么每隔1/r秒，就生产一个令牌放入桶中。
 *  令牌上限  
    假设令牌桶的上限为N，如果令牌桶已经满了，那么放进来的令牌就会被丢弃
 *  消耗令牌  
    每当收到一个请求，就消耗掉1个令牌
 *  突发流量  
    因为桶的上限为N，那么最多就允许N个请求的突发流量
 *  限流处理 因为生产令牌的速率是固定的，所以请求的处理也是限定的

### 和漏桶算法比较 ###

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

## 总结 ##

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

[format_png]: https://img-blog.csdnimg.cn/img_convert/8e55ff55e1acbe93e3081cc35fdcb5a8.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/b32c588a24430d600d08f928b8c9ff99.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/5b65e991197df85085a30c24a03bd12d.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/525cdca02357191265d35eabef5c2c36.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/79039b3a7d1aff420639967a558ae146.webp?x-oss-process=image/format,png