常見限流演算法

Ⅰ Golang中的限速器 time/rate

在高並發的系統中，限流已作為必不可少的功能，而常見的限流演算法有：計數器、滑動窗口、令牌桶、漏斗(漏桶)。其中滑動窗口演算法、令牌桶和漏斗演算法應用最為廣泛。

這里不再對計數器演算法和滑動窗口作介紹了，有興趣的同學可以參考其它相關文章。

非常很好理解，就像有一個漏斗容器一樣，漏鬥上面一直往容器里倒水(請求)，漏斗下方以 固定速率 一直流出(消費)。如果漏斗容器滿的情況下，再倒入的水就會溢出，此時表示新的請求將被丟棄。可以看到這種演算法在應對大的突發流量時，會造成部分請求棄用丟失。

可以看出漏斗演算法能強行限制數據的傳輸速率。

令牌桶演算法

從某種意義上來說，令牌演算法是對漏斗演算法的一種改進。對於很多應用場景來說，除了要求能夠限制數據的平均傳輸速率外，還要求允許某種程度的突發情況。這時候漏桶演算法可能就不合適了，令牌桶演算法更為適合。

令牌桶演算法是指一個固定大小的桶，可以存放的令牌的最大個數也是固定的。此演算法以一種 固定速率 不斷的往桶中存放令牌，而每次請求調用前必須先從桶中獲取令牌才可以。否則進行拒絕或等待，直到獲取到有效令牌為止。如果桶內的令牌數量已達到桶的最大允許上限的話，則丟棄令牌。

Golang標准庫中的限制演算法是基於令牌桶演算法(Token Bucket) 實現的，庫名為golang.org/x/time/rate

對於限流器的消費方式有三種，分別為 Allow()、 Wait()和 Reserve()。前兩種內部調用的都是Reserve() ,每個都對應一個XXXN()的方法。如Allow()是AllowN(t, 1)的簡寫方式。

主要用來限速控制並發事件，採用令牌池演算法實現。

使用 NewLimiter(r Limit, b int) 函數創建限速器，令牌桶容量為b。初始化狀態下桶是滿的，即桶里裝有b 個令牌，以後再以每秒往裡面填充 r 個令牌。

允許聲明容量為0的限速器，此時將會拒絕所有操作。

// As a special case, if r == Inf (the infinite rate), b is ignored.
有一種特殊情況，就是 r == Inf 時，此時b參數將被忽略。

Limiter 提供了三個主要函數 Allow, Reserve, 和 Wait. 大部分時候使用Wait。其中 AllowN, ReserveN 和 WaitN 允許消費n個令牌。

每個方法都可以消費一個令牌，當沒有可用令牌時，三個方法的處理方式不一樣

AllowN方法表示，截止在某一時刻，目前桶中數目是否至少為n個。如果條件滿足，則從桶中消費n個token，同時返回true。反之不消費Token，返回false。

使用場景：一般用在如果請求速率過快，直接拒絕請求的情況

輸出

當使用Wait方法消費Token時，如果此時桶內Token數量不足(小於N)，那麼Wait方法將會阻塞一段時間，直至Token滿足條件。否則直接返回。
// 可以看到Wait方法有一個context參數。我們可以設置context的Deadline或者Timeout，來決定此次Wait的最長時間。

輸出

// 此方法有一點復雜，它返回的是一個*Reservation類型，後續操作主要針對的全是這個類型
// 判斷限制器是否能夠在指定時間提供指定N個請求令牌。
// 如果Reservation.OK()為true，則表示需要等待一段時間才可以提供，其中Reservation.Delay()返回需要的延時時間。
// 如果Reservation.OK()為false,則Delay返回InfDuration, 此時不想等待的話，可以調用 Cancel()取消此次操作並歸還使用的token

輸出

https://www.cyhone.com/articles/analisys-of-golang-rate/
https://zhuanlan.hu.com/p/100594314
https://www.jianshu.com/p/1ecb513f7632
https://studygolang.com/articles/10148

Ⅱ 限流策略

在開發高並發系統時，為了保證系統的高可用和穩定性，常見的有以下幾種策略：

一般來說，限流的常用處理手段有：

計數器是一種比較簡單粗暴的限流演算法：
在一段時間間隔內，對請求進行計數，與閥值進行比較判斷是否需要限流，一旦到了時間臨界點，將計數器清零。

計數器演算法存在「時間臨界點」缺陷。比如每一分鍾限制100個請求，可以在00:00:00-00:00:58秒裡面都沒有請求，在00:00:59瞬間發送100個請求，這個對於演算法來是允許的，然後在00:01:00再次發送100個請求，意味著在短短1s內發送了200個請求，如果量更大呢，系統可能會承受不住瞬間流量，導致系統崩潰。（如下圖所示）

針對計數器演算法的缺陷，滑動窗口做了優化，將時間進行劃片，並隨著時間流逝，進行移動，固定數量可以移動固定的格子，進行計數並判斷閥值。

格子的具體數量影響滑動窗口演算法的精度，時間片的概念其實不能根本解決臨界點的問題。

原理和計數器類似，不做進一步引申

描述如下：

1、一個固定容量的漏桶，按照固定速率流出水滴
2、如果桶是空的，沒有水滴流出
3、水滴以任意速率的流速入桶
4、如果水超過桶的容量，則溢出（請求被丟棄）

通俗的講，我們有一個固定容量的桶，有水流入，也有水流出。對於流進來的水（請求）來說，我們無法預計一共會有多少水流進來，也無法估計流入水的速度。但是對於流出去的水來說，我們這個桶是可以按照固定流出的速率。從而達到流量控制的效果。

由於漏桶的出水的速率是恆定的，如果爆發了大流量的話，將會有大量的請求被丟棄（溢出），為了解決這個問題，令牌桶進行了演算法改進，演算法描述如下：

1、有一個固定容量的桶，桶一開始是空的。
2、以固定的速率向桶內填充令牌，到達桶的容量後，多餘令牌將被丟棄。
3、每一個請求過來，就會嘗試從令牌桶中移除一個令牌，如果沒有令牌，請求無法通過。

在正常請求下，桶中會積累一定量的令牌，這就使這個演算法支持一定程度的大流量訪問。也就是說，如果桶中有100個令牌，那就可以瞬時允許100個請求通過。從這點來說，對用戶比較友好，因此業內大部分用的是該演算法。
當然，不管是令牌桶拿不到令牌被拒絕還是漏桶滿了被拋棄，都是為了保證大部分流量的正常訪問，犧牲少部分流量，這個是合理的。

不同的限流演算法沒有所謂的誰比誰更優，主要還是看具體業務情況，比如令牌桶我們更多的是用於保護自身，而漏桶的限制流速則可以用於保護他人。

Ⅲ 關於API網關（四）——限流

通俗的說，流量控制就是控制用戶請求的策略，主要包括：許可權、限流、流量調度。
許可權上一篇已經講過了，這一篇講限流，下一篇講流量調度。
限流是指限制用戶調用的頻率（QPS/QPM）或者次數。

流量限制，站在用戶或者運營的角度看，最直觀能感受到的作用是——收費
各大主流開放平台的對外API，一般都有一些免費的額度，可以供個人測試用，一旦想大規模調用，就需要付費購買更大的額度（頻率、次數），根據調用次數或者頻率進行收費。一旦超過擁有的額度，就會被限制調用。

其實這才是限流最大的用處，只是用戶或者運營同學無感，所以不太被大多數人了解。
網關後面是各個服務，各個服務的介面通過網關透出去給用戶調用。理論上說，用戶的流量是不可預知的，隨時可能來一波，一旦流量的峰值超過了服務的承載能力，服務就掛了，比如有大新聞發生時的某浪微博，比如前些年的12306.
所以， 網關必須保證，放過去到達後端服務的流量一定不可以超過服務可以承載的上限 。這個上限，是網關和各個服務協商出來的。

由簡到難，限流可以 分為單機限流、單集群限流、全集群限流 。
這里不討論具體的如漏桶、令牌桶等限流演算法，只說概念和思想。

單機限流的思想很簡單，就是每個機器的限流值 x 機器數量 = 總的限流值。
舉個例子，A用戶的QPS限制是100，網關部署了10台機器，那麼，每台機器限制10QPS就可以了。
先說好處，這種方法實現起來非常簡單，每台機器在本地內存計算qps就可以了，超過閾值就拒流。
不過單機限流的缺陷也十分明顯，主要體現在兩點：
 當網關部署的機器數量發生變化時，每台機器的限流值需要根據機器數調整。現實中，因為擴容、縮容、機器宕機等原因，機器數的變化是常有的事。
 單機限流的前提是，每台網關承載的用戶的流量是平均的，但是事實上，在某些時間，用戶的流量並不是完全平均分布在每台機器上的。
舉個例子：
10台機器，每台限qps10，其中3台每台實際qps是15，因為超限導致用戶流量被拒。其餘7台每台qps是7。這樣用戶總的qps = 15 * 3 + 7 * 7 = 94. 用戶qps並沒有超限，但是卻有一部分流量被拒了，這樣就很有問題。
實際上，單台限流的閾值也會設置的稍微大一些，以抵消流量不均的問題。
因為上面的問題， 單機限流通常作為一種兜底的備用手段，大多數時候用的還是集群限流 。

先來看一個示意圖：

相比單機限流，集群限流的計數工作上移到redis集群內進行，解決了單機限流的缺陷。
但是集群限流也不是完美的，因為引入了redis，那麼，當網關和redis之間的網路抖動、redis本身故障時，集群限流就失效了，這時候，還是得依靠單機限流進行兜底。
也就是說， 集群限流 + 單機限流配合，才是一個比穩妥的方案 。

接下來我們來思考這樣一個問題：大型網關一般都是多機房、多地域部署的，當然，後端的服務也是多機房、多地域部署的，在保護服務這一點來說，集群限流是夠用了。但是對用戶來說，還是有一些問題：
比如，用戶購買的QPS上限是30，我們的網關部署在中國北、中、南三個地域，那麼這30QPS怎麼分配呢？
平均肯定不行，用戶的流量可能是明顯不均衡的，比如用戶的業務主要集中在中國北方，那麼用戶的流量大部分都會進入北方的網關，網關如果限制QPS為10的話，用戶肯定來投訴。
那每個地域都限制為30行不行？也不行，如果用戶的流量比較均勻的分布在各個地域，那麼用戶購買了30QPS，實際上可能使用了90QPS，這太虧了。
按照解決單機限流流量不均的思路，搞一個公共的redis集群來計數行不行？
也不行，受限於信號傳播速度和天朝的廣闊疆域，每個流量都計數，肯定不現實，rt太高會導致限流失去意義，帶寬成本也會變得極其昂貴，對redis的規格要求也會很高。總之，很貴還解決不了問題。
有一種巧妙的解決辦法是：本地集群階梯計數 + 全集群檢查。
還是剛才的例子：
限流閾值時90，那麼三個地域各自計數，當本地域的數值達到30時，去其他兩個地域取一次對方當前的計數值，三個地域的計數值加起來，如果超了，告訴另外兩個地域超了，開始拒流。如果沒超，本地QPS每上漲10，重復一次上述的動作。
這樣就能有效的減少與redis的交互次數，同時實現了全地域真·集群限流。
當然，這種全地域集群限流，因為rt和階梯計數間隔的存在，一定是不準的，但是，比單集群限流還是好很多。

當某個用戶流量特別大的時候，redis計數就會遇到典型的熱點key問題，導致redis集群單節點壓力過大， 有兩種辦法可以解決這個問題：打散和抽樣。

打散是指，把熱點key加一些後綴，使其變成多個key，從而hash到不通的redis節點上，均攤壓力。
比如熱點key是abcd，那麼打散後，key變成了abcd1、abcd2、abcd3、abcd4。技術時，輪流加1、2、3、4的後綴就可以了。

抽樣是指，針對熱點key，不是每個每個請求到來時都進行計數，而是進行一個抽樣，比如每10個請求記一次數，這樣redis的壓力就會降低到十分之一。

說著把流量調度的也說完了哈哈，那下一篇再說說監控好了，順便推一下我現在在用的國產網關：GOKU，來自Eolinker。我覺得比KONG好用，感興趣的同學可以自行去了解一下。
www.eolinker.com

Ⅳ 限流演算法

計數器是一種最簡單限流演算法，其原理就是：在一段時間間隔內，對請求進行計數，與閥值進行比較判斷是否需要限流，一旦到了時間臨界點，將計數器清零。
這種方法雖然簡單，但也有個大問題就是沒有很好的處理單位時間的邊界。

滑動窗口是針對計數器存在的臨界點缺陷，所謂 滑動窗口（Sliding window） 是一種流量控制技術，這個詞出現在 TCP 協議中。滑動窗口把固定時間片進行劃分，並且隨著時間的流逝，進行移動，固定數量的可以移動的格子，進行計數並判斷閥值。
假設一個時間窗口是一分鍾，每個時間窗口有 6 個格子，每個格子是 10 秒鍾。每過 10 秒鍾時間窗口向右移動一格。我們為每個格子都設置一個獨立的計數器 Counter，假如一個請求在 0:45 訪問了那麼我們將第五個格子的計數器 +1（也是就是 0:40~0:50），在判斷限流的時候需要把所有格子的計數加起來和設定的頻次進行比較即可。
想讓限流做的更精確只需要劃分更多的格子就可以了，為了更精確我們也不知道到底該設置多少個格子，格子的數量影響著滑動窗口演算法的精度，依然有時間片的概念，無法根本解決臨界點問題。

漏桶演算法（Leaky Bucket），原理就是一個固定容量的漏桶，按照固定速率流出水滴。用過水龍頭都知道，打開龍頭開關水就會流下滴到水桶里，而漏桶指的是水桶下面有個漏洞可以出水。如果水龍頭開的特別大那麼水流速就會過大，這樣就可能導致水桶的水滿瞭然後溢出。
一個固定容量的桶，有水流進來，也有水流出去。對於流進來的水來說，我們無法預計一共有多少水會流進來，也無法預計水流的速度。但是對於流出去的水來說，這個桶可以固定水流出的速率（處理速度），從而達到 流量整形 和 流量控制 的效果。
漏桶演算法有以下特點：

漏桶限制的是常量流出速率（即流出速率是一個固定常量值），所以最大的速率就是出水的速率，不能出現突發流量。

令牌桶演算法（Token Bucket）是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種演算法。典型情況下，令牌桶演算法用來控制發送到網路上的數據的數目，並允許突發數據的發送。
我們有一個固定的桶，桶里存放著令牌（token）。一開始桶是空的，系統按固定的時間（rate）往桶里添加令牌，直到桶里的令牌數滿，多餘的請求會被丟棄。當請求來的時候，從桶里移除一個令牌，如果桶是空的則拒絕請求或者阻塞。
令牌桶有以下特點：

令牌桶限制的是平均流入速率（允許突發請求，只要有令牌就可以處理，支持一次拿3個令牌，4個令牌...），並允許一定程度突發流量。

參考：
https://mp.weixin.qq.com/s/GOZkM2PGctqim4sp_uIEsg
https://mp.weixin.qq.com/s/-wU7SA8Hjh1Y2vOySdgGJw

Ⅳ 分布式組件-Sentinel-常見流量控制演算法

在指定周期內累加訪問次數，當訪問次數達到設定的閾值時，觸發限流策略，當進入下一個時間周期時進行訪問次數的清零。

限定每一分鍾能夠處理的總的請求數為100，在第一個一分鍾內，一共請求了60次。接著到第二個一分鍾，counter又從0開始計數，在一分半鍾時，已經達到了最大限流的閾值，這個時候後續的所有請求都會被拒絕。這種演算法可以用在簡訊發送的頻次限制上，比如限制同一個用戶一分鍾之內觸發簡訊發送的次數。

這種演算法存在一個臨界問題，這種演算法針對的是固定周期的累加訪問次數，但是如果伺服器需要做到的是限制每個一分鍾內的訪問量，這種演算法顯然就不適用了，因為計數器演算法無法限制每隔一段時間內的訪問量均不超過閾值。

在第一分鍾的0：58和第二分鍾的1：02這個時間段內，分別出現了100個請求，整體來看就會出現4秒內總的請求量達到200，超出了設置的閾值。

滑動窗口演算法是將時間周期分為N個小周期（窗口），分別記錄每個小周期內訪問次數，然後根據時間將窗口往前滑動並刪除過期的小時間窗口。最終只需要統計滑動窗口范圍內的所有小時間窗口總的計數即可。

將一分鍾拆分為4個小時間窗口，每個小時間窗口最多能夠處理25個請求。並且通過虛線框表示滑動窗口的大小（當前窗口的大小是2，也就是在這個窗口內最多能夠處理50個請求）。同時滑動窗口會隨著時間往前移動，比如前面15s結束之後，窗口會滑動到15s～45s這個范圍，然後在新的窗口中重新統計數據。

由此可見，當滑動窗口的格子劃分的越多，那麼滑動窗口的滾動就越平滑，限流的統計就會越精確。此演算法可以很好的解決固定窗口演算法的臨界問題。

令牌桶是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種演算法。對於每一個請求，都需要從令牌桶中獲得一個令牌，如果沒有獲得令牌，則需要觸發限流策略。

系統會以一個恆定速度（r tokens/sec）往固定容量的令牌桶中放入令牌，如果此時有客戶端請求過來，則需要先從令牌桶中拿到令牌以獲得訪問資格。

假設令牌生成速度是每秒10個，也就等同於QPS=10，此時在請求獲取令牌的時候，會存在三種情況：

• 請求速度大於令牌生成速度：那麼令牌會很快被取完，後續再進來的請求會被限流。

• 請求速度等於令牌生成速度：此時流量處於平穩狀態。

• 請求速度小於令牌生成速度：說明此時系統的並發數並不高，請求能被正常處理。

由於令牌桶有固定的大小，當請求速度小於令牌生成速度時，令牌桶會被填滿。所以令牌桶能夠處理突發流量，也就是在短時間內新增的流量系統能夠正常處理，這是令牌桶的特性。

漏桶限流演算法的主要作用是控制數據注入網路的速度，平滑網路上的突發流量。

在漏桶演算法內部同樣維護一個容器，這個容器會以恆定速度出水，不管上面的水流速度多快，漏桶水滴的流出速度始終保持不變。訪問請求到達時直接放入漏桶，如當前容量已達到上限（限流值），則進行丟棄（觸發限流策略）。漏桶以固定的速率進行釋放訪問請求（即請求通過），直到漏桶為空。實際上消息中間件就使用了漏桶限流的思想，不管生產者的請求量有多大，消息的處理能力取決於消費者。

在漏桶限流演算法中，存在以下幾種可能的情況：

• 請求速度大於漏桶流出水滴的速度：也就是請求數超出當前服務所能處理的極限，將會觸發限流策略。

• 請求速度小於或者等於漏桶流出水滴的速度，也就是服務端的處理能力正好滿足客戶端的請求量，將正常執行。

漏桶限流演算法和令牌桶限流演算法的實現原理相差不大，最大的區別是漏桶無法處理短時間內的突發流量，漏桶限流演算法是一種恆定速度的限流演算法。

Ⅵ 單機限流演算法筆記

限流演算法為了防止問題：並發過高導致內存吃不消，系統崩潰。

計數器

計數器演算法的特點是把系統運行時間劃分為一個一個時間段，每個時間段通過計數器限制請求量，超過了則放棄掉。

這種演算法適合長時間高並發訪問的情況，但是互聯網環境很多時候有點類似潮汐，某些時間點會出現大量並發訪問，其他時間則訪問很少。這會造成臨界問題。

滑動窗口

滑動窗口的特點依然是先把時間劃分為多個小段，然後使用一個時間窗口來掃描時間，請求數沒滿就加入到隊列中，滿了則拋棄。這個演算法看似和計數器差不多，如果時間段設定合理，倒是可以緩解洪峰帶來的損失。區間越小，演算法需要的空間容量越大。

漏斗

這個演算法有2個部分，一個是容器，用來存放「水滴」，另一個就是漏鬥口，用來消費「水滴」，關鍵在於漏鬥口通過控制能處理的最大速率來起到限流作用。這個演算法重點關注的是保護cpu處理的能力，如果設置的漏口過小，則在高峰時期會影響到業務處理的效率。

令牌桶

令牌桶也有一個容器，也有一個控制流量的閥門，但是令牌空關注的是訪問速率，完全放開cpu的限制，這個思路比漏斗要優的地方就是可以處充分利用處理能力，問題就是訪問量的控制如果太寬松，系統也會有承受不住的問題。

令牌桶演算法是目前主流的單機限流方案。也有一些框架例如guava，對這個演算法提供了封裝，並且再這個基礎上進一步做了優化。比如 平滑預熱限流 、 平滑突發限流 。

Ⅶ 四川北大青鳥分享分布式限流的運行原理

分布式編程架構技術我們在前幾期的文章中已經給大家簡單分析過很多次了，今天我們就一起來了解一下API網關分布式限流的運行原理都有哪些。
API網關中針對一個API、API分組、接入應用APPID,IP等進行限流。
這些限流條件都將會產生一個限流使用的key，在後續的限流中都是對這個key進行限流。
限流演算法通常在API網關中可以採用令牌桶演算法實現。
必須說明一點的是分布式限流由於有網路的開銷，TPS的支持隔本地限流是有差距的，因此在對於TPS要求很高的場景，建議採用本地限流進行處理。
下面討論我們應該採用redis的哪一種分布式鎖的方案：由於redis事務要得到鎖的效果需要在高TPS時會產生大量的無效的訪問請求，所以不建議在這種場景下使用。
SETNX/EX的鎖方案會產生在過期時間的問題，同時也有非同步復制master數據到slave的問題。
相比lua方案會產生更多的不穩定性。
我建議採用lua的方案來實施分布式鎖，因為都是單進程單線程的執行，因此在TPS上和二種方案沒有大的區別，而且由於只是一個lua腳本在執行，甚至是可能純lua執行可能會有更高的TPS。
當然是lua腳本中可能還是會去設置過期時間，但是應用server宕機並不會影響到redis中的鎖。
當然master非同步復制的問題還是有，但是並不會造成問題，因為數據只會有1個lua腳本執行問題，下一個執行就正常了。
在實現方案的時候使用了Jedis庫，四川java課程http://www.kmbdqn.cn/認為有一些問題在方案的實現層面我已經去做過驗證了，可能也會是讀者的疑問。

Ⅷ 武漢北大青鳥分享分布式限流的運行原理

分布式編程架構技術我們在前幾期的文章中已經給大家簡單分析過很多次了，今天我們就一起來了解一下API網關分布式限流的運行原理都有哪些。
API網關中針對一個API、API分組、接入應用APPID,IP等進行限流。
這些限流條件都將會產生一個限流使用的key，在後續的限流中都是對這個key進行限流。
限流演算法通常在API網關中可以採用令牌桶演算法實現。
必須說明一點的是分布式限流由於有網路的開銷，TPS的支持隔本地限流是有差距的，因此在對於TPS要求很高的場景，建議採用本地限流進行處理。
下面討論我們應該採用redis的哪一種分布式鎖的方案：由於redis事務要得到鎖的效果需要在高TPS時會產生大量的無效的訪問請求，所以不建議在這種場景下使用。
SETNX/EX的鎖方案會產生在過期時間的問題，同時也有非同步復制master數據到slave的問題。
相比lua方案會產生更多的不穩定性。
我建議採用lua的方案來實施分布式鎖，因為都是單進程單線程的執行，因此在TPS上和二種方案沒有大的區別，而且由於只是一個lua腳本在執行，甚至是可能純lua執行可能會有更高的TPS。
當然是lua腳本中可能還是會去設置過期時間，但是應用server宕機並不會影響到redis中的鎖。
當然master非同步復制的問題還是有，但是並不會造成問題，因為數據只會有1個lua腳本執行問題，下一個執行就正常了。
在實現方案的時候使用了Jedis庫，武漢java課程http://www.kmbdqn.cn/認為有一些問題在方案的實現層面我已經去做過驗證了，可能也會是讀者的疑問。

Ⅸ 分布式解決方案之：限流

限流在日常生活中限流很常見，例如去有些景區玩，每天售賣的門票數是有限的，例如 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 計數，

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

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

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

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

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