用户您好!请先登录!

常用的限流算法有哪些?

常用的限流算法有哪些?

为什么要做限流呢?举一个生活中的例子,大家早上上班都要挤地铁吧,地铁站在早高峰的时候经常要限制客流,为什么呢?有人会觉得这是人为添堵。真是这样吗?如果不执行客流控制,大家想想会是什么场景呢?站台到处都挤满了乘客,就算你使出洪荒之力也不一定能顺利上车,且非常容易引发肢体碰撞,造成冲突。有了客流控制之后,地铁站才能变得秩序井然,大家才能安全上地铁。

一个系统的处理能力是有上限的,当服务请求量超过处理能力,通常会引起排队,造成响应时间迅速提升。如果对服务占用的资源量没有约束,还可能因为系统资源占用过多而宕机。因此,为了保证系统在遭遇突发流量时,能够正常运行,需要为你的服务加上限流。

常见的限流算法有:漏桶、令牌桶、滑动窗口计数。

分类

按照计数范围,可以分为:单机限流、全局限流。单机限流,一般是为了应对突发流量,而全局限流,通常是为了给有限资源进行流量配额。

按照计数周期,可以分为:QPS、并发(连接数)。

按照阈值设定方式的不同,可以分为:固定阈值、动态阈值。

漏桶算法

下面这张图,是漏桶的示意图。漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大时,会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。漏桶算法(Leaky Bucket)是网络世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)时经常使用的一种算法,它的主要目的是控制数据注入到网络的速率,平滑网络上的突发流量。

常用的限流算法有哪些?

漏桶算法原理

漏桶算法可以使用 Redis 队列来实现,生产者发送消息前先检查队列长度是否超过阈值,超过阈值则丢弃消息,否则发送消息到 Redis 队列中;消费者以固定速率从 Redis 队列中取消息。Redis 队列在这里起到了一个缓冲池的作用,起到削峰填谷、流量整形的作用。

令牌桶算法

对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。桶里能够存放令牌的最高数量,就是允许的突发传输量。

常用的限流算法有哪些?

令牌桶算法原理

Guava 中的限流工具 RateLimiter,其原理就是令牌桶算法。

滑动窗口计数法

计数法是限流算法里最容易理解的一种,该方法统计最近一段时间的请求量,如果超过一定的阈值,就开始限流。在 TCP 网络协议中,也用到了滑动窗口来限制数据传输速率。

常用的限流算法有哪些?

滑动窗口计数原理

滑动窗口计数有两个关键的因素:窗口时长、滚动时间间隔。滚动时间间隔一般等于上图中的一个桶 bucket,窗口时长除以滚动时间间隔,就是一个窗口所包含的 bucket 数目。

滑动窗口计数算法的实现,可以查看这篇文章:降级熔断框架 Hystrix 源码解析:滑动窗口统计。

动态限流

一般情况下的限流,都需要我们手动设定限流阈值,不仅繁琐,而且容易因系统的发布升级而过时。为此,我们考虑根据系统负载来动态决定是否限流,动态计算限流阈值。可以参考的系统负载参数有:Load、CPU、接口响应时间等。

常用的限流算法有哪些?

动态限流

乞力马扎罗的鱼
乞力马扎罗的鱼

不积跬步,无以至千里

要发表评论,您必须先登录