前言

在高并發(fā)場景下，為避免系統(tǒng)被壓垮，經常會采用限流的方式來控制流量，這對系統(tǒng)的穩(wěn)定性和可靠性至關重要，限流有很多成熟的解決方案，例如Hystrix，今天不聊Hystrix，而是從限流的基本算法進行刨析，理解各算法的優(yōu)劣和使用場景，常用的限流算法主要有以下幾種：

• 計數器法
• 滑動窗口計數法
• 漏桶算法
• 令牌桶算法

計數器法

這種算法最簡單，把時間劃分為窗口，比如1分鐘一個窗口，在一段窗口內只接受固定數量的請求，比如60個，到達窗口結束時重新開一個新窗口

image.png

這種方法最簡單，當然也有個明顯的問題，比如如下圖1min~2min時間段內，如果之前都沒請求只在最后10ms發(fā)生大量請求，此時通過限流機制確實只收了60個，但由于馬上進入第二個窗口，又開始重新計數，馬上又進入大量請求，相當與在一窗口和二窗口切換這段時間內進入了雙倍120個請求，顯然瞬間量超過預期

image.png

滑動窗口計數法

基于上述問題，滑動窗口計數法在計數法之上進行了改進，為了避免上述情況發(fā)生，時間窗口不再是固定的時間段，而是根據時間的流轉動態(tài)的調整窗口，增加更小的粒度來拆分窗口，且窗口隨著時間的移動而移動，說法略微抽象，舉個例子，比如還是控制1分鐘60個請求，再把一分鐘劃分為60小格，每一格一秒，那么每過一秒就可以把窗口向前推一秒，即窗口范圍永遠是1分鐘前到當前時間

如下圖同一場景下，01:59時進入60個請求，假設當前時間到了02:01，進來大量請求，此時實際的窗口為01:01~02:01，計數器判斷出窗口內已大到最大請求量60所以直接觸發(fā)了限流，也就是說直到02:59秒后采能接收新的請求

image.png

漏桶算法

這也是一個經典算法，它的工作原理類似于一個裝滿水的桶，水以恒定的速度從桶底的孔中流出。當有新的水流（數據包）進入桶時，如果桶還沒有滿，則水流會被接納并逐漸流出；如果桶已經滿了，則多余的水流會被溢出，從而達到限流的目的

image.png

這種算法明顯的特點是可以嚴格控制固定時間接收請求的次數，缺點也很明顯：太嚴格了，想想一個一般系統(tǒng)的并發(fā)處理量只是一個平均值，系統(tǒng)的并發(fā)處理能力受硬件網絡等各種情況影響，哪有那么準確的數

使用漏桶算法，你如果把流出速率控制到極限比如每秒1000個，某時系統(tǒng)突然來了1000個請求，系統(tǒng)能勉強能正常處理，但緊接著下一個時間節(jié)點又來了1000個請求你就吃不消了，因為上1000個可能還沒處理完，然后下一秒又來1000個結果系統(tǒng)慢慢就崩潰了

那怎么辦，設小點，比如設500，那么假如突然在某個時間點來了1000個請求，前后并沒有其它大量請求(比如并發(fā)場景)，此時明明系統(tǒng)可以處理這1000個請求，卻白白丟棄了500個。。。

所以漏桶算法適合比較有規(guī)律的請求數或處理能力，對突發(fā)流量場景非常不友好

令牌桶算法

令牌桶算法實現如下

• 令牌生成：系統(tǒng)以一個恒定的速率向桶中添加令牌。
• 桶的容量：桶有一個固定的容量，用于存儲令牌。
• 數據包處理：當數據包到達時，需要從桶中獲取一個令牌。如果有可用的令牌，則數據包被處理；如果沒有足夠的令牌，則數據包被延遲或丟棄。

image.png

令牌桶算法就太適合上述場景了，有一個最大令牌數應對突發(fā)流量，有一個令牌添加速度來控制流量，在上述場景下，可以把令牌數設為1000，這樣在突發(fā)1000請求時由于之前沒有大量請求積累了很多令牌，因此1000個請求大部分都被接收，而令牌耗盡后有一定的生成頻率，又可以防止下一秒又來1000個干崩系統(tǒng)

其實令牌算法更符合系統(tǒng)的實際處理能力，即可以再空閑狀態(tài)下瞬間處理大量請求，但處理這些請求的需要一段時間，所以不能長期處理這么大量的請求

就好比線程池有核心線程和最大線程，就是為了不浪費資源同時又能處理瞬間的高并發(fā)，令牌桶的涉及有異曲同工之妙，而漏桶算法的容量則是為了避免消費積壓，實際關鍵的數據只有流出速率

總結

以上就是常見的限流算法，要說哪個好，只能說沒有最合適的技術，只有最合適的場景，結合實際場景選擇才是最理智的，而每一種結合場景都是個比較難的話題，而每種算法只是盡量合理不能做到絕對合理

擴展

我仔細想了下現實世界是如何實現限流的，馬上就想到了一個最適當的場景：醫(yī)院看病，醫(yī)院看病時醫(yī)院當然也要限流，因為每個診室外面占不了那么多人排隊啊，所以都是在外面等著叫號，叫完號再去里面排隊，而他是怎么限流的? 他沒有固定的算法(就像上面說的每個算法都并不玩?zhèn)?，一般是有個護士看門口排隊的情況，如果人少了就放一些號進去排隊，這是一種根據實際處理情況決定如何控制流量的方式，我想起軟件界的一個詞：背壓，那如果限流是根據實際處理能力來實時決定如何限流，是不是更為合理，但這樣做代價很大，現實中需要個人力一直觀察，代碼里就需要一個很復雜的邏輯實時監(jiān)控處理進度