常见的限流算法

蔚落 2022-09-10 12:13 182阅读 0赞

### 文章目录 ###

*  限流算法
 *   *  1、计数器
     *  2、漏桶算法
     *  3、令牌桶算法
     *  4、漏桶算法和令牌桶算法的区别

# 限流算法 #

## 1、计数器 ##

采用计数器是一种比较简单的限流算法，一般我们会限制一秒钟能够通过的请求数。比如限流QPS为100，算法的实现思路就是从第一个请求进来开始计时，在接下来的1秒内没来一个请求就把计数加1，如果累加的数字达到了100，后续的请求就会被全部拒绝。等到1秒结束后，把计数恢复成0，重新开始计数。如果在单位时间1秒内的前10毫秒处理了100个请求，那么后面的990毫秒会拒绝所有的请求，我们把这种现象称为“突刺现象”。

## 2、漏桶算法 ##

漏桶算法的思路很简单，一个固定容量的漏桶按照常量固定速率流出水滴。如果桶是空的，流入的水滴就会溢出(被丢弃)，而漏桶容量是不变的。漏桶算法的大致原理如下所示。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yir5Zui562Jc2h55ZOl5Y-R6IKy_size_12_color_FFFFFF_t_70_g_se_x_16]

## 3、令牌桶算法 ##

令牌桶算法是比较常见的限流算法之一，可以使用它进行接口限流，其大致原理图如下所示。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yir5Zui562Jc2h55ZOl5Y-R6IKy_size_17_color_FFFFFF_t_70_g_se_x_16]  
  令牌按固定的速率被放入令牌桶中，例如tokens/s。桶中最多存放b个令牌(Token),当桶装满时，新添加的令牌会被丢弃或拒绝。当请求到达时，将从桶中删除1个令牌。令牌桶中的令牌不仅可以被移除，还可以往里添加，所以为了保证接口随时有数据通过，必须不停的往桶里加令牌。由此可见，**往桶里加令牌的速度决定了数据通过接口的速度**。我们通过控制往令牌桶里加令牌的速度来控制接口的流量。

## 4、漏桶算法和令牌桶算法的区别 ##

*  漏桶算法是按照常量固定速率流出请求的，流入请求速率任意，当流入的请求数累积到漏桶容量时，新流入的请求会被拒绝。
 *  令牌桶算法是按照固定速率往桶中添加令牌的，请求是否被处理需要看桶中的令牌是否足够，当令牌数减为零时，拒绝新的请求。
 *  令牌桶算法允许突发情况，只要有令牌就可以处理，允许一定程度的突发容量。
 *  漏桶算法限制的是常量流出速率，从而使突发流入速率平滑。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yir5Zui562Jc2h55ZOl5Y-R6IKy_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/43e992482c1646f8a9e4186cff63581d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yir5Zui562Jc2h55ZOl5Y-R6IKy_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8f465e35e23a4480a3e4b9b989bbdf6a.png