常见限流算法

举报
u5c0fu80d6 发表于 2020/09/21 10:43:40 2020/09/21
【摘要】 保护高并发系统的稳定性的三把利器:缓存、降级和限流。 而降级、限流的本质都是基于限流算法,常见的限流算法有如下4种:计数器固定窗口算法、计数器滑动窗口算法、漏桶算法和令牌桶算法。

引言

         保护高并发系统的稳定性的三把利器:缓存、降级和限流。

l  缓存:提升系统的访问速度,增大系统处理容量;

l  降级:在系统过载时提供有损服务,通过减少非核心业务,降低业务质量等措施降低系统负载;

l  限流:在系统过载时主动丢弃部分业务请求。

         而降级、限流的本质都是基于限流算法,常见的限流算法有如下4种。

 


计数器固定窗口算法

计数器固定窗口算法是最简单的限流算法,实现方式也比较简单。就是通过维护一个单位时间内的计数值,每当一个请求通过时,就将计数值加1,当计数值超过预先设定的阈值时,就拒绝单位时间内的其他请求。如果单位时间已经结束,则将计数器清零,开启下一轮的计数。

固定窗口.png

代码实现:https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/CounterRateLimit.java

问题:这个算法很简单,但是却有十分致命的问题,那就是临界问题,还会有突刺现象导致拒绝大部分请求。

例如:第一秒的最后200ms和第二秒的最初200ms,极有可能超过1000的阈值,但并不会被限流。


计数器滑动窗口算法

计算器滑动窗口算法就是为解决计数器固定窗口临界问题而诞生的。简单来说,把1秒切割成2段,每段独立计数,通过滑动窗口内计数器累加统计结果限流。

代码实现:https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/SlidingWindowRateLimit.java

问题滑动窗口算法就是固定窗口算法的变种,但突刺现象仍然无法解决。不难发现,切割的片段越多,统计越精确,但若要做到平滑限流,就需要漏洞算法、令牌桶算法。


漏桶算法

漏桶算法以一个常量限制了出口流量速率,因此漏桶算法可以平滑突发的流量。其中漏桶作为流量容器我们可以看做一个FIFO的队列,当入口流量速率大于出口流量速率时,因为流量容器是有限的,当超出流量容器大小时,超出的流量会被丢弃。

算法实现:可以准备一个队列,用来保存请求,另外通过一个线程池(ScheduledExecutorService)来定期从队列中获取请求并执行,可以一次性获取多个并发执行。

代码实现:https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/LeakyBucketRateLimit.java

特点:

1)         入口流量无限制

2)         出口流量固定不变,即解决平滑限流问题

3)         桶容量固定,即限流阈值

问题:不过因为漏桶算法限制了流出速率是一个固定常量值,所以漏桶算法不支持出现突发流出流量。但是在实际情况下,流量往往是突发的。


令牌桶算法

令牌桶算法是漏桶算法的改进版,可以支持突发流量。不过与漏桶算法不同的是,令牌桶算法的漏桶中存放的是令牌而不是流量。

那么令牌桶算法是怎么突发流量的呢?

最开始,令牌桶是空的,我们以恒定速率往令牌桶里加入令牌,令牌桶被装满时,多余的令牌会被丢弃。当请求到来时,会先尝试从令牌桶获取令牌(相当于从令牌桶移除一个令牌),获取成功则请求被放行,获取失败则阻塞活拒绝请求。

算法实现:可以准备一个队列,用来保存令牌,另外通过一个线程池定期生成令牌放到队列中,每来一个请求,就从队列中获取一个令牌,并继续执行。

代码实现:https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/TokenBucketRateLimit.java

特点:

1)         入口流量固定,即解决平滑限流问题

2)         出口流量在不固定,即解决突发流量问题

3)         桶容量固定,即限流阈值

令牌桶算法限制的是平均流量,因此其允许突发流量(只要令牌桶中有令牌,就不会被限流)




总结:

算法

确定参数

空间复杂度

时间复杂度

限制突发流量

平滑限流

分布式环境下实现难度

固定窗口

计数周期T

周期内最大访问数N

O(1)

(记录周期内访问次数及周期开始时间)

O(1)

滑动窗口

计数周期T

周期内最大访问数N

O(N)

(记录每个小周期中的访问数量)

O(N)

相对实现。取决于各自切分数量。

漏桶

漏桶流出速度r、漏桶容量N

O(1)

(记录当前漏桶中容量)

O(N)

令牌桶

令牌产生速度r、令牌桶容量N

O(1)

(记录当前令牌桶中令牌数)

O(N)

 


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。