限流算法详解

迷南。 2023-10-01 21:31 11阅读 0赞

## 一、什么是限流 ##

限流是指在高并发、大流量请求的情况下，限制新的流量对系统的访问，从而保证系统服务的安全性。

限流可以应对：热点业务带来的突发请求；调用方bug导致的突发请求；恶意攻击请求

## 二、为什么要分布式限流 ##

当应用为单点应用时，只要应用进行了限流，那么应用所依赖的各种服务也得到了保护。但线上的业务出于各种原因考虑，多是分布式系统，单点的限流仅能保护自身节点，但无法保护应用依赖的各种服务，并且在进行节点扩容缩容时也无法整个服务的请求限制。而如果实现了分布式限流，那么就可以方便的控制整个服务集群的请求限制，，且由于整个集群的请求数量受到了限制，因此服务依赖的各种资源也得到了限流的保护。

## 三、常见的限流算法 ##

### 固定窗口计数器法 ###

该算法规定我们单位时间处理的请求数量。比如规定一个接口一分钟是能访问十次的话，使用固定窗口计数算法可以这样实现：给定一个变量counter来记录处理的请求数量，当一分钟内处理一个请求后counter+1，一分钟内如果counter大于100，后续所有的请求都会被拒绝，等到一分钟结束后，counter将回归成0，重新计数。（只要过了一个周期counter就会重新计数)

这种限流算法无法保证限流速率，因而无法保证突然激增的流量。比如我们限制一个接口一分钟只能访问10次，前半分钟一个请求没有，后半分钟接收了10个请求

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16][]

### 滑动窗口计数器算法 ###

该算法是上一个固定窗口计数算法的升级版，滑动窗口计数器算法相比于固定窗口计数器算法的优化在于：他把时间以一定比例分成片。例如限流每分钟处理60个请求，我们可以把1分钟分成60个窗口。每个一秒移动一次，每个窗口一秒只能处理不大于60(请求书) / 60(窗口数)的请求，如果当前窗口的计数总和超过了限制数量的话就不在处理其他请求。

很显然：滑动窗口格子划分的越多，滑动窗口滚动越平滑，限流的统计就会越精确。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

### 漏桶算法 ###

我们可以把发送请求的动作比作注入到水桶中，处理请求的过程可以比喻为漏桶漏水。我们往桶中以任意速率流入水，以一定速率流出水。当水超过桶容量就丢弃，因为桶容量是不变的，保证了整体的速率。实现这个算法也很简单，准备一个队列保存请求，然后定期从队列中拿请求来实行

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

### 令牌桶算法 ###

和漏桶算法一样，主角还是桶。不过现在桶里装的是令牌，请求在被处理之前需要拿到一个令牌，请求处理完毕之后将这个令牌丢弃（删除）。根据限流大小，按一定速率往桶里添加令牌

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

## 四、各算法比较 ##

<table style="width:500px;"> 
 <tbody> 
 <tr> 
 <td>算法</td> 
 <td>确定参数 </td> 
 <td>空间复杂度 </td> 
 <td>时间复杂度 </td> 
 <td>限制突发流 </td> 
 <td>平滑限流 </td> 
 <td>分布式环境下实现难度 </td> 
 </tr> 
 <tr> 
 <td>固定窗口</td> 
 <td>计数周期T、周期内最大访问数N</td> 
 <td>低O(1)（记录周期内访问次数及周期开始时间）</td> 
 <td>低O(1)</td> 
 <td>否</td> 
 <td>否</td> 
 <td>低</td> 
 </tr> 
 <tr> 
 <td>滑动窗口</td> 
 <td>计数周期T、周期内最大访问数N</td> 
 <td>高O(N)（记录每个周期中的访问数量）</td> 
 <td>中O(N)</td> 
 <td>是</td> 
 <td>滑动窗口格子分配越多，滑动窗口滚动越平滑</td> 
 <td>中</td> 
 </tr> 
 <tr> 
 <td>漏桶算法</td> 
 <td>漏桶流出速度r，漏桶容量N</td> 
 <td>低O(1)（记录当前漏桶中的容量）</td> 
 <td>高O(N)</td> 
 <td>是</td> 
 <td>是</td> 
 <td>高</td> 
 </tr> 
 <tr> 
 <td>令牌桶算法</td> 
 <td>漏桶流出速度r，漏桶容量N</td> 
 <td>低O(1)（记录当前桶中的令牌数）</td> 
 <td>高O(N)</td> 
 <td>是</td> 
 <td>是</td> 
 <td>高</td> 
 </tr> 
 </tbody> 
</table>

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8d07632d54154e8e9deb8b5bebd3f367.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b142df5ca8754a46b391b91dd603d743.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/d4884c0e60ac40c384dcda83e97ba428.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/830d06e61dda43f7b81356a3854d4322.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16