在分布式系統(tǒng)中，高并發(fā)場(chǎng)景下，為了防止系統(tǒng)因突然的流量激增而導(dǎo)致的崩潰，同時(shí)保證服務(wù)的高可用性和穩(wěn)定性，限流是最常用的手段。

限流算法也是面試中必考題，今天一燈帶大家一塊學(xué)習(xí)一下常見(jiàn)的四種限流算法，分別是：固定窗口算法、滑動(dòng)窗口算法、漏桶算法、令牌桶算法。

1. 固定窗口算法

1.1 實(shí)現(xiàn)原理

固定窗口限流算法，也叫計(jì)數(shù)器限流算法，是最簡(jiǎn)單的一種限流算法。

實(shí)現(xiàn)原理是： 在一個(gè)固定長(zhǎng)度的時(shí)間窗口內(nèi)限制請(qǐng)求數(shù)量，每來(lái)一個(gè)請(qǐng)求，請(qǐng)求次數(shù)加一，如果請(qǐng)求數(shù)量超過(guò)最大限制，就拒絕該請(qǐng)求。

下面使用Java偽代碼實(shí)現(xiàn)一下固定窗口限流算法，注意以下算法沒(méi)有考慮并發(fā)情況，在并發(fā)環(huán)境下，可以使用Synchronized、Reentrantlock或者AtomicLong等并發(fā)工具來(lái)保證數(shù)據(jù)安全性。

1.2 代碼實(shí)現(xiàn)

/**
 * @author 一燈架構(gòu)
 * @apiNote 固定窗口限流算法
 **/
public class FixWindowLimiter {

    /**
     * 每個(gè)窗口的最大請(qǐng)求數(shù)量
     */
    public static long threshold = 10;
    /**
     * 窗口大小，1000ms
     */
    public static long windowUnit = 1000;
    /**
     * 窗口內(nèi)的當(dāng)前請(qǐng)求數(shù)量
     */
    public static long count = 0;
    /**
     * 窗口的開(kāi)始時(shí)間
     */
    public static long lastTime = 0;

    /**
     * 限流方法，返回true表示通過(guò)
     */
    public boolean limit() {
        // 獲取系統(tǒng)當(dāng)前時(shí)間
        long currentTime = System.currentTimeMillis();
        // 判斷是否在當(dāng)前時(shí)間窗口內(nèi)，如果不在就開(kāi)啟一個(gè)新的時(shí)間窗口
        if (currentTime - lastTime > windowUnit) {
            // 計(jì)數(shù)器清零
            count = 0;
            // 開(kāi)啟新的時(shí)間窗口
            lastTime = currentTime;
        }
        // 判斷是否超過(guò)最大請(qǐng)求量
        if (count < threshold) {
            count++;
            return true;
        }
        return false;
    }

}

1.3 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)： 實(shí)現(xiàn)簡(jiǎn)單，容易理解。

缺點(diǎn)：

1. 限流不夠平滑。例如：限流是每秒3個(gè)，在第一毫秒發(fā)送了3個(gè)請(qǐng)求，達(dá)到限流，窗口剩余時(shí)間的請(qǐng)求都將會(huì)被拒絕，體驗(yàn)不好。
2. 無(wú)法處理窗口邊界問(wèn)題。因?yàn)槭窃谀硞€(gè)時(shí)間窗口內(nèi)進(jìn)行流量控制，所以可能會(huì)出現(xiàn)窗口邊界效應(yīng)，即在時(shí)間窗口的邊界處可能會(huì)有大量的請(qǐng)求被允許通過(guò)，從而導(dǎo)致突發(fā)流量。

例如：限流是每秒3個(gè)，在第一秒的最后一毫秒發(fā)送了3個(gè)請(qǐng)求，在第二秒的第一毫秒又發(fā)送了3個(gè)請(qǐng)求。在這兩毫米內(nèi)處理了6個(gè)請(qǐng)求，但是并沒(méi)有觸發(fā)限流。如果出現(xiàn)突發(fā)流量，可能會(huì)壓垮服務(wù)器。

2. 滑動(dòng)窗口算法

2.1 實(shí)現(xiàn)原理

滑動(dòng)窗口算法是對(duì)固定窗口算法的一種改進(jìn)。在滑動(dòng)窗口算法中，窗口的起止時(shí)間是動(dòng)態(tài)的，窗口的大小固定。這種算法能夠較好地處理窗口邊界問(wèn)題，但是實(shí)現(xiàn)相對(duì)復(fù)雜，需要記錄每個(gè)請(qǐng)求的時(shí)間戳。

實(shí)現(xiàn)原理是： 每來(lái)一個(gè)請(qǐng)求，就向后推一個(gè)時(shí)間窗口，計(jì)算這個(gè)窗口內(nèi)的請(qǐng)求數(shù)量。如果請(qǐng)求數(shù)量超過(guò)限制就拒絕請(qǐng)求，否則就處理請(qǐng)求，并記錄請(qǐng)求的時(shí)間戳。另外還需要一個(gè)任務(wù)清理過(guò)期的時(shí)間戳。

2.2 代碼實(shí)現(xiàn)

/**
 * @author 一燈架構(gòu)
 * @apiNote 固定窗口限流算法
 **/
public class SlidingWindowLimiter {

    /**
     * 每個(gè)窗口的最大請(qǐng)求數(shù)量
     */
    public static long threshold = 10;
    /**
     * 窗口大小，1000ms
     */
    public static long windowUnit = 1000;
    /**
     * 請(qǐng)求集合，用來(lái)存儲(chǔ)窗口內(nèi)的請(qǐng)求數(shù)量
     */
    public static List<Long> requestList = new ArrayList<>();

    /**
     * 限流方法，返回true表示通過(guò)
     */
    public boolean limit() {
        // 獲取系統(tǒng)當(dāng)前時(shí)間
        long currentTime = System.currentTimeMillis();
        // 統(tǒng)計(jì)當(dāng)前窗口內(nèi)，有效的請(qǐng)求數(shù)量
        int sizeOfValid = this.sizeOfValid(currentTime);
        // 判斷是否超過(guò)最大請(qǐng)求數(shù)量
        if (sizeOfValid < threshold) {
            // 把當(dāng)前請(qǐng)求添加到請(qǐng)求集合里
            requestList.add(currentTime);
            return true;
        }
        return false;
    }

    /**
     * 統(tǒng)計(jì)當(dāng)前窗口內(nèi)，有效的請(qǐng)求數(shù)量
     */
    private int sizeOfValid(long currentTime) {
        int sizeOfValid = 0;
        for (Long requestTime : requestList) {
            // 判斷是否在當(dāng)前時(shí)間窗口內(nèi)
            if (currentTime - requestTime <= windowUnit) {
                sizeOfValid++;
            }
        }
        return sizeOfValid;
    }

    /**
     * 清理過(guò)期的請(qǐng)求（單獨(dú)啟動(dòng)一個(gè)線(xiàn)程處理）
     */
    private void clean() {
        // 判斷是否超出當(dāng)前時(shí)間窗口內(nèi)
        requestList.removeIf(requestTime -> System.currentTimeMillis() - requestTime > windowUnit);
    }

}

2.3 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)： 解決了固定窗口算法的窗口邊界問(wèn)題，避免突發(fā)流量壓垮服務(wù)器。

缺點(diǎn)： 還是存在限流不夠平滑的問(wèn)題。例如：限流是每秒3個(gè)，在第一毫秒發(fā)送了3個(gè)請(qǐng)求，達(dá)到限流，剩余窗口時(shí)間的請(qǐng)求都將會(huì)被拒絕，體驗(yàn)不好。

3. 漏桶算法

3.1 實(shí)現(xiàn)原理

漏桶限流算法是一種常用的流量整形（Traffic Shaping）和流量控制（Traffic Policing）的算法，它可以有效地控制數(shù)據(jù)的傳輸速率以及防止網(wǎng)絡(luò)擁塞。

實(shí)現(xiàn)原理是：

1. 一個(gè)固定容量的漏桶，按照固定速率出水（處理請(qǐng)求）；
2. 當(dāng)流入水（請(qǐng)求數(shù)量）的速度過(guò)大會(huì)直接溢出（請(qǐng)求數(shù)量超過(guò)限制則直接拒絕）。
3. 桶里的水（請(qǐng)求）不夠則無(wú)法出水（桶內(nèi)沒(méi)有請(qǐng)求則不處理）。

當(dāng)請(qǐng)求流量正?；蛘咻^小的時(shí)候，請(qǐng)求能夠得到正常的處理。當(dāng)請(qǐng)求流量過(guò)大時(shí)，漏桶限流算法可以通過(guò)丟棄部分請(qǐng)求來(lái)防止系統(tǒng)過(guò)載。

這種算法的一個(gè)重要特性是，輸出數(shù)據(jù)的速率始終是穩(wěn)定的，無(wú)論輸入的數(shù)據(jù)流量如何變化。這就確保了系統(tǒng)的負(fù)載不會(huì)超過(guò)預(yù)設(shè)的閾值。但是，由于漏桶的出口速度是固定的，所以無(wú)法處理突發(fā)流量。此外，如果入口流量過(guò)大，漏桶可能會(huì)溢出，導(dǎo)致數(shù)據(jù)丟失。

3.2 代碼實(shí)現(xiàn)

/**
 * @author 一燈架構(gòu)
 * @apiNote 漏桶限流算法
 **/
public class LeakyBucketLimiter {

    /**
     * 桶的最大容量
     */
    public static long threshold = 10;
    /**
     * 桶內(nèi)當(dāng)前水量
     */
    public static long count = 0;
    /**
     * 漏水速率（每秒5次）
     */
    public static long leakRate = 5;
    /**
     * 上次漏水時(shí)間
     */
    public static long lastLeakTime = System.currentTimeMillis();

    /**
     * 限流方法，返回true表示通過(guò)
     */
    public boolean limit() {
        // 調(diào)用漏水方法
        this.leak();
        // 判斷是否超過(guò)最大請(qǐng)求數(shù)量
        if (count < threshold) {
            count++;
            return true;
        }
        return false;
    }

    /**
     * 漏水方法，計(jì)算并更新這段時(shí)間內(nèi)漏水量
     */
    private void leak() {
        // 獲取系統(tǒng)當(dāng)前時(shí)間
        long currentTime = System.currentTimeMillis();
        // 計(jì)算這段時(shí)間內(nèi)，需要流出的水量
        long leakWater = (currentTime - lastLeakTime) * leakRate / 1000;
        count = Math.max(count - leakWater, 0);
        lastLeakTime = currentTime;
    }

}

3.3 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 平滑流量。由于漏桶算法以固定的速率處理請(qǐng)求，可以有效地平滑和整形流量，避免流量的突發(fā)和波動(dòng)（類(lèi)似于消息隊(duì)列的削峰填谷的作用）。
2. 防止過(guò)載。當(dāng)流入的請(qǐng)求超過(guò)桶的容量時(shí)，可以直接丟棄請(qǐng)求，防止系統(tǒng)過(guò)載。

缺點(diǎn)：

1. 無(wú)法處理突發(fā)流量：由于漏桶的出口速度是固定的，無(wú)法處理突發(fā)流量。例如，即使在流量較小的時(shí)候，也無(wú)法以更快的速度處理請(qǐng)求。
2. 可能會(huì)丟失數(shù)據(jù)：如果入口流量過(guò)大，超過(guò)了桶的容量，那么就需要丟棄部分請(qǐng)求。在一些不能接受丟失請(qǐng)求的場(chǎng)景中，這可能是一個(gè)問(wèn)題。
3. 不適合速率變化大的場(chǎng)景：如果速率變化大，或者需要?jiǎng)討B(tài)調(diào)整速率，那么漏桶算法就無(wú)法滿(mǎn)足需求。

4. 令牌桶算法

4.1 實(shí)現(xiàn)原理

令牌桶限流算法是一種常用的流量整形和速率限制算法。與漏桶算法一樣，令牌桶算法也是用來(lái)控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)量。

實(shí)現(xiàn)原理：

1. 系統(tǒng)以固定的速率向桶中添加令牌；
2. 當(dāng)有請(qǐng)求到來(lái)時(shí)，會(huì)嘗試從桶中移除一個(gè)令牌，如果桶中有足夠的令牌，則請(qǐng)求可以被處理或數(shù)據(jù)包可以被發(fā)送；
3. 如果桶中沒(méi)有令牌，那么請(qǐng)求將被拒絕；
4. 桶中的令牌數(shù)不能超過(guò)桶的容量，如果新生成的令牌超過(guò)了桶的容量，那么新的令牌會(huì)被丟棄。

令牌桶算法的一個(gè)重要特性是，它能夠應(yīng)對(duì)突發(fā)流量。當(dāng)桶中有足夠的令牌時(shí)，可以一次性處理多個(gè)請(qǐng)求，這對(duì)于需要處理突發(fā)流量的應(yīng)用場(chǎng)景非常有用。但是又不會(huì)無(wú)限制的增加處理速率導(dǎo)致壓垮服務(wù)器，因?yàn)橥皟?nèi)令牌數(shù)量是有限制的。

4.2 代碼實(shí)現(xiàn)

/**
 * @author 一燈架構(gòu)
 * @apiNote 漏桶限流算法
 **/
public class TokenBucketLimiter {

    /**
     * 桶的最大容量
     */
    public static long threshold = 10;
    /**
     * 桶內(nèi)當(dāng)前的令牌數(shù)量
     */
    public static long count = 0;
    /**
     * 令牌生成速率（每秒5次）
     */
    public static long tokenRate = 5;
    /**
     * 上次生成令牌的時(shí)間
     */
    public static long lastRefillTime = System.currentTimeMillis();

    /**
     * 限流方法，返回true表示通過(guò)
     */
    public boolean limit() {
        // 調(diào)用生成令牌方法
        this.refillTokens();
        // 判斷桶內(nèi)是否還有令牌
        if (count > 0) {
            count--;
            return true;
        }
        return false;
    }

    /**
     * 生成令牌方法，計(jì)算并更新這段時(shí)間內(nèi)生成的令牌數(shù)量
     */
    private void refillTokens() {
        long currentTime = System.currentTimeMillis();
        // 計(jì)算這段時(shí)間內(nèi)，需要生成的令牌數(shù)量
        long refillTokens = (currentTime - lastRefillTime) * tokenRate / 1000;
        count = Math.min(count + refillTokens, threshold);
        lastRefillTime = currentTime;
    }

}

4.3 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1. 可以處理突發(fā)流量：令牌桶算法可以處理突發(fā)流量。當(dāng)桶滿(mǎn)時(shí)，能夠以最大速度處理請(qǐng)求。這對(duì)于需要處理突發(fā)流量的應(yīng)用場(chǎng)景非常有用。
2. 限制平均速率：在長(zhǎng)期運(yùn)行中，數(shù)據(jù)的傳輸率會(huì)被限制在預(yù)定義的平均速率（即生成令牌的速率）。
3. 靈活性：與漏桶算法相比，令牌桶算法提供了更大的靈活性。例如，可以動(dòng)態(tài)地調(diào)整生成令牌的速率。

缺點(diǎn)：

1. 可能導(dǎo)致過(guò)載：如果令牌產(chǎn)生的速度過(guò)快，可能會(huì)導(dǎo)致大量的突發(fā)流量，這可能會(huì)使網(wǎng)絡(luò)或服務(wù)過(guò)載。
2. 需要存儲(chǔ)空間：令牌桶需要一定的存儲(chǔ)空間來(lái)保存令牌，可能會(huì)導(dǎo)致內(nèi)存資源的浪費(fèi)。
3. 實(shí)現(xiàn)稍復(fù)雜：相比于計(jì)數(shù)器算法，令牌桶算法的實(shí)現(xiàn)稍微復(fù)雜一些。

5. 總結(jié)

這篇文章我們介紹了四種常用的限流算法：固定窗口算法、滑動(dòng)窗口算法、漏桶算法和令牌桶算法。每種算法都有其特點(diǎn)和適用場(chǎng)景，下面我們來(lái)對(duì)它們進(jìn)行簡(jiǎn)單的總結(jié)和比較。

固定窗口算法實(shí)現(xiàn)簡(jiǎn)單，但是限流不夠平滑，存在窗口邊界問(wèn)題，適用于需要簡(jiǎn)單實(shí)現(xiàn)限流的場(chǎng)景。

滑動(dòng)窗口算法解決了窗口邊界問(wèn)題，但是還是存在限流不夠平滑的問(wèn)題，適用于需要控制平均請(qǐng)求速率的場(chǎng)景。

漏桶算法的優(yōu)點(diǎn)是流量處理更平滑，但是無(wú)法應(yīng)對(duì)突發(fā)流量，適用于需要平滑流量的場(chǎng)景。

令牌桶算法既能平滑流量，又能處理突發(fā)流量，適用于需要處理突發(fā)流量的場(chǎng)景。