瞬時流量過高，服務被壓垮？
惡意使用者高頻光顧，導致伺服器宕機？
訊息消費過快，導致資料庫壓力過大，效能下降甚至崩潰？
……
在高併發系統中，出於系統保護角度考慮，通常會對流量進行限流；不但在工作中要頻繁使用，而且也是面試中的高頻考點。
今天我們將圖文並茂地對常見的限流演算法分別進行介紹，透過各個演算法的特點，給出限流演算法選型的一些建議，並給出Java語言實現的程式碼示例。
01 固定視窗
固定視窗又稱固定視窗（又稱計數器演算法，Fixed Window）限流演算法，是最簡單的限流演算法，透過在單位時間內維護的計數器來控制該時間單位內的最大訪問量。
假設限制每分鐘請求量不超過60，設定一個計數器，當請求到達時如果計數器到達閾值，則拒絕請求，否則計數器加1；每分鐘重置計數器為0。程式碼實現如下：
public class CounterRateLimiter extends MyRateLimiter { /** * 每秒限制請求數 */ private final long permitsPerSecond； /** * 上一個視窗的開始時間 */ public long timestamp = System。currentTimeMillis（）； /** * 計數器 */ private int counter； public CounterRateLimiter（long permitsPerSecond） { this。permitsPerSecond = permitsPerSecond； } @Override public synchronized boolean tryAcquire（） { long now = System。currentTimeMillis（）； // 視窗內請求數量小於閾值，更新計數放行，否則拒絕請求 if （now - timestamp < 1000） { if （counter < permitsPerSecond） { counter++； return true； } else { return false； } } // 時間視窗過期，重置計數器和時間戳 counter = 0； timestamp = now； return true； }}複製程式碼
固定視窗最大的優點在於
易於實現
；並且
記憶體佔用小
，我們只需要儲存時間視窗中的計數即可；它能夠確保處理更多的最新請求，不會因為舊請求的堆積導致新請求被餓死。當然也面臨著
臨界問題
，當兩個視窗交界處，瞬時流量可能為2n。
02 滑動視窗
為了防止瞬時流量，可以把固定視窗近一步劃分成多個格子，每次向後移動一小格，而不是固定視窗大小，這就是滑動視窗（Sliding Window）。
比如每分鐘可以分為6個10秒中的單元格，每個格子中分別維護一個計數器，視窗每次向前滑動一個單元格。每當請求到達時，只要視窗中所有單元格的計數總和不超過閾值都可以放行。TCP協議中資料包的傳輸，同樣也是採用滑動視窗來進行流量控制。
實現如下：
public class SlidingWindowRateLimiter extends MyRateLimiter { /** * 每分鐘限制請求數 */ private final long permitsPerMinute； /** * 計數器， k-為當前視窗的開始時間值秒，value為當前視窗的計數 */ private final TreeMap
滑動視窗解決了計數器中的瞬時流量高峰問題，其實計數器演算法也是滑動視窗的一種，只不過視窗沒有進行更細粒度單元的劃分。對比計數器可見，當視窗劃分的粒度越細，則流量控制更加精準和嚴格。
不過當視窗中流量到達閾值時，流量會瞬間切斷，在實際應用中我們要的限流效果往往不是把流量一下子掐斷，而是讓流量平滑地進入系統當中。
03 漏桶演算法
如何更加平滑的限流？不妨看看漏桶演算法（Leaky Bucket），請求就像水一樣以任意速度注入漏桶，而桶會按照固定的速率將水漏掉；當注入速度持續大於漏出的速度時，漏桶會變慢，此時新進入的請求將會被丟棄。
限流
和
整形
是漏桶演算法的兩個核心能力。
實現如下：
public class LeakyBucketRateLimiter extends MyRateLimiter { // 桶的容量 private final int capacity； // 漏出速率 private final int permitsPerSecond； // 剩餘水量 private long leftWater； // 上次注入時間 private long timeStamp = System。currentTimeMillis（）； public LeakyBucketRateLimiter（int permitsPerSecond， int capacity） { this。capacity = capacity； this。permitsPerSecond = permitsPerSecond； } @Override public synchronized boolean tryAcquire（） { //1。 計算剩餘水量 long now = System。currentTimeMillis（）； long timeGap = （now - timeStamp） / 1000； leftWater = Math。max（0， leftWater - timeGap * permitsPerSecond）； timeStamp = now； // 如果未滿，則放行；否則限流 if （leftWater < capacity） { leftWater += 1； return true； } return false； }}複製程式碼
這並不是一個完整的漏桶演算法的實現，以上程式碼中只是對流量是否會被拋棄進行校驗，即tryAcquire返回true表示漏桶未滿，否則表示漏桶已滿丟棄請求。
想要以恆定的速率漏出流量，通常還應配合一個FIFO佇列來實現，當tryAcquire返回true時，將請求入隊，然後再以固定頻率從佇列中取出請求進行處理。示例程式碼如下：
@Testpublic void testLeakyBucketRateLimiter（） throws InterruptedException { ScheduledExecutorService scheduledExecutorService = Executors。newSingleThreadScheduledExecutor（）； ExecutorService singleThread = Executors。newSingleThreadExecutor（）； LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter（20， 20）； // 儲存流量的佇列 Queue
漏桶演算法存在目的主要是用來
平滑突發的流量
，提供一種機制來確保網路中的突發流量被整合成平滑穩定的額流量。
不過由於漏桶對流量的控制過於嚴格，在有些場景下
不能充分使用系統資源
，因為漏桶的漏出速率是固定的，即使在某一時刻下游能夠處理更大的流量，漏桶也不允許突發流量透過。
04 令牌桶
如何在夠限制流量速率的前提下，又能夠允許突發流量呢？令牌桶演算法瞭解一下！令牌桶演算法是以恆定速率向令牌桶傳送令牌，請求到達時，嘗試從令牌桶中拿令牌，只有拿到令牌才能夠放行，否則將會被拒絕。
令牌桶具有以下特點：
以恆定的速率發放令牌，假設限流速率為v/s，則表示每1/v秒發放一個令牌
假設令牌桶容量是b，如果令牌桶已滿，則新的令牌會被丟棄
請求能夠透過限流器的前提是令牌桶中有令牌
令牌桶演算法中值得關注的引數有兩個，即限流速率v/s，和令牌桶容量b；速率a表示限流器一般情況下的限流速率，而b則是burst的簡寫，表示限流器允許的最大突發流量。
比如b=10，當令牌桶滿的時候有10個可用令牌，此時允許10個請求同時透過限流器（
允許流量一定程度的突發
），這10個請求瞬間消耗完令牌後，後續的流量只能按照速率r透過限流器。
實現如下：
public class TokenBucketRateLimiter extends MyRateLimiter { /** * 令牌桶的容量「限流器允許的最大突發流量」 */ private final long capacity； /** * 令牌發放速率 */ private final long generatedPerSeconds； /** * 最後一個令牌發放的時間 */ long lastTokenTime = System。currentTimeMillis（）； /** * 當前令牌數量 */ private long currentTokens； public TokenBucketRateLimiter（long generatedPerSeconds， int capacity） { this。generatedPerSeconds = generatedPerSeconds； this。capacity = capacity； } /** * 嘗試獲取令牌 * * @return true表示獲取到令牌，放行；否則為限流 */ @Override public synchronized boolean tryAcquire（） { /** * 計算令牌當前數量 * 請求時間在最後令牌是產生時間相差大於等於額1s（為啥時1s？因為生成令牌的最小時間單位時s），則 * 1。 重新計算令牌桶中的令牌數 * 2。 將最後一個令牌發放時間重置為當前時間 */ long now = System。currentTimeMillis（）； if （now - lastTokenTime >= 1000） { long newPermits = （now - lastTokenTime） / 1000 * generatedPerSeconds； currentTokens = Math。min（currentTokens + newPermits， capacity）； lastTokenTime = now； } if （currentTokens > 0） { currentTokens——； return true； } return false； }}複製程式碼
需要注意的是，非常容易被想到的實現是生產者消費者模式；用一個生產者執行緒定時向阻塞佇列中新增令牌，而試圖透過限流器的執行緒則作為消費者執行緒，只有從阻塞佇列中獲取到令牌，才允許透過限流器。
由於
執行緒排程的不確定性
，在高併發場景時，定時器誤差非常大，同時定時器本身會建立排程執行緒，也會對
系統的效能
產生影響。
05 滑動日誌
滑動日誌是一個比較“冷門”，但是確實好用的限流演算法。滑動日誌限速演算法需要記錄請求的時間戳，通常使用
有序集合
來儲存，我們可以在單個有序集合中跟蹤使用者在一個時間段內所有的請求。
假設我們要限制給定T時間內的請求不超過N，我們只需要儲存最近T時間之內的請求日誌，每當請求到來時判斷最近T時間內的請求總數是否超過閾值。
實現如下：
public class SlidingLogRateLimiter extends MyRateLimiter { /** * 每分鐘限制請求數 */ private static final long PERMITS_PER_MINUTE = 60； /** * 請求日誌計數器， k-為請求的時間（秒），value當前時間的請求數量 */ private final TreeMap
滑動日誌能夠避免突發流量，實現較為精準的限流；同樣
更加靈活，能夠支援更加複雜的限流策略
，如多級限流，每分鐘不超過100次，每小時不超過300次，每天不超過1000次，我們只需要儲存最近24小時所有的請求日誌即可實現。
靈活並不是沒有代價的，帶來的缺點就是
佔用儲存空間要高於其他限流演算法
。
06 分散式限流
以上幾種限流演算法的實現都僅適合單機限流。雖然給每臺機器平均分配限流配額可以達到限流的目的，但是由於機器效能，流量分佈不均以及計算數量動態變化等問題，單機限流在分散式場景中的效果總是差強人意。
分散式限流最簡單的實現就是利用中心化儲存，即將單機限流儲存在本地的資料儲存到同一個儲存空間中，如常見的Redis等。
當然也可以從上層流量入口進行限流，Nginx代理服務就提供了限流模組，同樣能夠實現高效能，精準的限流，其底層是漏桶演算法。
07 總結
固定視窗演算法實現簡單，效能高，但是會有臨界突發流量問題，瞬時流量最大可以達到閾值的2倍。
為了解決臨界突發流量，可以將視窗劃分為多個更細粒度的單元，每次視窗向右移動一個單元，於是便有了滑動視窗演算法。 滑動視窗當流量到達閾值時會瞬間掐斷流量，所以導致流量不夠平滑。
想要達到限流的目的，又不會掐斷流量，使得流量更加平滑？可以考慮漏桶演算法！需要注意的是，漏桶演算法通常配置一個FIFO的佇列使用以達到允許限流的作用。 由於速率固定，即使在某個時刻下游處理能力過剩，也不能得到很好的利用，這是漏桶演算法的一個短板。
限流和瞬時流量其實並不矛盾，在大多數場景中，短時間突發流量系統是完全可以接受的。令牌桶演算法就是不二之選了，令牌桶以固定的速率v產生令牌放入一個固定容量為n的桶中，當請求到達時嘗試從桶中獲取令牌。 當桶滿時，允許最大瞬時流量為n；當桶中沒有剩餘流量時則限流速率最低，為令牌生成的速率v。
如何實現更加靈活的多級限流呢？滑動日誌限流演算法瞭解一下！這裡的日誌則是請求的時間戳，透過計算指定時間段內請求總數來實現靈活的限流。 當然，由於需要儲存時間戳資訊，其佔用的儲存空間要比其他限流演算法要大得多。
不管黑貓白貓，能抓到老鼠的就是好貓。限流演算法並沒有絕對的好劣之分，如何選擇合適的限流演算法呢？不妨從效能，
是否允許超出閾值
，
落地成本
，
流量平滑度
，
是否允許突發流量
以及
系統資源
大小限制多方面考慮。
當然，市面上也有比較成熟的限流工具和框架。如Google出品的
Guava
中基於令牌桶實現的限流元件，拿來即用；以及alibaba開源的面向分散式服務架構的流量控制框架
Sentinel
更會讓你愛不釋手，它是基於滑動視窗實現的。
看後點贊，養成習慣！本次分享就到這裡，我們下期見！
