源码分析RateLimiter SmoothWarmingUp 实现原理(文末附流程图)

上一篇详细介绍了 SmoothBursty 的实现原理，本文将介绍带有预热机制的限速器实现原理。

本篇最大的亮点并不是简单对SmoothWarmingUp上的注释进行翻译，而是进行总结与提炼。

1、类图

从上文也详细介绍了 RateLimiter 相关的类图，本文就不详细介绍。

2、SmoothWarmingUp 创建流程

创建 SmoothWarmingUp 限速器的入口为 RateLimiter 的 create 方法，其代码如下：

RateLimiter#create

public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {  // @1
    checkArgument(warmupPeriod >= 0, "warmupPeriod must not be negative: %s", warmupPeriod);
    return create(
        SleepingStopwatch.createFromSystemTimer(), permitsPerSecond, warmupPeriod, unit, 3.0);
}

代码@1：首先先来看一下参数列表：

• double permitsPerSecond
  每秒发放许可数量，即所谓的QPS。
  
• long warmupPeriod
  设置预热时间。
  
• TimeUnit unit
  warmupPeriod 的时间单位。
  

代码@2：调用内部的重载方法创建 SmoothWarmingUp 。

RateLimiter#create

static RateLimiter create( SleepingStopwatch stopwatch, double permitsPerSecond, long warmupPeriod, TimeUnit unit, double coldFactor) {
    RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit, coldFactor);  // @1
    rateLimiter.setRate(permitsPerSecond); // @2
    return rateLimiter;
}

创建 SmoothWarmingUp 两个主要步骤分别是调用其构造方法首先创建 SmoothWarmingUp 实例，然后调用其 setRate 方法进行初始化速率。这里先突出 coldFactor，默认为 3.0，该属性的作用将在下文详细介绍。

我们先来重点探讨一下 setRate 方法的实现。最终会调用其父类 SmoothRateLimiter 的doSetRate 方法。

SmoothRateLimiter#doSetRate

final void doSetRate(double permitsPerSecond, long nowMicros) {
    resync(nowMicros);   // @1 
    double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;   
    this.stableIntervalMicros = stableIntervalMicros;   // @2
    doSetRate(permitsPerSecond, stableIntervalMicros);  // @3
}

代码@1：基于当前时间重置 SmoothRateLimiter 内部的 storedPermits(已存储的许可数量) 与 nextFreeTicketMicros(下一次可以免费获取许可的时间) 值，所谓的免费指的是无需等待就可以获取设定速率的许可，该方法对理解限流许可的产生非常关键，稍后详细介绍。

代码@2：根据 QPS 算出一个稳定的获取1个许可的时间。以一秒发放5个许可，即限速为5QPS，那发放一个许可的世界间隔为 200ms，stableIntervalMicros 变量是以微秒为单位。

代码@4：调用 SmoothRateLimiter 的抽象方法 doSetRate 设置速率，这里会调用 SmoothWarmingUp 的 doSetRate 方法。

在介绍 SmoothWarmingUp 的 doSetRate 方法之前，我们先来看一下 resync 方法的实现。

SmoothRateLimiter#resync

void resync(long nowMicros) {
    if (nowMicros > nextFreeTicketMicros) {  // @1 
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();  // @2
      storedPermits = min(maxPermits, storedPermits + newPermits);    // @3
      nextFreeTicketMicros = nowMicros;   // @4
    }
}

代码@1：如果当前已启动时间大于 nextFreeTicketMicros（下一次可以免费获取许可的时间），则需要重新计算许可，即又可以向许可池中添加许可。

代码@2：根据当前时间可增加的许可数量，由于 SmoothWarmingUp 实现了预热机制，平均生成一个许可的时间并不是固定不变的。具体由 coolDownIntervalMicros 方法实现，稍候详细介绍。

代码@3：计算当前可用的许可，将新增的这些许可添加到许可池，但不会超过其最大值。

代码@4：更新下一次可增加计算许可的时间。

SmoothWarmingUp#coolDownIntervalMicros

double coolDownIntervalMicros() {
    return warmupPeriodMicros / maxPermits;
}

这个方法的实现其实简单，用生成这些许可的总时间除以现在已经生成的许可数，即可得到当前时间点平均一个许可的生成时间。

接下来重点探讨 SmoothWarmingUp 的 doSetRate 方法。

为了方便理解 SmoothWarmingUp doSetRate 方法，我根据 SmoothWarmingUp 类的注释，结合代码，给出如下示例图：

首先我们先来根据 SmoothWarmingUp 的相关注释来理解一下上述这张图的几个要点。

• 图中有两个阴影面积，一个用 stable，另外一个warm up period。在预热算法中，这两个阴影面积的关系与冷却因子相关。
  
• 冷却因子 coldFactor 表示的含义为 coldIntervalMicros 与  stableIntervalMicros 的比值。
  
• warm up period 阴影面积 与 stable 阴影面积的比值等于 (coldIntervalMicros -  stableIntervalMicros ) / stableIntervalMicros ，例如 SmoothWarmingUp 固定的冷却因子为3，那么 coldIntervalMicros 与 stableIntervalMicros 的比值为 3，那  (coldIntervalMicros -  stableIntervalMicros ) / stableIntervalMicros 则为 2。
  
• 在预热算法中与数学中的积分相关（笔者对这方面的数学知识一窍不通），故这里只展示结论，而不做推导，阴影 WARM UP PERIOD 的面积等于 warmupPeriod,那阴影stable的面积等于 warmupPeriod/2。
  
• 存在如下等式 warmupPeriod/2 = thresholdPermits * stableIntervalMicros (长方形的面积)
  
• 同样存在如下等式 warmupPeriod = 0.5 * (stableInterval + coldInterval) * (maxPermits - thresholdPermits) （梯形面积，(上底 + 下底 * 高 / 2) ）
  

有了上述基本知识，我们再来看一下代码。

SmoothWarmingUp#doSetRate

void doSetRate(double permitsPerSecond, double stableIntervalMicros) { 
    double oldMaxPermits = maxPermits;
    double coldIntervalMicros = stableIntervalMicros * coldFactor;                // @1
    thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;    // @2
    maxPermits =
          thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);   // @3
    slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);  // @4
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        storedPermits = 0.0;
    } else {
        storedPermits =
            (oldMaxPermits == 0.0)
                ? maxPermits // initial state is cold
                : storedPermits * maxPermits / oldMaxPermits;    // @5
    }
}

代码@1：根据冷却因子(coldFactor)来计算冷却间隔(单位为微秒)，等于冷却因子与 stableIntervalMicros 的乘积。从这里我们可以得出如下几个基本的概念。冷却因子 coldFactor 为 冷却间隔与稳定间隔的比例。

代码@2：通过  warmupPeriod/2 = thresholdPermits * stableIntervalMicros 等式，求出 thresholdPermits 的值。

代码@3：根据  warmupPeriod = 0.5 * (stableInterval + coldInterval) * (maxPermits - thresholdPermits)  表示可求出 maxPermits 的数量。

代码@4：斜率，表示的是从 stableIntervalMicros 到 coldIntervalMicros 这段时间，许可数量从 thresholdPermits 变为 maxPermits 的增长速率。

代码@5：根据 maxPermits 更新当前存储的许可，即当前剩余可消耗的许可数量。

3、SmoothWarmingUp acquire 流程

首先 acquire 的定义在其父类，这里是典型的模板模式，由其父类定义基本流程，由具体的子类实现其特定功能。RateLimiter 中的 acquire 方法如下：

public double acquire(int permits) {
    long microsToWait = reserve(permits);    // @1
    stopwatch.sleepMicrosUninterruptibly(microsToWait);   // @2
    return 1.0 * microsToWait / SECONDS.toMicros(1L);   // @3
}

代码@1：根据当前剩余的许可与本次申请的许可来判断本次申请需要等待的时长，如果返回0则表示无需等待。

代码@2：如果需要等待的时间不为0，表示触发限速，睡眠指定时间后唤醒。

代码@3：返回本次申请等待的时长。

接下来重点介绍 reserve 方法的实现原理。

RateLimiter#reserve

inal long reserve(int permits) {
    checkPermits(permits);
    synchronized (mutex()) {  // @1
      return reserveAndGetWaitLength(permits, stopwatch.readMicros()); // @2
    }
}

代码@1：限速器主要维护的重要数据字段(storedPermits)，对其进行维护时都需要先获取锁。

代码@2：调用内部方法 reserveAndGetWaitLength 来计算需要等待时间。

继续跟踪 reserveAndGetWaitLength 方法。

final long reserveAndGetWaitLength(int permits, long nowMicros) {
    long momentAvailable = reserveEarliestAvailable(permits, nowMicros);   // @1
    return max(momentAvailable - nowMicros, 0);  // @2
}

代码@1：根据当前拥有的许可数量、当前时间判断待申请许可最早能得到满足的最早时间，用momentAvailable 表示。

代码@2：然后计算 momentAvailable 与 nowMicros 的差值与0做比较，得出需要等待的时间。

继续跟踪 reserveEarliestAvailable方法，该方法在 RateLimiter 中一个抽象方法，具体实现在其子类 SmoothRateLimiter 中。

SmoothRateLimiter#reserveEarliestAvailable

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    resync(nowMicros);   // @1
    long returnValue = nextFreeTicketMicros;
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits); // @2
    double freshPermits = requiredPermits - storedPermitsToSpend; // @3
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);  // @4
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);  // @5
    this.storedPermits -= storedPermitsToSpend;    // @6
    return returnValue;
}

代码@1：在尝试申请许可之前，先根据当前时间即发放许可速率更新 storedPermits 与 nextFreeTicketMicros（下一次可以免费获取许可的时间）。

代码@2：计算本次能从 storedPermits 中消耗的许可数量，取需要申请的许可数量与当前可用的许可数量的最小值，用 storedPermitsToSpend 表示。

代码@3：如果需要申请的许可数量(requiredPermits)大于当前剩余许可数量(storedPermits)，则还需要等待新的许可生成，用freshPermits 表示，即如果该值大于0，则表示本次申请需要阻塞一定时间。

代码@4：计算本次申请需要等待的时间，等待的时间由两部分组成，一部分是由 storedPermitsToWaitTime 方法返回的，另外一部分以稳定速率生成需要的许可，其需要时间为 freshPermits * stableIntervalMicros,稍后我们详细分析一下 storedPermitsToWaitTime 方法的实现。

代码@5：更新 nextFreeTicketMicros 为当前时间加上需要等待的时间。

代码@6：更新 storedPermits 的值，即减少本次已消耗的许可数量。

代码@7：请注意这里返回的 returnValue 的值，并没有包含由于剩余许可需要等待创建新许可的时间，即允许一定的突发流量，故本次计算需要的等待时间将对下一次请求生效。

接下来重点探讨一下 SmoothWarmingUp 的 storedPermitsToWaitTime 方法。

SmoothWarmingUp#SmoothWarmingUp

long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {  // @1
    double availablePermitsAboveThreshold = storedPermits - thresholdPermits;   // @2
    long micros = 0;
    if (availablePermitsAboveThreshold > 0.0) {  // @3
        double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);  // @31 
                // TODO(cpovirk): Figure out a good name for this variable.
                double length = permitsToTime(availablePermitsAboveThreshold)
                     + permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake);             // @32
                micros = (long) (permitsAboveThresholdToTake * length / 2.0);                                                      // @33
                permitsToTake -= permitsAboveThresholdToTake;                                                                          // @34
         }
        // measuring the integral on the left part of the function (the horizontal line)
        micros += (stableIntervalMicros * permitsToTake);   // @4
        return micros;
}

代码@1：首先介绍其两个参数的含义：

• double storedPermits
  当前存储的许可数量。
  
• double permitsToTake
  本次申请需要的许可数量。
  

代码@2：availablePermitsAboveThreshold ，当前超出 thresholdPermits 的许可个数，如果超过 thresholdPermits ，申请许可将来源于超过的部分，只有其不足后，才会从 thresholdPermits 中申请，这部分的详细逻辑见代码@3。

代码@3：如果当前存储的许可数量超过了稳定许可 thresholdPermits，即存在预热的许可数量的申请逻辑，其实现关键点如下：

• 获取本次从预热区间申请的许可数量。
  
• 从预热区间获取一个许可的时间其算法有点晦涩难懂，具体实现为@32~@34。
  

代码@4：从稳定区间获取一个许可的时间，就容易理解，为固定的 stableIntervalMicros 。

温馨提示：从预热区间计算获取多个许可的算法，与 slope 有关，笔者并未完成感悟（走过路过的朋友如果对这块比较熟悉，欢迎留言探讨），但至少我们需要明白的是，从 剩余许可(storedPermits)中申请许可时，优先消耗(大于thresholdPermits 的许可，即消耗 (thresholdPermits ~ maxPermit ) 之间的许可)。

SmoothWarmingUp 的 acquire 流程就介绍到这里了。

4、总结

SmoothWarmingUp 的 acquire 的流程与 SmoothBursty 类似，故其流程图与下图通用，主要的区别生成一个许可的时间有变化，主要是提供了预热机制。