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

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

高并发系统的三把利器：缓存、限流、降级，利用此3种技术方案即可保系统运行无忧。由于限流是系统的首道关口，所以本文以限流为主题，普及限流算法的基础知识。
为什么要限流
限流即限制流量，通过流量控制来保证系统接收到的请求量在正常范围内。由于任何系统的吞吐量都有上限，所以必须设置合理的限定值，以避免流量洪峰将整个系统打垮。
假如一个系统可以承载的网络带宽是1G，如果流量大于1G就会导致带宽打满，影响整个服务。在现实生活中，限流场景也随处可见：例如银行的叫号系统、餐厅的排队系统，如今的疫情，政府也是全力排除隐患，保证医疗系统健康运行。
限流的目的只有一个：保护系统，保证系统在可控的负载下平稳运行。

触发限流的条件：

1. 用户增长过快
2. 热点事件（突发流量）
3. 竞争对象爬虫
4. 恶意的刷单
5. 攻击
常见限流算法
常见的限流算法共3种：

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

2. 漏桶算法

3. 令牌桶算法

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

0 1

计数器算法

计数器算法是在单位时间内统计用户请求数，一旦请求数量超出设定的阀值，即触发限流策略。计数器算法根据单位时间的计算方式又分为 固定窗口算法
及 滑动窗口算法
。
固定窗口算法指每个单位时间相对隔离，一个单位区间的请求量统计跟其他单位区间的请求量统计完全独立。当一个单位时间过期，自动进入下一个时间阶段重新进行计数，固定窗口计数器算法逻辑图如下：

固定窗口计数器算法相对简单，但会存在临界问题（何为临界问题？临界问题即为用户流量并不会像我们所期望的匀速请求，而是可能在某个时间点集中爆发）。如下图所示：在第一个单位时间内的前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

0 2

漏桶算法
漏桶算法业务逻辑也相对简单，如下图所示：水滴（用户请求）优先注入到桶中（定长队列、先进先出队列），桶（队列）盛满后自动抛弃（限流）多余的水（请求），另外桶以匀速的方式漏出水滴（处理请求）。
由此可见，漏桶算法以绝对平均的速度处理用户请求，无论用户请求有多大，最终消费用户请求的速率是固定不变的。在真实的业务场景中，漏桶算法可以解决请求毛刺问题（不平均问题），但面对合法的突发流量，漏桶算法就有点捉襟见肘。

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

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);

0 3

令牌桶算法
令牌桶算法与漏桶算法有相似之处，都包含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限流策略。