常用限流算法与Guava RateLimiter源码解析

在分布式系统中,应对高并发访问时,缓存、限流、降级是保护系统正常运行的常用方法。当请求量突发暴涨时,如果不加以限制访问,则可能导致整个系统崩溃,服务不可用。同时有一些业务场景,比如短信验证码,或者其它第三方API调用,也需要提供必要的访问限制支持。还有一些资源消耗过大的请求,比如数据导出等(参考 记一次线上Java服务CPU 100%处理过程 ),也有限制访问频率的需求。

常见的限流算法有令牌桶算法,漏桶算法,与计数器算法。本文主要对三个算法的基本原理及Google Guava包中令牌桶算法的实现RateLimiter进行介绍,下一篇文章介绍最近写的一个以RateLimiter为参考的分布式限流实现及计数器限流实现。

令牌桶算法

令牌桶算法的原理就是以一个恒定的速度往桶里放入令牌,每一个请求的处理都需要从桶里先获取一个令牌,当桶里没有令牌时,则请求不会被处理,要么排队等待,要么降级处理,要么直接拒绝服务。当桶里令牌满时,新添加的令牌会被丢弃或拒绝。

令牌桶算法的处理示意图如下(图片来自网络)

token-bucket

令牌桶算法主要是可以控制请求的平均处理速率,它允许预消费,即可以提前消费令牌,以应对突发请求,但是后面的请求需要为预消费买单(等待更长的时间),以满足请求处理的平均速率是一定的。

漏桶算法

漏桶算法的原理是水(请求)先进入漏桶中,漏桶以一定的速度出水(处理请求),当水流入速度大于流出速度导致水在桶内逐渐堆积直到桶满时,水会溢出(请求被拒绝)。

漏桶算法的处理示意图如下(图片来自网络)

leaky-bucket

漏桶算法主要是控制请求的处理速率,平滑网络上的突发流量,请求可以以任意速度进入漏桶中,但请求的处理则以恒定的速度进行。

计数器算法

计数器算法是限流算法中最简单的一种算法,限制在一个时间窗口内,至多处理多少个请求。比如每分钟最多处理10个请求,则从第一个请求进来的时间为起点,60s的时间窗口内只允许最多处理10个请求。下一个时间窗口又以前一时间窗口过后第一个请求进来的时间为起点。常见的比如一分钟内只能获取一次短信验证码的功能可以通过计数器算法来实现。

Guava RateLimiter解析

Guava是Google开源的一个工具包,其中的RateLimiter是实现了令牌桶算法的一个限流工具类。在pom.xml中添加guava依赖,即可使用RateLimiter

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>29.0-jre</version> </dependency>

如下测试代码示例了RateLimiter的用法,

public static void main(String[] args) { RateLimiter rateLimiter = RateLimiter.create(1); //创建一个每秒产生一个令牌的令牌桶 for(int i=1;i<=5;i++) { double waitTime = rateLimiter.acquire(i); //一次获取i个令牌 System.out.println("acquire:" + i + " waitTime:" + waitTime); } }

运行后,输出如下,

acquire:1 waitTime:0.0 acquire:2 waitTime:0.997729 acquire:3 waitTime:1.998076 acquire:4 waitTime:3.000303 acquire:5 waitTime:4.000223

第一次获取一个令牌时,等待0s立即可获取到(这里之所以不需要等待是因为令牌桶的预消费特性),第二次获取两个令牌,等待时间1s,这个1s就是前面获取一个令牌时因为预消费没有等待延到这次来等待的时间,这次获取两个又是预消费,所以下一次获取(取3个时)就要等待这次预消费需要的2s了,依此类推。可见预消费不需要等待的时间都由下一次来买单,以保障一定的平均处理速率(上例为1s一次)。

RateLimiter有两种实现:

SmoothBursty: 令牌的生成速度恒定。使用 RateLimiter.create(double permitsPerSecond) 创建的是 SmoothBursty 实例。

SmoothWarmingUp:令牌的生成速度持续提升,直到达到一个稳定的值。WarmingUp,顾名思义就是有一个热身的过程。使用 RateLimiter.create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) 时创建就是 SmoothWarmingUp 实例,其中 warmupPeriod 就是热身达到稳定速度的时间。

类结构如下

ratelimiter-struct

关键属性及方法解析(以 SmoothBursty 为例)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzjpdf.html