令牌桶算法及实现（三）

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

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

public static RateLimiter create(
              double permitsPerSecond, 
              long warmupPeriod, 
              TimeUnit unit)

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

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

令牌桶算法及实现（三）
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。

令牌桶算法及实现（三）

当我们从上述的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令牌桶算法实现源码分析（二）