高并發(fā)面試必問，常見四大限流算法實現(xiàn)原理
在分布式系統(tǒng)中，高并發(fā)場景下，為了防止系統(tǒng)因突然的流量激增而導致的崩潰，同時保證服務的高可用性和穩(wěn)定性，限流是最常用的手段。
限流算法也是面試中必考題，今天一燈帶大家一塊學習一下常見的四種限流算法，分別是：固定窗口算法、滑動窗口算法、漏桶算法、令牌桶算法。
1. 固定窗口算法
1.1 實現(xiàn)原理
固定窗口限流算法，也叫計數(shù)器限流算法，是最簡單的一種限流算法。
實現(xiàn)原理是： 在一個固定長度的時間窗口內限制請求數(shù)量，每來一個請求，請求次數(shù)加一，如果請求數(shù)量超過最大限制，就拒絕該請求。
下面使用Java偽代碼實現(xiàn)一下固定窗口限流算法，注意以下算法沒有考慮并發(fā)情況，在并發(fā)環(huán)境下，可以使用Synchronized、Reentrantlock或者AtomicLong等并發(fā)工具來保證數(shù)據(jù)安全性。
1.2 代碼實現(xiàn)
/**
* @author 一燈架構
* @apiNote 固定窗口限流算法
**/
public class FixWindowLimiter {
/**
* 每個窗口的最大請求數(shù)量
*/
public static long threshold = 10;
/**
* 窗口大小，1000ms
*/
public static long windowUnit = 1000;
/**
* 窗口內的當前請求數(shù)量
*/
public static long count = 0;
/**
* 窗口的開始時間
*/
public static long lastTime = 0;
/**
* 限流方法，返回true表示通過
*/
public boolean limit() {
// 獲取系統(tǒng)當前時間
long currentTime = System.currentTimeMillis();
// 判斷是否在當前時間窗口內，如果不在就開啟一個新的時間窗口
if (currentTime - lastTime > windowUnit) {
// 計數(shù)器清零
count = 0;
// 開啟新的時間窗口
lastTime = currentTime;
}
// 判斷是否超過最大請求量
if (count < threshold) {
count++;
return true;
}
return false;
}
}1.3 優(yōu)缺點
優(yōu)點： 實現(xiàn)簡單，容易理解。
缺點：
- 限流不夠平滑。例如：限流是每秒3個，在第一毫秒發(fā)送了3個請求，達到限流，窗口剩余時間的請求都將會被拒絕，體驗不好。
- 無法處理窗口邊界問題。因為是在某個時間窗口內進行流量控制，所以可能會出現(xiàn)窗口邊界效應，即在時間窗口的邊界處可能會有大量的請求被允許通過，從而導致突發(fā)流量。
例如：限流是每秒3個，在第一秒的最后一毫秒發(fā)送了3個請求，在第二秒的第一毫秒又發(fā)送了3個請求。在這兩毫米內處理了6個請求，但是并沒有觸發(fā)限流。如果出現(xiàn)突發(fā)流量，可能會壓垮服務器。
2. 滑動窗口算法
2.1 實現(xiàn)原理
滑動窗口算法是對固定窗口算法的一種改進。在滑動窗口算法中，窗口的起止時間是動態(tài)的，窗口的大小固定。這種算法能夠較好地處理窗口邊界問題，但是實現(xiàn)相對復雜，需要記錄每個請求的時間戳。
實現(xiàn)原理是： 每來一個請求，就向后推一個時間窗口，計算這個窗口內的請求數(shù)量。如果請求數(shù)量超過限制就拒絕請求，否則就處理請求，并記錄請求的時間戳。另外還需要一個任務清理過期的時間戳。
2.2 代碼實現(xiàn)
/**
* @author 一燈架構
* @apiNote 固定窗口限流算法
**/
public class SlidingWindowLimiter {
/**
* 每個窗口的最大請求數(shù)量
*/
public static long threshold = 10;
/**
* 窗口大小，1000ms
*/
public static long windowUnit = 1000;
/**
* 請求集合，用來存儲窗口內的請求數(shù)量
*/
public static List<Long> requestList = new ArrayList<>();
/**
* 限流方法，返回true表示通過
*/
public boolean limit() {
// 獲取系統(tǒng)當前時間
long currentTime = System.currentTimeMillis();
// 統(tǒng)計當前窗口內，有效的請求數(shù)量
int sizeOfValid = this.sizeOfValid(currentTime);
// 判斷是否超過最大請求數(shù)量
if (sizeOfValid < threshold) {
// 把當前請求添加到請求集合里
requestList.add(currentTime);
return true;
}
return false;
}
/**
* 統(tǒng)計當前窗口內，有效的請求數(shù)量
*/
private int sizeOfValid(long currentTime) {
int sizeOfValid = 0;
for (Long requestTime : requestList) {
// 判斷是否在當前時間窗口內
if (currentTime - requestTime <= windowUnit) {
sizeOfValid++;
}
}
return sizeOfValid;
}
/**
* 清理過期的請求（單獨啟動一個線程處理）
*/
private void clean() {
// 判斷是否超出當前時間窗口內
requestList.removeIf(requestTime -> System.currentTimeMillis() - requestTime > windowUnit);
}
}2.3 優(yōu)缺點
優(yōu)點： 解決了固定窗口算法的窗口邊界問題，避免突發(fā)流量壓垮服務器。
缺點： 還是存在限流不夠平滑的問題。例如：限流是每秒3個，在第一毫秒發(fā)送了3個請求，達到限流，剩余窗口時間的請求都將會被拒絕，體驗不好。
3. 漏桶算法
3.1 實現(xiàn)原理
漏桶限流算法是一種常用的流量整形（Traffic Shaping）和流量控制（Traffic Policing）的算法，它可以有效地控制數(shù)據(jù)的傳輸速率以及防止網絡擁塞。
實現(xiàn)原理是：
- 一個固定容量的漏桶，按照固定速率出水（處理請求）；
- 當流入水（請求數(shù)量）的速度過大會直接溢出（請求數(shù)量超過限制則直接拒絕）。
- 桶里的水（請求）不夠則無法出水（桶內沒有請求則不處理）。
當請求流量正?；蛘咻^小的時候，請求能夠得到正常的處理。當請求流量過大時，漏桶限流算法可以通過丟棄部分請求來防止系統(tǒng)過載。
這種算法的一個重要特性是，輸出數(shù)據(jù)的速率始終是穩(wěn)定的，無論輸入的數(shù)據(jù)流量如何變化。這就確保了系統(tǒng)的負載不會超過預設的閾值。但是，由于漏桶的出口速度是固定的，所以無法處理突發(fā)流量。此外，如果入口流量過大，漏桶可能會溢出，導致數(shù)據(jù)丟失。
3.2 代碼實現(xiàn)
/**
* @author 一燈架構
* @apiNote 漏桶限流算法
**/
public class LeakyBucketLimiter {
/**
* 桶的最大容量
*/
public static long threshold = 10;
/**
* 桶內當前水量
*/
public static long count = 0;
/**
* 漏水速率（每秒5次）
*/
public static long leakRate = 5;
/**
* 上次漏水時間
*/
public static long lastLeakTime = System.currentTimeMillis();
/**
* 限流方法，返回true表示通過
*/
public boolean limit() {
// 調用漏水方法
this.leak();
// 判斷是否超過最大請求數(shù)量
if (count < threshold) {
count++;
return true;
}
return false;
}
/**
* 漏水方法，計算并更新這段時間內漏水量
*/
private void leak() {
// 獲取系統(tǒng)當前時間
long currentTime = System.currentTimeMillis();
// 計算這段時間內，需要流出的水量
long leakWater = (currentTime - lastLeakTime) * leakRate / 1000;
count = Math.max(count - leakWater, 0);
lastLeakTime = currentTime;
}
}3.3 優(yōu)缺點
優(yōu)點：
- 平滑流量。由于漏桶算法以固定的速率處理請求，可以有效地平滑和整形流量，避免流量的突發(fā)和波動（類似于消息隊列的削峰填谷的作用）。
- 防止過載。當流入的請求超過桶的容量時，可以直接丟棄請求，防止系統(tǒng)過載。
缺點：
- 無法處理突發(fā)流量：由于漏桶的出口速度是固定的，無法處理突發(fā)流量。例如，即使在流量較小的時候，也無法以更快的速度處理請求。
- 可能會丟失數(shù)據(jù)：如果入口流量過大，超過了桶的容量，那么就需要丟棄部分請求。在一些不能接受丟失請求的場景中，這可能是一個問題。
- 不適合速率變化大的場景：如果速率變化大，或者需要動態(tài)調整速率，那么漏桶算法就無法滿足需求。
4. 令牌桶算法
4.1 實現(xiàn)原理
令牌桶限流算法是一種常用的流量整形和速率限制算法。與漏桶算法一樣，令牌桶算法也是用來控制發(fā)送到網絡上的數(shù)據(jù)的數(shù)量。
實現(xiàn)原理：
- 系統(tǒng)以固定的速率向桶中添加令牌；
- 當有請求到來時，會嘗試從桶中移除一個令牌，如果桶中有足夠的令牌，則請求可以被處理或數(shù)據(jù)包可以被發(fā)送；
- 如果桶中沒有令牌，那么請求將被拒絕；
- 桶中的令牌數(shù)不能超過桶的容量，如果新生成的令牌超過了桶的容量，那么新的令牌會被丟棄。
令牌桶算法的一個重要特性是，它能夠應對突發(fā)流量。當桶中有足夠的令牌時，可以一次性處理多個請求，這對于需要處理突發(fā)流量的應用場景非常有用。但是又不會無限制的增加處理速率導致壓垮服務器，因為桶內令牌數(shù)量是有限制的。
4.2 代碼實現(xiàn)
/**
* @author 一燈架構
* @apiNote 漏桶限流算法
**/
public class TokenBucketLimiter {
/**
* 桶的最大容量
*/
public static long threshold = 10;
/**
* 桶內當前的令牌數(shù)量
*/
public static long count = 0;
/**
* 令牌生成速率（每秒5次）
*/
public static long tokenRate = 5;
/**
* 上次生成令牌的時間
*/
public static long lastRefillTime = System.currentTimeMillis();
/**
* 限流方法，返回true表示通過
*/
public boolean limit() {
// 調用生成令牌方法
this.refillTokens();
// 判斷桶內是否還有令牌
if (count > 0) {
count--;
return true;
}
return false;
}
/**
* 生成令牌方法，計算并更新這段時間內生成的令牌數(shù)量
*/
private void refillTokens() {
long currentTime = System.currentTimeMillis();
// 計算這段時間內，需要生成的令牌數(shù)量
long refillTokens = (currentTime - lastRefillTime) * tokenRate / 1000;
count = Math.min(count + refillTokens, threshold);
lastRefillTime = currentTime;
}
}4.3 優(yōu)缺點
優(yōu)點：
- 可以處理突發(fā)流量：令牌桶算法可以處理突發(fā)流量。當桶滿時，能夠以最大速度處理請求。這對于需要處理突發(fā)流量的應用場景非常有用。
- 限制平均速率：在長期運行中，數(shù)據(jù)的傳輸率會被限制在預定義的平均速率（即生成令牌的速率）。
- 靈活性：與漏桶算法相比，令牌桶算法提供了更大的靈活性。例如，可以動態(tài)地調整生成令牌的速率。
缺點：
- 可能導致過載：如果令牌產生的速度過快，可能會導致大量的突發(fā)流量，這可能會使網絡或服務過載。
- 需要存儲空間：令牌桶需要一定的存儲空間來保存令牌，可能會導致內存資源的浪費。
- 實現(xiàn)稍復雜：相比于計數(shù)器算法，令牌桶算法的實現(xiàn)稍微復雜一些。
5. 總結
這篇文章我們介紹了四種常用的限流算法：固定窗口算法、滑動窗口算法、漏桶算法和令牌桶算法。每種算法都有其特點和適用場景，下面我們來對它們進行簡單的總結和比較。
固定窗口算法實現(xiàn)簡單，但是限流不夠平滑，存在窗口邊界問題，適用于需要簡單實現(xiàn)限流的場景。
滑動窗口算法解決了窗口邊界問題，但是還是存在限流不夠平滑的問題，適用于需要控制平均請求速率的場景。
漏桶算法的優(yōu)點是流量處理更平滑，但是無法應對突發(fā)流量，適用于需要平滑流量的場景。
令牌桶算法既能平滑流量，又能處理突發(fā)流量，適用于需要處理突發(fā)流量的場景。
