欄目導(dǎo)航

新聞資訊

新聞資訊

嘍，大家好呀，我是呼嚕嚕，好久沒有更新文章了，今天我們來聊聊在企業(yè)級(jí)項(xiàng)目中，常見的幾種限流手段的原理及其實(shí)現(xiàn)

什么場(chǎng)景需要限流

隨著互聯(lián)網(wǎng)的業(yè)務(wù)發(fā)展，比如秒殺、雙十一、618等這些我們耳熟能詳，也有被人惡意攻擊的場(chǎng)景下，系統(tǒng)往往經(jīng)受被高并發(fā)流量沖垮的風(fēng)險(xiǎn)，這個(gè)時(shí)候可以采用限流的方式，來保護(hù)自身的系統(tǒng)以及下游系統(tǒng)，當(dāng)然還有其他各種方式手段，比如熔斷、降級(jí)、隔離等，本文將重點(diǎn)來講講限流

限流就是就是對(duì)請(qǐng)求或并發(fā)數(shù)進(jìn)行限制，通過在一定時(shí)間內(nèi)對(duì)請(qǐng)求量進(jìn)行限制，來達(dá)到保護(hù)系統(tǒng)正常運(yùn)行的目的。常見的限流算法，有計(jì)數(shù)器算法、滑動(dòng)窗口計(jì)數(shù)算法、漏桶算法、令牌桶算法

計(jì)數(shù)器算法

計(jì)數(shù)器算法，通過計(jì)數(shù)器在周期內(nèi)累加訪問次數(shù)，并規(guī)定一個(gè)周期(時(shí)間窗口)內(nèi)的系統(tǒng)處理的請(qǐng)求數(shù)量(閾值)，當(dāng)在一個(gè)周期內(nèi)，計(jì)數(shù)的值達(dá)到限流閾值時(shí)觸發(fā)拒絕策略；到下一周期計(jì)數(shù)器就重置為0，重新開始計(jì)數(shù)，它是一種簡(jiǎn)單方便的限流算法

比如我們?cè)O(shè)置系統(tǒng)的閾值1s中最多請(qǐng)求100次，在計(jì)數(shù)器算法中，我們需要把時(shí)間劃分固定大小窗口(所以計(jì)數(shù)器算法又叫固定窗口算法Fixed Window)，這里我們將1s劃分為一個(gè)時(shí)間窗口；然后用計(jì)數(shù)器來記錄在每個(gè)時(shí)間窗口的處理的請(qǐng)求數(shù)量，如果請(qǐng)求數(shù)量超過100次，后續(xù)的請(qǐng)求會(huì)被直接拒絕，直到1s結(jié)束后，重新開始計(jì)數(shù)

計(jì)數(shù)器算法優(yōu)點(diǎn)實(shí)現(xiàn)簡(jiǎn)單, 占用內(nèi)存小，性能較高，但是有一個(gè)缺點(diǎn)，就是臨界問題，因?yàn)樵谝粋€(gè)時(shí)間窗口中，請(qǐng)求或者流量并不是均勻分布的，比如，在1.9s和2.1s的時(shí)間點(diǎn)，分別被人惡意并發(fā)請(qǐng)求了100次，也就是說從1.9s開始后的1s時(shí)間窗口期間，被瞬間請(qǐng)求了200次已經(jīng)超過系統(tǒng)的閾值了，即使窗口2和窗口3還是正常的，這樣可能會(huì)導(dǎo)致系統(tǒng)直接掛掉

這里提供一個(gè)簡(jiǎn)單的demo(Java版，其他語言大家自行改寫):

public class MyFixedWindowRateLimiterDemo {
    // 閾值
    private static Integer QPS=2;
    // 時(shí)間窗口（毫秒）
    private static long TIME_WINDOWS=1000;
    // 計(jì)數(shù)器
    private static AtomicInteger counter=new AtomicInteger();

    //上一個(gè)窗口的開始時(shí)間
    private static long START_TIME=System.currentTimeMillis();

    public synchronized static boolean tryAcquire() {
        if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
            counter.set(0);
            START_TIME=System.currentTimeMillis();
        }
        return counter.incrementAndGet() <=QPS;
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i=0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now=LocalTime.now();
            if (!tryAcquire()) {
                System.out.println(now + " 請(qǐng)求被限流");
            } else {
                System.out.println(now + " 請(qǐng)求通過");
            }
        }
    }
}

滑動(dòng)窗口計(jì)數(shù)算法

滑動(dòng)窗口算法(Sliding Window)出現(xiàn)于網(wǎng)絡(luò)協(xié)議中傳輸層，是一種流量控制技術(shù)。我們這里對(duì)計(jì)數(shù)器(固定窗口)算法的臨界問題，滑動(dòng)窗口算法進(jìn)行了改進(jìn)，不再固定窗口大小，而是將把固定窗口近一步劃分成多個(gè)小周期，每個(gè)周期都記錄自己的請(qǐng)求訪問次數(shù)，隨著時(shí)間流逝，滑動(dòng)時(shí)間窗口(每次向后移動(dòng)一周期)，同時(shí)刪除過期的小周期。每次判斷限流時(shí)，需要將一個(gè)窗口的所有小周期合起來，再與閾值進(jìn)行比較

舉個(gè)例子，上圖我們將1s時(shí)間窗口，劃分成5個(gè)200ms的小周期，記錄每個(gè)周期的請(qǐng)求訪問次數(shù)，這里沿用上一小節(jié)的情形在1.9s和2.1s的時(shí)間點(diǎn)，分別被人惡意并發(fā)請(qǐng)求了100次，當(dāng)滑動(dòng)到第5個(gè)小周期時(shí)，訪問量為100次，未達(dá)到閾值；而當(dāng)窗口滑動(dòng)到第6個(gè)小周期時(shí)，訪問數(shù)量變?yōu)椋?/span>200，這個(gè)時(shí)候會(huì)超過閾值，觸發(fā)拒絕訪問的限制

這樣就能限制住瞬時(shí)流量爆發(fā)。如果滑動(dòng)窗口的單位區(qū)間劃分越細(xì)的話，滑動(dòng)窗口的滾動(dòng)就越平滑，限流統(tǒng)計(jì)也會(huì)越精準(zhǔn)。但隨著而來的是實(shí)現(xiàn)滑動(dòng)窗口算法，需要更多的存儲(chǔ)空間。另外計(jì)數(shù)器算法實(shí)現(xiàn)起來比較簡(jiǎn)單，滑動(dòng)窗口則更復(fù)雜

這里提供一個(gè)筆者感覺非常簡(jiǎn)單明了的demo，參考于簡(jiǎn)單的java實(shí)現(xiàn)滑動(dòng)時(shí)間窗口限流算法，在此感謝

public class MySlidingWindowRateLimiterDemo {

    /** 隊(duì)列id和隊(duì)列的映射關(guān)系，隊(duì)列里面存儲(chǔ)的是每一次通過時(shí)候的時(shí)間戳，這樣可以使得程序里有多個(gè)限流隊(duì)列 */
    private volatile static Map<String, List<Long>> MAP=new ConcurrentHashMap<>();
    
    //閾值
    private static int QPS=2;
    //時(shí)間窗口總大小（毫秒）
    private static long WindowSize=10 * 1000;


    /**
     * 滑動(dòng)時(shí)間窗口限流算法
     * 在指定時(shí)間窗口，指定限制次數(shù)內(nèi)，是否允許通過
     *
     * @param listId     隊(duì)列id
     * @param count      限制次數(shù)
     * @param timeWindow 時(shí)間窗口大小
     * @return 是否允許通過
     */
    public static synchronized boolean tryAcquire(String listId, int count, long timeWindow) {
        // 獲取當(dāng)前時(shí)間
        long nowTime=System.currentTimeMillis();
        // 根據(jù)隊(duì)列id，取出對(duì)應(yīng)的限流隊(duì)列，若沒有則創(chuàng)建
        List<Long> list=MAP.computeIfAbsent(listId, k -> new LinkedList<>());
        // 如果隊(duì)列還沒滿，則允許通過，并添加當(dāng)前時(shí)間戳到隊(duì)列開始位置
        if (list.size() < count) {
            list.add(0, nowTime);
            return true;
        }

        // 隊(duì)列已滿（達(dá)到限制次數(shù)），則獲取隊(duì)列中最早添加的時(shí)間戳
        Long farTime=list.get(count - 1);
        // 用當(dāng)前時(shí)間戳 減去 最早添加的時(shí)間戳
        if (nowTime - farTime <=timeWindow) {
            // 若結(jié)果小于等于timeWindow，則說明在timeWindow內(nèi)，通過的次數(shù)大于count
            // 不允許通過
            return false;
        } else {
            // 若結(jié)果大于timeWindow，則說明在timeWindow內(nèi)，通過的次數(shù)小于等于count
            // 允許通過，并刪除最早添加的時(shí)間戳，將當(dāng)前時(shí)間添加到隊(duì)列開始位置
            list.remove(count - 1);
            list.add(0, nowTime);
            return true;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i=0; i < 20; i++) {
            Thread.sleep(1000);
            LocalTime now=LocalTime.now();
            if (!tryAcquire("ip", QPS, WindowSize)) {// 任意10秒內(nèi)，只允許2次通過;自定義限流規(guī)則“ip”
                System.out.println(now + " 請(qǐng)求被限流");
            } else {
                System.out.println(now + " 請(qǐng)求通過");
            }
        }
    }
}

美中不足的是，在滑動(dòng)窗口算法，窗口中流量到達(dá)閾值時(shí)，流量會(huì)瞬間切斷，而現(xiàn)實(shí)中我們還是更希望，讓流量跟平滑地放行到系統(tǒng)中，而不是簡(jiǎn)單粗暴地將其掐斷

漏桶算法

我們?cè)賮砜纯?/span>漏桶算法Leaky Bucket，是一個(gè)非常貼切的比喻，意思是，水(就是請(qǐng)求/流量)從進(jìn)水口(生產(chǎn)端)進(jìn)入桶(隊(duì)列)中，這個(gè)桶是漏的(比方說桶底有一個(gè)孔)，以一定的速度漏水(消費(fèi)端不斷的在消費(fèi)隊(duì)列中的請(qǐng)求)，當(dāng)水進(jìn)入桶的速度過大(大于漏水的速度)，會(huì)導(dǎo)致桶里的水堆積，當(dāng)超過桶容量時(shí)會(huì)溢出來(請(qǐng)求被拒絕)。從而實(shí)現(xiàn)網(wǎng)絡(luò)流量整形和限流的功能

這里漏水的速度其實(shí)就是限流的閾值，所謂的閾值，表示在一個(gè)單位時(shí)間內(nèi)允許的請(qǐng)求量，比如如QPS為100，說明1秒內(nèi)系統(tǒng)最多可以消費(fèi)100個(gè)請(qǐng)求。如果生產(chǎn)端的速率超過閾值的話，請(qǐng)求會(huì)慢慢堆積，又因?yàn)?/span>漏桶的容量是固定的，最后會(huì)觸發(fā)拒絕策略(溢出)

漏桶算法它的優(yōu)點(diǎn)是，實(shí)現(xiàn)起來簡(jiǎn)單，很容易理解。它可以嚴(yán)格限制請(qǐng)求的處理速度，一旦超過該速度就拒絕服務(wù)，從而避免網(wǎng)絡(luò)擁塞和系統(tǒng)過載

但它也有缺點(diǎn)：

即使沒有大流量，也求需要等待漏桶處理完成(流量限制過于嚴(yán)格)，這樣就會(huì)導(dǎo)致請(qǐng)求處理延遲，不適用于實(shí)時(shí)性要求很高的場(chǎng)景
由于它請(qǐng)求的處理速度是固定的，哪怕網(wǎng)絡(luò)沒有發(fā)生擁塞時(shí)，也不能使某一個(gè)單獨(dú)的數(shù)據(jù)流達(dá)到生產(chǎn)端的速率，也無法很好地應(yīng)對(duì)突發(fā)特性的流量，不能充分利用系統(tǒng)資源

這里提供一個(gè)簡(jiǎn)單的demo(不完整，生產(chǎn)慎用，僅用來演示):

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

    public MyLeakyBucketRateLimiterDemo(int rate, int capacity) {
        this.capacity=capacity;
        this.rate=rate;
    }

    public synchronized boolean tryAcquire() {
        //1. 計(jì)算剩余水量
        long now=System.currentTimeMillis();
        long timeGap=(now - timeStamp) / 1000;
        leftWater=Math.max(0, leftWater - timeGap * rate);
        timeStamp=now;

        // 如果未滿，則放行；否則限流
        if (leftWater < capacity) {
            leftWater +=1;
            return true;
        }
        return false;
    }


    public static void main(String[] args) throws InterruptedException {
        MyLeakyBucketRateLimiterDemo limiterDemo=new MyLeakyBucketRateLimiterDemo(2,5);
        for (int i=0; i < 10; i++) {
            Thread.sleep(500);
            LocalTime now=LocalTime.now();
            if (!limiterDemo.tryAcquire()) {
                System.out.println(now + " 請(qǐng)求被限流");
            } else {
                System.out.println(now + " 請(qǐng)求通過");
            }
        }
    }
}

令牌桶算法

令牌桶算法是漏桶算法的改進(jìn)版，是網(wǎng)絡(luò)流量整形(Traffic Shaping)和限流(Rate Limiting)中最常使用的一種算法，它也有一個(gè)桶，現(xiàn)在用來存放固定數(shù)量的令牌(token)，該算法會(huì)以一定的速率(閾值)往桶中發(fā)放令牌。每次請(qǐng)求都需要先獲取到桶中的一個(gè)令牌才能繼續(xù)執(zhí)行，請(qǐng)求處理完畢之后將這個(gè)令牌丟棄，否則執(zhí)行拒絕策略(一般有直接拒絕、排隊(duì)等待等)；另外放令牌的動(dòng)作是持續(xù)不斷進(jìn)行的，如果桶裝滿了，則丟棄令牌

表面上看，令牌桶算法和漏桶算法是相反的，一個(gè)"進(jìn)水"，一個(gè)是"漏水"。但與漏桶算法實(shí)際不同的是，令牌桶不僅能夠在限制客戶端請(qǐng)求流量速率的同時(shí)還能允許一定程度的突發(fā)流量。限流和允許瞬時(shí)流量其實(shí)并不矛盾，在大多數(shù)場(chǎng)景中，小批量的突發(fā)流量系統(tǒng)是完全可以接受的

因?yàn)榱钆仆八惴ㄖ校l(fā)放令牌是持續(xù)不間斷的，當(dāng)流量一直比較緩和時(shí)，桶能夠一直持有冗余的令牌，以應(yīng)對(duì)突發(fā)流量。如果這時(shí)突發(fā)大流量，形成流量尖峰，這些請(qǐng)求進(jìn)來可以直接拿到令牌去執(zhí)行。只有超越系統(tǒng)閾值的流量，由于未獲得桶中的令牌，請(qǐng)求只能等待或者被拒絕，從而維護(hù)系統(tǒng)的穩(wěn)定。

當(dāng)然相較于漏桶算法，令牌桶算法，實(shí)現(xiàn)更為復(fù)雜，需要維護(hù)令牌的生成和消耗，還需要精確的時(shí)間控制(不然會(huì)影響限流的效果)，需要消耗更多的內(nèi)存來儲(chǔ)存令牌

這里也提供一下代碼實(shí)現(xiàn)，單機(jī)下推薦使用(或者仿寫)Google Guava自帶的限流工具類RateLimiter

先引入依賴：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.0-jre</version>
</dependency>

設(shè)置發(fā)放令牌的速率，然后直接調(diào)用tryAcquire，大家感興趣地可以看看其源碼實(shí)現(xiàn)

public class MyTokenBucketRateLimiterDemo {
    public static void main(String[] args) throws InterruptedException {
        // 每1s發(fā)放5個(gè)令牌到桶里
        RateLimiter rateLimiter=RateLimiter.create(5);
        for (int i=0; i < 10; i++) {
            Thread.sleep(100L);
            if(rateLimiter.tryAcquire()) {
                System.out.println("get one token");
            }else {
                System.out.println("no token");
            }
        }
    }
}

補(bǔ)充：分布式限流

本文上述提供的例子，僅適用于單機(jī)，如果是多機(jī)部署(分布式)場(chǎng)景下，算法還是可以采用上述算法，需要通過中間件將限流算法的參數(shù)信息(比如令牌桶、計(jì)數(shù)器等)改成存儲(chǔ)全局化，比如采用redis+lua的方式實(shí)現(xiàn)，或者使用開源工具比如redisson(內(nèi)部封裝了基于Redis的限流)、Sentinel(帶有監(jiān)控監(jiān)控平臺(tái))等

或者我們也可以利用nginx來從上層流量入口進(jìn)行限流，它提供2個(gè)限流模塊ngx_http_limit_req_module，ngx_http_limit_conn_module

上述幾種限流算法都是業(yè)內(nèi)常見的，各有優(yōu)劣，我們需要理解每種方案的工作原理和特性，這樣可以能更好地根據(jù)項(xiàng)目具體的情況和多種因素，選擇合適的方案

全文完，感謝您的閱讀，點(diǎn)贊收藏在看就是對(duì)筆者最好的催更！

我們下期再見~

作者：小牛呼嚕嚕，關(guān)注公眾號(hào)「小牛呼嚕嚕」，更多高質(zhì)量好文等你！

電腦出現(xiàn)故障，即便是老鳥也要研究半天才能找到原因(有時(shí)候根本就找不到)，比如突然網(wǎng)絡(luò)中斷，就得從軟到硬排查個(gè)遍，令人煩躁。

為了幫助用戶查找解決電腦故障，微軟也是一直不遺余力。Windows 10 v1809的時(shí)候，就引入了一個(gè)名為“Packet Monitor”(數(shù)據(jù)包監(jiān)視器)的新功能，簡(jiǎn)稱PacketMon，對(duì)應(yīng)進(jìn)程為pktmon.exe。

這是一個(gè)跨組件的網(wǎng)絡(luò)診斷工具，支持?jǐn)?shù)據(jù)包捕捉、丟包檢測(cè)、數(shù)據(jù)包過濾與計(jì)數(shù)等，會(huì)捕捉通過網(wǎng)絡(luò)的每一個(gè)數(shù)據(jù)包，深入網(wǎng)絡(luò)堆棧內(nèi)部，從而可以快速準(zhǔn)確地檢測(cè)網(wǎng)絡(luò)故障根源，尤其適合大型網(wǎng)絡(luò)環(huán)境。

這個(gè)功能自誕生后一直在升級(jí)，而在最新的Windows 10 v2004版本中，它迎來了一次大規(guī)模更新，技能更加豐富：

－可在不同的網(wǎng)絡(luò)位置捕捉數(shù)據(jù)包

－支持丟包檢測(cè)，包括丟包原因報(bào)告

－運(yùn)行時(shí)數(shù)據(jù)包篩選，包括封裝支持

－彈性數(shù)據(jù)包計(jì)數(shù)

－實(shí)時(shí)屏幕數(shù)據(jù)包監(jiān)控

－大容量?jī)?nèi)存日志

－兼容網(wǎng)絡(luò)監(jiān)視器(NetMon)、Wireshark(pcapng)