關於Sentinel中冷啟動限流原理WarmUpController
冷啟動
所謂冷啟動，或預熱是指，系統長時間處理低水平請求狀態，當大量請求突然到來時，並非所有請求都放行，而是慢慢的增加請求，目的時防止大量請求沖垮應用，達到保護應用的目的。
Sentinel中冷啟動是采用令牌桶算法實現。
令牌桶算法圖例如下：
預熱模型
Sentinel中的令牌桶算法，是參照Google Guava中的RateLimiter，在學習Sentinel中預熱算法之前，先瞭解下整個預熱模型，如下圖：
Guava中預熱是通過控制令牌的生成時間，而Sentinel中實現不同：
- 不控制每個請求通過的時間間隔，而是控制每秒通過的請求數。
- 在Guava中，冷卻因子coldFactor固定為3，上圖中②是①的兩倍
- Sentinel增加冷卻因子coldFactor的作用，在Sentinel模型中，②是①的(coldFactor-1)倍，coldFactor默認為3，可以通過csp.sentinel.flow.cold.factor參數修改
原理分析
Sentinel中冷啟動對應的FlowRule配置為RuleConstant.CONTROL_BEHAVIOR_WARM_UP,對應的Controller為WarmUpController，首先瞭解其中的屬性和構造方法：
count：FlowRule中設定的閾值warmUpPeriodSec：系統預熱時間，代表上圖中的②coldFactor：冷卻因子，默認為3，表示倍數，即系統最"冷"時(令牌桶飽和時)，令牌生成時間間隔是正常情況下的多少倍warningToken：預警值，表示進入預熱或預熱完畢maxToken：最大可用token值，計算公式：warningToken+(2*時間*閾值)/(1+因子)，默認情況下為warningToken的2倍slope：斜度，(coldFactor-1)/count/(maxToken-warningToken)，用於計算token生成的時間間隔，進而計算當前token生成速度，最終比較token生成速度與消費速度，決定是否限流storedTokens：姑且可以理解為令牌桶中令牌的數量
public class WarmUpController implements TrafficShapingController {
// FlowRule中設置的閾值
protected double count;
// 冷卻因子，默認為3，通過SentinelConfig加載，可以修改
private int coldFactor;
// 預警token數量
protected int warningToken = 0;
// 最大token數量
private int maxToken;
// 斜率，用於計算當前生成token的時間間隔，即生成速率
protected double slope;
// 令牌桶中剩餘令牌數
protected AtomicLong storedTokens = new AtomicLong(0);
// 最後一次添加令牌的時間戳
protected AtomicLong lastFilledTime = new AtomicLong(0);
public WarmUpController(double count, int warmUpPeriodInSec, int coldFactor) {
construct(count, warmUpPeriodInSec, coldFactor);
}
public WarmUpController(double count, int warmUpPeriodInSec) {
construct(count, warmUpPeriodInSec, 3);
}
private void construct(double count, int warmUpPeriodInSec, int coldFactor) {
if (coldFactor <= 1) {
throw new IllegalArgumentException("Cold factor should be larger than 1");
}
this.count = count;
// 默認為3
this.coldFactor = coldFactor;
// thresholdPermits = 0.5 * warmupPeriod / stableInterval.
// warningToken = 100;
// 計算預警token數量
// 例如 count=5，warmUpPeriodInSec=10，coldFactor=3，則waringToken=5*10/2=25
warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1);
// / maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval)
// maxToken = 200
// 最大token數量=25+2*10*5/4=50
maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor));
// slope
// slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits- thresholdPermits);
// 傾斜度=(3-1)/5/(50-25) = 0.016
slope = (coldFactor - 1.0) / count / (maxToken - warningToken);
}
}
舉例說明：
FlowRule設定閾值count=5，即1s內QPS閾值為5，設置的預熱時間默認為10s，即warmUpPeriodSec=10，冷卻因子coldFactor默認為3，即count = 5，coldFactor=3，warmUpPeriodSec=10，則
stableInterval=1/count=200ms，coldInterval=coldFactor*stableInterval=600ms warningToken=warmUpPeriodSec/(coldFactor-1)/stableInterval=(warmUpPeriodSec*count)/(coldFactor-1)=25 maxToken=2warmUpPeriodSec/(stableInterval+coldInterval)+warningToken=warningToken+2warmUpPeriodSeccount/(coldFactor+1)=50 slope=(coldInterval-stableInterval)/(maxToken-warningToken)=(coldFactor-1)/count/(maxToken-warningToken)=0.016
接下來學習，WarmUpController是如何進行限流的，進入canPass()方法:
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
// 獲取當前1s的QPS
long passQps = (long) node.passQps();
// 獲取上一窗口通過的qps
long previousQps = (long) node.previousPassQps();
// 生成和滑落token
syncToken(previousQps);
// 如果進入瞭警戒線，開始調整他的qps
long restToken = storedTokens.get();
// 如果令牌桶中的token數量大於警戒值，說明還未預熱結束，需要判斷token的生成速度和消費速度
if (restToken >= warningToken) {
long aboveToken = restToken - warningToken;
// 消耗的速度要比warning快，但是要比慢
// y軸，當前token生成時間 current interval = restToken*slope+stableInterval
// 計算此時1s內能夠生成token的數量
double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count));
// 判斷token消費速度是否小於生成速度，如果是則正常請求，否則限流
if (passQps + acquireCount <= warningQps) {
return true;
}
} else {
// 預熱結束，直接判斷是否超過設置的閾值
if (passQps + acquireCount <= count) {
return true;
}
}
return false;
}
canPass()方法分為3個階段：
syncToken()：負責令牌的生產和滑落
判斷令牌桶中剩餘令牌數
- 如果剩餘令牌數大於警戒值，說明處於預熱階段，需要比較令牌的生產速率與令牌的消耗速率。若消耗速率大，則限流；否則請求正常通行
仍然以count=5進行舉例，警戒線warningToken=25，maxToken=50
假設令牌桶中剩餘令牌數storedTokens=30，即在預熱范圍內，此時restToken=30，slope=0.016，則aboveToken=30-25=5
由斜率slope推導當前token生成時間間隔：(restToken-warningToken)*slope+stableInterval=5*0.016+1/5=0.28，即280ms生成一個token
此時1s內生成token的數量=1/0.28≈4，即1s內生成4個token
假設當前窗口通過的請求數量passQps=4，acquiredCount=1，此時passQps+acquiredCount=5>4，即令牌消耗速度大於生產速度，則限流
- 如果剩餘令牌數小於警戒值，說明系統已經處於高水位，請求穩定，則直接判斷QPS與閾值，超過閾值則限流
接下來分析Sentinel是如何生產及滑落token的，進入到syncToken()方法：
獲取當前時間秒數currentTime，與lastFilledTime進行比較，之所以取秒數，是因為時間窗口的設定為1s，若兩個時間相等，說明還處於同一秒內，不進行token填充和滑落，避免重復問題
令牌桶中添加token
- 當流量極大，令牌桶中剩餘token遠低於預警值時，添加token
- 處於預熱節點，單令牌的消耗速度小於系統最冷時令牌的生成速度，則添加令牌
通過CAS操作，修改storedToken，並進行令牌扣減
protected void syncToken(long passQps) {
long currentTime = TimeUtil.currentTimeMillis();
// 獲取整秒數
currentTime = currentTime - currentTime % 1000;
// 上一次的操作時間
long oldLastFillTime = lastFilledTime.get();
// 判斷成立，如果小於，說明可能出現瞭時鐘回撥
// 如果等於，說明當前請求都處於同一秒內，則不進行token添加和滑落操作，避免的重復扣減
// 時間窗口的跨度為1s
if (currentTime <= oldLastFillTime) {
return;
}
// token數量
long oldValue = storedTokens.get();
long newValue = coolDownTokens(currentTime, passQps);
// 重置token數量
if (storedTokens.compareAndSet(oldValue, newValue)) {
// token滑落，即token消費
// 減去上一個時間窗口的通過請求數
long currentValue = storedTokens.addAndGet(0 - passQps);
if (currentValue < 0) {
storedTokens.set(0L);
}
// 設置最後添加令牌時間
lastFilledTime.set(currentTime);
}
}
private long coolDownTokens(long currentTime, long passQps) {
long oldValue = storedTokens.get();
long newValue = oldValue;
// 添加令牌的判斷前提條件:
// 當令牌的消耗程度遠遠低於警戒線的時候
if (oldValue < warningToken) {
// 計算過去一段時間內，可以通過的QPS總量
// 初始加載時，令牌數量達到maxToken
newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
} else if (oldValue > warningToken) {
// 處於預熱過程，且消費速度低於冷卻速度，則補充令牌
if (passQps < (int)count / coldFactor) {
newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
}
}
// 當令牌桶滿瞭之後，拋棄多餘的令牌
return Math.min(newValue, maxToken);
}
總結
Sentinel采用令牌桶算法實現預熱限流
系統流量突增，令牌消耗從maxPermits(令牌桶容量)到thresholdPermits(警戒線)所需要的時間，是從警戒線到0的(coldFactor-1)倍，並非其他博客中的2倍。另外，關於預熱模型中②和①的關系，是通過結果反推而來，並沒有找到模型定義的官方文檔。
Sentinel限流是針對某時刻令牌的生成與消耗速度
Sentinel通過比較整秒數，來判斷是否需要進行令牌扣減，並通過CAS操作，保證同一時刻隻能由1個線程成功操作，從而避免多次扣減passQps導致限流失效的問題
以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。