一、计数器算法
在指定周期内累加访问次数,当访问次数达到设定的阈值时,触发限流策略,当进入下一个时间周期时进行访问次数的清零。如图所示,我们要求3秒内的请求不要超过150次:
但是,貌似看似很“完美”的流量统计方式其实存在一个非常严重的临界问题,即:如果第2到3秒内产生了150
次请求,而第3到4秒内产生了150
次请求,那么其实在第2秒到第4秒这两秒内,就已经发生了300
次请求了,远远大于我们要求的3秒内的请求不要超过150次这个限制,如下图所示:
二、滑动窗口算法
滑动窗口为固定窗口的改良版,解决了固定窗口在窗口切换时会受到两倍于阈值数量的请求,滑动窗口在固定窗口的基础上,将一个窗口分为若干个等份的小窗口,每个小窗口对应不同的时间点,拥有独立的计数器,当请求的时间点大于当前窗口的最大时间点时,则将窗口向前平移一个小窗口(将第一个小窗口的数据舍弃,第二个小窗口变成第一个小窗口,当前请求放在最后一个小窗口),整个窗口的所有请求数相加不能大于阈值。其中,Sentinel就是采用滑动窗口算法来实现限流的。如图所示:
【1】 把3秒钟划分为3个小窗,每个小窗限制请求不能超过50秒。<br> 【2】 比如我们设置,3秒内不能超过150个请求,那么这个窗口就可以容纳3个小窗,并且随着时间推移,往前滑动。每次请求过来后,都要统计滑动窗口内所有小窗的请求总量。
三、令牌桶限流算法(控制令牌生成速度,取的速度不控制)
令牌桶是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。对于每一个请求,都需要从令牌桶中获得一个令牌;如果没有获得令牌,则需要触发限流策略。系统会以恒定速度(r tokens/sec)往固定容量的令牌桶中放入令牌。令牌桶有固定的大小,如果令牌桶被填满,则会丢弃令牌。
会存在三种情况:
【请求速度 大于 令牌生成速度】当令牌被取空后,会被限流<br> 【请求速度 等于 令牌生成速度】流量处于平稳状态<br> 【请求速度 小于 令牌生成速度】请求可被正常处理,桶满则丢弃令牌
如图所示:
四、漏桶限流算法(控制水滴流出速度,不控制水滴产生速度)
主要的作用:
【1】 控制数据注入网络的速度。<br> 【2】 平滑网络上的突发流量。
漏桶限流算法的核心就是:不管上面的水流速度有多块,漏桶水滴的流出速度始终保持不变。消息中间件就采用的漏桶限流的思想。如图所示:
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」
标签:令牌,窗口,请求,算法,限流,速度,四种 From: https://blog.51cto.com/u_15003301/7163135