分布式设计——限流算法

朱雀 2022-11-09 16:21 175阅读 0赞

### 文章目录 ###

*   *   *  （1）计数器算法
         *  （2）滑动窗口算法
         *  （3）令牌桶限流算法
         *  （4）漏桶限流算法

### （1）计数器算法 ###

计数器算法是一种比较简单的限流实现算法，在指定周期内累加访问次数，当访问次数达到设定的阈值时，触发限流策略,当进入下一个时间周期时进行访问次数的清零。  
实践：短信验证码，一分钟中不能重复发送  
不足：由于是固定周期区间，容易出现极值问题，比如并发请求都集中在前一分钟的后几秒后下一分钟的前几秒

### （2）滑动窗口算法 ###

为了解决计数器算法带来的临界问题，所以引入了滑动窗口算法。滑动窗口是一种流量控制技术，在TCP网络通信协议中，就采用了滑动窗口算法来解决网络拥塞的情况。  
简单来说，滑动窗口算法的原理是在固定窗口中分割出多个小时间窗口，分别在每个小时间窗口中记录访问次数，然后根据时间将窗口往前滑动并删除过期小时间窗口。最终只需要统计滑动窗口范围内的所有小时间窗口总的计数即可。  
参考：Sentinel就是采用滑动窗口算法来实现限流的

### （3）令牌桶限流算法 ###

令牌桶是网络流量整形(Traffic Shaping ）和速率限制(Rate Limiting)中最常使用的一种算法。对于每一个请求，都需要从令牌桶中获得一个令牌，如果没有获得令牌，则需要触发限流策略。  
基本流程：服务器端系统会定时生成一个Token,然后放入到一个容器中，如果达到容器最大值则停止，如果中间有客户端请求，他需要先向这个容器获取一个Token，如果有则说明当前请求可以正常通过，如果Token没有，则说明此时流量较大，容器内的Token已被其他并发的请求拿走，当前请求要么拒绝，要么进入队列等待，或者其他的处理方式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70 1]

由于令牌桶有固定的大小，当请求速度小于令牌生成速度时，令牌桶会被填满。  
所以令牌桶能够处理突发流量，也就是在短时间内新增的流量系统能够正常处理，这是令牌桶的特性。

### （4）漏桶限流算法 ###

漏桶限流算法的主要作用是控制数据注入网络的速度，平滑网络上的突发流量。  
漏桶限流算法的原理，在漏桶算法内部同样维护一个容器（比如队列），这个容器会以恒定速度出水，不管上面的水流速度多快，漏桶水滴的流出速度始终保持不变。实际上消息中间件就使用了漏桶限流的思想，不管生产者的请求量有多大,消息的处理能力取决于消费者。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70 2]

漏桶限流算法和令牌桶限流算法的实现原理相差不大，最大的区别是漏桶无法处理短时间内的突发流量，漏桶限流算法是一种恒定速度的限流算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70]: /images/20221023/d2a76ffe351e4a12a7920425e597f75b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/d8be914edbd745e29d829b1c8c2a0aea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/0d3d9e06a9b143c3ac6070a28987b51e.png