- 瞬時流量過高，服務被壓垮？
- 惡意用戶高頻光顧，導致服務器宕機？
-
消息消費過快，導致數(shù)據(jù)庫壓力過大，性能下降甚至崩潰？
......
在高并發(fā)系統(tǒng)中，出于系統(tǒng)保護角度考慮，通常會對流量進行限流；不但在工作中要頻繁使用，而且也是面試中的高頻考點。
今天我們將圖文并茂地對常見的限流算法分別進行介紹，通過各個算法的特點，給出限流算法選型的一些建議，并給出Java語言實現(xiàn)的代碼示例。
01 固定窗口
固定窗口又稱固定窗口（又稱計數(shù)器算法，F(xiàn)ixed Window）限流算法，是最簡單的限流算法，通過在單位時間內(nèi)維護的計數(shù)器來控制該時間單位內(nèi)的最大訪問量。
假設限制每分鐘請求量不超過60，設置一個計數(shù)器，當請求到達時如果計數(shù)器到達閾值，則拒絕請求，否則計數(shù)器加1；每分鐘重置計數(shù)器為0。代碼實現(xiàn)如下：
public class CounterRateLimiter extends MyRateLimiter {
/**
* 每秒限制請求數(shù)
*/
private final long permitsPerSecond;
/**
* 上一個窗口的開始時間
*/
public long timestamp = System.currentTimeMillis();
/**
* 計數(shù)器
*/
private int counter;
public CounterRateLimiter(long permitsPerSecond) {
this.permitsPerSecond = permitsPerSecond;
}
@Override
public synchronized boolean tryAcquire() {
long now = System.currentTimeMillis();
// 窗口內(nèi)請求數(shù)量小于閾值，更新計數(shù)放行，否則拒絕請求
if (now - timestamp < 1000) {
if (counter < permitsPerSecond) {
counter++;
return true;
} else {
return false;
}
}
// 時間窗口過期，重置計數(shù)器和時間戳
counter = 0;
timestamp = now;
return true;
}
}
固定窗口最大的優(yōu)點在于易于實現(xiàn)；并且內(nèi)存占用小，我們只需要存儲時間窗口中的計數(shù)即可；它能夠確保處理更多的最新請求，不會因為舊請求的堆積導致新請求被餓死。當然也面臨著臨界問題，當兩個窗口交界處，瞬時流量可能為2n。
02 滑動窗口
為了防止瞬時流量，可以把固定窗口近一步劃分成多個格子，每次向后移動一小格，而不是固定窗口大小，這就是滑動窗口（Sliding Window）。
比如每分鐘可以分為6個10秒中的單元格，每個格子中分別維護一個計數(shù)器，窗口每次向前滑動一個單元格。每當請求到達時，只要窗口中所有單元格的計數(shù)總和不超過閾值都可以放行。TCP協(xié)議中數(shù)據(jù)包的傳輸，同樣也是采用滑動窗口來進行流量控制。
實現(xiàn)如下：
public class SlidingWindowRateLimiter extends MyRateLimiter {
/**
* 每分鐘限制請求數(shù)
*/
private final long permitsPerMinute;
/**
* 計數(shù)器, k-為當前窗口的開始時間值秒，value為當前窗口的計數(shù)
*/
private final TreeMap<Long, Integer> counters;
public SlidingWindowRateLimiter(long permitsPerMinute) {
this.permitsPerMinute = permitsPerMinute;
this.counters = new TreeMap<>();
}
@Override
public synchronized boolean tryAcquire() {
// 獲取當前時間的所在的子窗口值； 10s一個窗口
long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / 10 * 10;
// 獲取當前窗口的請求總量
int currentWindowCount = getCurrentWindowCount(currentWindowTime);
if (currentWindowCount >= permitsPerMinute) {
return false;
}
// 計數(shù)器 + 1
counters.merge(currentWindowTime, 1, Integer::sum);
return true;
}
/**
* 獲取當前窗口中的所有請求數(shù)（并刪除所有無效的子窗口計數(shù)器）
*
* @param currentWindowTime 當前子窗口時間
* @return 當前窗口中的計數(shù)
*/
private int getCurrentWindowCount(long currentWindowTime) {
// 計算出窗口的開始位置時間
long startTime = currentWindowTime - 50;
int result = 0;
// 遍歷當前存儲的計數(shù)器，刪除無效的子窗口計數(shù)器，并累加當前窗口中的所有計數(shù)器之和
Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Long, Integer> entry = iterator.next();
if (entry.getKey() < startTime) {
iterator.remove();
} else {
result += entry.getValue();
}
}
return result;
}
}
滑動窗口解決了計數(shù)器中的瞬時流量高峰問題，其實計數(shù)器算法也是滑動窗口的一種，只不過窗口沒有進行更細粒度單元的劃分。對比計數(shù)器可見，當窗口劃分的粒度越細，則流量控制更加精準和嚴格。
不過當窗口中流量到達閾值時，流量會瞬間切斷，在實際應用中我們要的限流效果往往不是把流量一下子掐斷，而是讓流量平滑地進入系統(tǒng)當中。
03 漏桶算法
如何更加平滑的限流？不妨看看漏桶算法（Leaky Bucket），請求就像水一樣以任意速度注入漏桶，而桶會按照固定的速率將水漏掉；當注入速度持續(xù)大于漏出的速度時，漏桶會變滿，此時新進入的請求將會被丟棄。限流和整形是漏桶算法的兩個核心能力。
實現(xiàn)如下：
public class LeakyBucketRateLimiter extends MyRateLimiter {
// 桶的容量
private final int capacity;
// 漏出速率
private final int permitsPerSecond;
// 剩余水量
private long leftWater;
// 上次注入時間
private long timeStamp = System.currentTimeMillis();
public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) {
this.capacity = capacity;
this.permitsPerSecond = permitsPerSecond;
}
@Override
public synchronized boolean tryAcquire() {
//1. 計算剩余水量
long now = System.currentTimeMillis();
long timeGap = (now - timeStamp) / 1000;
leftWater = Math.max(0, leftWater - timeGap * permitsPerSecond);
timeStamp = now;
// 如果未滿，則放行；否則限流
if (leftWater < capacity) {
leftWater += 1;
return true;
}
return false;
}
}
這并不是一個完整的漏桶算法的實現(xiàn)，以上代碼中只是對流量是否會被拋棄進行校驗，即tryAcquire返回true表示漏桶未滿，否則表示漏桶已滿丟棄請求。
想要以恒定的速率漏出流量，通常還應配合一個FIFO隊列來實現(xiàn)，當tryAcquire返回true時，將請求入隊，然后再以固定頻率從隊列中取出請求進行處理。示例代碼如下：
@Test
public void testLeakyBucketRateLimiter() throws InterruptedException {
ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
ExecutorService singleThread = Executors.newSingleThreadExecutor();
LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(20, 20);
// 存儲流量的隊列
Queue<Integer> queue = new LinkedList<>();
// 模擬請求 不確定速率注水
singleThread.execute(() -> {
int count = 0;
while (true) {
count++;
boolean flag = rateLimiter.tryAcquire();
if (flag) {
queue.offer(count);
System.out.println(count + "--------流量被放行--------");
} else {
System.out.println(count + "流量被限制");
}
try {
Thread.sleep((long) (Math.random() * 1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
// 模擬處理請求 固定速率漏水
scheduledExecutorService.scheduleAtFixedRate(() -> {
if (!queue.isEmpty()) {
System.out.println(queue.poll() + "被處理");
}
}, 0, 100, TimeUnit.MILLISECONDS);
// 保證主線程不會退出
while (true) {
Thread.sleep(10000);
}
}
漏桶算法存在目的主要是用來平滑突發(fā)的流量，提供一種機制來確保網(wǎng)絡中的突發(fā)流量被整合成平滑穩(wěn)定的額流量。
不過由于漏桶對流量的控制過于嚴格，在有些場景下不能充分使用系統(tǒng)資源，因為漏桶的漏出速率是固定的，即使在某一時刻下游能夠處理更大的流量，漏桶也不允許突發(fā)流量通過。
04 令牌桶
如何在夠限制流量速率的前提下，又能夠允許突發(fā)流量呢？令牌桶算法了解一下！令牌桶算法是以恒定速率向令牌桶發(fā)送令牌，請求到達時，嘗試從令牌桶中拿令牌，只有拿到令牌才能夠放行，否則將會被拒絕。
<img src="https://source.mycookies.cn/0233143ca414e9057a682fb8f45b5772.jpg" style="zoom:80%;" />
令牌桶具有以下特點：
以恒定的速率發(fā)放令牌，假設限流速率為v/s，則表示每1/v秒發(fā)放一個令牌
假設令牌桶容量是b，如果令牌桶已滿，則新的令牌會被丟棄
請求能夠通過限流器的前提是令牌桶中有令牌
令牌桶算法中值得關注的參數(shù)有兩個，即限流速率v/s，和令牌桶容量b；速率a表示限流器一般情況下的限流速率，而b則是burst的簡寫，表示限流器允許的最大突發(fā)流量。
比如b=10，當令牌桶滿的時候有10個可用令牌，此時允許10個請求同時通過限流器（允許流量一定程度的突發(fā)），這10個請求瞬間消耗完令牌后，后續(xù)的流量只能按照速率r通過限流器。
實現(xiàn)如下：
public class TokenBucketRateLimiter extends MyRateLimiter {
/**
* 令牌桶的容量「限流器允許的最大突發(fā)流量」
*/
private final long capacity;
/**
* 令牌發(fā)放速率
*/
private final long generatedPerSeconds;
/**
* 最后一個令牌發(fā)放的時間
*/
long lastTokenTime = System.currentTimeMillis();
/**
* 當前令牌數(shù)量
*/
private long currentTokens;
public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
this.generatedPerSeconds = generatedPerSeconds;
this.capacity = capacity;
}
/**
* 嘗試獲取令牌
*
* @return true表示獲取到令牌，放行；否則為限流
*/
@Override
public synchronized boolean tryAcquire() {
/**
* 計算令牌當前數(shù)量
* 請求時間在最后令牌是產(chǎn)生時間相差大于等于額1s（為啥時1s？因為生成令牌的最小時間單位時s），則
* 1. 重新計算令牌桶中的令牌數(shù)
* 2. 將最后一個令牌發(fā)放時間重置為當前時間
*/
long now = System.currentTimeMillis();
if (now - lastTokenTime >= 1000) {
long newPermits = (now - lastTokenTime) / 1000 * generatedPerSeconds;
currentTokens = Math.min(currentTokens + newPermits, capacity);
lastTokenTime = now;
}
if (currentTokens > 0) {
currentTokens--;
return true;
}
return false;
}
}
需要主意的是，非常容易被想到的實現(xiàn)是生產(chǎn)者消費者模式；用一個生產(chǎn)者線程定時向阻塞隊列中添加令牌，而試圖通過限流器的線程則作為消費者線程，只有從阻塞隊列中獲取到令牌，才允許通過限流器。
由于線程調度的不確定性，在高并發(fā)場景時，定時器誤差非常大，同時定時器本身會創(chuàng)建調度線程，也會對系統(tǒng)的性能產(chǎn)生影響。
05 滑動日志
滑動日志是一個比較“冷門”，但是確實好用的限流算法。滑動日志限速算法需要記錄請求的時間戳，通常使用有序集合來存儲，我們可以在單個有序集合中跟蹤用戶在一個時間段內(nèi)所有的請求。
假設我們要限制給定T時間內(nèi)的請求不超過N，我們只需要存儲最近T時間之內(nèi)的請求日志，每當請求到來時判斷最近T時間內(nèi)的請求總數(shù)是否超過閾值。
實現(xiàn)如下：
public class SlidingLogRateLimiter extends MyRateLimiter {
/**
* 每分鐘限制請求數(shù)
*/
private static final long PERMITS_PER_MINUTE = 60;
/**
* 請求日志計數(shù)器, k-為請求的時間（秒），value當前時間的請求數(shù)量
*/
private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();
@Override
public synchronized boolean tryAcquire() {
// 最小時間粒度為s
long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
// 獲取當前窗口的請求總數(shù)
int currentWindowCount = getCurrentWindowCount(currentTimestamp);
if (currentWindowCount >= PERMITS_PER_MINUTE) {
return false;
}
// 請求成功，將當前請求日志加入到日志中
requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
return true;
}
/**
* 統(tǒng)計當前時間窗口內(nèi)的請求數(shù)
*
* @param currentTime 當前時間
* @return -
*/
private int getCurrentWindowCount(long currentTime) {
// 計算出窗口的開始位置時間
long startTime = currentTime - 59;
// 遍歷當前存儲的計數(shù)器，刪除無效的子窗口計數(shù)器，并累加當前窗口中的所有計數(shù)器之和
return requestLogCountMap.entrySet()
.stream()
.filter(entry -> entry.getKey() >= startTime)
.mapToInt(Map.Entry::getValue)
.sum();
}
}
滑動日志能夠避免突發(fā)流量，實現(xiàn)較為精準的限流；同樣更加靈活，能夠支持更加復雜的限流策略，如多級限流，每分鐘不超過100次，每小時不超過300次，每天不超過1000次，我們只需要保存最近24小時所有的請求日志即可實現(xiàn)。
靈活并不是沒有代價的，帶來的缺點就是占用存儲空間要高于其他限流算法。
06 分布式限流
以上幾種限流算法的實現(xiàn)都僅適合單機限流。雖然給每臺機器平均分配限流配額可以達到限流的目的，但是由于機器性能，流量分布不均以及計算數(shù)量動態(tài)變化等問題，單機限流在分布式場景中的效果總是差強人意。
分布式限流最簡單的實現(xiàn)就是利用中心化存儲，即將單機限流存儲在本地的數(shù)據(jù)存儲到同一個存儲空間中，如常見的Redis等。
當然也可以從上層流量入口進行限流，Nginx代理服務就提供了限流模塊，同樣能夠實現(xiàn)高性能，精準的限流，其底層是漏桶算法。
07 總結
固定窗口算法實現(xiàn)簡單，性能高，但是會有臨界突發(fā)流量問題，瞬時流量最大可以達到閾值的2倍。
-
為了解決臨界突發(fā)流量，可以將窗口劃分為多個更細粒度的單元，每次窗口向右移動一個單元，于是便有了滑動窗口算法。
滑動窗口當流量到達閾值時會瞬間掐斷流量，所以導致流量不夠平滑。
-
想要達到限流的目的，又不會掐斷流量，使得流量更加平滑？可以考慮漏桶算法！需要注意的是，漏桶算法通常配置一個FIFO的隊列使用以達到允許限流的作用。
由于速率固定，即使在某個時刻下游處理能力過剩，也不能得到很好的利用，這是漏桶算法的一個短板。
-
限流和瞬時流量其實并不矛盾，在大多數(shù)場景中，短時間突發(fā)流量系統(tǒng)是完全可以接受的。令牌桶算法就是不二之選了，令牌桶以固定的速率v產(chǎn)生令牌放入一個固定容量為n的桶中，當請求到達時嘗試從桶中獲取令牌。
當桶滿時，允許最大瞬時流量為n；當桶中沒有剩余流量時則限流速率最低，為令牌生成的速率v。
-
如何實現(xiàn)更加靈活的多級限流呢？滑動日志限流算法了解一下！這里的日志則是請求的時間戳，通過計算制定時間段內(nèi)請求總數(shù)來實現(xiàn)靈活的限流。
當然，由于需要存儲時間戳信息，其占用的存儲空間要比其他限流算法要大得多。
不管黑貓白貓，能抓到老鼠的就是好貓。限流算法并沒有絕對的好劣之分，如何選擇合適的限流算法呢？不妨從性能，是否允許超出閾值，落地成本，流量平滑度，是否允許突發(fā)流量以及系統(tǒng)資源大小限制多方面考慮。
當然，市面上也有比較成熟的限流工具和框架。如Google出品的Guava中基于令牌桶實現(xiàn)的限流組件，拿來即用；以及alibaba開源的面向分布式服務架構的流量控制框架Sentinel更會讓你愛不釋手，它是基于滑動窗口實現(xiàn)的。
看后點贊，養(yǎng)成習慣！本次分享就到這里，我們下期見！
