高并发之限流算法

女爷i 2022-11-30 05:48 95阅读 0赞

# 高并发之限流算法 #

## 前言 ##

在我们的实际的生产当中存在这样的业务场景：短时间有大量的请求涌入造成了系统的崩溃。针对这种问题我们会采用一种服务降级的方式来保证核心服务可以正常运行。本博客着重讲一下通过限流降级的方式来解决峰值流量问题。

## 正文 ##

## 限流算法 ##

**一般来说服务降级分为两种：**

*  **故障降级**：当发生网络故障或者`RPC`服务返回异常，这种情况我们通常采用关联`fallback`方法，为客户端设置兜底数据，从而避免造成服务依赖的“雪崩”现象。
 *  **限流降级**：无论系统运行在什么样的服务器，它都会有一定的流量带宽极限，我们可以采用设置请求阈值的方式来避免过多的请求涌入从而造成系统的崩溃。

不同的`RPC`框架都有着不同的配置故障降级的方式，故而我们这里注重讲解一下限流降级这种方式。  
我们常见的限流算法有：**漏桶算法、令牌桶算法和滑动窗口算法**。

## 漏桶算法 ##

[nginx的limit\_conn\_zone模块][nginx_limit_conn_zone]底层就是漏桶算法，它的特点是：

*  它可以简单的比作就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。
 *  它能够强行限制数据的传输速率，但是由于流速是恒定的，对突发特性的流量是无法处理的 。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]

## 令牌桶算法 ##

能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。  
令牌桶算法是最常用的限流算法，通常配合`redis`来实现， 具体参考我的博客：[redis令牌桶限流][redis]。

**在某种极端情况下存在请求量两倍进入**：  
令牌桶比如以 1个/1秒 速率进入时，请求又是以 2个/1秒进入，这个时候令牌桶并没有满，请求数就是令牌数的两倍，如果 超过平均速率的突发流量持续的时间过长，并且令牌桶的令牌没有得到释放，那么存在请求数是令牌桶大小的两倍。

**令牌桶算法的组件**

*  **计数器**：实时地统计接口的调用速率，记录单位时间内调用了多少次。
 *  **限流器**：当令牌桶中令牌已经无法放入时，使用限流器进行限流。
 *  **阈值配置**：用于配置时间窗口，平均速率以及突发情况下允许的最大速率
 *  **阈值更新**：通过一个参数来实时调整对阈值的配置
 *  **令牌桶**：通过一个工具类根据配置的时间窗口、平均速率、突发最大速率来模拟向桶中放置令牌的操作，如果溢出了，则触发限流器操作。

**它的工作原理可以简单概括为**：

1.  所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；
2.  根据限流大小，设置按照一定的速率往桶里添加令牌；
3.  桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝；
4.  请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除；
5.  令牌桶有最低限额，当桶中的令牌达到最低限额的时候，请求处理完之后将不会删除令牌，以此保证足够的限流；

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

## 滑动窗口算法 ##

我们熟知的[Sentinel高可用流量控制框架][Sentinel]采用的就是滑动窗口的方式进行流量控制。

*  它将时间窗口划分为更小的时间片段，每过一个时间片段，我们的时间窗口就会往右滑动一格，每个时间片段都有独立的计数器。
 *  我们在计算整个时间窗口内的请求总数时会累加所有的时间片段内的计数器。
 *  时间窗口划分的越细，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

简单举个例子：我们设置一个窗口有两个方案

*  设置 A ：10s 100条请求
 *  设置 B ：1s 10条请求

相对而言设置B的系统相对而言更加稳定。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 2]

**总得来说：**

*  **令牌桶算法**：能够保证自身系统的流量均匀，令牌桶的填满时间，是由桶的自身容量、令牌漏出速率（桶下面的水管）、超过平均速率的突发流量持续的时间三个方面共同决定的。
 *  **漏桶算法**：保证被调用系统（目标系统）流量均匀，适合请求到达频率稳定、需要严格控制处理速率的场景，而令牌桶适合允许突发请求的情况。

实际的生产中通常采用 `漏桶算法+令牌桶算法`的方式来对网络流量进行高效地控制。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 3]

[nginx_limit_conn_zone]: https://www.cnblogs.com/hukey/p/10498544.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/68b91465e671491ebbaec3450504de2e.png
[redis]: https://blog.csdn.net/weixin_40990818/article/details/106974256
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/edebacaf44214646841d00f469a9a85d.png
[Sentinel]: https://www.oschina.net/p/sentinel
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/18c6ba43ec5440eca164b93d96aa679a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/0b9da841525948248c101eb1d7492cc4.png