限流

限流的目的是通過對并發(fā)訪問/請求進(jìn)行限速，或者對一個(gè)時(shí)間窗口內(nèi)的請求進(jìn)行限速來保護(hù)系統(tǒng)，一旦達(dá)到限制速率則可以拒絕服務(wù)、排隊(duì)或等待、降級等處理

限流一詞常用于計(jì)算機(jī)網(wǎng)絡(luò)之中，定義如下：

In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks.

• 通過控制數(shù)據(jù)的網(wǎng)絡(luò)數(shù)據(jù)的發(fā)送或接收速率來防止可能出現(xiàn)的DOS攻擊。而實(shí)際的軟件服務(wù)過程中，限流也可用于API服務(wù)的保護(hù)。
• 由于提供服務(wù)的計(jì)算機(jī)資源(包括CPU、內(nèi)存、磁盤及網(wǎng)絡(luò)帶寬等)是有限的，則其提供的API服務(wù)的QPS也是有限的，限流工具就是通過限流算法對API訪問進(jìn)行限制，保證服務(wù)不會超過其能承受的負(fù)載壓力。

主要內(nèi)容：

常用限流算法的簡單介紹及比較

常用限流算法

常用的限流算法主要包括：

• Token bucket-令牌桶
• Leaky bucket-漏桶
• Fixed window counter-固定窗口計(jì)數(shù)
• Sliding window log-滑動窗口日志
• Sliding window counter-滑動窗口計(jì)數(shù)
• 以上幾種方式其實(shí)可以簡單的分為計(jì)數(shù)算法、漏桶算法和令牌桶算法。

計(jì)數(shù)限流算法

無論固定窗口還是滑動窗口核心均是對請求進(jìn)行計(jì)數(shù)，區(qū)別僅僅在于對于計(jì)數(shù)時(shí)間區(qū)間的處理。

固定窗口計(jì)數(shù)

實(shí)現(xiàn)原理

• 固定窗口計(jì)數(shù)法思想比較簡單，只需要確定兩個(gè)參數(shù)：計(jì)數(shù)周期T及周期內(nèi)最大訪問（調(diào)用）數(shù)N。請求到達(dá)時(shí)使用以下流程進(jìn)行操作：

算法優(yōu)點(diǎn)

• 固定窗口計(jì)數(shù)實(shí)現(xiàn)簡單，并且只需要記錄上一個(gè)周期起始時(shí)間與周期內(nèi)訪問總數(shù)，幾乎不消耗額外的存儲空間。

算法缺陷

固定窗口計(jì)數(shù)缺點(diǎn)也非常明顯，在進(jìn)行周期切換時(shí)，上一個(gè)周期的訪問總數(shù)會立即置為0，這可能導(dǎo)致在進(jìn)行周期切換時(shí)可能出現(xiàn)流量突發(fā)，

如圖所示

image

簡化模型

• 兩個(gè)周期T0中a時(shí)刻有n1個(gè)訪問同時(shí)到達(dá);
• 周期T1中b時(shí)刻有n2個(gè)訪問同時(shí)到達(dá);
• n1和n2均小于設(shè)定的最高訪問次數(shù)N（否則會觸發(fā)限流）。

在發(fā)生時(shí)間間隔切換的時(shí)候，在切換的過程中發(fā)生并發(fā)突變，所以在實(shí)際使用過程中，固定窗口計(jì)數(shù)器存在突破限額N的可能。

• 舉例，限制QPS為10，某用戶在周期切換的前后的0.1秒內(nèi)，分兩次發(fā)送10次請求，根據(jù)算法規(guī)則此20次請求可通過限流器，則0.1面秒請求數(shù)20，超過每秒最多10次請求的限制。

滑動窗口計(jì)數(shù)

為解決固定窗口計(jì)數(shù)帶來的周期切換處流量突發(fā)問題，可以使用滑動窗口計(jì)數(shù)?；瑒哟翱谟?jì)算本質(zhì)上也是固定窗口計(jì)數(shù)，區(qū)別在于將計(jì)數(shù)周期進(jìn)行細(xì)化。

實(shí)現(xiàn)原理

滑動窗口計(jì)數(shù)法與固定窗口計(jì)數(shù)法相比較，除了計(jì)數(shù)周期T及周期內(nèi)最大訪問（調(diào)用）數(shù)N兩個(gè)參數(shù)，增加一個(gè)參數(shù)M，用于設(shè)置周期T內(nèi)的滑動窗口數(shù)。

限流流程如下：

image

滑動窗口計(jì)數(shù)在固定窗口計(jì)數(shù)記錄數(shù)據(jù)基礎(chǔ)上，需要增加一個(gè)長度為M的計(jì)數(shù)數(shù)組，用于記錄在窗口滑動過程中各窗口訪問數(shù)據(jù)。其流程示例如下：

image

周期切換問題

滑動窗口針對周期進(jìn)行了細(xì)分，不存在周期到后計(jì)數(shù)直接重置為0的情況，故不會出現(xiàn)跨周期的流量限制問題。

非計(jì)數(shù)限流法

常用的限流算法有兩種：漏桶算法和令牌桶算法

• 漏桶算法思路很簡單，水（請求）先進(jìn)入到漏桶里，漏桶以一定的速度出水，當(dāng)水流入速度過大會直接溢出，可以看出漏桶算法能強(qiáng)行限制數(shù)據(jù)的傳輸速率。

漏桶限流

實(shí)現(xiàn)原理

漏桶限流算法的實(shí)現(xiàn)原理圖：

image

• 設(shè)定漏桶流出速度及漏桶的總?cè)萘?，在請求到達(dá)時(shí)判斷當(dāng)前漏桶容量是否已滿，不滿則可將請求存入桶中，否則拋棄請求。
• 采用一個(gè)線程以設(shè)定的速率取出請求進(jìn)行處理。
• 需要確定參數(shù)為漏桶流出速度r及漏桶容量N

流程如下：

image

算法特點(diǎn)

• 漏桶算法主要特點(diǎn)在于可以保證無論收到請求的速率如何，真正抵達(dá)服務(wù)方接口的請求速率最大為r，能夠?qū)斎氲恼埱筮M(jìn)行平滑處理。
• 漏桶算法的缺點(diǎn)也非常明顯，由于其只能以特定速率處理請求，則如何確定該速率就是核心問題，如果速率設(shè)置太小則會浪費(fèi)性能資源，設(shè)置太大則會造成資源不足。
• 并且由于速率的設(shè)置，無論輸入速率如何波動，均不會體現(xiàn)在服務(wù)端，即使資源有空余，對于突發(fā)請求也無法及時(shí)處理，故對有突發(fā)請求處理需求時(shí)，不宜選擇該方法。

令牌桶限流

• 對于很多應(yīng)用場景來說，除了要求能夠限制數(shù)據(jù)的平均傳輸速率外，還要求允許某種程度的突發(fā)傳輸。這時(shí)候漏桶算法可能就不合適了，令牌桶算法更為適合。

• 令牌桶算法的原理是系統(tǒng)會以一個(gè)恒定的速度往桶里放入令牌，而如果請求需要被處理，則需要先從桶里獲取一個(gè)令牌，當(dāng)桶里沒有令牌可取時(shí)，則拒絕服務(wù)。

實(shí)現(xiàn)原理

設(shè)定令牌桶中添加令牌的速率，并且設(shè)置桶中最大可存儲的令牌，當(dāng)請求到達(dá)時(shí)，向桶中請求令牌（根據(jù)應(yīng)用需求，可能為1個(gè)或多個(gè)），若令牌數(shù)量滿足要求，則刪除對應(yīng)數(shù)量的令牌并通過當(dāng)前請求，若桶中令牌數(shù)不足則觸發(fā)限流規(guī)則。

根據(jù)描述需要設(shè)置的參數(shù)為，令牌添加速率r，令牌桶中最大容量N，流程如下：

image

算法特點(diǎn)

令牌桶算法通過設(shè)置令牌放入速率可以控制請求通過的平均速度，且由于設(shè)置的容量為N的桶對令牌進(jìn)行緩存，可以容忍一定流量的突發(fā)。

限流算法比較

以上提到四種算法，本小節(jié)主要對四種算法做簡單比較算法進(jìn)行對比。

image

image

image

image

image

image

image

image