通俗易懂 限流算法原理剖析

618临近，你的系统还在裸奔吗？

高并发系统的三把利器：缓存、限流、降级，利用此3种技术方案即可保系统运行无忧。由于限流是系统的首道关口，所以本文以限流为主题，普及限流算法的基础知识。

为什么要限流

限流即限制流量，通过流量控制来保证系统接收到的请求量在正常范围内。由于任何系统的吞吐量都有上限，所以必须设置合理的限定值，以避免流量洪峰将整个系统打垮。

假如一个系统可以承载的网络带宽是1G，如果流量大于1G就会导致带宽打满，影响整个服务。在现实生活中，限流场景也随处可见：例如银行的叫号系统、餐厅的排队系统，如今的疫情，政府也是全力排除隐患，保证医疗系统健康运行。

限流的目的只有一个：保护系统，保证系统在可控的负载下平稳运行。

触发限流的条件：

1. 用户增长过快

2. 热点事件（突发流量）

3. 竞争对象爬虫

4. 恶意的刷单

5. 攻击

常见限流算法

常见的限流算法共3种：

1. 计数器算法（固定窗口限流+滑动窗口限流）

2. 漏桶算法

3. 令牌桶算法

每种算法均有其应用场景，下面章节将逐步讲解各个限流算法的原理以及优缺点。

01计数器算法

计数器算法是在单位时间内统计用户请求数，一旦请求数量超出设定的阈值，即触发限流策略。计数器算法根据单位时间的计算方式又分为固定窗口算法及滑动窗口算法。

固定窗口算法指每个单位时间相对隔离，一个单位区间的请求量统计跟其他单位区间的请求量统计完全独立。当一个单位时间过期，自动进入下一个时间阶段重新进行计数，固定窗口计数器算法逻辑图如下：

固定窗口计数器算法相对简单，但会存在临界问题（何为临界问题？临界问题即为用户流量并不会像我们所期望的匀速请求，而是可能在某个时间点集中爆发）。如下图所示：在第一个单位时间内的前800ms只有一次请求，后200ms（800ms-1s范围内）内承载999次请求，而第二个单位时间内前200ms承载1001-2000次共1000个请求。这样系统在400ms（800ms到1200ms时间范围内）内共承载了1999次用户请求，此访问量已经远远超出系统所能承载的1000次请求（系统最大QPS），从而给系统带来灾难性后果。

固定窗口计数器算法实现代码（伪代码）如下：

int unitTime = 1s //设置单位时间为1s
int limitCount = 1000 //设置单位时间只能1000次请求
string limitKey = 'limitkey'; //单位时间限流状态key


if（!has（limitKey））{
    //初始化单位时间限流状态，并设定期有效期（有效期为一个单位时间）
    //参考redis的set命令
    set（limitKey,0,unitTime）
}


//原子递增请求量，并返回当前单位时间已有的请求数
int counter = incr（limitKey,1）


if counter>limitCount then
    //超出设置的限流规则，直接返回503（也可自定义返回内容）
    return 503 
else
    continue;//继续执行业务逻辑   
end

为了解决固定窗口算法的临界问题，我们将其升级为滑动窗口算法。滑动窗口算法实现借鉴滑动窗口协议，将单位时间继续细化为更小粒度的时间网格，每当用户请求，时间网格随之推移，计数器的的统计时间区间也随之变动。滑动窗口算法的单位时间不再是彼此独立，而是步步递进，彼此重叠。这也是滑动窗口算法跟固定窗口算法最大的区别。

（滑动窗口协议主要用于网络数据传输时的流量控制，避免发送网络堵塞 具体可参考https://baike.baidu.com/item/%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E5%8D%8F%E8%AE%AE）

如下图所示，滑动窗口算法将计数器算法（固定窗口算法）的单位时间进一步细化，例如将1秒分为10个时间网格，每个网格占用100ms的时间。第一个单位时间为0ms-1000ms（以毫秒为单位）、第二个单位时间为100ms-1100ms、第三个单位时间为200ms-1200ms，以此类推。每个单位时间的请求总量都需小于设定的最大请求量。

由于滑动窗口算法每次都需要统计单位时间的请求量，开销远大于固定窗口算法，所以在真实的业务环境中需要慎重使用滑动窗口算法。

滑动窗口计数器算法实现代码（伪代码）如下：

int unitTime = 1000ms //设置单位时间为1s（1000ms）
int limitCount = 1000 //设置单位时间只能1000次请求
string listKey = 'limitkey'; //单位时间限流状态key


//获取当前毫秒数 demo：1589510627001
int curMilliseconds = nowMilliseconds（）;
//计算单位时间的起始时间
int startMilliseconds = curMilliseconds-unitTime*1000 //获取单位时间的起始时间


//获取当前往前推1s 之内的所有请求量（这一步及耗性能）
//参考redis的ZCOUNT命令
int counter = ZCOUNT（listKey,startMilliseconds,curMilliseconds）


if counter>limitCount
    //超出设置的限流规则，直接返回503（也可自定义返回内容）
    return 503 
else
    ZADD（listKey,curMilliseconds,唯一标识）
    continue;//继续执行业务逻辑   
end

02漏桶算法

漏桶算法业务逻辑也相对简单，如下图所示：水滴（用户请求）优先注入到桶中（定长队列、先进先出队列），桶（队列）盛满后自动抛弃（限流）多余的水（请求），另外桶以匀速的方式漏出水滴（处理请求）。

由此可见，漏桶算法以绝对平均的速度处理用户请求，无论用户请求有多大，最终消费用户请求的速率是固定不变的。在真实的业务场景中，漏桶算法可以解决请求毛刺问题（不平均问题），但面对合法的突发流量，漏桶算法就有点捉襟见肘。

漏桶算法的业务逻辑如下：

1、 创建定长队列（demo：长度固定为1000的队列）

2、 用户请求优先入队列（如果队列已满，直接抛弃请求）（入队列速率不限定）

3、 事件调度器以固定速率（demo：1000r/s）消费队列数据，并释放队列资源

漏桶算法实现代码（伪代码）如下：

//代码实现(伪代码)
local rate = 1ms //设置生产速率为1个/ms
local bucketSize = 1000 //漏桶大小 设置可容纳1000个水滴
//初始化漏桶
local bucketQueue = new BucketQueue(bucketSize)
//用户请求
local userRequest = new UserRequest();
local res = bucketQuest.push(userRequest)
if res ==false then
    //目前漏桶已满，无法将请求放入漏桶(队列),直接返回503(也可自定义）
    return 503
else
    //等待事件调度处理
end
//队列消费（每1ms处理一个请求(一滴水)）
setTimeout(function () {
    local userRequest = bucketQuest.lpop()
    //执行业务逻辑
}, rate);

03令牌桶算法

令牌桶算法与漏桶算法有相似之处，都包含2部分业务逻辑。漏桶算法的2部分业务逻辑为：漏桶队列+事件调度器；令牌桶算法的2部分业务逻辑为：令牌生产+令牌消费。漏桶算法是以固定的速率处理用户请求（消费），而令牌桶算法则以固定的速率生产令牌（生产）。

如下图所示：令牌工厂以固定的速率生产令牌并注入到令牌桶中，令牌桶满时会自动抛弃多余的令牌。当有用户请求，优先从令牌桶获取有效令牌（可以理解为打开大门的钥匙），只有获取到令牌的请求才会继续向下执行业务逻辑，否则直接拒绝请求（限流）。其中需要重点关注的是：1、一个令牌不可被2个请求获取（需要加锁，并置为不可用状态）；2、在请求处理完毕后需销毁令牌。

令牌桶算法实现代码（伪代码）如下：

//代码实现(伪代码)
local tokenProducerRate = 1ms //设置生产速率为1个/ms
local bucketSize = 1000 //令牌桶大小 设置可容纳1000个令牌
local bucketKey = "bucketKey" //令牌桶名称
bucketKey.setSize(bucketSize) //设置令牌桶大小
local token = bucketKey.getValidToken() //获取有效令牌
if token ~= false then
    token.lock() //加锁，需要原子性
else
    //超出设置的限流规则，直接返回503(也可自定义)
    return 503
end
//继续执行业务逻辑
token.destroy()  //令牌销毁
//令牌工厂代码（每1ms向令牌桶推送一个令牌）
setTimeout(function () {
    local token = new Token();
    local result = bucketKey.push(token)
    if result == false then
        //向令牌桶已满，push命令失败
    else
        //向令牌桶未满，push成功
    end
}, tokenProducerRate);

限流算法比较

每种算法都有其可取的优点，在真实的业务环境需要结合实际情况确定使用哪种限流算法，也可对各类算法聚合使用，满足更多的业务场景。

注：本文以基础理论为主讲解各类算法的原理以及实现方案，后期将结合业务场景分别讲解nginx的限流策略以及google的guava限流策略。