解析Java通信：Sentinel中的冷啟動限流算法實(shí)現(xiàn)

冷啟動算法基于令牌桶算法實(shí)現(xiàn)。

令牌桶算法的原理是：按一定的速率往令牌桶中放入令牌，當(dāng)接收到請求時，從令牌桶申請令牌，只有拿到令牌的請求才能通過。當(dāng)令牌桶放滿時，多余的令牌就會被丟棄;當(dāng)令牌桶為空時，請求拿不到令牌就拒絕請求。

例如，想要使用令牌桶算法限制接口的最大QPS為200，那么就要每5毫秒就要生產(chǎn)一個令牌放入令牌桶，且生產(chǎn)令牌放入的速度不變。

冷啟動算法用于控制令牌桶的令牌生產(chǎn)速率，即控制每個令牌生產(chǎn)的時間間隔。

假設(shè)冷啟動時長為10秒，初始狀態(tài)為冷啟動狀態(tài)，限流閾值為200QPS，正常情況下生產(chǎn)令牌的速率應(yīng)該為5毫秒/個，而在冷啟動階段，速率會從最小值上升至5毫秒/個，最小速率與冷啟動系數(shù)有關(guān)，與冷啟動周期時長有關(guān)。

Sentinel與Guava的實(shí)現(xiàn)不同，Sentinel可能是出于對性能的考慮，并不控制每個請求的通過時間間隔，只控制每秒鐘能通過的請求數(shù)。

通過下面這張圖來理解冷啟動算法。

坐標(biāo)軸：

橫坐標(biāo)storedPermits代表存儲桶中的令牌數(shù)量;

縱坐標(biāo)代表獲取一個令牌需要的時間，即請求通過的時間間隔;

stableInterval：穩(wěn)定產(chǎn)生令牌的時間間隔，假設(shè)限流閾值QPS為200，stableInterval的值為5毫秒。

coldInterval：冷啟動產(chǎn)生令牌的最大時間隔間，等于穩(wěn)定產(chǎn)生令牌的時間間隔乘以冷啟動系數(shù)（stableInterval * coldFactor），Sentinel中coldFactor默認(rèn)為3。

warmupPeriod：預(yù)熱時間，即冷啟動周期，對應(yīng)上圖中的梯形面積，Sentinel中默認(rèn)為10秒。

thresholdPermits：從冷啟動到正常的令牌桶中令牌數(shù)量的閾值，當(dāng)令牌桶中的令牌數(shù)量超過該值時，則進(jìn)入冷啟動階段。

由于coldFactor默認(rèn)為3，所以（coldInterval - stableInterval）是stableInterval的兩倍，所以從thresholdPermits到0的時間是從maxPermits到thresholdPermits時間的一半，也就是冷啟動周期的一半。因?yàn)樘菪蔚拿娣e等于warmupPeriod，所以長方形面積是梯形面積的一半，長方形的面積是warmupPeriod / 2。

根據(jù)長方形面積公式：長 * 寬 = 面積

可得：

thresholdPermits = 0.5 * warmupPeriod / stableInterval

maxPermits：最大允許桶中存放的令牌數(shù)。

根據(jù)梯形的面積公式：（上低 + 下低）* 高 / 2

可得：

warmupPeriod = （stableInterval + coldInterval）* （maxPermits - thresholdPermits）/ 2

推出：

maxPermits = thresholdPermits + 2 * warmupPeriod / （stableInterval + coldInterval）

slope：直線的斜率，即生產(chǎn)令牌的速率。

根據(jù)斜率計算公式：（y2-y1） / （x2-x1），可得：

slope = （coldInterval - stableInterval） / （maxPermits - thresholdPermits）

Sentinel每秒生產(chǎn)一次令牌，將新生產(chǎn)的令牌放入令牌桶，并記錄本次生產(chǎn)令牌的時間，當(dāng)下次生產(chǎn)時，根據(jù)當(dāng)前時間與上一次生產(chǎn)令牌的時間間隔計算、以及每個令牌的生產(chǎn)間隔時間計算出本次需要生產(chǎn)的令牌數(shù)。

服務(wù)第一次啟動時，或者接口很久沒有被訪問，都會導(dǎo)致當(dāng)前時間與上次生產(chǎn)令牌的時間相差甚遠(yuǎn)，所以第一次生產(chǎn)令牌將會生產(chǎn)maxPermits個令牌，直接將令牌桶裝滿。由于令牌桶已滿，接下來10s就是冷啟動階段。

由于冷啟動階段生產(chǎn)令牌的間隔時間比較正常消費(fèi)速度慢，因此隨著時間的推移，桶中的剩余令牌數(shù)就會趨近于thresholdPermits，生產(chǎn)令牌的時間間隔也會從coldInterval降低到stableInterval。當(dāng)桶中剩余令牌數(shù)小于thresholdPermits時，冷啟動結(jié)束，系統(tǒng)進(jìn)入穩(wěn)定狀態(tài)，生產(chǎn)令牌的時間間隔為stableInterval，每秒生產(chǎn)的令牌數(shù)就等于QPS。

Sentinel并不會在請求通過時減少令牌桶中的令牌數(shù)量，而是在下一秒生產(chǎn)新的令牌時，再減去桶中與上一秒通過的請求數(shù)相等數(shù)量的令牌，這就是Sentinel官方介紹的令牌自動掉落。

Sentinel沒有在每個請求通過時從令牌桶取走令牌，那么Sentinel是如何控制QPS的呢，我們再來看一張圖：

x1：當(dāng)前令牌桶中超過thresholdPermits的令牌數(shù)量;

y1：y1加上stableInterval等于當(dāng)前令牌生產(chǎn)的時間間隔;

根據(jù)斜率和x1可算出y1：

y1 = slope * x1

y1加上stableInterval即為當(dāng)前的令牌生產(chǎn)速率。

當(dāng)前秒生產(chǎn)令牌的時間間隔為：

slope * （storedTokens - thresholdPermits） + stableInterval

由于：stableInterval = 1.0（1秒） / 限流閾值（count）

所以上述等式 = slope * （storedTokens - thresholdPermits） + 1.0 / count

最后算得當(dāng)前時間戳的QPS閾值為：

1.0 / slope * （storedTokens - thresholdPermits） + 1.0 / count