Java中常見的限流算法有哪些

這篇“Java中常見的限流算法有哪些”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java中常見的限流算法有哪些”文章吧。

01固定窗口

固定窗口又稱固定窗口（又稱計數器算法，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。

02滑動窗口

為了防止瞬時流量，可以把固定窗口近一步劃分成多個格子，每次向后移動一小格，而不是固定窗口大小，這就是滑動窗口（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;
    }
}

滑動窗口解決了計數器中的瞬時流量高峰問題，其實計數器算法也是滑動窗口的一種，只不過窗口沒有進行更細粒度單元的劃分。對比計數器可見，當窗口劃分的粒度越細，則流量控制更加精準和嚴格。

不過當窗口中流量到達閾值時，流量會瞬間切斷，在實際應用中我們要的限流效果往往不是把流量一下子掐斷，而是讓流量平滑地進入系統當中。

03漏桶算法

如何更加平滑的限流？不妨看看漏桶算法（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);
    }
}

漏桶算法存在目的主要是用來平滑突發的流量，提供一種機制來確保網絡中的突發流量被整合成平滑穩定的額流量。

不過由于漏桶對流量的控制過于嚴格，在有些場景下不能充分使用系統資源，因為漏桶的漏出速率是固定的，即使在某一時刻下游能夠處理更大的流量，漏桶也不允許突發流量通過。

04令牌桶

如何在夠限制流量速率的前提下，又能夠允許突發流量呢？令牌桶算法了解一下！令牌桶算法是以恒定速率向令牌桶發送令牌，請求到達時，嘗試從令牌桶中拿令牌，只有拿到令牌才能夠放行，否則將會被拒絕。

令牌桶具有以下特點：

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;
    }
}

需要主意的是，非常容易被想到的實現是生產者消費者模式；用一個生產者線程定時向阻塞隊列中添加令牌，而試圖通過限流器的線程則作為消費者線程，只有從阻塞隊列中獲取到令牌，才允許通過限流器。

由于線程調度的不確定性，在高并發場景時，定時器誤差非常大，同時定時器本身會創建調度線程，也會對系統的性能產生影響。

05滑動日志

滑動日志是一個比較“冷門”，但是確實好用的限流算法。滑動日志限速算法需要記錄請求的時間戳，通常使用有序集合來存儲，我們可以在單個有序集合中跟蹤用戶在一個時間段內所有的請求。

假設我們要限制給定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小時所有的請求日志即可實現。

靈活并不是沒有代價的，帶來的缺點就是占用存儲空間要高于其他限流算法。

06分布式限流

以上幾種限流算法的實現都僅適合單機限流。雖然給每臺機器平均分配限流配額可以達到限流的目的，但是由于機器性能，流量分布不均以及計算數量動態變化等問題，單機限流在分布式場景中的效果總是差強人意。

分布式限流最簡單的實現就是利用中心化存儲，即將單機限流存儲在本地的數據存儲到同一個存儲空間中，如常見的Redis等。

當然也可以從上層流量入口進行限流，Nginx代理服務就提供了限流模塊，同樣能夠實現高性能，精準的限流，其底層是漏桶算法。

以上就是關于“Java中常見的限流算法有哪些”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。