什么是RateLimiter

RateLimiter是Guava库中的一个限流器，它提供如下功能：

1. 基于PPS进行限流
2. 基于PPS限流的同时提供热启动

下面是一段示例代码，它展示了如何创建一个RateLimiter，并且进行使用

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

可以看出，在创建RateLimiter时，设置了RateLimiter的PPS=2.0，
而之后每次执行一个任务之前，进行一次acquire（），
一次acquire消耗一个permit，
那么可以计算出任务的执行速度是 2个/秒

Permit是什么

在上文中提到了PPS（Permit per second），其中第一个P就是接下来要讲解的Permit。
Permit是什么?你可以把它理解为一个消耗单位：

• 如果要对QPS进行限制，那么Permit = Query，一次Query消耗一个Permit就能达到效果
• 如果对文件网络IO进行限制，那么Permit = Size of Package，每次包大小越大消耗的Permit越多
• 如果要对请求时长进行限制，那么Permit = Time Cost of Query

如下代码就是对网络IO进行限制，可以看出RateLimiter的PPS为5000，那么可以推断出
该程序的IO速度为 5000byte/s

final RateLimiter rateLimiter = RateLimiter.create(5000.0); // rate = 5000 permits per second
void submitPacket(byte[] packet) {
rateLimiter.acquire(packet.length);
networkService.send(packet);
}

如果让你实现一个RateLimiter，你如何实现？

如果仅考虑RateLimiter的第一个特性：

• 基于PPS进行限流

那么实现起来十分简单。
我们只需要记录上一个acquire执行的时间，用当前时间减去上一次执行的时间，获得一个Δt。
如果 > acquire消耗的Permit,则无需等待，否则等待 （ acquire消耗的Permit - Δt * PPS）/ PPS

上面这种实现虽然很简单，并且由于它只记录了上一次任务执行的时间，空间复杂度也很低。
但也由于只记录最近一次的执行时间，这种实现无法判断出当前系统是否处于缺少利用(underutilization)的状态。

做了再等

上面这种简单的实现还有一个问题，就是当一个acquire执行时，如果Permit不够，就需要等待，然而等待的过程中系统什么事儿也没干，这多浪费啊。不如学习如今的超前消费 ，先借用Permit，然后将还款日期作为执行时间计入内存。

缺少利用(underutilization)

当一个系统在近一段时间接受的请求（消耗的Permit数）远远小于 PPS，这个系统就处于缺少利用的状态。
比如进入深夜，用户请求减少，社区服务的QPS就减少了，因此处于缺少利用的状态。
缺少利用的状态，对于服务的处理能力是有很大影响的：

• 缺少利用，意味着系统的缓存命中率低，很多缓存都被淘汰了，因此此时执行效率也偏低，若QPS突然上升，可能无法承受。
• 缺少利用也意味着系统资源限制，比如buffer空置，就拿网络IO举例，当网络IO处于缺少利用的状态，网络缓冲区就是空的，那此时，网络IO的处理能力实际是更强的，因为刚来的请求可以马上写入缓冲区。
• 服务刚启动，也可以被看作处于缺少利用的状态，此时同样是处理效率偏低的（因为要进行很多初始化操作，而且缓存也是空的）

热启动（warm up）

对于上面描述的，关于缺少利用很有可能导致系统工作效率降低，如果系统面临突如其来的QPS增长，但概率会GG。因此为系统预留一段时间，逐步去提升QPS，成为了一个对抗策略，我们把它叫做热启动。

实现热启动

要实现热启动，我们需要引入一个变量storedPermits，通过这个变量可以来描述系统的利用状态。
storedPermits从字面上看就是，被存储的permit。
在之前的实现方法中，permit没被使用完直接就被扔掉，而现在如果permit没被使用完，则被加在storedPermits中，则如果storedPermits也多，则系统越空闲，而storedPermits越小则表明系统越繁忙。

现在当我们需要处理一个acquire时，storedPermits越大则需要等待的时间越长，而storedPermits越低，这越接近我们的PPS，在RateLimiter中使用storedPermitsToWaitTime方法来计算等待时间

storedPermitsToWaitTime

storedPermitsToWaitTime第一个规则是，有storedPermits就使用storedPermits，没有或不够再使用fresh Permits（即更新的Permits）

Fresh Permits消耗的时间 = stable interval * count（Fresh Permits）
Stable Interval（稳定状态下一个Permit需要消耗的时间间隔）= 1 / PPS

   *
   *          ^ 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

而storedPermits消耗的时间如何计算呢？
那就要参考上图了，我先介绍一下上图的一些参数：

• Stable Interval ，稳定状态下一个Permit需要等待的时间，它等于 1 / PPS
• Cold Interval，极度缺乏利用状态下一个Permit需要等待的时间， Cold Interval = Stable Interval * Cold Factor
• Cold Factor,可配置参数
• thresholdPermits，当storedPermits超过这个预置，等待时间将会发生变化
• maxPermits，最大的storedPermits
• warmup period，热启动时长，可配置，它是对图中函数进行[thresholdPermits,maxPermits]的积分

其中有

• Cold Interval = Stable Interval * Cold Factor
• Stable Interval * thresholdPermits = 0.5 * warmup period，没有为什么，就这样规定的
• warmup period = （Stable Interval + Cold Interval）* （maxPermits - thresholdPermits）* 0.5
• maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval).

当我们需要使用storedPermits，
就对我们要消耗的storedPermits对如上图函数做积分就能获得。

那么使用RateLimiter进行热启动时，（QPS/t）的图像应该是什么样的？

首先，已知throttling和stormPermits之间的关系

throttling = 1/QPS = t / q
stormPermits = maxPermits - q

image.png
我们实际上只要求出红色虚线范围内QPS/t的图像就OK了
image.png
但是由于
stormPermits = maxPermits - q，而我们要对q进行分析，因此先对图像进行反转
image.png
为了计算简单，我们假设这根直线的方程是 f(q) = t/q = -ax + b
其中a，b都大于0
那么我们先对f(q)求积分
integral f(q) = -a/2 * q^2 + bq = t
对f(q)求积分自然是等于t的
然后我们用t来表示q
q = （2b [-/+] sqrt(4b^2 - 4at)）/ 2a = g(t)
然后我们对g(t)求导
g'(t) = -1 / (sqrt(4b^2 - 4a*t)) = q / t = qps
image.png