我們常見的限流算法有四種：計數器（固定視窗）算法、滑動視窗算法、漏桶算法、令牌桶算法。
為什麼要限流
資源是有限的，我們的系統的處理能力也是有限的，對于那些已經超出系統處理能力的請求我們應該盡可能早的識别出來并讓其等待或拒絕這些請求。
如果當大流量進入系統的時候不進行限流，那麼将超出系統的負載，這種情況會導緻服務異常、當機等情況的出現。
常見的四種限流算法
1.計數器算法
計數器算法是限流算法裡最簡單也是最容易實作的一種算法。
比如我們規定，對于A接口來說，我們1分鐘的通路次數不能超過100個。那麼我們可以設定一個計數器counter，每當一個請求過來的時候，counter就加1，如果counter的值大于100并且該請求與第一個請求的間隔時間還在1分鐘之内，那麼說明請求數過多。
如果該請求與第一個請求的間隔時間大于1分鐘，且counter的值還在限流範圍内，那麼就重置 counter，具體算法的示意圖如下：
這個算法雖然簡單，但是有一個十分緻命的問題，那就是臨界問題，我們看下圖：
通過上圖我們可以看到，假設有一個惡意使用者，他在0:59時，瞬間發送了100個請求，并且1:00又瞬間發送了100個請求，那麼其實這個使用者在 1秒裡面，瞬間發送了200個請求。
我們剛才規定的是1分鐘最多100個請求，也就是每秒鐘最多1.7個請求，使用者通過在時間視窗的重置節點處突發請求， 可以瞬間超過我們的速率限制。使用者有可能通過算法的這個漏洞，瞬間壓垮我們的系統。
導緻這個問題出現的原因是我們統計的精度太低。
是以就有了下面的算法滑動視窗算法。
2.滑動視窗
滑動視窗，又稱rolling window。如果學過TCP網絡協定的話，那麼一定對滑動視窗這個名詞不會陌生。
下面這張圖，很好地解釋了滑動視窗算法：
在上圖中，整個紅色的矩形框表示一個時間視窗，在我們的例子中，一個時間視窗就是一分鐘。然後我們将時間視窗進行劃分，比如圖中，我們就将滑動視窗劃成了6格，是以每格代表的是10秒鐘。每過10秒鐘，我們的時間視窗就會往右滑動一格。每一個格子都有自己獨立的計數器counter，比如當一個請求 在0:35秒的時候到達，那麼0:30~0:39對應的counter就會加1。
那麼滑動視窗怎麼解決之前的臨界問題的呢？我們可以看上圖，0:59到達的100個請求會落在灰色的格子中，而1:00到達的請求會落在橘黃色的格子中。當時間到達1:00時，我們的視窗會往右移動一格，那麼此時時間視窗内的總請求數量一共是200個，超過了限定的100個，是以此時能夠檢測出來觸發了限流。
我們可以發現，計數器算法其實就是滑動視窗算法。隻是它沒有對時間視窗做進一步地劃分，是以隻有1格。
是以，當滑動視窗的格子劃分的越多，那麼滑動視窗的滾動就越平滑，限流的統計就會越精确。
3.漏桶算法
漏桶算法(Leaky Bucket)是網絡世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經常使用的一種算法，它的主要目的是控制資料注入到網絡的速率，平滑網絡上的突發流量。漏桶算法提供了一種機制，通過它，突發流量可以被整形以便為網絡提供一個穩定的流量。
在網絡中，漏桶算法可以控制端口的流量輸出速率，平滑網絡上的突發流量，實作流量整形，進而為網絡提供一個穩定的流量。
漏桶算法思路很簡單，水（請求）先進入到漏桶裡，漏桶以一定的速度出水，當水流入速度過大會直接溢出，可以看出漏桶算法能強行限制資料的傳輸速率。
漏桶算法有以下特點：
- 漏桶具有固定容量，出水速率是固定常量（流出請求）
- 如果桶是空的，則不需流出水滴
- 可以以任意速率流入水滴到漏桶（流入請求）
- 如果流入水滴超出了桶的容量，則流入的水滴溢出（新請求被拒絕）
在某些情況下，漏桶算法不能夠有效地使用網絡資源。因為漏桶的漏出速率是固定的參數，是以，即使網絡中不存在資源沖突（沒有發生擁塞），漏桶算法也不能使某一個單獨的流突發到端口速率。是以，漏桶算法對于存在突發特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發特性的流量。
4.令牌桶算法
令牌桶算法是網絡流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。
典型情況下，令牌桶算法用來控制發送到網絡上的資料的數目，并允許突發資料的發送。
大小固定的令牌桶可自行以恒定的速率源源不斷地産生令牌。如果令牌不被消耗，或者被消耗的速度小于産生的速度，令牌就會不斷地增多，直到把桶填滿。後面再産生的令牌就會從桶中溢出。最後桶中可以儲存的最大令牌數永遠不會超過桶的大小。
傳送到令牌桶的資料包需要消耗令牌。不同大小的資料包，消耗的令牌數量不一樣。
令牌桶這種控制機制基于令牌桶中是否存在令牌來訓示什麼時候可以發送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許發送流量。而如果令牌桶中不存在令牌，則不允許發送流量。是以，如果突發門限被合理地配置并且令牌桶中有足夠的令牌，那麼流量就可以以峰值速率發送。
令牌桶算法的基本過程如下：
- 假如使用者配置的平均發送速率為r，則每隔1/r秒一個令牌被加入到桶中
- 假設桶最多可以存發b個令牌。如果令牌到達時令牌桶已經滿了，那麼這個令牌會被丢棄
- 當一個n個位元組的資料包到達時，就從令牌桶中删除n個令牌，并且資料包被發送到網絡
- 如果令牌桶中少于n個令牌，那麼不會删除令牌，并且認為這個資料包在流量限制之外
- 算法允許最長b個位元組的突發，但從長期運作結果看，資料包的速率被限制成常量r
漏桶算法和令牌桶算法的差別
| 限流政策 | 限流政策 | |
| 漏桶算法 | 漏桶是按照常量固定速率流出請求，流入請求速率任意，當流入的請求數累積到漏桶容量時，則新流入的請求被拒絕 | 漏桶限制的是常量流出速率（即流出速率是一個固定常量值，比如都是 1 的速率流出，而不能一次是 1 ，下次又是 2 ），進而平滑突發流入速率 |
| 令牌桶算法 | 令牌桶是按照固定速率往桶中添加令牌，請求是否被處理需要看桶中令牌是否足夠，當令牌數減為零時則拒絕新的請求 | 令牌桶限制的是平均流入速率（允許突發請求，隻要有令牌就可以處理，支援一次拿 3 個令牌， 4 個令牌），并允許一定程度突發流量 |
漏桶算法與令牌桶算法在表面看起來類似，很容易将兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。漏桶算法與令牌桶算法的差別在于：
- 漏桶算法能夠強行限制資料的傳輸速率。
- 令牌桶算法能夠在限制資料的平均傳輸速率的同時還允許某種程度的突發傳輸。
在某些情況下，漏桶算法不能夠有效地使用網絡資源。因為漏桶的漏出速率是固定的，是以即使網絡中沒有發生擁塞，漏桶算法也不能使某一個單獨的資料流達到端口速率。是以，漏桶算法對于存在突發特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發特性的流量。通常，漏桶算法與令牌桶算法結合起來為網絡流量提供更高效的控制。