🏆【演算法數據結構專題】「限流演算法專項」帶你認識常用的限流演算法的技術指南（分析篇）
限流
限流的目的是通過對並發訪問/請求進行限速，或者對一個時間窗口內的請求進行限速來保護系統，一旦達到限制速率則可以拒絕服務、排隊或等待、降級等處理
限流一詞常用於電腦網路之中，定義如下：
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.
- 通過控制數據的網路數據的發送或接收速率來防止可能出現的DOS攻擊。而實際的軟體服務過程中，限流也可用於API服務的保護。
- 由於提供服務的電腦資源(包括CPU、記憶體、磁碟及網路頻寬等)是有限的，則其提供的API服務的QPS也是有限的，限流工具就是通過限流演算法對API訪問進行限制，保證服務不會超過其能承受的負載壓力。
主要內容：
常用限流演算法的簡單介紹及比較
常用限流演算法
常用的限流演算法主要包括：
- Token bucket-令牌桶
- Leaky bucket-漏桶
- Fixed window counter-固定窗口計數
- Sliding window log-滑動窗口日誌
- Sliding window counter-滑動窗口計數
- 以上幾種方式其實可以簡單的分為計數演算法、漏桶演算法和令牌桶演算法。
計數限流演算法
無論固定窗口還是滑動窗口核心均是對請求進行計數，區別僅僅在於對於計數時間區間的處理。
固定窗口計數
實現原理
- 固定窗口計數法思想比較簡單，只需要確定兩個參數：計數周期T及周期內最大訪問（調用）數N。請求到達時使用以下流程進行操作：
演算法優點
- 固定窗口計數實現簡單，並且只需要記錄上一個周期起始時間與周期內訪問總數，幾乎不消耗額外的存儲空間。
演算法缺陷
固定窗口計數缺點也非常明顯，在進行周期切換時，上一個周期的訪問總數會立即置為0，這可能導致在進行周期切換時可能出現流量突發，
如圖所示
簡化模型
- 兩個周期T0中a時刻有n1個訪問同時到達;
- 周期T1中b時刻有n2個訪問同時到達;
- n1和n2均小於設定的最高訪問次數N（否則會觸發限流）。
在發生時間間隔切換的時候，在切換的過程中發生並發突變，所以在實際使用過程中，固定窗口計數器存在突破限額N的可能。
- 舉例，限制QPS為10，某用戶在周期切換的前後的0.1秒內，分兩次發送10次請求，根據演算法規則此20次請求可通過限流器，則0.1面秒請求數20，超過每秒最多10次請求的限制。
滑動窗口計數
為解決固定窗口計數帶來的周期切換處流量突發問題，可以使用滑動窗口計數。滑動窗口計算本質上也是固定窗口計數，區別在於將計數周期進行細化。
實現原理
滑動窗口計數法與固定窗口計數法相比較，除了計數周期T及周期內最大訪問（調用）數N兩個參數，增加一個參數M，用於設置周期T內的滑動窗口數。
限流流程如下：
滑動窗口計數在固定窗口計數記錄數據基礎上，需要增加一個長度為M的計數數組，用於記錄在窗口滑動過程中各窗口訪問數據。其流程示例如下：
周期切換問題
滑動窗口針對周期進行了細分，不存在周期到後計數直接重置為0的情況，故不會出現跨周期的流量限制問題。
非計數限流法
常用的限流演算法有兩種：漏桶演算法和令牌桶演算法
- 漏桶演算法思路很簡單，水（請求）先進入到漏桶里，漏桶以一定的速度出水，當水流入速度過大會直接溢出，可以看出漏桶演算法能強行限制數據的傳輸速率。
漏桶限流
實現原理
漏桶限流演算法的實現原理圖：
- 設定漏桶流出速度及漏桶的總容量，在請求到達時判斷當前漏桶容量是否已滿，不滿則可將請求存入桶中，否則拋棄請求。
- 採用一個執行緒以設定的速率取出請求進行處理。
- 需要確定參數為漏桶流出速度r及漏桶容量N
流程如下：
演算法特點
- 漏桶演算法主要特點在於可以保證無論收到請求的速率如何，真正抵達服務方介面的請求速率最大為r，能夠對輸入的請求進行平滑處理。
- 漏桶演算法的缺點也非常明顯，由於其只能以特定速率處理請求，則如何確定該速率就是核心問題，如果速率設置太小則會浪費性能資源，設置太大則會造成資源不足。
- 並且由於速率的設置，無論輸入速率如何波動，均不會體現在服務端，即使資源有空餘，對於突發請求也無法及時處理，故對有突發請求處理需求時，不宜選擇該方法。
令牌桶限流
-
對於很多應用場景來說，除了要求能夠限制數據的平均傳輸速率外，還要求允許某種程度的突發傳輸。這時候漏桶演算法可能就不合適了，令牌桶演算法更為適合。
-
令牌桶演算法的原理是系統會以一個恆定的速度往桶里放入令牌，而如果請求需要被處理，則需要先從桶里獲取一個令牌，當桶里沒有令牌可取時，則拒絕服務。
實現原理
設定令牌桶中添加令牌的速率，並且設置桶中最大可存儲的令牌，當請求到達時，向桶中請求令牌（根據應用需求，可能為1個或多個），若令牌數量滿足要求，則刪除對應數量的令牌並通過當前請求，若桶中令牌數不足則觸發限流規則。
根據描述需要設置的參數為，令牌添加速率r，令牌桶中最大容量N，流程如下：
演算法特點
令牌桶演算法通過設置令牌放入速率可以控制請求通過的平均速度，且由於設置的容量為N的桶對令牌進行快取，可以容忍一定流量的突發。
限流演算法比較
以上提到四種演算法，本小節主要對四種演算法做簡單比較演算法進行對比。
