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

在高并發(fā)系統(tǒng)中走哺，出于系統(tǒng)保護角度考慮，通常會對流量進行限流哲虾；不但在工作中要頻繁使用丙躏，而且也是面試中的高頻考點。

今天我們將圖文并茂地對常見的限流算法分別進行介紹束凑，通過各個算法的特點晒旅，給出限流算法選型的一些建議，并給出Java語言實現(xiàn)的代碼示例汪诉。

01 固定窗口

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

假設(shè)限制每分鐘請求量不超過60拟烫，設(shè)置一個計數(shù)器，當(dāng)請求到達時如果計數(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ù)即可赃份；它能夠確保處理更多的最新請求寂拆，不會因為舊請求的堆積導(dǎo)致新請求被餓死。當(dāng)然也面臨著 臨界問題 抓韩，當(dāng)兩個窗口交界處纠永，瞬時流量可能為2n。

image

02 滑動窗口

為了防止瞬時流量谒拴，可以把固定窗口近一步劃分成多個格子尝江，每次向后移動一小格，而不是固定窗口大小英上，這就是滑動窗口（Sliding Window）炭序。

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

image

實現(xiàn)如下：

public class SlidingWindowRateLimiter extends MyRateLimiter {
    /**
     * 每分鐘限制請求數(shù)
     */
    private final long permitsPerMinute;
    /**
     * 計數(shù)器, k-為當(dāng)前窗口的開始時間值秒拦耐，value為當(dāng)前窗口的計數(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)前時間的所在的子窗口值耕腾； 10s一個窗口
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / 10 * 10;
        // 獲取當(dāng)前窗口的請求總量
        int currentWindowCount = getCurrentWindowCount(currentWindowTime);
        if (currentWindowCount >= permitsPerMinute) {
            return false;
        }
        // 計數(shù)器 + 1
        counters.merge(currentWindowTime, 1, Integer::sum);
        return true;
    }
    /**
     * 獲取當(dāng)前窗口中的所有請求數(shù)（并刪除所有無效的子窗口計數(shù)器）
     *
     * @param currentWindowTime 當(dāng)前子窗口時間
     * @return 當(dāng)前窗口中的計數(shù)
     */
    private int getCurrentWindowCount(long currentWindowTime) {
        // 計算出窗口的開始位置時間
        long startTime = currentWindowTime - 50;
        int result = 0;

        // 遍歷當(dāng)前存儲的計數(shù)器，刪除無效的子窗口計數(shù)器杀糯，并累加當(dāng)前窗口中的所有計數(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ù)器可見狼纬，當(dāng)窗口劃分的粒度越細羹呵，則流量控制更加精準(zhǔn)和嚴(yán)格。

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

03 漏桶算法

如何更加平滑的限流涛癌？不妨看看漏桶算法（Leaky Bucket），請求就像水一樣以任意速度注入漏桶送火，而桶會按照固定的速率將水漏掉拳话；當(dāng)注入速度持續(xù)大于漏出的速度時，漏桶會變滿种吸，此時新進入的請求將會被丟棄弃衍。 限流 和 整形 是漏桶算法的兩個核心能力。

image

實現(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表示漏桶未滿速缆，否則表示漏桶已滿丟棄請求。

想要以恒定的速率漏出流量恩闻，通常還應(yīng)配合一個FIFO隊列來實現(xiàn)艺糜，當(dāng)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)絡(luò)中的突發(fā)流量被整合成平滑穩(wěn)定的額流量尉剩。

不過由于漏桶對流量的控制過于嚴(yán)格真慢，在有些場景下 不能充分使用系統(tǒng)資源 ，因為漏桶的漏出速率是固定的理茎，即使在某一時刻下游能夠處理更大的流量晤碘，漏桶也不允許突發(fā)流量通過。

04 令牌桶

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

image

令牌桶具有以下特點：

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

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

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

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

比如b=10芽腾，當(dāng)令牌桶滿的時候有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();
    /**
     * 當(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() {
          /**
           * 計算令牌當(dāng)前數(shù)量
           * 請求時間在最后令牌是產(chǎn)生時間相差大于等于額1s（為啥時1s呻袭？因為生成令牌的最小時間單位時s），則
           * 1. 重新計算令牌桶中的令牌數(shù)
           * 2. 將最后一個令牌發(fā)放時間重置為當(dāng)前時間
           */
        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)者線程定時向阻塞隊列中添加令牌，而試圖通過限流器的線程則作為消費者線程含长，只有從阻塞隊列中獲取到令牌券腔，才允許通過限流器。

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

05 滑動日志

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

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

image

實現(xiàn)如下：

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

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

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

滑動日志能夠避免突發(fā)流量，實現(xiàn)較為精準(zhǔn)的限流弹沽；同樣 更加靈活檀夹，能夠支持更加復(fù)雜的限流策略 ，如多級限流贷币，每分鐘不超過100次击胜，每小時不超過300次，每天不超過1000次役纹，我們只需要保存最近24小時所有的請求日志即可實現(xiàn)偶摔。

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

06 分布式限流

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

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

image

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

image

07 總結(jié)

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

2. 為了解決臨界突發(fā)流量俗孝，可以將窗口劃分為多個更細粒度的單元酒甸，每次窗口向右移動一個單元，于是便有了滑動窗口算法赋铝。

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

3. 想要達到限流的目的，又不會掐斷流量饮六，使得流量更加平滑？可以考慮漏桶算法苛蒲！需要注意的是卤橄，漏桶算法通常配置一個FIFO的隊列使用以達到允許限流的作用。

   由于速率固定臂外，即使在某個時刻下游處理能力過剩窟扑，也不能得到很好的利用，這是漏桶算法的一個短板漏健。

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

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

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

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

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

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