隨著系統(tǒng)服務(wù)的不斷擴(kuò)展，越來越多的用戶訪問讓我們的系統(tǒng)“不堪重負(fù)”，為了防止某些用戶惡意高頻的訪問接口信息，限流（流量限速 Rate Limit）應(yīng)運(yùn)而生，這時(shí)候選擇一個(gè)合適的限流算法也就尤為重要。

作者：程造洋

單位：中國移動(dòng)智慧家庭運(yùn)營中心智慧互聯(lián)產(chǎn)品部

Part 01 ●為什么需要限流呢？●

大量正常用戶高頻訪問導(dǎo)致服務(wù)器宕機(jī)

用戶惡意高頻訪問導(dǎo)致服務(wù)宕機(jī)

網(wǎng)頁爬蟲

對(duì)于這些情況我們需要對(duì)用戶的訪問進(jìn)行限流訪問，限流的目的是保護(hù)服務(wù)節(jié)點(diǎn)或集群底層的存儲(chǔ)資源，防止調(diào)用方過度使用服務(wù)，引起系統(tǒng)崩潰，或者某個(gè)調(diào)用方過度的使用某個(gè)服務(wù)，導(dǎo)致其他服務(wù)的不可用，為了維持系統(tǒng)的穩(wěn)定性和可用性，限流刻不容緩。

Part 02 ●常見的限流算法介紹●

2.1 計(jì)數(shù)器限流

計(jì)數(shù)器法是限流算法里最簡(jiǎn)單也是最容易實(shí)現(xiàn)的一種算法，具體規(guī)則為：在指定周期內(nèi)累加訪問次數(shù)，當(dāng)訪問的次數(shù)達(dá)到我們?cè)O(shè)定的閾值時(shí)，觸發(fā)限流策略，當(dāng)進(jìn)入下一個(gè)時(shí)間周期時(shí)會(huì)將訪問次數(shù)重新清零。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單；

缺點(diǎn)：突刺現(xiàn)象，如果設(shè)置每分鐘的并發(fā)限制數(shù)量為100，在單位時(shí)間1分鐘內(nèi)的前1s，通過了100個(gè)請(qǐng)求，則后面的59s都無法接受任何請(qǐng)求，也就無法應(yīng)對(duì)短時(shí)間高并發(fā)，存在一定的局限性。

舉例：假設(shè)有一個(gè)惡意用戶，他在0:59時(shí)，瞬間發(fā)送了100個(gè)請(qǐng)求，并且1:00又瞬間發(fā)送了100個(gè)請(qǐng)求，那么其實(shí)這個(gè)用戶在 1秒里面，瞬間發(fā)送了200個(gè)請(qǐng)求。

我們剛才規(guī)定的是1分鐘最多100個(gè)請(qǐng)求（規(guī)劃的吞吐量），也就是每秒鐘最多1.7個(gè)請(qǐng)求，用戶通過在時(shí)間窗口的重置節(jié)點(diǎn)處突發(fā)請(qǐng)求， 可以瞬間突破我們的限流限制。用戶有可能通過算法的這個(gè)漏洞，瞬間壓垮我們的應(yīng)用。

2.2 滑動(dòng)窗口限流

在了解滑動(dòng)窗口之前我們需要先了解一下固定窗口，規(guī)定：我們單位時(shí)間處理的請(qǐng)求數(shù)量比如我們規(guī)定我們的一個(gè)接口一分鐘只能訪問10次的話。使用固定窗口計(jì)數(shù)器算法的話可以這樣實(shí)現(xiàn)：給定一個(gè)變量counter來記錄處理的請(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ù)。

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

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

2.3 漏桶算法限流

漏桶算法思路很簡(jiǎn)單：水（請(qǐng)求）先進(jìn)入到漏桶里，漏桶以一定的速度出水，當(dāng)水流入速度過大，會(huì)在超過桶可接納的容量時(shí)直接溢出。漏桶算法其實(shí)很簡(jiǎn)單，可以粗略的認(rèn)為就是注水漏水過程，往桶中以任意速率流入水，以一定速率流出水，當(dāng)水超過桶容量（capacity）則丟棄，因?yàn)橥叭萘渴遣蛔兊?，保證了整體的速率。

優(yōu)點(diǎn)：削峰，有大量流量進(jìn)入時(shí)，會(huì)發(fā)生溢出，從而限流保護(hù)服務(wù)可用；緩沖，不至于直接請(qǐng)求到服務(wù)器，緩沖壓力；

缺點(diǎn)：漏桶不能有效應(yīng)對(duì)突發(fā)流量，但是能起到平滑突發(fā)流量（整流）的作用，同時(shí)不支持動(dòng)態(tài)擴(kuò)容。

2.4 令牌桶算法限流

令牌桶算法以一個(gè)設(shè)定的速率產(chǎn)生令牌并放入令牌桶中，每次請(qǐng)求都得申請(qǐng)令牌，如果令牌數(shù)量不足，則拒絕請(qǐng)求。令牌桶算法中新請(qǐng)求到來時(shí)會(huì)從桶里拿走一個(gè)令牌，如果桶內(nèi)沒有令牌可拿，就拒絕服務(wù)。當(dāng)然，令牌的數(shù)量也是有上限的。令牌的數(shù)量與時(shí)間和發(fā)放速率強(qiáng)相關(guān)，時(shí)間流逝的時(shí)間越長(zhǎng)，會(huì)不斷往桶里加入越多的令牌，如果令牌發(fā)放的速度比申請(qǐng)速度快，令牌桶會(huì)放滿令牌，直到令牌占滿整個(gè)令牌桶，如下圖所示。

令牌桶限流大致的規(guī)則如下：

1）進(jìn)水口按照某個(gè)速度，向桶中放入令牌。

2）令牌的容量是固定的，但是放行的速度不是固定的，只要桶中還有剩余令牌，一旦請(qǐng)求過來就能申請(qǐng)成功，然后放行。

3）如果令牌的發(fā)放速度，慢于請(qǐng)求到來速度，桶內(nèi)就無牌可領(lǐng)，請(qǐng)求就會(huì)被拒絕。

優(yōu)點(diǎn)：可以改變令牌的發(fā)放速度，方便應(yīng)對(duì)突發(fā)出口流量，是選擇較多的限流算法；

缺點(diǎn)：實(shí)現(xiàn)復(fù)雜，相對(duì)于其他限流算法，令牌桶算法的實(shí)現(xiàn)較為復(fù)雜，對(duì)短時(shí)請(qǐng)求難以處理，這種情況下，可以考慮使用漏桶算法。

Part 03 ●常見的限流器，算法庫包以及實(shí)現(xiàn)方案●

滴滴的 tollbooth

Guava RateLimiter限流

輕量級(jí)流量控制組件sentinel

redis+lua分布式限流組件

redission分布式限流采用令牌桶思想和固定時(shí)間窗口

spring cloud gateway集成redis限流，但屬于網(wǎng)關(guān)層限流

編輯：黃飛