一文詳解四種經典限流算法，面試必備。

前言

最近一位朋友去拼夕夕面試,被問了這麼一道題:限流算法有哪些?用代碼實作令牌桶算法。跟好友讨論了一波,發現大家都忘記得差不多了.是以再整理一波，常見的四種限流算法,以及簡單代碼實作,相信大家看完,會茅塞頓開的。

1. 固定視窗限流算法

1.1 什麼是固定視窗限流算法

固定視窗限流算法（Fixed Window Rate Limiting Algorithm）是一種最簡單的限流算法，其原理是在固定時間視窗(機關時間)内限制請求的數量。該算法将時間分成固定的視窗，并在每個視窗内限制請求的數量。具體來說，算法将請求按照時間順序放入時間視窗中，并計算該時間視窗内的請求數量，如果請求數量超出了限制，則拒絕該請求。

假設機關時間(固定時間視窗)是1秒，限流閥值為3。在機關時間1秒内，每來一個請求,計數器就加1，如果計數器累加的次數超過限流閥值3，後續的請求全部拒絕。等到1s結束後，計數器清0，重新開始計數。如下圖：

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閥值的定義啦。

2. 滑動視窗限流算法

2.1 什麼是滑動視窗限流算法

滑動視窗限流算法是一種常用的限流算法，用于控制系統對外提供服務的速率，防止系統被過多的請求壓垮。它将機關時間周期分為n個小周期，分别記錄每個小周期内接口的通路次數，并且根據時間滑動删除過期的小周期。它可以解決固定視窗臨界值的問題。

用一張圖解釋滑動視窗算法，如下：

假設機關時間還是1s，滑動視窗算法把它劃分為5個小周期，也就是滑動視窗（機關時間）被劃分為5個小格子。每格表示0.2s。每過0.2s，時間視窗就會往右滑動一格。然後呢，每個小周期，都有自己獨立的計數器，如果請求是0.83s到達的，0.8~1.0s對應的計數器就會加1。

我們來看下，滑動視窗,去解決固定視窗限流算法的臨界問題，思想是怎樣

假設我們1s内的限流閥值還是5個請求，0.8~1.0s内（比如0.9s的時候）來了5個請求，落在黃色格子裡。時間過了1.0s這個點之後，又來5個請求，落在紫色格子裡。如果是固定視窗算法，是不會被限流的，但是滑動視窗的話，每過一個小周期，它會右移一個小格。過了1.0s這個點後，會右移一小格，目前的機關時間段是0.2~1.2s，這個區域的請求已經超過限定的5了，已觸發限流啦，實際上，紫色格子的請求都被拒絕啦。

當滑動視窗的格子周期劃分的越多，那麼滑動視窗的滾動就越平滑，限流的統計就會越精确。

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 synchronized 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 滑動視窗限流算法的優缺點

優點：

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

缺點：

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

3. 漏桶限流算法

3.1 什麼是漏桶限流算法

漏桶限流算法（Leaky Bucket Algorithm）是一種流量控制算法，用于控制流入網絡的資料速率，以防止網絡擁塞。它的思想是将資料包看作是水滴，漏桶看作是一個固定容量的水桶，資料包像水滴一樣從桶的頂部流入桶中，并通過桶底的一個小孔以一定的速度流出，進而限制了資料包的流量。

漏桶限流算法的基本工作原理是：對于每個到來的資料包，都将其加入到漏桶中，并檢查漏桶中目前的水量是否超過了漏桶的容量。如果超過了容量，就将多餘的資料包丢棄。如果漏桶中還有水，就以一定的速率從桶底輸出資料包，保證輸出的速率不超過預設的速率，進而達到限流的目的。

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

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 漏桶限流算法的優缺點

優點

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

缺點

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

4. 令牌桶算法

4.1 什麼是令牌桶算法

令牌桶算法是一種常用的限流算法，可以用于限制機關時間内請求的數量。該算法維護一個固定容量的令牌桶，每秒鐘會向令牌桶中放入一定數量的令牌。當有請求到來時，如果令牌桶中有足夠的令牌，則請求被允許通過并從令牌桶中消耗一個令牌，否則請求被拒絕。

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 令牌桶算法的優缺點

優點：

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

Guava的RateLimiter限流元件，就是基于令牌桶算法實作的。

缺點：

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

總體來說，令牌桶算法具有較高的穩定性和精度，但實作相對複雜，适用于對穩定性和精度要求較高的場景。