引言
在開發高并發系統時有三把利器用來保護系統：快取、降級和限流，今天我們要聊的就是限流（Rate Limit），限流的目的很簡單，就是為了保護系統不被瞬時大流量沖垮，
需要用到限流，特別是類似秒殺這種瞬時流量非常大但實際成單率低的業務場景，
目前比較常用的限流演算法有三種
-
計數器固定視窗演算法
-
計數器滑動視窗演算法
-
漏桶演算法
-
令牌桶演算法
計數器固定視窗演算法
計數器固定視窗演算法是最簡單的限流演算法，實作方式也比較簡單，就是通過維護一個單位時間內的計數值，每當一個請求通過時，就將計數值加1，當計數值超過預先設定的閾值時，就拒絕單位時間內的其他請求，如果單位時間已經結束，則將計數器清零，開啟下一輪的計數，
但是這種實作會有一個問題，舉個例子:
假設我們設定1秒內允許通過的請求閾值是200，如果有用戶在時間視窗的最后幾毫秒發送了200個請求，緊接著又在下一個時間視窗開始時發送了200個請求，那么這個用戶其實在一秒內成功請求了400次，顯然超過了閾值但并不會被限流，其實這就是臨界值問題，那么臨界值問題要怎么解決呢？
- 代碼實作 -- [CounterRateLimit.java](https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/CounterRateLimit.java)
計數器滑動視窗演算法
計數器滑動視窗法就是為了解決上述固定視窗計數存在的問題而誕生，學過TCP協議的同學應該對滑動視窗不陌生，其實還是不太一樣的，下文我們要說的滑動視窗是基于時間來劃分視窗的，而TCP的滑動視窗指的是能夠接受的位元組數，并且大小是可變的（擁塞控制）
滑動視窗是怎么做的？
前面說了固定視窗存在臨界值問題，要解決這種臨界值問題，顯然只用一個視窗是解決不了問題的，假設我們仍然設定1秒內允許通過的請求是200個，但是在這里我們需要把1秒的時間分成多格，假設分成5格（格數越多，流量過渡越平滑），每格視窗的時間大小是200毫秒，每過200毫秒，就將視窗向前移動一格，為了便于理解，可以看下圖
圖中將視窗劃為5份，每個小視窗中的數字表示在這個視窗中請求數，所以通過觀察上圖，可知在當前時間快（200毫秒）允許通過的請求數應該是20而不是200（只要超過20就會被限流），因為我們最終統計請求數時是需要把當前視窗的值進行累加，進而得到當前請求數來判斷是不是需要進行限流，
那么滑動視窗限流法是完美的嗎？
細心觀察的我們應該能馬上發現問題，滑動視窗限流法其實就是計數器固定視窗演算法的一個變種，流量的過渡是否平滑依賴于我們設定的視窗格數也就是統計時間間隔，格數越多，統計越精確，但是具體要分多少格我們也說不上來呀...
- 代碼實作 -- [SlidingWindowRateLimit.java](https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/SlidingWindowRateLimit.java)
漏桶演算法
上面所介紹的兩種演算法都不能非常平滑的過渡，下面就是漏桶演算法登場了
什么是漏桶演算法？
漏桶演算法以一個常量限制了出口流量速率，因此漏桶演算法可以平滑突發的流量，其中漏桶作為流量容器我們可以看做一個FIFO的佇列，當入口流量速率大于出口流量速率時，因為流量容器是有限的，當超出流量容器大小時，超出的流量會被丟棄，
下圖比較形象的說明了漏桶演算法的原理，其中水龍頭是入口流量，漏桶是流量容器，勻速流出的水是出口流量，
漏桶演算法的特點
-
漏桶具有固定容量，出口流量速率是固定常量（流出請求）
-
入口流量可以以任意速率流入到漏桶中（流入請求）
-
如果入口流量超出了桶的容量，則流入流量會溢位（新請求被拒絕）
-
代碼實作 -- [LeakyBucketRateLimit.java](https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/LeakyBucketRateLimit.java)
不過因為漏桶演算法限制了流出速率是一個固定常量值，所以漏桶演算法不支持出現突發流出流量，但是在實際情況下，流量往往是突發的，
令牌桶演算法
令牌桶演算法是漏桶演算法的改進版，可以支持突發流量，不過與漏桶演算法不同的是，令牌桶演算法的漏桶中存放的是令牌而不是流量，
那么令牌桶演算法是怎么突發流量的呢？
最開始，令牌桶是空的，我們以恒定速率往令牌桶里加入令牌，令牌桶被裝滿時，多余的令牌會被丟棄，當請求到來時，會先嘗試從令牌桶獲取令牌（相當于從令牌桶移除一個令牌），獲取成功則請求被放行，獲取失敗則阻塞活拒絕請求，
令牌桶演算法的特點
-
最多可以存發b個令牌，如果令牌到達時令牌桶已經滿了，那么這個令牌會被丟棄
-
請求到來時，如果令牌桶中少于n個令牌，那么不會洗掉令牌，該請求會被限流（阻塞活拒絕）
-
演算法允許最大b(令牌桶大小)個請求的突發
令牌桶演算法限制的是平均流量，因此其允許突發流量（只要令牌桶中有令牌，就不會被限流）
- 代碼實作 -- [TokenBucketRateLimit.java](https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/TokenBucketRateLimit.java)
總結
至此，基本把以上4種限流演算法的原理都解釋清楚了，每種限流演算法都有其固定特點，及各自適用的場景，其中計數器演算法是其中最簡單的，相當于滑動視窗演算法的簡化版，令牌桶演算法相比漏桶演算法對資源的利用率更高（允許突發流量）
參考：https://www.cnblogs.com/taromilk/p/11751211.html
Sentinel原始碼決議一（流程總覽）
Sentinel原始碼決議二（Slot總覽）
Sentinel原始碼決議三（滑動視窗流量統計）
Sentinel原始碼決議四（流控策略和流控效果）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/89879.html
標籤：Java
下一篇：Java編譯解釋之cmd