前言
上文針對(duì)RateLimiter的基本實(shí)現(xiàn)做了一個(gè)代碼分析，本文將對(duì)Guava中另一個(gè)RateLimiter實(shí)現(xiàn)：帶預(yù)熱功能的SmoothWarmingUp RateLimiter算法和代碼做一個(gè)簡(jiǎn)單的分析。使用帶預(yù)熱的限流器的需求是很明顯的，如果突發(fā)的大量流量到來，在沒有預(yù)熱的情況下，大量請(qǐng)求會(huì)打到后臺(tái)的服務(wù)，如果后臺(tái)服務(wù)的緩存陳舊，db和io操作耗時(shí)，就有可能會(huì)拖垮后臺(tái)服務(wù)，如果有一個(gè)預(yù)熱階段的話就能夠?qū)⒘髁勘容^平滑的過渡，從而降低后臺(tái)服務(wù)down掉的風(fēng)險(xiǎn)。
變量關(guān)系
（這里基本上是翻譯的Guava RateLimiter的注釋）
我們首先來看一張圖：
有幾個(gè)變量需要說明：
- stableInterval 這個(gè)跟之前的文章描述的有點(diǎn)不同，這里考慮是放行令牌桶令牌的速率，類似于漏桶算法
- coldInterval 這個(gè)是在冷卻情況下發(fā)放令牌的速率，目前取值為：coldInterval = coldFactor * stableInterval
- thresholdPermits 當(dāng)令牌桶中存儲(chǔ)的令牌數(shù)目到達(dá)閾值時(shí)，發(fā)放令牌的速率到達(dá)穩(wěn)定
- maxPermits 令牌桶中存放令牌的最大數(shù)目
- warmUpPeriod 預(yù)熱的時(shí)間長(zhǎng)度，在這段預(yù)熱期內(nèi)令牌桶的存放數(shù)目從maxPermits減少到了thresholdPermits
首先我們來明確幾個(gè)基本點(diǎn)：
- 限流器的狀態(tài)（storedPermits）可以視為圖中的水平線
- 當(dāng)限流器沒有流量進(jìn)來，限流器的狀態(tài)向右變化（最大到maxPermits）
- 當(dāng)限流器發(fā)揮功能，它的狀態(tài)向左變化（最少到0），因?yàn)槲覀儽旧砹钆仆爸杏衧toredPermits，我們首先會(huì)通過它來獲取令牌
- 如果限流器空閑，那么它將會(huì)以一個(gè)恒定速率向右變化，變化的速率是maxPermits/warmupPeriod，這樣保證了限流器令牌數(shù)目從0到maxPermits一共用了warmupPeriod的時(shí)長(zhǎng)，這里也就隱含了stableInterval * maxPermits = warmupPeriod這一層關(guān)系
- 如果限流器使用中，取得K個(gè)令牌的耗時(shí)，等于我們上圖所示的函數(shù)在X個(gè)令牌到X-K個(gè)令牌之間積分（不要害怕）。舉個(gè)例子，我們從maxPermits到了thresholdPermits用的時(shí)間就是這兩個(gè)橫坐標(biāo)之間的積分，也就是上圖中的梯形區(qū)域，這塊區(qū)域本身就等于warmupPeriod
- 從thresholdPermits到0所需要的時(shí)間是warmupPeriod/2，這里信息量有點(diǎn)大，我們可以算一下：
coldFactor目前寫死的3
梯形區(qū)域 = 上面的三角形加上下面的矩形
三角形 = （coldInterval - stableInterval）* (maxPermits - thresholdPermits) / 2 = stableInterval * (maxPermits - thresholdPermits)
矩形 = stableInterval * (maxPermits - thresholdPermits) = 三角形區(qū)域
由梯形區(qū)域 = warmupPeriod 得到 stableInterval * (maxPermits - thresholdPermits ) = warmupPeriod / 2
又由stableInterval * maxPermits = warmupPermits 得到：
stableInterval * thresholdPermits = stableInterval * maxPermits - warmupPeriod / 2 = warmupPeriod / 2
（其實(shí)這里已經(jīng)可以推送出thresholdPermits = maxPermits / 2 了，之前版本的注釋其實(shí)thresholdPermits 就寫的halfPermits，我也不太清楚這里為啥要這么改）
在上面幾點(diǎn)的基礎(chǔ)上，我們就可以建立各個(gè)變量之間的關(guān)系了：
- 已知量：我們創(chuàng)建限流器時(shí)預(yù)設(shè)stableInterval 和warmupPeriod
- 由thresholdPermits * stableInterval = warmupPeriod / 2推出：thresholdPermits = 0.5 * warmupPeriod / stableInterval
- 由warmupPeriod = (stableInterval + coldInterval) * (maxPermits - thresholdPermits) / 2 推出（這里就是通過上底加下底乘高除2來得到梯形面積）：maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval)
其實(shí)你這里把coldInterval = 3 * stableInterval帶進(jìn)去算，你就會(huì)發(fā)現(xiàn) 2 * thresholdPermits = maxPermits
代碼分析
說了這么多，我們?cè)倏创a：
// 初始化設(shè)置限流器
@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
double oldMaxPermits = maxPermits;
//跟之前部分描述的計(jì)算一致
double coldIntervalMicros = stableIntervalMicros * coldFactor;
thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;
maxPermits =
thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);
//slop可以看作是梯形斜邊的斜率，用于計(jì)算threshold到maxPermits之間的限流速率
slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);
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;
}
}
初始化的代碼跟之前我們描述的計(jì)算基本一致。
我們記得之前的文章說過，再調(diào)用acquire之后會(huì)先調(diào)用resync方法去更新桶中的令牌數(shù)量：
void resync(long nowMicros) {
// if nextFreeTicket is in the past, resync to now
if (nowMicros > nextFreeTicketMicros) {
storedPermits = min(maxPermits,
storedPermits
+ (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros());
nextFreeTicketMicros = nowMicros;
}
}
在不預(yù)熱的版本中，coolDownIntervalMicros函數(shù)穩(wěn)定返回stableInterval:
double coolDownIntervalMicros() {
return stableIntervalMicros;
}
而在預(yù)熱版本中，根據(jù)我們之前分析，限流器狀態(tài)往右運(yùn)動(dòng)到maxPermits的速率恒定為maxPermits/warmupPeriod，因此這里
coolDownIntervalMicros函數(shù)的實(shí)現(xiàn)就應(yīng)該是：
double coolDownIntervalMicros() {
return warmupPeriodMicros / maxPermits;
}
其實(shí)我這里大致算了一下，也就等于stableIntervalMicros了
maxPermits
= thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);
= 0.5 * warmupPeriod/stableInterval + 2 * warmupPeriod/(stableInterval + 3*stableInterval)
= warmupPeriod/stableInterval
然后再除，就完事兒了
然后我們?cè)賮砜纯从?jì)算等待時(shí)間的函數(shù)：
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);
try {
this.nextFreeTicketMicros = LongMath.checkedAdd(nextFreeTicketMicros, waitMicros);
} catch (ArithmeticException e) {
this.nextFreeTicketMicros = Long.MAX_VALUE;
}
this.storedPermits -= storedPermitsToSpend;
return returnValue;
}
這里基本的功能流程和描述我在之前的文章也已經(jīng)說明了，這里也不再贅述，大家可以看到真正有變化的就是在這一行
long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
這一行計(jì)算了消費(fèi)令牌桶中storedPermits需要的時(shí)間，我們知道再不預(yù)熱的版本中這里是直接返回了0，那么在預(yù)熱的版本中應(yīng)該是怎樣的呢？
long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
//在閾值以上可用的令牌數(shù)目
double availablePermitsAboveThreshold = storedPermits - thresholdPermits;
long micros = 0;
// measuring the integral on the right part of the function (the climbing line)
//計(jì)算右邊梯形區(qū)域的積分（面積）
if (availablePermitsAboveThreshold > 0.0) {
//計(jì)算在閾值以上能拿的令牌數(shù)目
double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);
//梯形高:permitsAboveThresholdToTake
//梯形下底:permitsToTime(availablePermitsAboveThreshold)
//梯形上帝:permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake)
micros = (long) (permitsAboveThresholdToTake
* (permitsToTime(availablePermitsAboveThreshold)
+ permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake)) / 2.0);
permitsToTake -= permitsAboveThresholdToTake;
}
// measuring the integral on the left part of the function (the horizontal line)
// 加上示意圖左邊的矩形區(qū)域，即放行速率穩(wěn)定在stableInterval
micros += (stableIntervalMicros * permitsToTake);
return micros;
}
//根據(jù)slop和stableIntervalMicros計(jì)算放行的時(shí)間
//可以想象計(jì)算出的結(jié)果為梯形斜邊上的某個(gè)點(diǎn)
private double permitsToTime(double permits) {
return stableIntervalMicros + permits * slope;
}
上面代碼計(jì)算出了獲取storedPermits需要的時(shí)間長(zhǎng)度?？赡艽a和注釋大家看起來比較模糊，我這里也用圖來說明:
測(cè)試
測(cè)試代碼如下：
/**
* @author: Yuanqing Luo
* @date: 2018/11/13
**/
public class GuavaWarmupDemo {
public static void main(String[] args){
RateLimiter limiter = RateLimiter.create(5, 2, TimeUnit.SECONDS);
ExecutorService executorService = Executors.newFixedThreadPool(2);
final long start = System.currentTimeMillis();
for(int i=2;i>0;i--){
executorService.submit(() -> {
int round = 5;
while(round-- > 0){
limiter.acquire();
try {
Thread.sleep(300);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("time:" + (System.currentTimeMillis() - start));
}
});
}
}
}
得到的結(jié)果
time:411
time:964
time:1454
time:1841
time:2162
time:2399
time:2615
time:2801
time:3000
time:3200
可以看到，最開始獲取令牌的時(shí)間在450ms左右，此時(shí)屬于預(yù)熱階段，到第5次之后慢慢穩(wěn)定到了200ms，這與我們?cè)谥霸O(shè)置的QPS=5是一致的。證實(shí)了這個(gè)算法的有效性
結(jié)語(yǔ)
這篇文章作為之前Guava RateLimiter的補(bǔ)充，解釋了Guava中預(yù)熱的限流器的算法與工作方式。最后發(fā)現(xiàn)，還是要學(xué)好數(shù)學(xué)呀。
