1. 瞬時(shí)流量過高，服務(wù)被壓垮？
2. 惡意用戶高頻光顧，導(dǎo)致服務(wù)器宕機(jī)？
3. 消息消費(fèi)過快，導(dǎo)致數(shù)據(jù)庫壓力過大，性能下降甚至崩潰？
   ……

在高并發(fā)系統(tǒng)中，出于系統(tǒng)保護(hù)角度考慮，通常會(huì)對(duì)流量進(jìn)行限流；不但在工作中要頻繁使用，而且也是面試中的高頻考點(diǎn)。

今天我們將圖文并茂地對(duì)常見的限流算法分別進(jìn)行介紹，通過各個(gè)算法的特點(diǎn)，給出限流算法選型的一些建議，并給出Java語言實(shí)現(xiàn)的代碼示例。

01 固定窗口

固定窗口又稱固定窗口（又稱計(jì)數(shù)器算法，F(xiàn)ixed Window）限流算法，是最簡單的限流算法，通過在單位時(shí)間內(nèi)維護(hù)的計(jì)數(shù)器來控制該時(shí)間單位內(nèi)的最大訪問量。

假設(shè)限制每分鐘請(qǐng)求量不超過60，設(shè)置一個(gè)計(jì)數(shù)器，當(dāng)請(qǐng)求到達(dá)時(shí)如果計(jì)數(shù)器到達(dá)閾值，則拒絕請(qǐng)求，否則計(jì)數(shù)器加1；每分鐘重置計(jì)數(shù)器為0。代碼實(shí)現(xiàn)如下：

public class CounterRateLimiter extends MyRateLimiter {
    /**
     * 每秒限制請(qǐng)求數(shù)
     */
    private final long permitsPerSecond;
    /**
     * 上一個(gè)窗口的開始時(shí)間
     */
    public long timestamp = System.currentTimeMillis();
    /**
     * 計(jì)數(shù)器
     */
    private int counter;

    public CounterRateLimiter(long permitsPerSecond) {
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 窗口內(nèi)請(qǐng)求數(shù)量小于閾值，更新計(jì)數(shù)放行，否則拒絕請(qǐng)求
        if (now - timestamp < 1000) {
            if (counter < permitsPerSecond) {
                counter++;
                return true;
            } else {
                return false;
            }
        }
        // 時(shí)間窗口過期，重置計(jì)數(shù)器和時(shí)間戳
        counter = 0;
        timestamp = now;
        return true;
    }
}

固定窗口最大的優(yōu)點(diǎn)在于 易于實(shí)現(xiàn) ；并且 內(nèi)存占用小 ，我們只需要存儲(chǔ)時(shí)間窗口中的計(jì)數(shù)即可；它能夠確保處理更多的最新請(qǐng)求，不會(huì)因?yàn)榕f請(qǐng)求的堆積導(dǎo)致新請(qǐng)求被餓死。當(dāng)然也面臨著 臨界問題 ，當(dāng)兩個(gè)窗口交界處，瞬時(shí)流量可能為2n。

image

02 滑動(dòng)窗口

為了防止瞬時(shí)流量，可以把固定窗口近一步劃分成多個(gè)格子，每次向后移動(dòng)一小格，而不是固定窗口大小，這就是滑動(dòng)窗口（Sliding Window）。

比如每分鐘可以分為6個(gè)10秒中的單元格，每個(gè)格子中分別維護(hù)一個(gè)計(jì)數(shù)器，窗口每次向前滑動(dòng)一個(gè)單元格。每當(dāng)請(qǐng)求到達(dá)時(shí)，只要窗口中所有單元格的計(jì)數(shù)總和不超過閾值都可以放行。TCP協(xié)議中數(shù)據(jù)包的傳輸，同樣也是采用滑動(dòng)窗口來進(jìn)行流量控制。

image

實(shí)現(xiàn)如下：

public class SlidingWindowRateLimiter extends MyRateLimiter {
    /**
     * 每分鐘限制請(qǐng)求數(shù)
     */
    private final long permitsPerMinute;
    /**
     * 計(jì)數(shù)器, k-為當(dāng)前窗口的開始時(shí)間值秒，value為當(dāng)前窗口的計(jì)數(shù)
     */
    private final TreeMap<Long, Integer> counters;

    public SlidingWindowRateLimiter(long permitsPerMinute) {
        this.permitsPerMinute = permitsPerMinute;
        this.counters = new TreeMap<>();
    }

    @Override
    public synchronized boolean tryAcquire() {
        // 獲取當(dāng)前時(shí)間的所在的子窗口值； 10s一個(gè)窗口
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / 10 * 10;
        // 獲取當(dāng)前窗口的請(qǐng)求總量
        int currentWindowCount = getCurrentWindowCount(currentWindowTime);
        if (currentWindowCount >= permitsPerMinute) {
            return false;
        }
        // 計(jì)數(shù)器 + 1
        counters.merge(currentWindowTime, 1, Integer::sum);
        return true;
    }
    /**
     * 獲取當(dāng)前窗口中的所有請(qǐng)求數(shù)（并刪除所有無效的子窗口計(jì)數(shù)器）
     *
     * @param currentWindowTime 當(dāng)前子窗口時(shí)間
     * @return 當(dāng)前窗口中的計(jì)數(shù)
     */
    private int getCurrentWindowCount(long currentWindowTime) {
        // 計(jì)算出窗口的開始位置時(shí)間
        long startTime = currentWindowTime - 50;
        int result = 0;

        // 遍歷當(dāng)前存儲(chǔ)的計(jì)數(shù)器，刪除無效的子窗口計(jì)數(shù)器，并累加當(dāng)前窗口中的所有計(jì)數(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;
    }
}

滑動(dòng)窗口解決了計(jì)數(shù)器中的瞬時(shí)流量高峰問題，其實(shí)計(jì)數(shù)器算法也是滑動(dòng)窗口的一種，只不過窗口沒有進(jìn)行更細(xì)粒度單元的劃分。對(duì)比計(jì)數(shù)器可見，當(dāng)窗口劃分的粒度越細(xì)，則流量控制更加精準(zhǔn)和嚴(yán)格。

不過當(dāng)窗口中流量到達(dá)閾值時(shí)，流量會(huì)瞬間切斷，在實(shí)際應(yīng)用中我們要的限流效果往往不是把流量一下子掐斷，而是讓流量平滑地進(jìn)入系統(tǒng)當(dāng)中。

03 漏桶算法

如何更加平滑的限流？不妨看看漏桶算法（Leaky Bucket），請(qǐng)求就像水一樣以任意速度注入漏桶，而桶會(huì)按照固定的速率將水漏掉；當(dāng)注入速度持續(xù)大于漏出的速度時(shí)，漏桶會(huì)變滿，此時(shí)新進(jìn)入的請(qǐng)求將會(huì)被丟棄。 限流 和 整形 是漏桶算法的兩個(gè)核心能力。

image

實(shí)現(xiàn)如下：

public class LeakyBucketRateLimiter extends MyRateLimiter {
    // 桶的容量
    private final int capacity;
    // 漏出速率
    private final int permitsPerSecond;
    // 剩余水量
    private long leftWater;
    // 上次注入時(shí)間
    private long timeStamp = System.currentTimeMillis();

    public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) {
        this.capacity = capacity;
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        //1. 計(jì)算剩余水量
        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;
    }
}

這并不是一個(gè)完整的漏桶算法的實(shí)現(xiàn)，以上代碼中只是對(duì)流量是否會(huì)被拋棄進(jìn)行校驗(yàn)，即tryAcquire返回true表示漏桶未滿，否則表示漏桶已滿丟棄請(qǐng)求。

想要以恒定的速率漏出流量，通常還應(yīng)配合一個(gè)FIFO隊(duì)列來實(shí)現(xiàn)，當(dāng)tryAcquire返回true時(shí)，將請(qǐng)求入隊(duì)，然后再以固定頻率從隊(duì)列中取出請(qǐng)求進(jìn)行處理。示例代碼如下：

@Test
public void testLeakyBucketRateLimiter() throws InterruptedException {
    ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
    ExecutorService singleThread = Executors.newSingleThreadExecutor();

    LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(20, 20);
    // 存儲(chǔ)流量的隊(duì)列
    Queue<Integer> queue = new LinkedList<>();
    // 模擬請(qǐng)求  不確定速率注水
    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();
            }
        }
    });

    // 模擬處理請(qǐng)求 固定速率漏水
    scheduledExecutorService.scheduleAtFixedRate(() -> {
        if (!queue.isEmpty()) {
            System.out.println(queue.poll() + "被處理");
        }
    }, 0, 100, TimeUnit.MILLISECONDS);

    // 保證主線程不會(huì)退出
    while (true) {
        Thread.sleep(10000);
    }
}

漏桶算法存在目的主要是用來 平滑突發(fā)的流量 ，提供一種機(jī)制來確保網(wǎng)絡(luò)中的突發(fā)流量被整合成平滑穩(wěn)定的額流量。

不過由于漏桶對(duì)流量的控制過于嚴(yán)格，在有些場景下 不能充分使用系統(tǒng)資源 ，因?yàn)槁┩暗穆┏鏊俾适枪潭ǖ模词乖谀骋粫r(shí)刻下游能夠處理更大的流量，漏桶也不允許突發(fā)流量通過。

04 令牌桶

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

image

令牌桶具有以下特點(diǎn)：

1. 以恒定的速率發(fā)放令牌，假設(shè)限流速率為v/s，則表示每1/v秒發(fā)放一個(gè)令牌

2. 假設(shè)令牌桶容量是b，如果令牌桶已滿，則新的令牌會(huì)被丟棄

3. 請(qǐng)求能夠通過限流器的前提是令牌桶中有令牌

令牌桶算法中值得關(guān)注的參數(shù)有兩個(gè)，即限流速率v/s，和令牌桶容量b；速率a表示限流器一般情況下的限流速率，而b則是burst的簡寫，表示限流器允許的最大突發(fā)流量。

比如b=10，當(dāng)令牌桶滿的時(shí)候有10個(gè)可用令牌，此時(shí)允許10個(gè)請(qǐng)求同時(shí)通過限流器（ 允許流量一定程度的突發(fā) ），這10個(gè)請(qǐng)求瞬間消耗完令牌后，后續(xù)的流量只能按照速率r通過限流器。

實(shí)現(xiàn)如下：

public class TokenBucketRateLimiter extends MyRateLimiter {
    /**
     * 令牌桶的容量「限流器允許的最大突發(fā)流量」
     */
    private final long capacity;
    /**
     * 令牌發(fā)放速率
     */
    private final long generatedPerSeconds;
    /**
     * 最后一個(gè)令牌發(fā)放的時(shí)間
     */
    long lastTokenTime = System.currentTimeMillis();
    /**
     * 當(dāng)前令牌數(shù)量
     */
    private long currentTokens;

    public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
        this.generatedPerSeconds = generatedPerSeconds;
        this.capacity = capacity;
    }

    /**
     * 嘗試獲取令牌
     *
     * @return true表示獲取到令牌，放行；否則為限流
     */
    @Override
    public synchronized boolean tryAcquire() {
          /**
           * 計(jì)算令牌當(dāng)前數(shù)量
           * 請(qǐng)求時(shí)間在最后令牌是產(chǎn)生時(shí)間相差大于等于額1s（為啥時(shí)1s？因?yàn)樯闪钆频淖钚r(shí)間單位時(shí)s），則
           * 1. 重新計(jì)算令牌桶中的令牌數(shù)
           * 2. 將最后一個(gè)令牌發(fā)放時(shí)間重置為當(dāng)前時(shí)間
           */
        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;
    }
}

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

由于 線程調(diào)度的不確定性 ，在高并發(fā)場景時(shí)，定時(shí)器誤差非常大，同時(shí)定時(shí)器本身會(huì)創(chuàng)建調(diào)度線程，也會(huì)對(duì) 系統(tǒng)的性能 產(chǎn)生影響。

05 滑動(dòng)日志

滑動(dòng)日志是一個(gè)比較“冷門”，但是確實(shí)好用的限流算法。滑動(dòng)日志限速算法需要記錄請(qǐng)求的時(shí)間戳，通常使用 有序集合 來存儲(chǔ)，我們可以在單個(gè)有序集合中跟蹤用戶在一個(gè)時(shí)間段內(nèi)所有的請(qǐng)求。

假設(shè)我們要限制給定T時(shí)間內(nèi)的請(qǐng)求不超過N，我們只需要存儲(chǔ)最近T時(shí)間之內(nèi)的請(qǐng)求日志，每當(dāng)請(qǐng)求到來時(shí)判斷最近T時(shí)間內(nèi)的請(qǐng)求總數(shù)是否超過閾值。

image

實(shí)現(xiàn)如下：

public class SlidingLogRateLimiter extends MyRateLimiter {
    /**
     * 每分鐘限制請(qǐng)求數(shù)
     */
    private static final long PERMITS_PER_MINUTE = 60;
    /**
     * 請(qǐng)求日志計(jì)數(shù)器, k-為請(qǐng)求的時(shí)間（秒），value當(dāng)前時(shí)間的請(qǐng)求數(shù)量
     */
    private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();

    @Override
    public synchronized boolean tryAcquire() {
        // 最小時(shí)間粒度為s
        long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
        // 獲取當(dāng)前窗口的請(qǐng)求總數(shù)
        int currentWindowCount = getCurrentWindowCount(currentTimestamp);
        if (currentWindowCount >= PERMITS_PER_MINUTE) {
            return false;
        }
        // 請(qǐng)求成功，將當(dāng)前請(qǐng)求日志加入到日志中
        requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
        return true;
    }

    /**
     * 統(tǒng)計(jì)當(dāng)前時(shí)間窗口內(nèi)的請(qǐng)求數(shù)
     *
     * @param currentTime 當(dāng)前時(shí)間
     * @return -
     */
    private int getCurrentWindowCount(long currentTime) {
        // 計(jì)算出窗口的開始位置時(shí)間
        long startTime = currentTime - 59;
        // 遍歷當(dāng)前存儲(chǔ)的計(jì)數(shù)器，刪除無效的子窗口計(jì)數(shù)器，并累加當(dāng)前窗口中的所有計(jì)數(shù)器之和
        return requestLogCountMap.entrySet()
                .stream()
                .filter(entry -> entry.getKey() >= startTime)
                .mapToInt(Map.Entry::getValue)
                .sum();
    }
}

滑動(dòng)日志能夠避免突發(fā)流量，實(shí)現(xiàn)較為精準(zhǔn)的限流；同樣 更加靈活，能夠支持更加復(fù)雜的限流策略 ，如多級(jí)限流，每分鐘不超過100次，每小時(shí)不超過300次，每天不超過1000次，我們只需要保存最近24小時(shí)所有的請(qǐng)求日志即可實(shí)現(xiàn)。

靈活并不是沒有代價(jià)的，帶來的缺點(diǎn)就是 占用存儲(chǔ)空間要高于其他限流算法 。

06 分布式限流

以上幾種限流算法的實(shí)現(xiàn)都僅適合單機(jī)限流。雖然給每臺(tái)機(jī)器平均分配限流配額可以達(dá)到限流的目的，但是由于機(jī)器性能，流量分布不均以及計(jì)算數(shù)量動(dòng)態(tài)變化等問題，單機(jī)限流在分布式場景中的效果總是差強(qiáng)人意。

分布式限流最簡單的實(shí)現(xiàn)就是利用中心化存儲(chǔ)，即將單機(jī)限流存儲(chǔ)在本地的數(shù)據(jù)存儲(chǔ)到同一個(gè)存儲(chǔ)空間中，如常見的Redis等。

image

當(dāng)然也可以從上層流量入口進(jìn)行限流，Nginx代理服務(wù)就提供了限流模塊，同樣能夠?qū)崿F(xiàn)高性能，精準(zhǔn)的限流，其底層是漏桶算法。

image

07 總結(jié)

1. 固定窗口算法實(shí)現(xiàn)簡單，性能高，但是會(huì)有臨界突發(fā)流量問題，瞬時(shí)流量最大可以達(dá)到閾值的2倍。

2. 為了解決臨界突發(fā)流量，可以將窗口劃分為多個(gè)更細(xì)粒度的單元，每次窗口向右移動(dòng)一個(gè)單元，于是便有了滑動(dòng)窗口算法。

   滑動(dòng)窗口當(dāng)流量到達(dá)閾值時(shí)會(huì)瞬間掐斷流量，所以導(dǎo)致流量不夠平滑。

3. 想要達(dá)到限流的目的，又不會(huì)掐斷流量，使得流量更加平滑？可以考慮漏桶算法！需要注意的是，漏桶算法通常配置一個(gè)FIFO的隊(duì)列使用以達(dá)到允許限流的作用。

   由于速率固定，即使在某個(gè)時(shí)刻下游處理能力過剩，也不能得到很好的利用，這是漏桶算法的一個(gè)短板。

4. 限流和瞬時(shí)流量其實(shí)并不矛盾，在大多數(shù)場景中，短時(shí)間突發(fā)流量系統(tǒng)是完全可以接受的。令牌桶算法就是不二之選了，令牌桶以固定的速率v產(chǎn)生令牌放入一個(gè)固定容量為n的桶中，當(dāng)請(qǐng)求到達(dá)時(shí)嘗試從桶中獲取令牌。

   當(dāng)桶滿時(shí)，允許最大瞬時(shí)流量為n；當(dāng)桶中沒有剩余流量時(shí)則限流速率最低，為令牌生成的速率v。

5. 如何實(shí)現(xiàn)更加靈活的多級(jí)限流呢？滑動(dòng)日志限流算法了解一下！這里的日志則是請(qǐng)求的時(shí)間戳，通過計(jì)算制定時(shí)間段內(nèi)請(qǐng)求總數(shù)來實(shí)現(xiàn)靈活的限流。

   當(dāng)然，由于需要存儲(chǔ)時(shí)間戳信息，其占用的存儲(chǔ)空間要比其他限流算法要大得多。

不管黑貓白貓，能抓到老鼠的就是好貓。限流算法并沒有絕對(duì)的好劣之分，如何選擇合適的限流算法呢？不妨從性能， 是否允許超出閾值 ， 落地成本 ， 流量平滑度 ， 是否允許突發(fā)流量 以及 系統(tǒng)資源 大小限制多方面考慮。

當(dāng)然，市面上也有比較成熟的限流工具和框架。如Google出品的 Guava 中基于令牌桶實(shí)現(xiàn)的限流組件，拿來即用；以及alibaba開源的面向分布式服務(wù)架構(gòu)的流量控制框架 Sentinel 更會(huì)讓你愛不釋手，它是基于滑動(dòng)窗口實(shí)現(xiàn)的。