[[336019]]

冷啟動算法基于令牌桶算法實現。

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

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

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

假設冷啟動時長為10秒，初始狀態為冷啟動狀態，限流閾值為200QPS，正常情況下生產令牌的速率應該為5毫秒/個，而在冷啟動階段，速率會從最小值上升至5毫秒/個，最小速率與冷啟動系數有關，與冷啟動周期時長有關。

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

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

坐標軸：

• 橫坐標storedPermits代表存儲桶中的令牌數量;
• 縱坐標代表獲取一個令牌需要的時間，即請求通過的時間間隔;

stableInterval：穩定產生令牌的時間間隔，假設限流閾值QPS為200，stableInterval的值為5毫秒。

coldInterval：冷啟動產生令牌的最大時間隔間，等于穩定產生令牌的時間間隔乘以冷啟動系數(stableInterval * coldFactor)，Sentinel中coldFactor默認為3。

warmupPeriod：預熱時間，即冷啟動周期，對應上圖中的梯形面積，Sentinel中默認為10秒。

thresholdPermits：從冷啟動到正常的令牌桶中令牌數量的閾值，當令牌桶中的令牌數量超過該值時，則進入冷啟動階段。

由于coldFactor默認為3，所以(coldInterval - stableInterval)是stableInterval的兩倍，所以從thresholdPermits到0的時間是從maxPermits到thresholdPermits時間的一半，也就是冷啟動周期的一半。因為梯形的面積等于warmupPeriod，所以長方形面積是梯形面積的一半，長方形的面積是warmupPeriod / 2。

根據長方形面積公式：長 * 寬 = 面積

可得：

thresholdPermits = 0.5 * warmupPeriod / stableInterval 

maxPermits：最大允許桶中存放的令牌數。

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

可得：

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

推出：

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

slope：直線的斜率，即生產令牌的速率。

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

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

Sentinel每秒生產一次令牌，將新生產的令牌放入令牌桶，并記錄本次生產令牌的時間，當下次生產時，根據當前時間與上一次生產令牌的時間間隔計算、以及每個令牌的生產間隔時間計算出本次需要生產的令牌數。

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

由于冷啟動階段生產令牌的間隔時間比較正常消費速度慢，因此隨著時間的推移，桶中的剩余令牌數就會趨近于thresholdPermits，生產令牌的時間間隔也會從coldInterval降低到stableInterval。當桶中剩余令牌數小于thresholdPermits時，冷啟動結束，系統進入穩定狀態，生產令牌的時間間隔為stableInterval，每秒生產的令牌數就等于QPS。

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

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

x1：當前令牌桶中超過thresholdPermits的令牌數量;

y1：y1加上stableInterval等于當前令牌生產的時間間隔;

根據斜率和x1可算出y1：

y1 = slope * x1 

y1加上stableInterval即為當前的令牌生產速率。

當前秒生產令牌的時間間隔為：

slope * (storedTokens - thresholdPermits) + stableInterval 

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

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

最后算得當前時間戳的QPS閾值為：

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

參考文獻：

[1] Guava RateLimiter分析：

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

本文轉載自微信公眾號「Java藝術」，可以通過以下二維碼關注。轉載本文請聯系Java藝術公眾號。