Guava RateLimiter是一个谷歌提供的限流工具，可以有效限定单个JVM实例上某个接口的流量。
RateLimiter抽象类提供限流的所有功能，它的实现类只有SmoothRateLimiter。而SmoothRateLimiter的具体策略又由它的两个内部子类来实现。
SmoothBursty：兼容突发流量的令牌桶实现，也就是经典的令牌桶算法。
SmoothWarmingUp：带预热过程的令牌桶实现，即在桶较满时产生令牌的速度较慢，随着令牌的消耗慢慢增长到恒定速率。如下所示，x轴为令牌数，y轴为延迟，从右向左看的梯形区域就是令牌消耗的预热过程。
public static RateLimiter create(double permitsPerSecond) {return create(permitsPerSecond, RateLimiter.SleepingStopwatch.createFromSystemTimer());}static RateLimiter create(double permitsPerSecond, RateLimiter.SleepingStopwatch stopwatch) {RateLimiter rateLimiter = new SmoothBursty(stopwatch,maxBurstSeconds: 1.0D);rateLimiter.setRate(permitsPerSecond);return rateLimiter;}public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {Preconditions.checkArgument(b: warmupPeriod >= 0L,errorMessageTemplate:"warmupPeriod must not be negative：%s", warmupPeriod);return create(permitsPerSecond,warmupPeriod, unit,coldFactor: 3.0D，RateLimiter.SleepingStopwatch.createFormSystemTimer();}static RateLimiter create(double permitsPerSecond,long warmupPeriod, TimeUnit unit, double coldFactor, SleepingStopwatch stopwatch) {RateLimiter rateLimiter = new SmoothRateLimiter.SmoothWarmingUp(stopwatch,warmupPeriod, unit, coldFactor);rateLimiter.setRate(permitsPerSecond);return rateLimiter;}
由上看出，通过RateLimiter的重载create()方法，返回不同的实现类。
SmoothBursty
以SmoothBursty为例。首先看SmoothRateLimiter四个参数的含义：
abstract class SmoothRateLimiter extends RateLimiter {double storedPermits;double maxPermits;double stableIntervalMicros;private long nextFreeTicketMicros;}
storedPermits：当前桶里有的令牌数量。
maxPermits：桶装满时的令牌数量，storedPermits不会比它大。
stableIntervalMicros：产生令牌的频率（时间间隔），单位为微秒。举个栗子，如果我们想限制系统的QPS为10，亦即每秒有10个令牌放入桶中，那么stableIntervalMicros的值就是100000。
nextFreeTicketMicros：下一个令牌可用的时间戳，也就是下一个请求能够被处理的时间戳，单位为微秒。该值会随着当前请求获得令牌而增大（因为时间是自然流动的）。若当前请求的令牌数超出可用令牌数，这个时间就被推后（需要时间产生新的令牌）。当然，如果有一段时间没有请求进入的话，它就会保持在上次请求的过去时间戳。
从后往前看获取令牌的过程：首先，RateLimiter提供了acquire()的默认实现，acquire()是阻塞式获得令牌的一种方法，其逻辑为：首先由reserve方法计算出需要获取指定数量领牌的时间，再sleep该时间。可以看出它的核心是reserve()方法。
public double acquire() {return this.acquire(permits:1);}public double acquire(intpermits) {long microsToWait = this.reserve(permits);this.stopwatch.sleepMicrosUninterruptibly(microsToWait);return 1.0D * (double)microsToWait / (double)TimeUnit.SECONDS.toMicros(duration:1L);}final long reserve(intpermits) {checkPermits(permits);synchronized(this.mutex()){return this.reserveAndGetWaitLength(permits,this.stopwatch.readMicros());}}
可以看出，reserve方法是通过同步加锁的方式来获取令牌的。其中加锁的对象是mutex()返回的一个单例对象：
private Object mutex() {Object mutex = this.mutexDoNotUseDirectly;if (mutex == null) {synchronized(this) {mutex = this.mutexDoNotUseDirectly;if (mutex == null) {this.mutexDoNotUseDirectly = mutex = new Object();}}}return mutex;}
回到reserve()方法，继续向上溯源：
final long reserveAndGetWaitLength(intpermits, long nowMicros) {long momentAvailable = this.reserveEarliestAvailable(permits,nowMicros);return Math.max(momentAvailable - nowMicros, OL);}abstract long queryEarliestAvailable(long var1);abstract long reserveEarliestAvailable(int var1, long var2);
reserveAndGetWaitLength方法的作用是预定令牌并且返回需要等待的时间。acquire和tryAcquire的底层调用的都是该方法。
最终，可以看出，RateLimiter交给其SmoothRateLimiter类实现的是reserveEarliestAvailable方法。
SmoothRateLimiter仍然是一个抽象类，它提供了部分方法的默认实现，比如setRate和reserveEarliestAvailable。从方法名中我们就可以看出来，reserveEarliestAvailable的功能是预定令牌。
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {this.resync(nowMicros);long returnValue = this.nextFreeTicketMicros;double storedPermitsToSpend = Math.min((double)requiredPermits,this.storedPermits);double freshPermits = (double)requiredPermits - storedPermitsToSpend;long waitMicros = this.storedPermitsToWaitTime(this.storedPermits,storedPermitsToSpend) + (long)(freshPermits * this.stableIntervalMicros);this.nextFreeTicketMicros = LongMath.saturatedAdd(this.nextFreeTicketMicros,waitMicros);this.storedPermits -= storedPermitsToSpend;return returnValue;}
其逻辑为：
-
首先resync方法产生令牌；
-
然后将需要的令牌的数量和桶中已有的令牌数量比较，作差，即得出还需要多少令牌，生产这些令牌还需多少时间（waitMicors）,这里计算的等待时间包括两部分，一部分是获取已存在令牌时需要消耗的时间，另一部分是生成预获取令牌数需要消耗的时间。SmoothBursty和SmoothWarmingUp对于计算已获取令牌需要消耗的时间存在着不同的实现方式。对于稳定限流器来说，它是可以应对突增请求的，因此在获取已存在令牌时是不应该消耗时间的，因此SmoothBursty类中的storedPermitsToWaitTime方法直接return了0。对于预热限流器来说，它有一个预热的阶段。如果像稳定限流器一样，获取已存在的令牌不需要消耗时间，那么他就没有了预热效果。因此它在获取桶中已存在的令牌时，是需要计算消耗时间的。这样既保证下一次请求需要等待一段时间再通过，也可以在这段时间里再生成一些令牌，进而保证他的预热效果。
-
然后根据所需的时间，将nextFreeTicketMicros向后推延。即起到了“预定”的效果。同时预扣减令牌库存。
resync方法详解
voidresync(long nowMicros) {if (nowMicros > nextFreeTicketMicros) {double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();storedPermits = min(maxPermits, storedPermits + newPermits);nextFreeTicketMicros = nowMicros;}}// SmoothBursty.coolDownIntervalMicros()@OverridedoublecoolDownIntervalMicros() {return stableIntervalMicros;}
生成令牌的逻辑为：
首先判断当前时间是否超过了下一个令牌时间戳，即可以处理请求的时间戳。
如果没有超过令牌时间戳，则无需更新令牌桶状况，此时桶内情况可以直接参与预定令牌的时间计算，得到的需要等待的时间。
如果当前时间已经超过了该时间戳，则会计算出从时间戳到当前时间共产生了多少令牌，更新桶中的情况和时间戳。结合上文，此时的时间戳还需要加上未来成产所需令牌的时间，才会是下一次可处理请求的时间。
可见，RateLimiter的令牌是延迟（lazy）生成的，也就是说每次受理当前请求时，如果系统已经空闲了一定时间，才会计算上次请求到当前时间应该产生多少个令牌，而不是使用单独的任务来定期产生令牌——因为定时器无法保证较高的精度，并且性能不佳。当然，如果令牌已经“超支”，当前就不需要再更新令牌了。
extra: semaphore信号量也有着类似于令牌桶的概念，可以对比学习。
......
文章作者 | 张德轩
原文始发于微信公众号（EBCloud）：Guava的RateLimiter源码探究
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论