了解高并发场景下的限流算法和解决方案

你的名字 2024-03-26 15:31 70阅读 0赞

> 想必大家在做项目的时候，或多或少的都遇到过一些高并发的场景，这里主要是和大家一起来探讨下有关高并发下的处理方案。

## 常见的限流算法 ##

1. 计数器

直接计数，简单暴力，举个例子：

比如限流设定为1小时内10次，那么每次收到请求就计数加一，并判断这一小时内计数是否大于上限10，没超过上限就返回成功，否则返回失败。

这个算法的**缺点**就是在时间临界点会有较大瞬间流量。

继续上面的例子，理想状态下，请求匀速进入，系统匀速处理请求：

![34a812c3f1fd44719e04a5fe88802d31.png][]

但实际情况中，请求往往不是匀速进入，假设第n小时59分59秒的时候突然进入10个请求，全部请求成功，到达下一个时间区间时刷新计数。那么第n+1小时刚开始又打进10个请求，等于瞬间进入20个请求，肯定不符合“1小时10次”的规则，这种现象叫做“突刺现象”。

![f0a25ef563702457bec5d920e0fcf1d9.png][]

为解决这个问题，计数器算法经过优化后，产生了**滑动窗口**算法：

我们将时间间隔均匀分隔，比如将一分钟分为6个10秒，每一个10秒内单独计数，总的数量限制为这6个10秒的总和，我们把这6个10秒成为“**窗口**”。

那么每过10秒，窗口往前滑动一步，数量限制变为新的6个10秒的总和，如图所示：

![b7d88220e9850942886a7875342d9d5b.png][]

那么如果在临界时，收到10个请求（图中灰色格子），在下一个时间段来临时，橙色部分又进入10个请求，但窗口内包含灰色部分，所以已经到达请求上线，不再接收新的请求。

这就是**滑动窗口**算法。

但是滑动窗口仍然有缺陷，为了保证匀速，我们要划分尽可能多的格子，而格子越多，每一个格子能够接收的请求数就越少，这样就限制了系统瞬间处理能力。

2. 漏桶

![414330cf9a500ea38ac6ef04f89e915c.png][]

漏桶算法其实也很简单，假设我们有一个固定容量的桶，流速（系统处理能力）固定，如果一段时间水龙头水流太大，水就溢出了（请求被抛弃了）。

用编程的语言来说，每次请求进来都放入一个先进先出的队列中，队列满了，则直接返回失败。另外有一个线程池固定间隔不断地从这个队列中拉取请求。

消息队列、jdk的线程池，都有类似的设计。

3. 令牌桶

令牌桶算法比漏桶算法稍显复杂。

首先，我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，token以一个固定的速率往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。

![2390d3069e8f2536f389faa5dadc804d.png][]

漏桶和令牌桶算法的区别：

漏桶的特点是**消费能力固定**，当请求量超出消费能力时，提供一定的冗余能力，把请求缓存下来匀速消费。优点是对下游保护更好。

令牌桶遇到激增流量会更从容，只要存在令牌，则可以一并消费掉。适合有突发特征的流量，如秒杀场景。

## 常见的限流方案 ##

#### 一、容器限流 ####

1. Tomcat

tomcat能够配置连接器的最大线程数属性，该属性`maxThreads`是Tomcat的最大线程数，当请求的并发大于`maxThreads`时，请求就会排队执行(**排队数设置：accept-count**)，这样就完成了限流的目的。

2. Nginx

Nginx 提供了两种限流手段：一是控制速率，二是控制并发连接数。

*  **控制速率**
    
    我们需要使用 `limit_req_zone`配置来限制单位时间内的请求数，即速率限制，示例配置如下：
    
        limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
    
    第一个参数：$binary\_remote\_addr 表示通过remote\_addr这个标识来做限制，“binary\_”的目的是缩写内存占用量，是限制同一客户端ip地址。
    
    第二个参数：zone=mylimit:10m表示生成一个大小为10M，名字为one的内存区域，用来存储访问的频次信息。
    
    第三个参数：rate=2r/s表示允许相同标识的客户端的访问频次，这里限制的是每秒2次，还可以有比如30r/m的。
 *  **并发连接数**
    
    利用 `limit_conn_zone` 和 `limit_conn` 两个指令即可控制并发数，示例配置如下
    
        limit_conn_zone $binary_remote_addr zone=perip:10m;
        limit_conn_zone $server_name zone=perserver:10m;
        server {   
            ...
            limit_conn perip 10; # 限制同一个客户端ip
            limit_conn perserver 100;
        }

**只有当 request header 被后端处理后，这个连接才进行计数**

## **分布式限流方案** ##

**首先我们将分布式限流分为两种情况：**

*  时间 限流基于某段时间范围或者某个时间点，也就是我们常说的“时间窗口”，比如对每分钟、每秒钟的时间窗口做限定
 *  资源 基于可用资源的限制，比如设定最大访问次数，或最高可用连接数

一、Tair通过incr方法实现简单窗口

实现方式是使用`incr()`自增方法来计数并与阈值进行大小比较。

二、Redis通过lua脚本实现简单窗口

与Tair实现方式类似，不过redis的`incr()`方法不能原子性的设置过期时间，所以需要使用lua脚本，在第一次调用返回1时，设置下过期时间为1秒。

local current
    current = redis.call("incr",KEYS[1])
    if tonumber(current) == 1 then 
        redis.call("expire",KEYS[1],1)
    end
    return current

三、Redis通过lua脚本实现令牌桶

实现思路是获取令牌后，用SET记录“请求时间”和“剩余token数量”。

每次请求令牌时，通过这两个参数和请求的时间、流速等参数进行计算，返回是否获取令牌成功。

**获取令牌lua脚本：**

local ratelimit_info = redis.pcall('HMGET',KEYS[1],'last_time','current_token')
    local last_time = ratelimit_info[1]
    local current_token = tonumber(ratelimit_info[2])
    local max_token = tonumber(ARGV[1])
    local token_rate = tonumber(ARGV[2])
    local current_time = tonumber(ARGV[3])
    local reverse_time = 1000/token_rate
    
    if current_token == nil then
      current_token = max_token
      last_time = current_time
    else
      local past_time = current_time-last_time
      local reverse_token = math.floor(past_time/reverse_time)
      current_token = current_token+reverse_token
      last_time = reverse_time*reverse_token+last_time
      if current_token>max_token then
        current_token = max_token
      end
    end
    
    local result = 0
    if(current_token>0) then
      result = 1
      current_token = current_token-1
    end 
    
    redis.call('HMSET',KEYS[1],'last_time',last_time,'current_token',current_token)
    redis.call('pexpire',KEYS[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))
    return result

**初始化令牌桶lua脚本：**

local result=1
    redis.pcall("HMSET",KEYS[1],"last_mill_second",ARGV[1],"curr_permits",ARGV[2],"max_burst",ARGV[3],"rate",ARGV[4])
    return result

四、网关层限流

在整个分布式系统中，起到一夫当关，万夫莫开的角色，非网关层莫属。服务网关，作为整个分布式链路中的第一道关卡，承接了所有用户来访请求.

五、限流组件

除了上面介绍的几种方式以外，目前也有一些开源组件提供了类似的功能，比如Sentinel就是一个不错的选择。Sentinel是阿里出品的开源组件，并且包含在了Spring Cloud Alibaba组件库中，可以为Cloud服务在下一个“微服务架构设计与落地”的大章节中，我们将详细介绍Sentinel在分布式限流中的应用

[34a812c3f1fd44719e04a5fe88802d31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/653569511b6d4f47a3911a60e264b9a6.png
[f0a25ef563702457bec5d920e0fcf1d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b15bf37e73174369a33bf83d17550da5.png
[b7d88220e9850942886a7875342d9d5b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/52030ee1b60d4b14b5d928c3e00deba6.png
[414330cf9a500ea38ac6ef04f89e915c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/cc4677c01b3d4826bc0574882534f965.png
[2390d3069e8f2536f389faa5dadc804d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/bc60a27e95c04b38a21f6916698a46d9.png