前言

大家好,我是田螺。pWA28資訊網——每日最新資訊28at.com

最近一位朋友去拼夕夕面試,被問了這么一道題:限流算法有哪些?用代碼實現令牌桶算法。跟星球好友討論了一波,發現大家都忘記得差不多了.所以田螺哥再整理一波，常見的四種限流算法,以及簡單代碼實現,相信大家看完,會茅塞頓開的。pWA28資訊網——每日最新資訊28at.com

圖片pWA28資訊網——每日最新資訊28at.com

1. 固定窗口限流算法

1.1 什么是固定窗口限流算法

固定窗口限流算法（Fixed Window Rate Limiting Algorithm）是一種最簡單的限流算法，其原理是在固定時間窗口(單位時間)內限制請求的數量。該算法將時間分成固定的窗口，并在每個窗口內限制請求的數量。具體來說，算法將請求按照時間順序放入時間窗口中，并計算該時間窗口內的請求數量，如果請求數量超出了限制，則拒絕該請求。pWA28資訊網——每日最新資訊28at.com

假設單位時間(固定時間窗口)是1秒，限流閥值為3。在單位時間1秒內，每來一個請求,計數器就加1，如果計數器累加的次數超過限流閥值3，后續的請求全部拒絕。等到1s結束后，計數器清0，重新開始計數。如下圖：pWA28資訊網——每日最新資訊28at.com

圖片pWA28資訊網——每日最新資訊28at.com

1.2 固定窗口限流的偽代碼

public static Integer counter = 0;  //統計請求數   public static long lastAcquireTime =  0L;   public static final Long windowUnit = 1000L ; //假設固定時間窗口是1000ms   public static final Integer threshold = 10; // 窗口閥值是10       /**     * 固定窗口時間算法     * 關注公眾號：撿田螺的小男孩     * @return     */    public synchronized boolean fixedWindowsTryAcquire() {        long currentTime = System.currentTimeMillis();  //獲取系統當前時間        if (currentTime - lastAcquireTime > windowUnit) {  //檢查是否在時間窗口內            counter = 0;  // 計數器清0            lastAcquireTime = currentTime;  //開啟新的時間窗口        }        if (counter < threshold) {  // 小于閥值            counter++;  //計數統計器加1            return true;        }        return false;    }

1.2 固定窗口算法的優缺點

• 優點：固定窗口算法非常簡單，易于實現和理解。
• 缺點：存在明顯的臨界問題，比如: 假設限流閥值為5個請求，單位時間窗口是1s,如果我們在單位時間內的前0.8-1s和1-1.2s，分別并發5個請求。雖然都沒有超過閥值，但是如果算0.8-1.2s,則并發數高達10，已經超過單位時間1s不超過5閥值的定義啦。

圖片pWA28資訊網——每日最新資訊28at.com

2. 滑動窗口限流算法

2.1 什么是滑動窗口限流算法

滑動窗口限流算法是一種常用的限流算法，用于控制系統對外提供服務的速率，防止系統被過多的請求壓垮。它將單位時間周期分為n個小周期，分別記錄每個小周期內接口的訪問次數，并且根據時間滑動刪除過期的小周期。它可以解決固定窗口臨界值的問題。pWA28資訊網——每日最新資訊28at.com

用一張圖解釋滑動窗口算法，如下：pWA28資訊網——每日最新資訊28at.com

圖片pWA28資訊網——每日最新資訊28at.com

假設單位時間還是1s，滑動窗口算法把它劃分為5個小周期，也就是滑動窗口（單位時間）被劃分為5個小格子。每格表示0.2s。每過0.2s，時間窗口就會往右滑動一格。然后呢，每個小周期，都有自己獨立的計數器，如果請求是0.83s到達的，0.8~1.0s對應的計數器就會加1。pWA28資訊網——每日最新資訊28at.com

我們來看下，滑動窗口,去解決固定窗口限流算法的臨界問題，思想是怎樣pWA28資訊網——每日最新資訊28at.com

假設我們1s內的限流閥值還是5個請求，0.8~1.0s內（比如0.9s的時候）來了5個請求，落在黃色格子里。時間過了1.0s這個點之后，又來5個請求，落在紫色格子里。如果是固定窗口算法，是不會被限流的，但是滑動窗口的話，每過一個小周期，它會右移一個小格。過了1.0s這個點后，會右移一小格，當前的單位時間段是0.2~1.2s，這個區域的請求已經超過限定的5了，已觸發限流啦，實際上，紫色格子的請求都被拒絕啦。pWA28資訊網——每日最新資訊28at.com

當滑動窗口的格子周期劃分的越多，那么滑動窗口的滾動就越平滑，限流的統計就會越精確。pWA28資訊網——每日最新資訊28at.com

2.2 滑動窗口限流算法的偽代碼實現

/**     * 單位時間劃分的小周期（單位時間是1分鐘，10s一個小格子窗口，一共6個格子）     */    private int SUB_CYCLE = 10;    /**     * 每分鐘限流請求數     */    private int thresholdPerMin = 100;    /**     * 計數器, k-為當前窗口的開始時間值秒，value為當前窗口的計數     */    private final TreeMap<Long, Integer> counters = new TreeMap<>();   /**     * 滑動窗口時間算法實現     */     public synchronized boolean slidingWindowsTryAcquire() {        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //獲取當前時間在哪個小周期窗口        int currentWindowNum = countCurrentWindow(currentWindowTime); //當前窗口總請求數        //超過閥值限流        if (currentWindowNum >= thresholdPerMin) {            return false;        }        //計數器+1        counters.get(currentWindowTime)++;        return true;    }   /**    * 統計當前窗口的請求數    */    private int countCurrentWindow(long currentWindowTime) {        //計算窗口開始位置        long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);        int count = 0;        //遍歷存儲的計數器        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 {                //累加當前窗口的所有計數器之和                count =count + entry.getValue();            }        }        return count;    }

2.3 滑動窗口限流算法的優缺點

優點：pWA28資訊網——每日最新資訊28at.com

• 簡單易懂
• 精度高（通過調整時間窗口的大小來實現不同的限流效果）
• 可擴展性強（可以非常容易地與其他限流算法結合使用）

缺點：pWA28資訊網——每日最新資訊28at.com

• 突發流量無法處理（無法應對短時間內的大量請求，但是一旦到達限流后，請求都會直接暴力被拒絕。醬紫我們會損失一部分請求，這其實對于產品來說，并不太友好），需要合理調整時間窗口大小。

3. 漏桶限流算法

3.1 什么是漏桶限流算法

漏桶限流算法（Leaky Bucket Algorithm）是一種流量控制算法，用于控制流入網絡的數據速率，以防止網絡擁塞。它的思想是將數據包看作是水滴，漏桶看作是一個固定容量的水桶，數據包像水滴一樣從桶的頂部流入桶中，并通過桶底的一個小孔以一定的速度流出，從而限制了數據包的流量。pWA28資訊網——每日最新資訊28at.com

漏桶限流算法的基本工作原理是：對于每個到來的數據包，都將其加入到漏桶中，并檢查漏桶中當前的水量是否超過了漏桶的容量。如果超過了容量，就將多余的數據包丟棄。如果漏桶中還有水，就以一定的速率從桶底輸出數據包，保證輸出的速率不超過預設的速率，從而達到限流的目的。pWA28資訊網——每日最新資訊28at.com

圖片pWA28資訊網——每日最新資訊28at.com

• 流入的水滴，可以看作是訪問系統的請求，這個流入速率是不確定的。
• 桶的容量一般表示系統所能處理的請求數。
• 如果桶的容量滿了，就達到限流的閥值，就會丟棄水滴（拒絕請求）
• 流出的水滴，是恒定過濾的，對應服務按照固定的速率處理請求。

3.2 漏桶限流算法的偽代碼實現

/** * LeakyBucket 類表示一個漏桶, * 包含了桶的容量和漏桶出水速率等參數， * 以及當前桶中的水量和上次漏水時間戳等狀態。 */public class LeakyBucket {    private final long capacity;    // 桶的容量    private final long rate;        // 漏桶出水速率    private long water;             // 當前桶中的水量    private long lastLeakTimestamp; // 上次漏水時間戳    public LeakyBucket(long capacity, long rate) {        this.capacity = capacity;        this.rate = rate;        this.water = 0;        this.lastLeakTimestamp = System.currentTimeMillis();    }    /**     * tryConsume() 方法用于嘗試向桶中放入一定量的水，如果桶中還有足夠的空間，則返回 true，否則返回 false。     * @param waterRequested     * @return     */    public synchronized boolean tryConsume(long waterRequested) {        leak();        if (water + waterRequested <= capacity) {            water += waterRequested;            return true;        } else {            return false;        }    }    /**     * 。leak() 方法用于漏水，根據當前時間和上次漏水時間戳計算出應該漏出的水量，然后更新桶中的水量和漏水時間戳等狀態。     */    private void leak() {        long now = System.currentTimeMillis();        long elapsedTime = now - lastLeakTimestamp;        long leakedWater = elapsedTime * rate / 1000;        if (leakedWater > 0) {            water = Math.max(0, water - leakedWater);            lastLeakTimestamp = now;        }    }}

• 注意:   tryConsume() 和 leak() 方法中，都需要對桶的狀態進行同步，以保證線程安全性。

3.3 漏桶限流算法的優缺點

優點pWA28資訊網——每日最新資訊28at.com

• 可以平滑限制請求的處理速度，避免瞬間請求過多導致系統崩潰或者雪崩。
• 可以控制請求的處理速度，使得系統可以適應不同的流量需求，避免過載或者過度閑置。
• 可以通過調整桶的大小和漏出速率來滿足不同的限流需求，可以靈活地適應不同的場景。

缺點pWA28資訊網——每日最新資訊28at.com

• 需要對請求進行緩存，會增加服務器的內存消耗。
• 對于流量波動比較大的場景，需要較為靈活的參數配置才能達到較好的效果。
• 但是面對突發流量的時候，漏桶算法還是循規蹈矩地處理請求，這不是我們想看到的啦。流量變突發時，我們肯定希望系統盡量快點處理請求，提升用戶體驗嘛。

4. 令牌桶算法

4.1 什么是令牌桶算法

令牌桶算法是一種常用的限流算法，可以用于限制單位時間內請求的數量。該算法維護一個固定容量的令牌桶，每秒鐘會向令牌桶中放入一定數量的令牌。當有請求到來時，如果令牌桶中有足夠的令牌，則請求被允許通過并從令牌桶中消耗一個令牌，否則請求被拒絕。pWA28資訊網——每日最新資訊28at.com

4.2 令牌桶算法的偽代碼實現

/** * TokenBucket 類表示一個令牌桶 */public class TokenBucket {    private final int capacity;     // 令牌桶容量    private final int rate;         // 令牌生成速率，單位：令牌/秒    private int tokens;             // 當前令牌數量    private long lastRefillTimestamp;  // 上次令牌生成時間戳    /**     * 構造函數中傳入令牌桶的容量和令牌生成速率。     * @param capacity     * @param rate     */    public TokenBucket(int capacity, int rate) {        this.capacity = capacity;        this.rate = rate;        this.tokens = capacity;        this.lastRefillTimestamp = System.currentTimeMillis();    }    /**     * allowRequest() 方法表示一個請求是否允許通過，該方法使用 synchronized 關鍵字進行同步，以保證線程安全。     * @return     */    public synchronized boolean allowRequest() {        refill();        if (tokens > 0) {            tokens--;            return true;        } else {            return false;        }    }    /**     * refill() 方法用于生成令牌，其中計算令牌數量的邏輯是按照令牌生成速率每秒鐘生成一定數量的令牌，     * tokens 變量表示當前令牌數量，     * lastRefillTimestamp 變量表示上次令牌生成的時間戳。     */    private void refill() {        long now = System.currentTimeMillis();        if (now > lastRefillTimestamp) {            int generatedTokens = (int) ((now - lastRefillTimestamp) / 1000 * rate);            tokens = Math.min(tokens + generatedTokens, capacity);            lastRefillTimestamp = now;        }    }}

4.3 令牌桶算法的優缺點

優點：pWA28資訊網——每日最新資訊28at.com

• 穩定性高：令牌桶算法可以控制請求的處理速度，可以使系統的負載變得穩定。
• 精度高：令牌桶算法可以根據實際情況動態調整生成令牌的速率，可以實現較高精度的限流。
• 彈性好：令牌桶算法可以處理突發流量，可以在短時間內提供更多的處理能力，以處理突發流量。

Guava的RateLimiter限流組件，就是基于令牌桶算法實現的。pWA28資訊網——每日最新資訊28at.com

缺點：pWA28資訊網——每日最新資訊28at.com

• 實現復雜：相對于固定窗口算法等其他限流算法，令牌桶算法的實現較為復雜。對短時請求難以處理：在短時間內有大量請求到來時，可能會導致令牌桶中的令牌被快速消耗完，從而限流。這種情況下，可以考慮使用漏桶算法。
• 時間精度要求高：令牌桶算法需要在固定的時間間隔內生成令牌，因此要求時間精度較高，如果系統時間不準確，可能會導致限流效果不理想。

總體來說，令牌桶算法具有較高的穩定性和精度，但實現相對復雜，適用于對穩定性和精度要求較高的場景。pWA28資訊網——每日最新資訊28at.com

本文鏈接：http://www.tebozhan.com/showinfo-26-75311-0.html面試必備：四種經典限流算法講解

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： Vue2問題：分享一個通用多文件類型預覽庫

下一篇： 淺談鏈路聚合，你學會了嗎？