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

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

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

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

這種限流算法無(wú)法保證限流速率，因而無(wú)法保證突然激增的流量。比如我們限制一個(gè)接口一分鐘只能訪問(wèn)10次的話，前半分鐘一個(gè)請(qǐng)求沒(méi)有接收，后半分鐘接收了10個(gè)請(qǐng)求。

二、滑動(dòng)窗口計(jì)數(shù)器算法

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

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

三、漏桶算法

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

四、令牌桶算法

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