圖解常見的限流算法 -計數器算法、滑動窗口計數算法、漏桶算法、令牌桶算法-

什麼場景需要限流
計數器算法
滑動窗口計數算法
漏桶算法
令牌桶算法
補充：分佈式限流

哈嘍，大家好呀，我是呼嚕嚕，好久沒有更新文章了，最近實在是忙的不行，今天我們來聊聊在企業級項目中，常見的幾種限流手段的原理及其實現

什麼場景需要限流

隨着互聯網的業務發展，比如秒殺、雙十一、618等這些我們耳熟能詳，也有被人惡意攻擊的場景下，系統往往經受被高併發流量沖垮的風險，這個時候可以採用限流的方式，來保護自身的系統以及下游系統，當然還有其他各種方式手段，比如熔斷、降級、隔離等，本文將重點來講講限流

限流就是就是對請求或併發數進行限制，通過在一定時間內對請求量進行限制，來達到保護系統正常運行的目的。常見的限流算法，有計數器算法、滑動窗口計數算法、漏桶算法、令牌桶算法

計數器算法

計數器算法，通過計數器在週期內累加訪問次數，並規定一個週期 (時間窗口) 內的系統處理的請求數量 (閾值)，當在一個週期內，計數的值達到限流閾值時觸發拒絕策略；到下一週期計數器就重置爲 0，重新開始計數，它是一種簡單方便的限流算法

比如我們設置系統的閾值1s中最多請求100次，在計數器算法中，我們需要把時間劃分固定大小窗口 (所以計數器算法又叫固定窗口算法Fixed Window)，這裏我們將1s劃分爲一個時間窗口；然後用計數器來記錄在每個時間窗口的處理的請求數量，如果請求數量超過100次，後續的請求會被直接拒絕，直到1s結束後，重新開始計數

計數器算法優點實現簡單, 佔用內存小，性能較高，但是有一個缺點，就是臨界問題，因爲在一個時間窗口中，請求或者流量並不是均勻分佈的，比如，在1.9s和2.1s的時間點，分別被人惡意併發請求了100次，也就是說從1.9s開始後的1s時間窗口期間，被瞬間請求了200次已經超過系統的閾值了，即使窗口2和窗口3還是正常的，這樣可能會導致系統直接掛掉

這裏提供一個簡單的 demo(Java 版，其他語言大家自行改寫):

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

    //上一個窗口的開始時間
    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 + " 請求被限流");
            } else {
                System.out.println(now + " 請求通過");
            }
        }
    }
}

滑動窗口計數算法

滑動窗口算法(Sliding Window)出現於網絡協議中傳輸層，是一種流量控制技術。我們這裏對計數器 (固定窗口) 算法的臨界問題，滑動窗口算法進行了改進，不再固定窗口大小，而是將把固定窗口近一步劃分成多個小週期，每個週期都記錄自己的請求訪問次數，隨着時間流逝，滑動時間窗口 (每次向後移動一週期)，同時刪除過期的小週期。每次判斷限流時，需要將一個窗口的所有小週期合起來，再與閾值進行比較

舉個例子，上圖我們將1s時間窗口，劃分成5個200ms的小週期，記錄每個週期的請求訪問次數，這裏沿用上一小節的情形在1.9s和2.1s的時間點，分別被人惡意併發請求了100次，當滑動到第5個小週期時，訪問量爲100次，未達到閾值；而當窗口滑動到第6個小週期時，訪問數量變爲：200，這個時候會超過閾值，觸發拒絕訪問的限制

這樣就能限制住瞬時流量爆發。如果滑動窗口的單位區間劃分越細的話，滑動窗口的滾動就越平滑，限流統計也會越精準。但隨之而來的是實現滑動窗口算法**，需要更多的存儲空間**。另外計數器算法實現起來比較簡單，滑動窗口則更復雜

這裏提供一個筆者感覺非常簡單明瞭的 demo，參考於簡單的 java 實現滑動時間窗口限流算法，在此感謝

public class MySlidingWindowRateLimiterDemo {

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


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

        // 隊列已滿（達到限制次數），則獲取隊列中最早添加的時間戳
        Long farTime = list.get(count - 1);
        // 用當前時間戳 減去 最早添加的時間戳
        if (nowTime - farTime <= timeWindow) {
            // 若結果小於等於timeWindow，則說明在timeWindow內，通過的次數大於count
            // 不允許通過
            return false;
        } else {
            // 若結果大於timeWindow，則說明在timeWindow內，通過的次數小於等於count
            // 允許通過，並刪除最早添加的時間戳，將當前時間添加到隊列開始位置
            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秒內，只允許2次通過;自定義限流規則“ip”
                System.out.println(now + " 請求被限流");
            } else {
                System.out.println(now + " 請求通過");
            }
        }
    }
}

美中不足的是，在滑動窗口算法，窗口中流量到達閾值時，流量會瞬間切斷，而現實中我們還是更希望，讓流量更平滑地放行到系統中，而不是簡單粗暴地將其掐斷

漏桶算法

我們再來看看漏桶算法Leaky Bucket，是一個非常貼切的比喻，意思是，水 (就是請求/流量) 從進水口 (生產端) 進入桶 (隊列) 中，這個桶是漏的 (比方說桶底有一個孔)，以一定的速度漏水 (消費端不斷的在消費隊列中的請求)，當水進入桶的速度過大 (大於漏水的速度)，會導致桶裏的水堆積，當超過桶容量時會溢出來 (請求被拒絕)。從而實現網絡流量整形和限流的功能

這裏漏水的速度其實就是限流的閾值，所謂的閾值，表示在一個單位時間內允許的請求量，比如如 QPS 爲 100，說明 1 秒內系統最多可以消費 100 個請求。如果生產端的速率超過閾值的話，請求會慢慢堆積，又因爲漏桶的容量是固定的，最後會觸發拒絕策略 (溢出)

漏桶算法它的優點是，實現起來簡單，很容易理解。它可以嚴格限制請求的處理速度，一旦超過該速度就拒絕服務，從而避免網絡擁塞和系統過載

但它也有缺點：

即使沒有大流量，也需要等待漏桶處理完成 (流量限制過於嚴格)，這樣就會導致請求處理延遲，不適用於實時性要求很高的場景
由於它請求的處理速度是固定的，哪怕網絡沒有發生擁塞時，也不能使某一個單獨的數據流達到生產端的速率，也無法很好地應對突發特性的流量，不能充分利用系統資源

這裏提供一個簡單的 demo(不完整，生產慎用，僅用來演示):

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

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

    public synchronized boolean tryAcquire() {
        //1. 計算剩餘水量
        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 + " 請求被限流");
            } else {
                System.out.println(now + " 請求通過");
            }
        }
    }
}

令牌桶算法

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

表面上看，令牌桶算法和漏桶算法是相反的，一個 "進水"，一個是 "漏水"。但與漏桶算法實際不同的是，令牌桶不僅能夠在限制客戶端請求流量速率的同時還能允許一定程度的突發流量。限流和允許瞬時流量其實並不矛盾，在大多數場景中，小批量的突發流量系統是完全可以接受的

因爲令牌桶算法中，發放令牌是持續不間斷的，當流量一直比較緩和時，桶能夠一直持有冗餘的令牌，以應對突發流量。如果這時突發大流量，形成流量尖峯，這些請求進來可以直接拿到令牌去執行。只有超越系統閾值的流量，由於未獲得桶中的令牌，請求只能等待或者被拒絕，從而維護系統的穩定。

當然相較於漏桶算法，令牌桶算法，實現更爲複雜，需要維護令牌的生成和消耗，還需要精確的時間控制 (不然會影響限流的效果)，需要消耗更多的內存來儲存令牌

這裏也提供一下代碼實現，單機下推薦使用 (或者仿寫)Google Guava自帶的限流工具類RateLimiter

先引入依賴：

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

設置發放令牌的速率，然後直接調用tryAcquire，大家感興趣的可以看看其源碼實現

public class MyTokenBucketRateLimiterDemo {
    public static void main(String[] args) throws InterruptedException {
        // 每1s發放5個令牌到桶裏
        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");
            }
        }
    }
}

補充：分佈式限流

本文上述提供的例子，僅適用於單機，如果是多機部署 (分佈式) 場景下，算法還是可以採用上述算法，需要通過中間件將限流算法的參數信息 (比如令牌桶、計數器等) 改成存儲全局化，比如採用redis+lua的方式實現，或者使用開源工具比如redisson(內部封裝了基於Redis的限流)、Sentinel(帶有監控監控平臺) 等

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

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

參考資料：

https://en.wikipedia.org/wiki/Rate_limiting

https://baike.baidu.com/item/%E6%BC%8F%E6%A1%B6%E7%AE%97%E6%B3%95

https://www.cnblogs.com/dijia478/p/13807826.html

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/UW8PmyqN_UiLeFd-KhIxgg