前言
在流量突增的場景下，為了保證後端服務在整體上一個穩定性，我們需要對請求進行限流，來避免系統崩潰。
不過限流會對少部分使用者的請求直接進行拒絕或者延遲處理，影響這些使用者的體驗。
本文會介紹一些常見的限流算法，并在最後附上對分布式限流的一些思考。
計數器法
計數器算法，也成固定視窗法。可以控制在固定的時間視窗内，允許通過的最大的請求數。
例如，我們設定時間間隔視窗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，支援漏桶與令牌桶算法。