限流系列之RateLimiter解析（一）：SmoothBursty
限流系列之RateLimiter解析（二）：SmoothWarmingUp
限流系列之RateLimiter解析（二）：SmoothWarmingUp
一、简介
SmoothWarmingUp是guava提供的另一个限流工具类，与SmoothBursty不同的是，SmoothWarmingUp在固定速度的基础上增加了预热流程，可以更好的应对突发流量。另外，在初始化和小流量时更慢得进行流量得提供也符合实际的应用场景。
This implements the following function:
^ 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)
在SmoothWarmingUp类的注释中，也针对原理进行的描述，如上图，流量的速度控制interval 和库存令牌数storedPermits存在着一定的数学关系
- 令牌数storedPermits有两个关键值：threshold和max，interval也有两个关键值：stable和cold。当storedPermits介于0–threshold之间时，interval固定为stable；当storePermits介于threshold–max之间时，interval均匀增大。
- perimits从max到threshold的过程称之为warm up，permits从0到max的过程则为cool down。warm up是令牌的消耗过程，cool dowm是令牌的生成。
- 根据微积分计算可以得到，warming up阶段需要的时间就是上图中梯形部分的面积，称之为warm up period。warmUpPeriod = (stable+cold) * (max-threshold) / 2
- 该类中存在两处硬编码：分别为
（1）coldInterval = 3 * stableInterval，那么warmUpPeriod = 2 * stable * (max-threshold)
（2）矩形面积（速率不变期间）是梯形的一半，即stable * threshold = warmUpPeriod/2，可以得到 max = 2 * threshold。所以上图中用halfPermits来表示threshold。
最终得到，warmUpPeriod = stable * max。 - cooldown的时间是矩形面积（from 0 to maxPermits, and height == stableInterval，这时候coolDownPeriod=warmUpPeriod。这也是上述硬编码的目的。
二、创建和初始化
1. 成员变量
private final long warmupPeriodMicros;
private double slope;
private double halfPermits;
本篇只介绍在SmoothWarmingUp里定义的成员变量，从父类继承的成员变量在上一篇对SmoothBursty的介绍里已经提到，不了解的可以回顾。
warmupPeriodMicros如简介中所说warmingUp过程的所需时间，即简介图中的梯形面积。
halfPermits如简介里提到的，是流量速度控制的一个阈值
slope代表令牌从halfPermits到maxPermits期间的interval的变化率，即简介图中的梯形斜边的斜率。slope = (maxPermits - halfPermits) / (coldInterval - stableInterval)
2. RateLimiter#create
public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
checkArgument(warmupPeriod >= 0, "warmupPeriod must not be negative: %s", warmupPeriod);
return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond, warmupPeriod, unit);
}
static RateLimiter create(
SleepingStopwatch stopwatch, double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit);
rateLimiter.setRate(permitsPerSecond);
return rateLimiter;
}
可以看到，基本和SmoothBursty的创建一样，调用构造方法，然后设置速率。
3. SmoothWarmingUp#doSet
@Override
final void doSetRate(double permitsPerSecond, long nowMicros) {
resync(nowMicros);
double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
this.stableIntervalMicros = stableIntervalMicros;
doSetRate(permitsPerSecond, stableIntervalMicros);
}
@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;
if (oldMaxPermits == Double.POSITIVE_INFINITY) {
// if we don't special-case this, we would get storedPermits == NaN, below
storedPermits = 0.0;
} else {
storedPermits = (oldMaxPermits == 0.0)
? maxPermits // initial state is cold
: storedPermits * maxPermits / oldMaxPermits;
}
}
可以看到，整体逻辑就是，
- 根据前面简介中所介绍的数学关系设置成员变量的值
- 和SmoothBursty对比，库存令牌数storePermits还是先按照原速率计算到当前时间后（resync方法），然后等比例缩放。但是对于初始化情况，storePermits初始化为maxPermits而不再是0，这时候流量处理较慢，符合实际需要。
三、限流判断
我们忽略SmoothBursty的解析中已经介绍过的内容，直接进入两者的差异部分。
@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 = nextFreeTicketMicros + waitMicros;
this.storedPermits -= storedPermitsToSpend;
//可以看到，本次请求即使令牌不足，对于预支令牌的时间也不会影响本次请求，智慧影响后续请求
return returnValue;
}
可以看到，实际上的差异就在于storedPermitsToWaitTime方法，此方法在SmoothBursty中固定为0，即不需要耗时，但在SmoothWarmingUp中则不然。
/**
* 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].
*
* <p>This always holds: {@code 0 <= permitsToTake <= storedPermits}
*/
abstract long storedPermitsToWaitTime(double storedPermits, double permitsToTake);
可以先看一下注释了解一下方法的作用：通过消耗库存令牌的时间来实现限流效果。
@Override
long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
//在halfPermits右侧的部分令牌
double availablePermitsAboveHalf = storedPermits - halfPermits;
long micros = 0;
// measuring the integral on the right part of the function (the climbing line)
if (availablePermitsAboveHalf > 0.0) {
//需要消耗的在halfPermits右侧的部分令牌
double permitsAboveHalfToTake = min(availablePermitsAboveHalf, permitsToTake);
//permitsAboveHalfToTake 对应的需要消耗的时间,实际上是梯形面积的计算
micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf)
+ permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0);
//剩下的就是需要在halfPermits左侧消耗的令牌
permitsToTake -= permitsAboveHalfToTake;
}
// measuring the integral on the left part of the function (the horizontal line)
//halfPermits左侧的令牌消耗需要的时间，矩形面积的计算
micros += (stableIntervalMicros * permitsToTake);
return micros;
}
private double permitsToTime(double permits) {
return stableIntervalMicros + permits * slope;
}
storedPermits是库存令牌数量，permitsToTake是需要从库存中消耗的令牌，根据前面的介绍，halfPermits左右的消耗速度是不一样的
stable + /.
interval | / .
| / .
| / .
| / .
| / * .
| / * .
| / * .
stable +----------/ * .
interval | * . * .
| * . * .
| * . * ·
| * . * .
| * . * .
| * . * .
| * . * .
|---------------------------------> storedPermits
(halfPermits) (maxPermits)
A B
还是要原来的图标上，假设令牌数需要从B消耗到A，即B-A=permitsToTake，那么从A-B之间的图形面积就是我们需要计算的时间
那么，计算方式就出来了，分成两部分计算，halfPermits左侧为矩形，右侧为梯形
（1）梯形部分
B = storePermits，
梯形高：storePermits - halfPermits，
上底（长的部分）：stableIntervalMicros + （storePermits - halfPermits）* slope;
下底（短的部分）：stableIntervalMicros
最终：S（梯形）= 0.5 * （stableIntervalMicros + （storePermits - halfPermits）* slope + stableIntervalMicros）* （storePermits - halfPermits）
即代码中的
micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf)
+ permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0);
（2）矩形部分 ： 剩余的storePermits * stableIntervalMicros
这就是storedPermitsToWaitTime计算消耗令牌时间的逻辑。
四、总结
SmoothBursty对于令牌消耗是没有时间的，只要库存令牌充足，限流器对于流量不会有任何延迟效果。
因此，对于流量平稳的场景，SmoothBursty可以满足需要，可以保证流量按照指定的速率(每秒1/stableInterval个)通过。但是对于流量波动场景，譬如极端下，库存达到了上线maxPermits，一旦这时候有突发流量，那么一秒钟的流量通过数木将是：maxPermits+1/stableInterval，对服务的压力极大，可能会出现承受不住的情况，
SmoothWarmingUp则不同，不但生成令牌需要时间，而且即使令牌充足，对于令牌消耗也需要一定的时间，正式通过这种方式保证在突发流量场景下，不会出现大量流量一次性通过压垮服务的场景。
五、版本差异 coldFactor的参数提取
本次对DateLimiter，包括SmoothBursty和SmoothWarmingUp的分析基于的是guava18的版本，后续版本虽然原理和逻辑不变，但其实代码上是有一些差异的，主要的差异为：
coldInterval = 3 * stableInteravl 不再硬编码在SmoothWarmingUp中，而是将倍率提取为一个成员变量coldFactor
因此在代码实现上会有一些细微差异。但是这个成员变量的设置并没有对外提供，而是在DateLimter中对外提供的SmoothWarmingUp的创建和初始化的create方法中进行硬编码为3。
带来的差异主要如下：
- 令牌的阈值不再是maxPermits的一半（halfPermits），因此我们重新取名为threaholdPermits来定义这个阈值。
thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;
maxPermits =
thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);
- stableInterval*maxPermits=warmUpPeriod不再成立，为了保证coolDownPeriod=warmUpPeriod，计算库存令牌时生成速率不再是stableInterval，而是warmUpPeriod/maxPermits。
具体体现在resync方法中，令牌生成速率被提取为了一个单独的方法coolDownIntervalMicros()。
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;
}
}
/**
* Returns the number of microseconds during cool down that we have to wait to get a new permit.
*/
abstract double coolDownIntervalMicros();
@Override
double coolDownIntervalMicros() {
return warmupPeriodMicros / maxPermits;
}