限流器及Guava实现分析

摘要：计数限流算法无论固定窗口还是滑动窗口核心均是对请求进行计数，区别仅仅在于对于计数时间区间的处理。令牌桶限流实现原理令牌桶限流的实现原理在有详细说明。因此由此为入口进行分析。目前可返回的实现子类包括及两种，具体不同下文详细分析。

限流一词常用于计算机网络之中，定义如下：

In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks.

通过控制数据的网络数据的发送或接收速率来防止可能出现的DOS攻击。而实际的软件服务过程中，限流也可用于API服务的保护。由于提供服务的计算机资源(包括CPU、内存、磁盘及网络带宽等)是有限的，则其提供的API服务的QPS也是有限的，限流工具就是通过限流算法对API访问进行限制，保证服务不会超过其能承受的负载压力。
本文主要涉及内容包括：

常用限流算法的简单介绍及比较

Guava包中限流工具的实现分析

援引wiki中关于限流的Algorithms一小节的说明，常用的限流算法主要包括：

Token bucket-令牌桶

Leaky bucket-漏桶

Fixed window counter-固定窗口计数

Sliding window log-滑动窗口日志

Sliding window counter-滑动窗口计数

以上几种方式其实可以简单的分为计数算法、漏桶算法和令牌桶算法。

无论固定窗口还是滑动窗口核心均是对请求进行计数，区别仅仅在于对于计数时间区间的处理。

固定窗口计数法思想比较简单，只需要确定两个参数：计数周期T及周期内最大访问（调用）数N。请求到达时使用以下流程进行操作：

固定窗口计数实现简单，并且只需要记录上一个周期起始时间与周期内访问总数，几乎不消耗额外的存储空间。

固定窗口计数缺点也非常明显，在进行周期切换时，上一个周期的访问总数会立即置为0，这可能导致在进行周期切换时可能出现流量突发，如下图所示

简化模型，假设在两个周期T0中a时刻有n1个访问同时到达，周期T1中b时刻有n2个访问同时到达，且n1和n2均小于设定的最高访问次数N（否则会触发限流）。
根据以上假设可以推断，限流器不会限流，n1+n2次访问均可以通过。现假设a，b两时刻之间时间差为t，则可以得出以下关系:

$$ left{ egin{aligned} n1 le N n2 le N (n1+n2) le 2N end{aligned} ight. $$

根据观察可发现，在$t$的时间内，出现了$n1+n2$次请求，且$n1+n2$是可能大于$N$的，所以在实际使用过程中，固定窗口计数器存在突破限额N的可能。
举例，限制QPS为10，某用户在周期切换的前后的0.1秒内，分两次发送10次请求，根据算法规则此20次请求可通过限流器，则0.1面秒请求数20，超过每秒最多10次请求的限制。

为解决固定窗口计数带来的周期切换处流量突发问题，可以使用滑动窗口计数。滑动窗口计算本质上也是固定窗口计数，区别在于将计数周期进行细化。

滑动窗口计数法与股固定窗口计数法相比较，除了计数周期T及周期内最大访问（调用）数N两个参数，增加一个参数M，用于设置周期T内的滑动窗口数。限流流程如下：

滑动窗口计数在固定窗口计数记录数据基础上，需要增加一个长度为M的计数数组，用于记录在窗口滑动过程中各窗口访问数据。其流程示例如下：

滑动窗口针对周期进行了细分，不存在周期到后计数直接重置为0的情况，故不会出现跨周期的流量限制问题。

漏桶限流算法的实现原理在wiki有详细说明，引用其原理图：
简单说明为：人为设定漏桶流出速度及漏桶的总容量，在请求到达时判断当前漏桶容量是否已满，不满则可将请求存入桶中，否则抛弃请求。程序以设定的速率取出请求进行处理。
根据描述，需要确定参数为漏桶流出速度r及漏桶容量N，流程如下：

漏桶算法主要特点在于可以保证无论收到请求的速率如何，真正抵达服务方接口的请求速率最大为r，能够对输入的请求进行平滑处理。
漏桶算法的缺点也非常明显，由于其只能以特定速率处理请求，则如何确定该速率就是核心问题，如果速率设置太小则会浪费性能资源，设置太大则会造成资源不足。并且由于速率的设置，无论输入速率如何波动，均不会体现在服务端，即使资源有空余，对于突发请求也无法及时处理，故对有突发请求处理需求时，不宜选择该方法。

令牌桶限流的实现原理在wiki有详细说明。简单总结为：设定令牌桶中添加令牌的速率，并且设置桶中最大可存储的令牌，当请求到达时，向桶中请求令牌（根据应用需求，可能为1个或多个），若令牌数量满足要求，则删除对应数量的令牌并通过当前请求，若桶中令牌数不足则触发限流规则。
根据描述需要设置的参数为，令牌添加速率r，令牌桶中最大容量N，流程如下：

令牌桶算法通过设置令牌放入速率可以控制请求通过的平均速度，且由于设置的容量为N的桶对令牌进行缓存，可以容忍一定流量的突发。

以上提到四种算法，本小节主要对四种算法做简单比较算法进行对比。

上文简单介绍了常用的限流算法，在JAVA软件开发过程中可使用Guava包中的限流工具进行服务限流。Guava包中限流工具类图如下所示：
其中RateLimiter类为限流的核心类，其为public的抽象类，RateLimiter有一个实现类SmoothRateLimiter，根据不同消耗令牌的策略SmoothRateLimiter又有两个具体实现类SmoothBursty和SmoothWarmingUp。
在实际使用过程中一般直接使用RateLimiter类，其他类对用户是透明的。RateLimiter类的设计使用了类似BUILDER模式的小技巧，并做了一定的调整。
通过RateLimiter类图可见，RateLimiter类不仅承担了具体实现类的创建职责，同时也确定了被创建出的实际类可提供的方法。标准创建者模式UML图如下所示（引用自百度百科）
RateLimiter类即承担了builder的职责，也承担了Product的职责。

在实际的代码编写过程中，对GUAVA包限流工具的使用参考以下代码：

final RateLimiter rateLimiter = RateLimiter.create(2.0); // rate is "2 permits per second"
void submitTasks(List tasks, Executor executor) {
  for (Runnable task : tasks) {
    rateLimiter.acquire(); // may wait
    executor.execute(task);
  }
}

以上代码摘自GUAVA包RateLimiter类的说明文档，首先使用create函数创建限流器，指定每秒生成2个令牌，在需要调用服务时使用acquire函数或取令牌。

根据代码示例，抽象类RateLimiter由于承担了Product的职责，其已经确定了暴露给编程人员使用的API函数，其中主要实现的核心函数为create及acquire。因此由此为入口进行分析。

create函数具有两个个重载，根据不同的重载可能创建不同的RateLimiter具体实现子类。目前可返回的实现子类包括SmoothBursty及SmoothWarmingUp两种，具体不同下文详细分析。

acquire函数也具有两个重载类，但分析过程仅仅需要关系具有整形参数的函数重载即可，无参数的函数仅仅是acquire(1)的简便写法。
在acquire(int permits)函数中主要完成三件事：

预分配授权数量，此函数返回需要等待的时间，可能为0；

根据等待时间进行休眠；

以秒为单位，返回获取授权消耗的时间。

完成以上工作的过程中，RateLimiter类确定了获取授权的过程骨架并且实现了一些通用的方法，这些通用方法中会调用为实现的抽象方法，开发人员根据不同的算法需求可实现特定子类对抽象方法进行覆盖。其调用流程如下图：
其中橙色块中reserveEarliestAvailable方法即为需要子类进行实现的，下文以该函数为核心，分析RateLimiter类的子类是如何实现该方法的。

根据上文的类图可见，RateLimiter类在GUAVA包中的直接子类仅有SmoothRateLimiter，故以reserveEarliestAvailable函数为入口研究其具体实现，而在代码实现的过程中需要使用SmoothRateLimiter类中的属性，现将类中各属性罗列出来：

reserveEarliestAvailable源码如下：

@Override
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
  resync(nowMicros);
  long returnValue = nextFreeTicketMicros;
  double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
  double freshPermits = requiredPermits - storedPermitsToSpend;
  long waitMicros =
      storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
          + (long) (freshPermits * stableIntervalMicros);

  this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
  this.storedPermits -= storedPermitsToSpend;
  return returnValue;
}

通过reserveEarliestAvailable的函数名称可以知道，该函数能够返回令牌可用的最早时间。函数需要的输入参数有需求的令牌数requiredPermits，当前时刻nowMicros。进入函数后，首先调用名为resync的函数：

void resync(long nowMicros) {
  // if nextFreeTicket is in the past, resync to now
  if (nowMicros > nextFreeTicketMicros) {
    double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
    storedPermits = min(maxPermits, storedPermits + newPermits);
    nextFreeTicketMicros = nowMicros;
  }
}

函数逻辑比较简单，首先获取nextFreeTicketMicros，该值在上表中已经说明，表示下一次有空闲令牌产生的时刻，如果当前时刻小于等于nextFreeTicketMicros，说明在当前时刻不可能有新的令牌产生，则直接返回。若当前时刻大于nextFreeTicketMicros，则完成以下工作：

计算到当前时刻新产生的令牌数，其中涉及一个名为coolDownIntervalMicros 的函数，该函数返回创建一个新令牌需要的冷却时间（注：该函数在当前类中并未实现，具体实现下文说明）；

更新storedPermits属性，取产生的令牌和最大可存储令牌之间的最小值；

将nextFreeTicketMicros属性置为当前时刻。

可见，resync函数主要功能在于计算新产生的令牌数，并更新nextFreeTicketMicros属性，nextFreeTicketMicros属性取值是当前时刻和nextFreeTicketMicros属性的原始值中最大的一个。
完成resync函数的调用后，使用returnValue变量记录更新令牌后的最近可用时间（即上文更新后的nextFreeTicketMicros属性）。
使用storedPermitsToSpend变量记录需要消耗以存储的令牌数，其取值为请求令牌数和当前存储令牌数之间的最小值。
使用freshPermits变量记录需要刷新的令牌数，其实现是用需求的令牌数减去之前计算的storedPermitsToSpend变量，可见freshPermits变量取值为需求令牌数与已存储令牌数之间的差值，当需求令牌数小于已存储令牌数是则为0。
后续为该函数核心，计算需要等待的时间，计算等待时间主要分为两个部分：消耗已经存储的令牌需要的时间及生成新令牌的时间，其中storedPermitsToWaitTime函数用于计算消耗已经存储的令牌需要的时间，该函数也是抽象函数，后文具体分析子类实现。
完成等待时间的计算后，程序更新nextFreeTicketMicros属性，将最近可用时间与需要等待的时间相加。
最后在更新存储的令牌数，将需要消耗额令牌数减去。

根据以上的代码分析可以发现，GUAVA对于令牌桶的实现跟理论有一点点小的区别。其当前一次的请求消耗的令牌数并不会影响本次请求的等待时间，而是会影响下一次请求的等待时间。
根据以上分析，当一次请求到达，最近可用时间返回当前时间和上一次请求计算的最近可用时间的最大值，而本次请求需要的令牌数会更新下一次的最近可用时间。在这样的设计下，如果每秒产生一个令牌，第一请求需求10个令牌，则当第一次请求调用acquire方法时能够立即返回，而下一次请求（无论需要多少令牌）均需要等待到第一个请求之后的10秒以后，第三次请求等待时间则取决于第二次需求了多少令牌。这也是函数名称中“reserve”的含义。

在以上文代码分析中出现了两个抽象函数coolDownIntervalMicros及storedPermitsToWaitTime，现分析这两个抽象函数。

coolDownIntervalMicros函数在代码中已经有说明：

Returns the number of microseconds during cool down that we have to wait to get a new permit.

主要含义为生成一个令牌需要消耗的时间，该函数主要应用于计算当前时间可产生的令牌数。根据上文的UML图SmoothRateLimiter类有两个子类SmoothBursty及SmoothWarmingUp。
SmoothBursty类中对于coolDownIntervalMicros函数的实现如下：

@Override
double coolDownIntervalMicros() {
  return stableIntervalMicros;
}

可见实现非常简单，仅仅只是返回stableIntervalMicros属性，即产生两个令牌需要的时间间隔。
SmoothWarmingUp类中对于coolDownIntervalMicros函数的实现如下：

@Override
double coolDownIntervalMicros() {
  return warmupPeriodMicros / maxPermits;
}

其中maxPermits属性上文已经出现过，表示当前令牌桶的最大容量。warmupPeriodMicros属性属于SmoothWarmingUp类的特有属性，表示令牌桶中令牌从0到maxPermits需要经过的时间，故warmupPeriodMicros / maxPermits表示在令牌数量达到maxPermits之前的令牌产生时间间隔。

storedPermitsToWaitTime函数在代码中已经有说明：

Translates a specified portion of our currently stored permits which we want to spend/acquire,
into a throttling time. Conceptually, this evaluates the integral of the underlying function we
use, for the range of [(storedPermits - permitsToTake), storedPermits]

主要表示消耗存储在令牌桶中的令牌需要的时间。
SmoothBursty类中对于storedPermitsToWaitTime函数的实现如下：

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

直接返回0，表示消耗令牌不需要时间。
SmoothBursty类中对于storedPermitsToWaitTime函数的实现如下：

@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;
}

实现较为复杂，其核心思想在于计算消耗当前存储令牌时需要根据预热设置区别对待。其中涉及到新变量thresholdPermits，该变量为令牌阈值，当当前存储的令牌数大于该值时，消耗(storedPermits-thresholdPermits)范围的令牌需要有预热的过程（即消耗每个令牌的间隔时间慢慢减小），而消耗0~thresholdPermits个数的以存储令牌，每个令牌消耗时间为固定值，即stableIntervalMicros。
而thresholdPermits取值需要考虑预热时间及令牌产生速度两个属性，即thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;。可见阈值为预热时间中能够产生的令牌数的一半，并且根据注释计算消耗阈值以上的令牌的时间可以转换为计算预热图的梯形面积（实际为积分），本处不详细展开。
使用此种设计可以保证在上次请求间隔时间较长时，令牌桶中存储了较多的令牌，当消耗这些令牌时，最开始的令牌消耗时间较长，后续时间慢慢缩短直到达到stableIntervalMicros的状态，产生预热的效果。

以上分析GUAVA限流器实现，其使用了两个抽象类及两个具体子类完成了限流器实现，其中使用顶层抽象类承担了创建者角色，将所有子类进行了透明化，减少了程序员在使用工具过程中需要了解的类的数量。
在实现限流器的过程中，基于令牌桶的思想，并且增加了带有预热器的令牌桶限流器实现。被限流的线程使用其自带的SleepingStopwatch工具类，最终使用的是Thread.sleep(ms, ns);方法，而线程使用sleep休眠时其持有的锁并不会释放，在多线程编程时此处需要注意。
最后，GUAVA的限流器触发算法采用的是预定令牌的方式，即当前请求需要的令牌数不会对当前请求的等待时间造成影响，而是会影响下一次请求的等待时间。

本文主要总结了当前常用的服务限流算法，对比个各算法特点，最后分析GUAVA包中对于限流器的实现的核心方法。