簡單介紹4種限流算法?。ü潭ù翱谟嫈?shù)器算法、滑動窗口計數(shù)器算法、漏桶算法、令牌桶算法）

作者：架構(gòu)小菜
鏈接：https://www.jianshu.com/p/7987bf427b5b

簡單介紹 4 種非常好理解并且容易實(shí)現(xiàn)的限流算法！

一、固定窗口計數(shù)器算法

規(guī)定我們單位時間處理的請求數(shù)量。比如我們規(guī)定我們的一個接口一分鐘只能訪問10次的話。使用固定窗口計數(shù)器算法的話可以這樣實(shí)現(xiàn)：給定一個變量counter來記錄處理的請求數(shù)量，當(dāng)1分鐘之內(nèi)處理一個請求之后counter 1，1分鐘之內(nèi)的如果counter=100的話，后續(xù)的請求就會被全部拒絕。等到 1分鐘結(jié)束后，將counter回歸成0，重新開始計數(shù)（ps：只要過了一個周期就講counter回歸成0）。

這種限流算法無法保證限流速率，因而無法保證突然激增的流量。比如我們限制一個接口一分鐘只能訪問10次的話，前半分鐘一個請求沒有接收，后半分鐘接收了10個請求。

二、滑動窗口計數(shù)器算法

算的上是固定窗口計數(shù)器算法的升級版?；瑒哟翱谟嫈?shù)器算法相比于固定窗口計數(shù)器算法的優(yōu)化在于：它把時間以一定比例分片。例如我們的借口限流每分鐘處理60個請求，我們可以把 1 分鐘分為60個窗口。每隔1秒移動一次，每個窗口一秒只能處理 不大于 60(請求數(shù))/60（窗口數(shù)） 的請求， 如果當(dāng)前窗口的請求計數(shù)總和超過了限制的數(shù)量的話就不再處理其他請求。

很顯然：當(dāng)滑動窗口的格子劃分的越多，滑動窗口的滾動就越平滑，限流的統(tǒng)計就會越精確。

三、漏桶算法

我們可以把發(fā)請求的動作比作成注水到桶中，我們處理請求的過程可以比喻為漏桶漏水。我們往桶中以任意速率流入水，以一定速率流出水。當(dāng)水超過桶流量則丟棄，因?yàn)橥叭萘渴遣蛔兊模ＷC了整體的速率。如果想要實(shí)現(xiàn)這個算法的話也很簡單，準(zhǔn)備一個隊列用來保存請求，然后我們定期從隊列中拿請求來執(zhí)行就好了。

四、令牌桶算法

令牌桶算法也比較簡單。和漏桶算法算法一樣，我們的主角還是桶（這限流算法和桶過不去?。２贿^現(xiàn)在桶里裝的是令牌了，請求在被處理之前需要拿到一個令牌，請求處理完畢之后將這個令牌丟棄（刪除）。我們根據(jù)限流大小，按照一定的速率往桶里添加令牌。