Guava预热（滑动）限流算法不完全翻译

首先粘贴guava原文链接：https://github.com/google/guava/blob/master/guava/src/com/google/common/util/concurrent/SmoothRateLimiter.java大量的篇幅都在写注释，详细的解释算法的设计实现以及原因，真得很佩服这些大神。注释真得太重要了由于篇幅不断，自己英文又贼烂，所以就将自己努力理解翻...

会灰翔的灰机

990人浏览 · 2019-04-01 20:40:14

会灰翔的灰机 · 2019-04-01 20:40:14 发布

首先粘贴guava原文链接：https://github.com/google/guava/blob/master/guava/src/com/google/common/util/concurrent/SmoothRateLimiter.java
大量的篇幅都在写注释，详细的解释算法的设计实现以及原因，真得很佩服这些大神。注释真得太重要了

由于篇幅不短，自己英文又贼烂，所以就将自己努力理解翻译的结果记录下来以供后面查看。希望大神们看到错误及时通知博主改正，谢谢
ok，let’s do it。（没错就是Maroon 5的sugar MV的那个骚气的开头）^_

RateLimiter怎样设计，为什么这样设计？

RateLimiter主要的特征是它稳定的速率，正常条件下它允许达到最大速率。需要时这可以强制“节流”进入的请求。也就是说，计算机，为一个进入的请求，适当的调节时间，让调用线程等待同样长的时间。
维护一个QPS的速率最简单的途径是为上一个通过的请求打一个时间戳，并确认至当前花费的时间（1/QPS）。例如，QPS=5（5个请求每秒），如果在上一个请求之后我们保证一个请求在200ms之前没有被通过，那么我们就达到了预期速率。如果在上一个请求之后100ms我们收到一个请求，那么我们再等待100ms。这样的速率，提供15个需求（也就是获得15个请求）自然的需要花费3秒。

重要的是要认识到，像RateLimiter这样对过去有一个非常浅显的记忆：它仅保存上一个请求。如果RateLimiter有一段长时间没有被使用，那么一个请求到达后并被立即通过吗？RateLimiter将会立即忘记过去“未充分利用”。这样可能会导致“未充分利用”或者超负荷的结果，取决于实际没有使用期望速率的后果。

过去“未充分利用”可以定义为额外的资源是可使用的。那么，RateLimiter可以提升一会儿速率，以利用这些资源。当速率被应用在网络（限制带宽）时这一点很重要，过去“未充分利用”通常会被转换为“几乎为空的bufffers”，可以被立即填充使用。

另一方面，过去“未充分利用”可以定义为“负责处理请求的服务器对未来的请求准备不足”，也就是它的缓存变得陈旧，并且请求变得更喜欢触发昂贵的操作（一个极端的情况是当一个服务器刚启动是，他最忙的是提升自身的速度）

为了处理这种情况，我们添加一个额外的维度，即“过去未充分利用”，使用“storedPermits”变量建模。当没有“未充分利用”（充分利用）的时候变量为0，它可以增长到“maxStoredPermits”，以获得足够大的“未充分利用”。因此，通过调用 acquire(permits) 请求的permits，由以下提供

stored permits 存储的许可（如果可用）
fresh permits 新发放的许可（为任意剩余的许可）

storedPermits怎样工作最好的解释是这个例子：

如果一个RateLimiter生产一个令牌每秒，如果一秒没有使用RateLimiter，我们将storedPermits增加1。假设我们让RateLimiter闲置10秒（也就是，我们期望在X时刻有一个请求，但是我们在X + 10秒时请求才真正到达）；这也与上一段中的观点关联），因此 storedPermits变为10.0（假定 maxStoredPermits >= 10.0）。在这时，获取3个许可的请求（acquire(3)）到达。我们从storedPermits取出令牌提供给请求，并且将其减小至7.0（稍后讨论怎样将其转换为节流时间）。紧接着之后，假定一个请求获得（10个许可）到达。我们从storePermits中为请求提供一部分，使用所有剩余的7.0个许可，并且剩余的3.0个，我们通过速率限制器生成的新许可证提供请求。

我们已经知道生产3个许可需要花费多少时间：如果这个速率是“每秒一个令牌”，那么这将花费3秒。但是提供7个许可意味着什么？在上面的解释，没有一个唯一的答案。如果我们主要关心解决“未充分利用”，那么我们希望“存储的permits”比“新发放的permits”生产的更快，因为“未充分利用” = 可被使用的空闲资源。如果我们主要关心解决溢出，那么“存储的permits”比“新发放的permits”生产的更慢。因此，我们需要一个（在每个情况下有不同的处理）方法转换storedPermits为throttling time。

这个角色则由storedPermitsToWaitTime（double storedPermits，double permitsToTake）扮演。底层模型是一个连续函数，将storedPermits（从0.0 至 maxStoredPermits）映射到在给定 storedPermits 下有效的 1/rate（即间隔）。“storedPermits”本质上是度量未使用的时间；我们花费未使用的时间购买/储存许可证。Rate是“permits/time”，因此“1/rate = time / permits”。所以，“1/rate”(time/permits)乘以"permits"得到时间，即，此函数上的积分(这是storedPermitsToWaitTime()计算的)对应于后续请求之间的最小间隔，对于指定数量的requested permits。

这里有一个storedPermitsToWaitTime的例子：如果storedPermits = 10.0，并且我们想要3个许可证，我们从storedPermits中提取，减小至7.0，并且为这些计算节流调用storedPermitsToWaitTime（storedPermits=10.0，permitsToTake=3.0），将求值该函数从7.0至10.0的积分。

使用积分保证一个作用是一个单独的获得3个许可是等价于{获得1；获得1；获得1；}，或者{获得2，获得1}，等等，由于[7.0,10.0]中函数的积分等于[7.0,8.0]，[8.0,9.0]，[9.0,10.0] (依此类推)的积分之和，无论是什么函数。这保证了我们正确处理不同权重的请求，无论实际函数是什么，因此我们可以自由的调整后者。（显然，唯一的要求是我们可以计算它的积分）。

请注意，如果，这个函数，我们选择一个水平线，高度正好是（1/QPS），那么函数的作用是不存在的：我们提供的storedPermits恰好与fresh Permits开销相同（1/QPS 是每一个的花费）。我们稍后会用到这个技巧。

如果我们选择一个函数它在水平线以下，这意味着我们减少了函数面积，从而减少了时间。因此在一段时间的未完全使用之后RateLimiter变得更快。另外一方面，如果我们选择一个高于水平线的函数，那么这意味着面积（时间）增长，因此storedPermits比fresh Permits开销更大，因此RateLimiter在一段时间的未完全使用之后变得更慢。

最后，但并非不重要：考虑一个速率为1许可每秒的RateLimiter，当前完全未使用的状态，并且一个昂贵的获取（100令牌）请求进来。它将毫无意义的去干等100秒，然后开始执行实际的任务。为什么等待不做些其他事情？一个更好的方法是立即允许请求（就好像它是一个获得（1）的请求一样），并根据需要推迟后续的请求。在这个版本，我们允许启动立即启动一个任务，并将未来的请求推迟100秒，因此我们允许工作在这段时间完成来代替无所事事的等待。（此时一次性休眠100秒，但是休眠的同事100令牌的请求作为一个一个的请求消费掉）

这样就有一个重要的推论：这意味着RateLimiter不记录上次请求的时间，但是它记录下次请求的时间（期望）。这也使我们能够立即知道（查看 tryAcquire(timeout)）某个特有的超时是否足够我们到达下一个调度时间点，因为我们一直维护期望时间。并且我们所说的“一个未使用的RateLimiter”也是有这个概念定义的：当我们观察到这个“下个请求期望到达时间”实际已经过去，那么差值（now - past）就是RateLimiter正式未被使用的时间量，这就是我们转换到storedPermits的时间量。（我们增长storedPermits的量为相应在空闲时间内应生产的许可证数量）。那么，如果速率==1许可每秒，并且恰好在上一个请求之后一秒一个请求到达进来，那么storePermits是绝不增加的，我们只会在到达时间晚于预期一秒时增加它。

这实现了以下函数，其中coldInterval = coldFactor * stableInterval。

*          ^ throttling
*          |
*    cold  +                  /
* interval |                 /.
*          |                / .
*          |               /  .   ← "warmup period" is the area of the trapezoid between
*          |              /   .     thresholdPermits and maxPermits
*          |             /    .
*          |            /     .
*          |           /      .
*   stable +----------/  WARM .
* interval |          .   UP  .
*          |          . PERIOD.
*          |          .       .
*        0 +----------+-------+--------------→ storedPermits
*          0 thresholdPermits maxPermits

在进入这个特殊函数的详细介绍之前，让我们先记住基础知识：

RateLimiter（storedPermits）的状态是图中的垂直线
当RateLimiter不使用时，它会向右走（上升至maxPermits）
当RateLimiter使用时，它会向左走（下降至0），如果我们有storedPermits的时候，我们从他们中的第一个提供
当未使用时候，我们保持一个常量的速率向右走！我们向右移动的速率被选为maxPermits/warmupPeriod。这确定了从0至maxPermits消耗的时间等于warmupPeriod的时间。（非翻译内容：其实从图中我们可以看到，如果匀速（即延长水平线至与maxPermits相交）走到maxPermits等于warmupPeriod时间，也就证明了0至thresholdPermits的时间=warmupPeriod/2）
当使用的时候，时间的消耗，正如介绍类的笔记中解释的一样，等于我们函数的积分，在X个许可与X-K个许可之间，假设我们想要花费K个保存的许可。

假定我们有饱和的需求，时间从maxPermits至thresholdPermits是等于warmupPeriod。并且时间从thresholdPermits至0是warmupPeriod/2。（预热期/2是维护原来实现行为的原因，冷因子coldFactor硬编码为3）

剩下的是去计算thresholdPermits与maxPermits

The time to go from thresholdPermits to 0 is equal to the integral of the function
   *       between 0 and thresholdPermits. This is thresholdPermits * stableIntervals. By (5) it is
   *       also equal to warmupPeriod/2. Therefore
   *       <blockquote>
   *       thresholdPermits = 0.5 * warmupPeriod / stableInterval
   *       </blockquote>
   *   <li>The time to go from maxPermits to thresholdPermits is equal to the integral of the
   *       function between thresholdPermits and maxPermits. This is the area of the pictured
   *       trapezoid, and it is equal to 0.5 * (stableInterval + coldInterval) * (maxPermits -
   *       thresholdPermits). It is also equal to warmupPeriod, so
   *       <blockquote>
   *       maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval)
   *       </blockquote>

从thresholdPermits至0的时间等于函数在0至thresholdPermits的积分。这就是thresholdPermits * stableIntervals。通过5点基础知识我们知道，他也等于warmupPeriod/2。因此

thresholdPermits = 0.5 * warmupPeriod / stableInterval

从maxPermits至thresholdPermits的时间等于函数在thresholdPermits至maxPermits之间的积分。这就是图形中梯形的面积，它等于0.5 * (stableInterval + coldInterval) * (maxPermits - thresholdPermits)。它也等于warmupPeriod，那么

maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval)