三色漏桶演算法

『壹』 流量整形的流量整形的核心演算法

流量整形的核心演算法有以下兩種，具體採用的技術為GTS（Generic Traffic Shaping），通用流量整形： 漏桶演算法（Leaky Bucket）
漏桶演算法是網路世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經常使用的一種演算法，它的主要目的是控制數據注入到網路的速率，平滑網路上的突發流量。漏桶演算法提供了一種機制，通過它，突發流量可以被整形以便為網路提供一個穩定的流量。 令牌桶演算法（Token Bucket）
有時人們將漏桶演算法與令牌桶演算法錯誤地混淆在一起。而實際上，這兩種演算法具有截然不同的特性並且為截然不同的目的而使用。它們之間最主要的差別在於：漏桶演算法能夠強行限制數據的傳輸速率，而令牌桶演算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
在某些情況下，漏桶演算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的參數，所以即使網路中不存在資源沖突（沒有發生擁塞），漏桶演算法也不能使某一個單獨的流突發到埠速率。因此，漏桶演算法對於存在突發特性的流量來說缺乏效率。而令牌桶演算法則能夠滿足這些具有突發特性的流量。通常，漏桶演算法與令牌桶演算法可以結合起來為網路流量提供更大的控制。

『貳』 GTS的通用流量整形

流量整形(traffic shaping)典型作用是限制流出某一網路的某一連接的流量與突發，使這類報文以比較均勻的速度向外發送。流量整形通常使用緩沖區和令牌桶來完成，當報文的發送速度過快時，首先在緩沖區進行緩存，在令牌桶的控制下再均勻地發送這些被緩沖的文。
流量整形的核心演算法有以下兩種，具體採用的技術為GTS（Generic Traffic Shaping），通用流量整形
漏桶演算法（Leaky Bucket）
漏桶演算法是網路世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經常使用的一種演算法，它的主要目的是控制數據注入到網路的速率，平滑網路上的突發流量。漏桶演算法提供了一種機制，通過它，突發流量可以被整形以便為網路提供一個穩定的流量。
令牌桶演算法（Token Bucket）
有時人們將漏桶演算法與令牌桶演算法錯誤地混淆在一起。而實際上，這兩種演算法具有截然不同的特性並且為截然不同的目的而使用。它們之間最主要的差別在於：漏桶演算法能夠強行限制數據的傳輸速率，而令牌桶演算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
在某些情況下，漏桶演算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的參數，所以即使網路中不存在資源沖突（沒有發生擁塞），漏桶演算法也不能使某一個單獨的流突發到埠速率。因此，漏桶演算法對於存在突發特性的流量來說缺乏效率。而令牌桶演算法則能夠滿足這些具有突發特性的流量。通常，漏桶演算法與令牌桶演算法可以結合起來為網路流量提供更大的控制。
GTS
GTS可以對不規則或不符合預定流量特性的流量進行整形，使得網路上下游之間的帶寬匹配。GTS與CAR一樣均採用了令牌桶技術來控制流量，但主要區別在於：利用CAR進行報文流量控制時對不符合流量特性的報文進行丟棄，而GTS對於不符合流量特性的報文則是進行緩沖減少了報文的丟棄，同時滿足報文的流量特性。
GTS可以對介面上指定的報文流或所有報文進行整形當報文到來的時候，首先對報文進行分類如果報文不需要進行GTS處理，就繼續發送不經過令牌桶的處理；如果報文需要進行 GTS處理，則與令牌桶中的令牌進行比較。
令牌桶按用戶設定的速度向桶中放置令牌，如果令牌桶中有足夠的令牌可以用來發送報文，則報文直接被繼續發送下去，同時令牌桶中的令牌量按報文的長度做相應的減少，當令牌桶中的令牌少到報文不能再發送時，報文將被緩存入GTS隊列中。
當GTS隊列中有報文的時候，GTS按一定的周期從隊列中取出報文進行發送。 每次發送都會與令牌桶中的令牌數作比較。直到令牌桶中的令牌數減少到隊列中的報文不能 再發送或是隊列中的報文全部發送完畢為止。

『叄』 Redis 限制頻繁請求攔截處理

項目運維人員發現NGINX日誌中短時間內有同一IP、同一用戶、同一設備發出的大量請求，比用戶正常行為產生的請求頻率要高出很多，所以有對單位時間內訪問頻次限制的需求。

一般就會在伺服器端將用戶信息和訪問信息做下關聯，以此來實現訪問頻次限制。通常大家都會選擇 Redis 來作為此中間件的存儲介質。

幾種最常用的限流演算法：

固定窗口計數器演算法概念如下：

固定窗口計數器是最為簡單的演算法，但這個演算法有時會讓通過請求量允許為限制的兩倍。考慮如下情況：限制 1 秒內最多通過 5 個請求，在第一個窗口的最後半秒內通過了 5 個請求，第二個窗口的前半秒內又通過了 5 個請求。這樣看來就是在 1 秒內通過了 10 個請求。

滑動窗口計數器演算法概念如下：

滑動窗口計數器是通過將窗口再細分，並且按照時間"滑動"，這種演算法避免了固定窗口計數器帶來的雙倍突發請求，但時間區間的精度越春廳高，演算法所需的空間容量就越大。

漏桶演算法概念如下：

漏桶演算法多使用 隊列 實現，服務的請求會存到隊列中，服務的提供方則按照固定的速率從隊列中取出請求並執行，過多的請求則放在隊列中排隊或直接拒絕。

漏桶演算法的缺陷也很明顯，當短時間內有大量的突發請求時，即便此時伺服器沒有任何負載，每個請求也都得在隊列中等待一段時間才能被響應。

令牌桶演算法概念如下：

令牌桶演算法既能夠將所有的請求平均分布到時間區間內，又能接受伺服器能夠純凱承受范圍內的突發請求，因此是目前使扒褲隱用較為廣泛的一種限流演算法。

業務對此要求不高，所以用了簡單的固定窗口計數器演算法。

『肆』 分布式解決方案之：限流

限流在日常生活中限流很常見，例如去有些景區玩，每天售賣的門票數是有限的，例如 2000 張，即每天最多隻有 2000 個人能進去遊玩。那在我們工程上限流是什麼呢？限制的是 「流」，在不同場景下「流」的定義不同，可以是 每秒請求數、每秒事務處理數、網路流量 等等。通常意義我們說的限流指代的是限制到達系統的並發請求數，使得系統能夠正常的處理部分用戶的請求，來保證系統的穩定性。

日常的業務上有類似秒殺活動、雙十一大促或者突發新聞等場景，用戶的流量突增，後端服務的處理能力是有限的，如果不能處理好突發流量，後端服務很容易就被打垮。另外像爬蟲之類的不正常流量，我們對外暴露的服務都要以最大惡意為前提去防備調用者。我們不清楚調用者會如何調用我們的服務，假設某個調用者開幾十個線程一天二十四小時瘋狂調用你的服務，如果不做啥處理咱服務基本也玩完了，更勝者還有ddos攻擊。

對於很多第三方開放平台來說，不僅僅要防備不正常流量，還要保證資源的公平利用，一些介面資源不可能一直都被一個客戶端占著，也需要保證其他客戶端能正常調用。

計數器限流也就是最簡單的限流演算法就是計數限流了。例如系統能同時處理 100 個請求，保存一個計數器，處理了一個請求，計數器就加一，一個請求處理完畢之後計數器減一。每次請求來的時候看看計數器的值，如果超過閾值就拒絕。計數器的值要是存內存中就算單機限流演算法，如果放在第三方存儲里（例如Redis中）集群機器訪問就算分布式限流演算法。

一般的限流都是為了限制在指定時間間隔內的訪問量，因此還有個演算法叫固定窗口。

它相比於計數限流主要是多了個時間窗口的概念，計數器每過一個時間窗口就重置。規則如下：

這種方式也會面臨一些問題，例如固定窗口臨界問題：假設系統每秒允許 100 個請求，假設第一個時間窗口是 0-1s，在第 0.55s 處一下次湧入 100 個請求，過了 1 秒的時間窗口後計數清零，此時在 1.05 s 的時候又一下次湧入100個請求。雖然窗口內的計數沒超過閾值，但是全局來看在 0.55s-1.05s 這 0.1 秒內湧入了 200 個請求，這其實對於閾值是 100/s 的系統來說是無法接受的。

為了解決這個問題，業界又提出另外一種限流演算法，即滑動窗口限流。

滑動窗口限流解決固定窗口臨界值的問題，可以保證在任意時間窗口內都不會超過閾值。相對於固定窗口，滑動窗口除了需要引入計數器之外還需要記錄時間窗口內每個請求到達的時間點，因此對內存的佔用會比較多。

規則如下，假設時間窗口為 1 秒：

但是滑動窗口和固定窗口都無法解決短時間之內集中流量的沖擊問題。 我們所想的限流場景是： 每秒限制 100 個請求。希望請求每 10ms 來一個，這樣我們的流量處理就很平滑，但是真實場景很難控制請求的頻率，因為可能就算我們設置了1s內只能有100個請求，也可能存在 5ms 內就打滿了閾值的情況。當然對於這種情況還是有變型處理的，例如設置多條限流規則。不僅限制每秒 100 個請求，再設置每 10ms 不超過 2 個，不過帶來的就是比較差的用戶體驗。

而漏桶演算法，可以解決時間窗口類的痛點，使得流量更加平滑。

如下圖所示，水滴持續滴入漏桶中，底部定速流出。如果水滴滴入的速率大於流出的速率，當存水超過桶的大小的時候就會溢出。

規則如下：

水滴對應的就是請求。

與線程池實現的方式方式如出一轍。

面對突發請求，服務的處理速度和平時是一樣的，這並非我們實際想要的。我們希望的是在突發流量時，在保證系統平穩的同時，也要盡可能提升用戶體驗，也就是能更快地處理並響應請求，而不是和正常流量一樣循規蹈矩地處理。

而令牌桶在應對突擊流量的時候，可以更加的「激進」。

令牌桶其實和漏桶的原理類似，只不過漏桶是定速地流出，而令牌桶是定速地往桶里塞入令牌，然後請求只有拿到了令牌才能通過，之後再被伺服器處理。

當然令牌桶的大小也是有限制的，假設桶里的令牌滿了之後，定速生成的令牌會丟棄。

規則：

令牌桶的原理與JUC的Semaphore 信號量很相似，信號量可控制某個資源被同時訪問的個數，其實和拿令牌思想一樣，不同的是一個是拿信號量，一個是拿令牌。信號量用完了返還，而令牌用了不歸還，因為令牌會定時再填充。

對比漏桶演算法可以看出 令牌桶更適合應對突發流量 ，假如桶內有 100 個令牌，那麼這100個令牌可以馬上被取走，而不像漏桶那樣勻速的消費。不過上面批量獲取令牌也會致使一些新的問題出現，比如導致一定范圍內的限流誤差，舉個例子你取了 10 個此時不用，等下一秒再用，那同一時刻集群機器總處理量可能會超過閾值，所以現實中使用時，可能不會去考慮redis頻繁讀取問題，轉而直接採用一次獲取一個令牌的方式，具體採用哪種策略還是要根據真實場景而定。

1、計數器 VS 固定窗口 VS 滑動窗口

2、漏桶演算法 VS 令牌桶演算法

總的來說

單機限流和分布式限流本質上的區別在於 「閾值」 存放的位置，單機限流就是「閥值」存放在單機部署的服務/內存中，但我們的服務往往是集群部署的，因此需要多台機器協同提供限流功能。像上述的計數器或者時間窗口的演算法，可以將計數器存放至 Redis 等分布式 K-V 存儲中。又如滑動窗口的每個請求的時間記錄可以利用 Redis 的 zset 存儲，利用 ZREMRANGEBYSCORE 刪除時間窗口之外的數據，再用 ZCARD 計數，

可以看到，每個限流都有個閾值，這個閾值如何定是個難點。定大了伺服器可能頂不住，定小了就「誤殺」了，沒有資源利用最大化，對用戶體驗不好。一般的做法是限流上線之後先預估個大概的閾值，然後不執行真正的限流操作，而是採取日誌記錄方式，對日誌進行分析查看限流的效果，然後調整閾值，推算出集群總的處理能力，和每台機子的處理能力(方便擴縮容)。然後將線上的流量進行重放，測試真正的限流效果，最終閾值確定，然後上線。

其實真實的業務場景很復雜，需要限流的條件和資源很多，每個資源限流要求還不一樣。

一般而言，我們不需要自己實現限流演算法來達到限流的目的，不管是接入層限流還是細粒度的介面限流，都有現成的輪子使用，其實現也是用了上述我們所說的限流演算法。

具體的使用還是很簡單的，有興趣的同學可以自行搜索，對內部實現感興趣的同學可以下個源碼看看，學習下生產級別的限流是如何實現的。

限流具體應用到工程還是有很多點需要考慮的，並且限流只是保證系統穩定性中的一個環節，還需要配合降級、熔斷等相關內容。