令牌桶 java_令牌桶算法及实现（三）

在第一篇、 第二篇文章中分别介绍了Guava令牌桶算法原理，固定速率生产token的SmothBursty限流器。但在实际环境中，如果想在初始阶段或隔一段时间系统再次被调用时，有一个预热的过程，即启动时生产令牌的速率慢一些，然后逐步加速，经过预热阶段后达到正常的生产速率，就像车辆的启动阶段，先从1档起步，逐渐加快，2档，3档一直到最快的6档。

RateLimiter.java提供了这种算法的实现。

public static RateLimiter create(

double permitsPerSecond,

long warmupPeriod,

TimeUnit unit)

它返回的实现类是SmoothRateLimiter.java类里的内嵌类SmoothWarmingUp。

SmoothWarmingUp的实现原理是怎样的呢，我们看下面的图。

图片发自简书App

X轴代表令牌桶存储的token数，Y轴代表限流的速率，单位是一个token的生成速率。XY代表了坐标轴围成的矩形面积，也就是(token生产速率)(token数量)，它有什么含义呢？是的，它代表了生产n个token的时长，这里使用了积分进行计算。右边的梯型面积表示了热身区的token生产总时长，左下边的长方形面积表示稳定期的token生产时长。我们用一个具体的例子来说明。

RateLimiter limiter = RateLimiter.create(2.0, 4000, MILLISECONDS, 3.0, stopwatch);

这里2.0代表QPS，4000代表warmup为4秒，3.0代表coldFactor即冷却因子，因此

stable interval=1/QPS=1/2=0.5秒=500毫秒，

coldinterval=coldFactor*stable interval=1500毫秒。

通过初始化函数设置令牌桶参数：

@Override

void doSetRate(double permitsPerSecond, double stableIntervalMicros) {

double oldMaxPermits = maxPermits;

double coldIntervalMicros = stableIntervalMicros * coldFactor;

thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;

maxPermits =

thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);

slope = (coldIntervalMicros – stableIntervalMicros) / (maxPermits – thresholdPermits);

if (oldMaxPermits == Double.POSITIVE_INFINITY) {

// if we don’t special-case this, we would get storedPermits == NaN, below

storedPermits = 0.0;

} else {

storedPermits =

(oldMaxPermits == 0.0)

? maxPermits // initial state is cold

: storedPermits * maxPermits / oldMaxPermits;

}

}

其中thresholdPermits设置为

thresholdPermits = 0.5 *warmupPeriodMicros /

stableIntervalMicros;

即0.5*4000/500=4，

maxPermits=thresholdPermits +

2.0 * warmupPeriodMicros /

(stableIntervalMicros +coldIntervalMicros);

maxPermits也就是右边梯型的下底，而warmupPeriodMicros是梯形的面积，所以maxPermits是利用梯形的面积公式导出的。而slope表示斜线的斜率，该字段用在计算热身区的token生产时间。初始状态令牌桶处于冷却态，也就是说初始时令牌桶的生产速率最慢，storedPermits等于maxpermits。

图片发自简书App

当我们从上述的limiter获取令牌时，

for (int i = 0; i < 8; i++) {

limiter.acquire(); // #1

}

输出的事件为：”R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50″(备注：参考com.google.common.util.concurrent.RateLimiterTest中的testWarmUp方法)。

通过上篇文章我们知道，R代表延迟时间，例如：R0.00代表无延迟获取一个令牌，R1.38代表等待1.38秒获取令牌。

i=0，第一次循环，通过第一篇文章我们知道ratelimiter是寅吃卯粮的思想，因为nextFreeTicketMicros初始值为0，当前时钟也为0，因此延迟为0，生产该token的时间用于下次消费时补偿，也就是右边第一个小梯形的面积。

@Override

long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {

double availablePermitsAboveThreshold = storedPermits – thresholdPermits;

long micros = 0;

// measuring the integral on the right part of the function (the climbing line)

if (availablePermitsAboveThreshold > 0.0) {

double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);

// TODO(cpovirk): Figure out a good name for this variable.

double length =

permitsToTime(availablePermitsAboveThreshold)

+ permitsToTime(availablePermitsAboveThreshold – permitsAboveThresholdToTake);

micros = (long) (permitsAboveThresholdToTake * length / 2.0);

permitsToTake -= permitsAboveThresholdToTake;

}

// measuring the integral on the left part of the function (the horizontal line)

micros += (long) (stableIntervalMicros * permitsToTake);

return micros;

}

private double permitsToTime(double permits) {

return stableIntervalMicros + permits * slope;

}

availablePermitsAboveThreshold 是储存的大于的threshold的token数量，第一次循环中，

availablePermitsAboveThreshold=maxpermits-threshold=4，

permitsAboveThresholdToTake是申请的token数量，为1，

private double permitsToTime(double permits)用来计算小梯形的上下底的高度，这里permitsToTime(availablePermitsAboveThreshold)获取了下底的高度，permitsToTime(availablePermitsAboveThreshold –

permitsAboveThresholdToTake)是上底的高度，所以

storedPermitsToWaitTime方法就是计算生产token的时间，在存储的token数量大于threshold，即availablePermitsAboveThreshold > 0.0时，计算右边小梯形的面积，这里计算的结果是1.38秒，反之，计算左边小长方形的面积。

i=1，2，3时，重复第二次循环的过程。延迟时间分别对应第2，3，4小梯形的面积，面积递减，分别是1.13，0.88，0.63。

i=4时，由于已经消费了4个token，总时长1.38, 1.13, 0.88, 0.63相加为4.02(由于存在舍入误差，其值不完全等于4)，已经过了warmup期，所以进入稳定期，左边的小矩形面积为micros += (long) (stableIntervalMicros * permitsToTake)，高为stableIntervalMicros，0.5秒，permitsToTake为1，即生产时长为0.5秒。

i=5，6，7，8重复上述过程。最后一次循环的生产时长需要后面的申请者偿还。

至此，warm up方式的ratelimiter限流器源码介绍完了，有问题可关注公众号，回复即可。

相关文章：

Guava令牌桶算法实现源码分析(一)

Guava令牌桶算法实现源码分析(二)