[[336019]]

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

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

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

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

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

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

通過下面這張圖來理解冷啟動(dòng)算法。

坐標(biāo)軸：

• 橫坐標(biāo)storedPermits代表存儲(chǔ)桶中的令牌數(shù)量;
• 縱坐標(biāo)代表獲取一個(gè)令牌需要的時(shí)間，即請(qǐng)求通過的時(shí)間間隔;

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

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

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

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

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

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

可得：

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ù)斜率計(jì)算公式：(y2-y1) / (x2-x1)，可得：

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

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

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

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

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

Sentinel沒有在每個(gè)請(qǐng)求通過時(shí)從令牌桶取走令牌，那么Sentinel是如何控制QPS的呢，我們?cè)賮砜匆粡垐D：

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

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

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

y1 = slope * x1 

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

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

slope * (storedTokens - thresholdPermits) + stableInterval 

由于：stableInterval = 1.0(1秒) / 限流閾值(count)

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

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

1.0 / slope * (storedTokens - thresholdPermits) + 1.0 / count 

參考文獻(xiàn)：

[1] Guava RateLimiter分析：

https://blog.wangqi.love/articles/Java/Guava%20RateLimiter%E5%88%86%E6%9E%90.html

本文轉(zhuǎn)載自微信公眾號(hào)「Java藝術(shù)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java藝術(shù)公眾號(hào)。