為什么需要限流？常見的限流算法有哪些

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

作者：程造洋

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

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

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

用戶惡意高頻訪問導致服務(wù)宕機

網(wǎng)頁爬蟲

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

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

2.1 計數(shù)器限流

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

優(yōu)點：實現(xiàn)簡單；

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

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

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

2.2 滑動窗口限流

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

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

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

2.3 漏桶算法限流

漏桶算法思路很簡單：水（請求）先進入到漏桶里，漏桶以一定的速度出水，當水流入速度過大，會在超過桶可接納的容量時直接溢出。漏桶算法其實很簡單，可以粗略的認為就是注水漏水過程，往桶中以任意速率流入水，以一定速率流出水，當水超過桶容量（capacity）則丟棄，因為桶容量是不變的，保證了整體的速率。

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

缺點：漏桶不能有效應對突發(fā)流量，但是能起到平滑突發(fā)流量（整流）的作用，同時不支持動態(tài)擴容。

2.4 令牌桶算法限流

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

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

1）進水口按照某個速度，向桶中放入令牌。

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

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

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

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

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

滴滴的 tollbooth

Guava RateLimiter限流

輕量級流量控制組件sentinel

redis+lua分布式限流組件

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

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

編輯：黃飛