固定視窗又稱固定視窗（又稱計數器演算法，Fixed Window）限流演算法，是最簡單的限流演算法，透過在單位時間內維護的計數器來控制該時間單位內的最大訪問量。
假設限制每分鐘請求量不超過60，設定一個計數器，當請求到達時如果計數器到達閾值，則拒絕請求，否則計數器加1；每分鐘重置計數器為0。程式碼實作如下：
public class CounterRateLimiter extends MyRateLimiter {
/**
* 每秒限制请求数
*/
private final long permitsPerSecond;
/**
* 上一个窗口的开始时间
*/
public long timestamp = System.currentTimeMillis();
/**
* 计数器
*/
private int counter;
public CounterRateLimiter(long permitsPerSecond) {
this.permitsPerSecond = permitsPerSecond;
}
@Override
public synchronized boolean tryAcquire() {
long now = System.currentTimeMillis();
// 窗口内请求数量小于阈值，更新计数放行，否则拒绝请求
if (now - timestamp < 1000) {
if (counter < permitsPerSecond) {
counter++;
return true;
} else {
return false;
}
}
// 时间窗口过期，重置计数器和时间戳
counter = 0;
timestamp = now;
return true;
}
}固定視窗最大的優點在於易於實現；並且記憶體佔用小，我們只需要儲存時間視窗中的計數即可；它能夠確保處理更多的最新請求，不會因為舊請求的堆積導致新請求被餓死。當然也面臨臨界問題，當兩個視窗交界處，瞬時流量可能為2n。
為了防止瞬時流量，可以把固定視窗近一步分割成多個格子，每次向後移動一小格，而不是固定視窗大小，這就是滑動視窗（Sliding Window）。
例如每分鐘可以分成6個10秒中的單元格，每個格子中分別維護一個計數器，視窗每次向前滑動一個單元格。每當請求到達時，只要視窗中所有儲存格的計數總和不超過閾值都可以放行。 TCP協定中資料包的傳輸，同樣也是採用滑動視窗來進行流量控制。
實現如下：
public class SlidingWindowRateLimiter extends MyRateLimiter {
/**
* 每分钟限制请求数
*/
private final long permitsPerMinute;
/**
* 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
*/
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;
}
// 计数器 + 1
counters.merge(currentWindowTime, 1, Integer::sum);
return true;
}
/**
* 获取当前窗口中的所有请求数（并删除所有无效的子窗口计数器）
*
* @param currentWindowTime 当前子窗口时间
* @return 当前窗口中的计数
*/
private int getCurrentWindowCount(long currentWindowTime) {
// 计算出窗口的开始位置时间
long startTime = currentWindowTime - 50;
int result = 0;
// 遍历当前存储的计数器，删除无效的子窗口计数器，并累加当前窗口中的所有计数器之和
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;
}
}滑動視窗解決了計數器中的瞬時流量高峰問題，其實計數器演算法也是滑動視窗的一種，只不過視窗沒有進行更細粒度單元的分割。對比計數器可見，當視窗劃分的粒度越細，則流量控制更加精準嚴格。
不過當視窗中流量到達閾值時，流量會瞬間切斷，在實際應用中我們要的限流效果往往不是把流量一下子掐斷，而是讓流量平滑地進入系統當中。
如何更平滑的限流？不妨看看漏桶演算法（Leaky Bucket），請求就像水一樣以任意速度注入漏桶，而桶子會按照固定的速率將水漏掉；當注入速度持續大於漏出的速度時，漏桶會變滿，此時新進入的請求將會被丟棄。限流和整形是漏桶演算法的兩個核心能力。
實作如下：
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;
}
}這並不是一個完整的漏桶演算法的實現，以上程式碼中只是對流量是否會被拋棄進行校驗，即tryAcquire回傳true表示漏桶未滿，否則表示漏桶已滿丟棄請求。
想要以恆定的速率漏出流量，通常也應配合一個FIFO佇列來實現，當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);
}
}漏桶演算法存在目的主要是用來平滑突發的流量，提供一個機制來確保網路中的突發流量被整合成平滑穩定的額流量。
不過由於漏桶對流量的控制過於嚴格，在有些場景下不能充分使用系統資源，因為漏桶的漏出速率是固定的，即使在某一時刻下游能夠處理更大的流量，漏桶也不允許突發流量通過。
如何在夠限制流量速率的前提下，又能夠允許突發流量呢？令牌桶演算法了解一下！令牌桶演算法是以恆定速率向令牌桶發送令牌，請求到達時，嘗試從令牌桶中拿令牌，只有拿到令牌才能夠放行，否則將會被拒絕。
令牌桶具有以下特點：
1.以恆定的速率發放令牌，假設限流速率為v/s，則表示每1/v秒發放一個令牌
2.假設令牌桶容量是b，如果令牌桶已滿，則新的令牌會被丟棄
3.請求能夠通過限流器的前提是令牌桶中有令牌
令牌桶演算法中值得關注的參數有兩個，即限流速率v/s，和令牌桶容量b；速率a表示限流器一般情況下的限流速率，而b則是burst的簡寫，表示限流器允許的最大突發流量。
例如b=10，當令牌桶滿的時候有10個可用令牌，此時允許10個請求同時通過限流器（允許流量一定程度的突發），這10個請求瞬間消耗完令牌後，後續的流量只能依照速率r通過限流器。
實作如下：
public class TokenBucketRateLimiter extends MyRateLimiter {
/**
* 令牌桶的容量「限流器允许的最大突发流量」
*/
private final long capacity;
/**
* 令牌发放速率
*/
private final long generatedPerSeconds;
/**
* 最后一个令牌发放的时间
*/
long lastTokenTime = System.currentTimeMillis();
/**
* 当前令牌数量
*/
private long currentTokens;
public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
this.generatedPerSeconds = generatedPerSeconds;
this.capacity = capacity;
}
/**
* 尝试获取令牌
*
* @return true表示获取到令牌，放行；否则为限流
*/
@Override
public synchronized boolean tryAcquire() {
/**
* 计算令牌当前数量
* 请求时间在最后令牌是产生时间相差大于等于额1s（为啥时1s？因为生成令牌的最小时间单位时s），则
* 1. 重新计算令牌桶中的令牌数
* 2. 将最后一个令牌发放时间重置为当前时间
*/
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;
}
}需要主意的是，非常容易被想到的實作是生產者消費者模式；用一個生產者執行緒定時在阻塞佇列中加入令牌，而試圖通過限流器的線程則作為消費者線程，只有從阻塞隊列中獲取到令牌，才允許通過限流器。
由於執行緒調度的不確定性，在高並發場景時，定時器誤差非常大，同時定時器本身會建立調度線程，也會對系統的效能產生影響。
滑動日誌是一個比較“冷門”，但是確實好用的限流演算法。滑動日誌限速演算法需要記錄請求的時間戳，通常使用有序集合來存儲，我們可以在單一有序集合中追蹤使用者在一個時間段內所有的請求。
假设我们要限制给定T时间内的请求不超过N，我们只需要存储最近T时间之内的请求日志，每当请求到来时判断最近T时间内的请求总数是否超过阈值。
实现如下：
public class SlidingLogRateLimiter extends MyRateLimiter {
/**
* 每分钟限制请求数
*/
private static final long PERMITS_PER_MINUTE = 60;
/**
* 请求日志计数器, k-为请求的时间（秒），value当前时间的请求数量
*/
private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();
@Override
public synchronized boolean tryAcquire() {
// 最小时间粒度为s
long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
// 获取当前窗口的请求总数
int currentWindowCount = getCurrentWindowCount(currentTimestamp);
if (currentWindowCount >= PERMITS_PER_MINUTE) {
return false;
}
// 请求成功，将当前请求日志加入到日志中
requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
return true;
}
/**
* 统计当前时间窗口内的请求数
*
* @param currentTime 当前时间
* @return -
*/
private int getCurrentWindowCount(long currentTime) {
// 计算出窗口的开始位置时间
long startTime = currentTime - 59;
// 遍历当前存储的计数器，删除无效的子窗口计数器，并累加当前窗口中的所有计数器之和
return requestLogCountMap.entrySet()
.stream()
.filter(entry -> entry.getKey() >= startTime)
.mapToInt(Map.Entry::getValue)
.sum();
}
}滑动日志能够避免突发流量，实现较为精准的限流；同样更加灵活，能够支持更加复杂的限流策略，如多级限流，每分钟不超过100次，每小时不超过300次，每天不超过1000次，我们只需要保存最近24小时所有的请求日志即可实现。
灵活并不是没有代价的，带来的缺点就是占用存储空间要高于其他限流算法。
以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到限流的目的，但是由于机器性能，流量分布不均以及计算数量动态变化等问题，单机限流在分布式场景中的效果总是差强人意。
分布式限流最简单的实现就是利用中心化存储，即将单机限流存储在本地的数据存储到同一个存储空间中，如常见的Redis等。
当然也可以从上层流量入口进行限流，Nginx代理服务就提供了限流模块，同样能够实现高性能，精准的限流，其底层是漏桶算法。
以上是Java中常見的限流演算法有哪些的詳細內容。更多資訊請關注PHP中文網其他相關文章！
