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