前言
相信大家对于谷歌RateLimiter一定并不陌生,在项目中应该也经常拿来进行限流,但是对于其实现原理并不一定能用熟于心,本文带大家从源码探究RateLimiter的设计与具体实现。
RateLimiter的组成
从源码可以看到,RateLimiter由stopwatch与mutexDoNotUseDirectly组成,先简单了解其分别的作用如下:
- stopwatch:计时器的作用.
- mutexDoNotUseDirectly:主要通过锁解决并发问题,本文暂不叙述此块,感兴趣的同学可以留言。
源码分析
上图展示了RateLimite的类图,可以看到其有一个子类SmoothRateLimiter,在往下看SmoothRateLimiter中有两个实现类SmoothBursty与SmoothWarmingUp,分别表示两种限流的不同场景,SmoothBursty是我们常见的关于限流算法中令牌桶算法的一个实现,通过固定速率生成令牌,当流量进入时,申请令牌,令牌充足时则直接获取成功,不充足时返回等待时间,而SmoothWarmingUp与SmoothBursty不同的是,SmoothWarmingUp在固定速度的基础上增加了预热流程,可以更好的应对突发流量。 另外,在初始化和小流量时更慢得进行流量得提供也符合实际的应用场景,本文主要讲述常用SmoothBursty的实现。
为了便于理解,我们从最简单限流程序开始一步一部理解RateLimiter的设计与实现。
1.RateLimiter创建
可以看到,RateLimiter创建分为两步,首先创建RateLimiter的实现类SmoothBursty对象,然后setRate设置限流器的控制速率。
首先我们看下SmoothBursty的实现,其首先创建了SleepingStopwatch类stopwatch对象。
stopwatch中初始elapsedNanos = 0 startTick = 765333275998400,其有一个sleepMicrosUninterruptibly方法,释义如下
- elapsedNanos:经过的时间,单位为纳秒
- startTick:开始时间
- sleepMicrosUninterruptibly(long micros):实现了不可中断的不可中断的sleep(用于令牌不足时限流等待)
紧接着其传入stopwatch与maxBurstSeconds创建一个SmoothBursty对象,SmoothBursty继承至SmoothRateLimiter,其额外定义了一个maxBurstSeconds变量,SmoothRateLimiter继承至RateLimiter,是RateLimiter抽象类的具体实现,其中有四个变量我们同maxBurstSeconds一起进行解释:
- SmoothRateLimiter.storedPermits:实际预存的许可(即令牌)
- SmoothRateLimiter.maxPermits:最大的许可数(即令牌)
- SmoothRateLimiter.stableIntervalMicros:每产生一个令牌需要消耗的微秒数
- SmoothRateLimiter.nextFreeTicketMicros:初始值为0L,表示下一个令牌可用的时间戳
- SmoothBursty.maxBurstSeconds:初始值为1.0D,表示桶中最多可以保存多少秒存入的令牌数
从上图可以看到RateLimiter创建后,开始setRate传入的permitsPerSecond设置限流速率
- permitsPerSecond:令牌数/每秒钟,即我们期望限制的qps.
传入的nowMicros当前值为1030409545,nextFreeTicketMicros初始为0,此步骤计算赋值了当前存储的令牌数量storedPermits与
nextFreeTicketMicros = nowMicros(1030409545);
然后根据传入的permitsPerSecond设置了产生一枚令牌需要的时间:stableIntervalMicros。
接着起开始按比例更新当前存储的令牌数量,可以看到,初始令牌数量为0时,其首次创建时存储的令牌数量即为0.0, maxPermits = maxBurstSeconds * permitsPerSecond = 1.0
至此RateLimiter的初始创建结束,下面我们从最简单也是日常使用最多的方法acquire()看看其如何通过上述各个变量控制限流。为了方便理解,下图展示了,当前RateLimiter的组成。
2.RateLimiter.acquire()控制限流
还是从源码入手,可以看到acquire()实际调用的方法acquire(1),即当前需要获取1块令牌,其实现分为3个步骤
- 计算需要等待的时间microsToWait
- stopwatch.sleepMicrosUninterruptibly(microsToWait)进行阻塞等待。
- 返回等待时间
从第1步开始看,传入令牌数与当前时间nowMicros = 2322440641 由于当前令牌数量足够计算出momentAvailable = 0,即无需阻塞等待,
且将nextFreeTicketMicro等于当前时间nowMicros后,则可以推测出下次计算时nowMicros必然大于nextFreeTicketMicros,此时无需等待。
这是因为nowMicros > nextFreeTicketMicros 时,此间产生令牌数量 + 当前持有的令牌数量 一定大于 最大的令牌数量,而最大的令牌数量大于请求的令牌数量,所以请求无需限流阻塞等待。
而当并发请求数变多,导致某一时刻持有的令牌数量不足时,则会发生限流阻塞等待,为了方便分析,我们通过限流设置为1qps,通过单词请求1000000000个令牌数模拟高并发场景。
可以看到初次请求时,nowMicros > nextFreeTicketMicros满足,此时令牌数量为1,而超过的令牌数量为refreshPermits = 99999999,通过计算,需要99999999000000的间隔时间才能产生这么多令牌,而此时注意了,返回值为上一次(这里初始请求的上一次即初始值为0)的nextFreeTicketMicros = 0,然后将本次请求的nextFreeTicketMicros增加99999999000000,而最终计算出的等待时间为Math.max(momentAvailable - nowMicros, 0L) = 0.实际并没有产生等待,而在下一次请求时,如下图可以看到此时nowMicros < nextFreeTicketMicros, 此时说明还未到令牌释放的时间,需要等待Math.max(momentAvailable - nowMicros, 0L) = 0, 可以看到本次请求等待的时间,其实时上次请求时超出的令牌数需要等待的时间,继续往下执行你就会发现,RateLimiter每次请求的超支的令牌等待时间,都是在下一次执行时进行等待。
结语
SmoothBrusty的设计遵循令牌桶的思路,SmoothBursty以指定的速率生成许可,当一个请求申请获取许可时,如果当前许可数满足申请数量,则消耗掉许可,直接返回无需等待。当当前许可数小于申请数量时,会计算多余部分许可需要等待生成的时间,更新下一次许可可发放的时间,但值得注意的是尽管已经消耗掉所有的许可并且不够总请求数量,本次请求也并不会阻塞等待,而是将阻塞等待放到下一个请求,说明此处可以支持突发流量。这里的设计其实还是蛮巧妙的。比如一些突发流量场景,当前瞬发的高流量请求可快速返回,无需阻塞,而后续请求可能相隔很久,则请求时不会等待,从而提高系统整体的响应速率,当然这在某些场景可能会导致qps超标,存在造成系统崩溃风险,这里我们主要了解其设计原理,放才能在合适场景合理使用以及规避风险。