本文介绍一下四种常见的限流算法:

  • 计数器算法

  • 滑动窗口法

  • 令牌桶限流算法

  • 漏桶限流算法

参看:

1. 计数器算法

在指定周期内累加访问次数,当访问次数达到设定的阈值时,触发限流策略,当进入下一个时间周期时进行访问次数的清零。如图所示,我们要求3秒内的请求不要超过150次:

limit-flowl

但是,貌似看似很“完美”的流量统计方式其实存在一个非常严重的临界问题,即:如果第2到3秒内产生了150次请求,而第3到4秒内产生了150次请求,那么其实在第2秒到第4秒这两秒内,就已经发生了300次请求了,远远大于我们要求的3秒内的请求不要超过150次这个限制,如下图所示:

limit-flowl

2. 滑动窗口算法

滑动窗口为固定窗口的改良版,解决了固定窗口在窗口切换时会受到两倍于阈值数量的请求,滑动窗口在固定窗口的基础上,将一个窗口分为若干个等份的小窗口,每个小窗口对应不同的时间点,拥有独立的计数器,当请求的时间点大于当前窗口的最大时间点时,则将窗口向前平移一个小窗口(将第一个小窗口的数据舍弃,第二个小窗口变成第一个小窗口,当前请求放在最后一个小窗口),整个窗口的所有请求数相加不能大于阈值。其中,Sentinel就是采用滑动窗口算法来实现限流的。如图所示:

limit-flowl

1) 把3秒钟划分为3个小窗,每个小窗限制请求不能超过50秒。

2) 比如我们设置,3秒内不能超过150个请求,那么这个窗口就可以容纳3个小窗,并且随着时间推移,往前滑动。每次请求过来后,都要统计滑动窗口内所有小窗的请求总量。

3. 令牌桶限流算法(控制令牌生成速度,取的速度不控制)

令牌桶是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。对于每一个请求,都需要从令牌桶中获得一个令牌;如果没有获得令牌,则需要触发限流策略。系统会以恒定速度(r tokens/sec)往固定容量的令牌桶中放入令牌。令牌桶有固定的大小,如果令牌桶被填满,则会丢弃令牌。

会存在三种情况:

  • 【请求速度 大于 令牌生成速度】当令牌被取空后,会被限流

  • 【请求速度 等于 令牌生成速度】流量处于平稳状态

  • 【请求速度 小于 令牌生成速度】请求可被正常处理,桶满则丢弃令牌

如图所示:

limit-flowl

4. 漏桶限流算法(控制水滴流出速度,不控制水滴产生速度)

主要的作用:

  • 控制数据注入网络的速度。

  • 平滑网络上的突发流量。

漏桶限流算法的核心就是:不管上面的水流速度有多块,漏桶水滴的流出速度始终保持不变。消息中间件就采用的漏桶限流的思想。如图所示:

limit-flowl