前言
在流量突增的場景下，為了保證后端服務在整體上一個穩定性，我們需要對請求進行限流，來避免系統崩潰，
不過限流會對少部分用戶的請求直接進行拒絕或者延遲處理，影響這些用戶的體驗，
本文會介紹一些常見的限流演算法，并在最后附上對分布式限流的一些思考，
計數器法
計數器演算法，也成固定視窗法，可以控制在固定的時間視窗內，允許通過的最大的請求數，
例如，我們設定時間間隔視窗intervalWindow為1分鐘，該視窗內的最大請求數max為100，
當第1個請求到來時，我們記錄下當前視窗內的第一個請求的時間firstReqTime，那么之后的請求到來時，先判斷是否進入下一個視窗，
如果進入，則直接重置firstReqTime為當前時間，該請求通過，如果沒進入，再判斷是否超過max，
demo如下（并沒有考慮執行緒安全）：
/**
* @author qcy
* @create 2021/12/04 18:20:30
*/
public class CountLimiter {
/**
* 時間間隔視窗(單位:毫秒)
*/
private long intervalWindow;
/**
* 該視窗內的最大請求數
*/
private int max;
/**
* 當前視窗內的請求計數
*/
private int count;
/**
* 當前視窗內的第一個請求的時間
*/
private long firstReqTime = System.currentTimeMillis();
public CountLimiter(int intervalWindow, int max) {
this.intervalWindow = intervalWindow;
this.max = max;
}
//省略get與set方法
public boolean limit() {
long now = System.currentTimeMillis();
if (now > firstReqTime + intervalWindow) {
//代表已經進入下一個視窗
firstReqTime = now;
count = 1;
return true;
}
//還在當前的時間視窗內
if (count + 1 <= max) {
count++;
return true;
}
return false;
}
}計數器法，非常簡單粗暴，以上demo只是單機式限流，
如果需要進行分布式限流，可以使用Redis，以介面名稱作為key，max作為value，intervalWindow作為key過期時間，
當請求過來時，如果key不存在，則代表已經進入下一個視窗，value賦值為max-1，并允許請求通過，
如果key存在，則再判斷value是否大于0，大于0則允許請求通過，否則進行限流，
使用Redis進行分布式限流，需要注意保證代碼的原子性，可以直接使用lua腳本，
計數器法的缺點
該演算法無法應對突發的流量，因為計數器法是固定視窗的，
例如第一個請求10:00:00到來，那么第一個時間視窗為10:00:00-10:01:00，之后在10:00:59時，突然來了99個請求，又在下一個時間視窗的10:01:01來了100個請求，
也就是說，在10:00:59-10:01:01的短短幾秒內，共有199個請求到來，可能會瞬間壓垮我們的應用，
滑動視窗法
滑動視窗法可以解決計數器在固定視窗法下無法應對突發流量的問題
固定視窗法是以第一個請求為視窗開始期，并向后截取intervalWindow長度，只有當視窗時間流逝完，才開辟新的視窗，
滑動視窗法以每一個請求為視窗結束期，向前截取intervalWindow長度，檢查該范圍內的請求總和，相當于會為每個請求開辟一個新視窗，
既然要知道前intervalWindow長度內到底有多少個請求，那么就要為每個放行的請求記錄發生時間，
demo如下：
public class SlidingWindowLimiter {
/**
* 時間間隔視窗(單位:毫秒)
*/
private long intervalWindow;
/**
* 視窗內的最大請求數
*/
private int max;
/**
* 限流容器
* 佇列尾部保存最新通過的請求時間
*/
private LinkedList<Long> list = new LinkedList<>();
public SlidingWindowLimiter(int intervalWindow, int max) {
this.intervalWindow = intervalWindow;
this.max = max;
}
//省略get與set方法
public boolean limit() {
long now = System.currentTimeMillis();
//佇列未滿,說明當前視窗還可以接收請求
if (list.size() < max) {
list.addLast(now);
return true;
}
//佇列已滿
Long first = list.getFirst();
if (now - first <= intervalWindow) {
//說明新請求和佇列中的請求還處于一個視窗內,觸發了限流
return false;
}
//說明新請求和佇列中的請求不在通過視窗內
list.removeFirst();
list.addLast(now);
return true;
}
}當然，也可以使用Redis的List或Zset實作嗎，大致步驟和以上demo類似，
這里多說一句，限流中的滑動視窗法和TCP的滑動視窗其實很像，滑動視窗法是去主動限流，而TCP的滑動視窗則是接收方為了告訴發送方自己還能接受多少資料，是對發送方的“限流”，
滑動視窗法的缺點
在滑動視窗法中，因為要倒推視窗的開始期，所以需要記錄每個請求的執行時間，會額外占用一些記憶體，
此外，在演算法中會頻繁地removeFirst與addLast，在選擇錯誤的資料結構下（例如陣列），可能會造成很大的移動開銷，
漏桶法
水龍頭可以通過松緊來控制出水的速率，下方有一個儲蓄桶來保存當前的水，儲蓄通底部有一個出口，內部的水會以恒定的速率從出口漏掉，
如果儲蓄桶滿了之后，再進來的水會全部溢位，只有當出水速率和漏水速率相同時，儲蓄桶才會在不漏水的前提下達到最大的吞吐量，
我們把水比作請求，水龍頭就是客戶端，請求產生的速率肯定不是恒定的，但處理請求的速率是恒定的，當儲蓄桶滿了之后，請求產生的速率必須要和處理請求的速率一致，
demo如下：
public class LeakyBucketLimiter {
/**
* 上次請求到來的時間
*/
private long preTime = System.currentTimeMillis();
/**
* 漏水速率,n/s
*/
private int leakRate;
/**
* 儲蓄桶容量
*/
private int capacity;
/**
* 當前水量
*/
private int water;
public LeakyBucketLimiter(int leakRate, int capacity) {
this.leakRate = leakRate;
this.capacity = capacity;
}
//省略get與set方法
public boolean limit() {
long now = System.currentTimeMillis();
//先漏水,計算剩余水量
water = Math.max(0, water - (int) ((now - preTime) / 1000) * leakRate);
preTime = now;
//桶未滿
if (water + 1 <= capacity) {
water++;
return true;
}
return false;
}
}仔細一想，儲蓄桶能夠把不定速率的請求轉化為恒定速率的請求，和訊息佇列一樣，具有削峰填谷的作用，
其實整套裝置和ScheduledThreadPoolExecutor執行緒池更像，將儲蓄桶想象為具有延時特性的阻塞佇列，超出佇列容量的請求，將直接執行拒絕策略，
如果儲蓄桶的容量為Integer.MAX_VALUE，流速為10/s，則可通過以下的代碼來模擬漏桶：
//最大任務數為Integer.MAX_VALUE,即儲蓄桶容量
ScheduledExecutorService pool = Executors.newScheduledThreadPool(30);
//每隔0.1秒處理1個請求,即流速為10/s
pool.scheduleAtFixedRate(() -> System.out.println("處理請求"), 0, 100, TimeUnit.MILLISECONDS);漏桶法的缺點
使用漏桶法去做限流，在業務平穩期其實已經夠用了，但是在業務高峰期，我們又希望動態地去調整處理請求的速率，而不是一成不變的速率，
我們大可以動態地去改變引數leakRate的值，不過在計算剩余水量的時候，將會十分復雜，
因此，如果要考慮到對突發流量的控制，就不太推薦漏桶法了，
令牌桶法
首先有一個令牌桶，然后系統以一個恒定的速率向桶中放入令牌，當桶滿時，會丟棄生成的令牌，
每有一個請求過來時，拿到令牌就可以執行，否則阻塞獲取或者被直接丟棄，
一個簡要的demo如下：
public class TokenBucketLimiter {
/**
* 上次請求到來的時間
*/
private long preTime = System.currentTimeMillis();
/**
* 放入令牌速率,n/s
*/
private int putRate;
/**
* 令牌桶容量
*/
private int capacity;
/**
* 當前令牌數
*/
private int bucket;
public TokenBucketLimiter(int putRate, int capacity) {
this.putRate = putRate;
this.capacity = capacity;
}
//省略get與set方法
public boolean limit() {
long now = System.currentTimeMillis();
//先放入令牌，再獲取令牌
bucket = Math.min(capacity, bucket + (int) ((now - preTime) / 1000) * putRate);
preTime = now;
if (bucket == 0) {
return false;
}
bucket--;
return true;
}
}看的出來，令牌桶和漏桶的原理有些相似，
漏桶是以一個恒定速率的出水，即處理請求的速率是恒定的，而令牌桶則是以一個恒定的速率往桶中放入令牌，在桶中令牌用完之前，并不限制處理請求的速率，
令牌桶的一個優勢在于，可以允許短時間內的一次突發流量，但不會允許在短時間內的多次突發流量，因為令牌的填充也是需要時間的，
Guava中的RateLimiter
google的工具包Guava中的RateLimiter就是對令牌桶的實作，其包含了兩種限流模式，位置處于SmoothRateLimiter的兩個靜態內部類中：
- SmoothBursty，穩定模式，令牌生成的速率是恒定的，為默認模式，
- SmoothWarmingUp，預熱模式，逐漸提升令牌的生成速率到一固定值，
其中acquire方法支持阻塞式獲取，tryAcquire支持獲取不到就回傳或者在指定時間內阻塞獲取，
關于RateLimiter原始碼分析，后面應該會另起篇幅介紹，
分布式限流
以上的RateLimiter屬于單機式限流，如果要進行分布式限流該怎么處理呢？
無非是將控制請求的閾值從單機中挪到統一的中間件上，例如Redis，
對于計數器法
如果要限制一天中對某個介面的呼叫次數，則可以使用介面的名稱作為key，value作為預設的閾值，過期時間為24小時，請求到來時利用原子指令判斷key是否存在，不存在則設定該key；存在則減1，再判斷是否大于0，
對于滑動視窗法
單機中我們使用list，在分布式系統中，則可以使用Redis的有序集合zset，key為某個介面名稱，value為處理請求的時間戳，請求到來時，先使用removeRangeByScore移除上一個時間視窗內的記錄，接著使用size獲取集合長度，若大于閾值，則進行限流，
對于漏桶法
阿里巴巴的開源分布式限流系統Sentienel，支持漏桶與令牌桶演算法，
個人覺得非常有必要去了解一下Sentienel的整體架構，可以看這篇文章入門阿里巴巴開源限流系統 Sentinel 全決議
對于令牌桶法
可以在每個應用中起一個延時的執行緒池，定時生產令牌到Redis中，這種方案在水平擴展時可以同比例的擴大限流閾值，但性能不高，
當然也可以利用lua腳本，在lua腳本中直接將生產令牌與獲取令牌的操作合在一起，即和上文的demo一樣，先放入令牌再獲取令牌，之后將腳本放在代碼中，每個應用先判斷Redis中是否存在該腳本，若不存在再加載該腳本，后續獲取令牌時直接執行該腳本即可，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/374750.html
標籤：java