Guava RateLimiter | 黑微狗的技术博客

URL

date

AI summary

slug

status

引言

主要分析一下Guava RateLimiter的源码，初写应该是19年，一直存在本地未发表，最近在系统性归纳总结限流这一块，于是又拿出来重新阅读、理解、完善。其中确有一些之前理解不到位的地方。

本篇文章基于guava 18.0，很古早的版本

核心设计思想

基于给定的QPS来限流

基于令牌桶来实现

令牌在请求的过程中计算生成

如何处理长期闲置的场景

如何处理一次性获取大量令牌的场景

基于令牌桶的限流器

前三点可以归为一类，就是基于令牌桶的限流器的实现。它的基本思想由两部分组成：生成令牌和消费令牌。

生成令牌：假设有一个令牌桶，最多能装T个，然后按某个固定的速度（每秒n个）往桶中放入令牌，桶满时不再放入；

消费令牌：我们的每次请求都需要从桶中拿一定的令牌才能放行，当桶中没有令牌时即触发限流。

令牌桶算法一般会有两种不同的实现方式。第一种方式是启动一个内部线程，不断的往桶中添加令牌，处理请求时从桶中获取令牌，完全符合上面描述的基本思想。第二种方式不依赖于内部线程，而是在每次处理请求之前先实时计算出要填充的令牌数并填充，然后再从桶中获取令牌。

Guava RateLimiter采用的就是后者：在每次请求令牌的时候，会按照限流的速率计算好下一次可以获取令牌的时间点。判断是否被限流的依据就是当前请求令牌的时间点是否已经超过了下一次可以获取令牌的时间点。

这个时间点就是Guava RateLimiter里最核心的成员变量——nextFreeTicketMicros。如果不考虑限流器长期闲置的场景，可以说，靠它就可以支撑起整个限流器了。获取令牌的伪代码如下：


public void acquire(var num){
    if (now < nextFreeTicketMicros) {
        wait(nextFreeTicketMicros - now)
    }
    nextFreeTicketMicros = nextFreeTicketMicros + num * stableInterval
}

处理长期闲置的场景

上面这个简单限流器再完善一下并发安全就已经可以work了。但它确实有点太简陋了，在这个大数据的时代，我们只记录了一个时间点信息，恐怕是不太够。假设最近一段时间都没有获取令牌的请求，那么只要来一个请求，我们就失去了这个重要的信息（因为nextFreeTicketMicros会被重新计算）。为了保留这个重要的信息，Guava RateLimiter引入了一个新的成员变量storedPermits，用它来体现最近一段时间限流器的繁忙程度。


storedPermits = storedPermits + (now - nextFreeTicketMicros) / stableInterval

storedPermits越多，则表示限流器在过去一段时间越空闲。那么当限流器空闲了较长一段时间之后，我们应该怎么调整之后的策略呢？Guava RateLimiter为我们考虑了两种场景：

长期闲置导致资源处于过剩状态，限流器可以适当加速来更好的利用这些资源。比如对于网卡缓冲区来说，长期不用可能就是空的，在这种场景下，我们是可以加速发送来将这些过程的资源利用起来

长期闲置导致服务器处于一个冷却的状态，此时的请求可能会触发一下“昂贵”的操作。比如由于缓存过期触发直接查询数据库等。限流器需要降低一定的速率来让服务器有个预热的过程。

Guava RateLimiter对于这两个场景，给出了两种不同策略的限流器实现。两个实现方案的区别主要是在于对storedPermits的使用上，这个在下文中会有比较

整体流程

下面我们来看看Guava RateLimiter的整体流程以及针对上面两个场景的不同策略。下图是以时间轴的维度来绘制的，上下两个时间轴的区别是：访问时间点是在可以生成新令牌的时间点(nextFreeTicketMicros)之后还是之前：

如果访问时间点在后，则本次请求不需要等待。假设本次请求的令牌数为N，优先使用storedPermits取P个，不够的部分(N-P)即时生成，并计算出下次可以生成新令牌的时间点(nextFreeTicketMicros)

如果访问时间点在后，那本次请求一定需要等待，等待时间为可以生成新令牌的时间点(nextFreeTicketMicros)和访问时间点的差值。阻塞等待醒来后，流程和前面一样，不过此时storedPermits一定为空，所有令牌都是新生成的

Note：图中红色的虚线指向的时间点表示只是一个计算值，并未在本次请求到达

可以看到从RateLimiter里获取的令牌，有两部分来源：storedPermits和freshPermits。前者表示由于之前一段时间的闲置(unused)而积攒的令牌。后者表示需要新生成的令牌。并且storedPermits的优先级更高。storedPermits不能无限积攒，存在一个上限值maxPermits。

积攒的storedPermits到底如何来使用呢，结合前面提到的两个场景，我们来看看具体的实现。

SmoothBursty

Bursty是突增的意思，这种限流器就是针对于场景一的具体实现：过去一段时间请求量偏少，导致资源的利用率不足，可以适当的通过“突增”令牌来提高资源利用率。这里可以“突增”的令牌是多少呢，就是前面提到的storedPermits，SmoothBursty给它的上限maxPermits是：


    @Override
    void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
      double oldMaxPermits = this.maxPermits;
      maxPermits = maxBurstSeconds * permitsPerSecond;
    }

通过指定最大突增令牌的时长（maxBurstSeconds）来算的，这个时间就表示可以缓存”突增“令牌的最长时间，有点拗口，但是应该比较容易理解。

再看看SmoothBursty对于storedPermits的使用上：


    @Override
    long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
      return 0L;
    }

这里的这个函数表示什么意思呢，返回值始终为0，表示从storedPermits里拿到的令牌，不参与计算nextFreeTicketMicros。也就是说，这完全是额外颁发的，所以会看到qps可能超过我们限定的速率，这也就是所谓的“突增”。假设maxBurstSeconds = 1s，那么qps最大可以到2倍的限定速率

SmoothWarmingUp

WarmingUp是预热的意思。我们带着两个问题来看这个带预热功能的限流器：

什么叫预热

什么情况下需要预热


   *          ^ throttling
   *          |
   * 3*stable +                  /
   * interval |                 /.
   *  (cold)  |                / .
   *          |               /  .   <-- "warmup period" is the area of the trapezoid between
   * 2*stable +              /   .       halfPermits and maxPermits
   * interval |             /    .
   *          |            /     .
   *          |           /      .
   *   stable +----------/  WARM . }
   * interval |          .   UP  . } <-- this rectangle (from 0 to maxPermits, and
   *          |          . PERIOD. }     height == stableInterval) defines the cooldown period,
   *          |          .       . }     and we want cooldownPeriod == warmupPeriod
   *          |---------------------------------> storedPermits
   *              (halfPermits) (maxPermits)

我们通过这张图来回答一下上面两个问题。这张图的x轴是storedPermits的数量，y轴是需要作用到nextFreeTicketMicros上的时间。

那么什么叫预热？ 我们以一个比正常限定速率更低的速率（更长的时间间隔）去生成令牌，就叫作预热。这段时间叫作预热期（warmup period）。

那什么情况下需要预热呢？ 限流器闲置时间过长了，从图上看，也就是当storedPermits超过halfPermits的时候，进入预热期。

可以看到storedPermits的数量越多，获取完令牌之后的下一次请求需要等待的时间就越长。最长的等待时间为cold_factor * stableInterval。图中的面积（函数图线与x轴y轴围成的多边形）就是整体获取完maxPermits个令牌(maxPermits -> 0)需要等待的时间。

💡

注：cold_factor当前被硬编码为3

如果把SmoothBursty画到这张图上来，那么它的线图会和x轴完全重合，因为storedPermits对于SmoothBursty来说，完全是额外的，只要有就可以立马拿去用。

下面这段代码就实现了上图的函数：


    @Override
    long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
      double availablePermitsAboveHalf = storedPermits - halfPermits;
      long micros = 0;
      // 这是右侧预热期的部分面积
      if (availablePermitsAboveHalf > 0.0) {
        double permitsAboveHalfToTake = min(availablePermitsAboveHalf, permitsToTake);
        micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf)
            + permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0);
        permitsToTake -= permitsAboveHalfToTake;
      }
      // 这是左侧稳定期的部分面积
      micros += (stableIntervalMicros * permitsToTake);
      return micros;
    }

上图中定义storedPermits从maxPermits降到halfPermits的阶段叫作预热期（warmup period）。storedPermits的值从0升到maxPermits的阶段叫作冷却期（cooldown period）。通过上面的分界点设定，两个周期的时长保持一致。

这个预热期的时长是我们在创建SmoothWarmingUp的时候指定的，根据预热期的时长（warmupPeriodMicros），我们可以算出maxPermits：


    @Override
    void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
      double oldMaxPermits = maxPermits;
      maxPermits = warmupPeriodMicros / stableIntervalMicros;
      halfPermits = maxPermits / 2.0;
      // Stable interval is x, cold is 3x, so on average it's 2x. Double the time -> halve the rate
      double coldIntervalMicros = stableIntervalMicros * 3.0;
      slope = (coldIntervalMicros - stableIntervalMicros) / halfPermits;
    }

关于coldFactor和halfPermits的取值

coldFactor，这个值被硬编码为3，但是文档里没有找到关于这个取值的说明。并且，我尝试调整这个值，单纯从运行上来看，并没有什么问题。按照上面的图来理解的话，只是预热那条曲线的斜率会不一样。

halfPermits，这个变量在后续的版本中，已经被更名成thresholdPermits了。从这个变更也可以看出，其实这个值的设定并不一定要是maxPermits的一半。只是最初设计的时候有一个目的：希望冷却周期和预热周期的时间相等，并且在coldFactor等于3的前提下，计算出这个thresholdPermits的位置刚好是maxPermits的一半。所以这个值也是可以调整的，只是整个图形也会有相应的变化。

We decided that the "cooldown period" time should be equivalent to "warmup period", thus a fully saturated RateLimiter (with zero stored permits, serving only fresh ones) can go to a fully unsaturated (with storedPermits == maxPermits) in the same amount of time it takes for a fully unsaturated RateLimiter to return to the stableInterval -- which happens in halfPermits, since beyond that point, we use a horizontal line of "stableInterval" height, simulating the regular rate.

初始化时的区别

这里两者还有个不太明显的区别：SmoothBursty初始化时storedPermits为0，而SmoothWarmingUp初始时storedPermits为maxPermits。这个也容易理解，因为对于SmoothWarmingUp来说，刚创建的时候，就应该走预热逻辑。

Try it

下面会准备一些简单的例子和输出再加深下理解

等待后置


    public static void main(String[] args) {
        RateLimiter rateLimiter = RateLimiter.create(1);
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
    }

输出：

体会RateLimiter是通过计算下一次可获得令牌的时间来达到限流的效果的，所以只要满足条件（now >= nextFreeTicketMicros）就不需要等待。比如创建完之后第一次请求永远不需要等待。在使用的过程中可能需要注意下，假设是限制流量的场景，那么第一秒无论是多大的流量都可以通过。

SmoothBursty令牌缓存策略


    public static void main(String[] args) throws InterruptedException {
        RateLimiter rateLimiter = RateLimiter.create(1);
        Thread.sleep(1000);
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
    }

输出：

休眠了1s模拟了限流器闲置了1s，缓存了1s的令牌。所以之后的第一次请求，根据时间差能算出storedPermits = 1，这个时候会直接从storedPermits里获取，并且nextFreeTicketMicros只会更新成当前获取的时间（因为不需要额外再生成令牌）

所以，第二次请求依旧满足条件（now >= nextFreeTicketMicros），不过这次的令牌是新生成出来的，所以计算出的nextFreeTicketMicros为下一秒，第三次请求令牌的时候就需要等待了。

预热的过程


    public static void main(String[] args) throws InterruptedException {
        RateLimiter rateLimiter = RateLimiter.create(10, 1, TimeUnit.SECONDS);
        for (int i = 0; i < 10; i++) {
            System.out.println(rateLimiter.acquire());
        }
        Thread.sleep(1100);
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
    }

输出：

由于刚创建出来的SmoothWarmingUp里储存的令牌就是满的（maxPermits）。那么第一次获取到的令牌就是从storedPermits里获取的，消耗时间就是作一条垂直于x轴，x=(maxPermits - 1)的直线，与x轴y轴和预热期的斜线围成的梯形的面积。(260 + 300) * 1 / 2 = 280ms

整体趋势和上图是一样的，slope = 40，等storedPermits降到一半的时候，等待时间就稳定在1s了。

最后sleep 1100ms模拟了长期闲置了场景。为什么是1100ms呢，100ms是为了消耗掉第十次获取令牌时计算出来的nextFreeTicketMicros

为什么打印出来的等待时间总是偏小呢

这个也很容易理解，因为nextFreeTicketMicros是提前计算好的。计算完这个时间后还有一些操作可能会占用一些时间，所以等到下一次请求令牌的时间点和nextFreeTicketMicros的差值肯定是偏小的。

自定义时钟问题

如果你仔细的阅读过源代码，你会发现Guava RateLimiter里最终使用的是System.nanoTime()来读取时间。System.nanoTime()是单调时钟，使用它可以避免时间回拨问题。不过它只能用于计算时间差值，无法表达一个实际的时间。

“突增”和“漏桶”

其实去研究Guava RateLimiter主要是因为在使用过程中碰到的一次实际问题：明明限流100，但是当时1s的并发是整整的两倍，也就是200。问题主要就是因为使用了SmoothBursty，然后一段时间都没有请求，导致缓存了1s的“突增”令牌数。那么怎么解决呢？其实指定maxBurstSeconds = 0就可以了。

但是，SmoothBursty的构造函数，只有包访问权限，外部并不能直接创建，只能通过静态方法来创建：


  public static RateLimiter create(double permitsPerSecond) {
    return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond);
  }

  @VisibleForTesting
  static RateLimiter create(SleepingStopwatch stopwatch, double permitsPerSecond) {
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
    rateLimiter.setRate(permitsPerSecond);
    return rateLimiter;
  }

maxBurstSeconds = 1.0是写死的，没有办法通过传参来指定。可以通过反射来修改：


    public static void main(String[] args) throws InterruptedException {
        RateLimiter rateLimiter = RateLimiter.create(1);
        Field maxBurstSecondsField = ReflectionUtils
                .findField(rateLimiter.getClass(), "maxBurstSeconds");
        ReflectionUtils.makeAccessible(maxBurstSecondsField);
        ReflectionUtils.setField(maxBurstSecondsField, rateLimiter, 0);
        rateLimiter.setRate(rateLimiter.getRate());
        Thread.sleep(1000);
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
        System.out.println(rateLimiter.acquire());
    }

不过，把maxBurstSeconds设置为0可能违背了SmoothBursty的设计初衷，因为这样就没有“突增”的概念了。整体的也更偏向于漏桶算法的实现了。

参考

还在用传统的System.currentTimeMillis来计算代码运行时间嘛？