前言

在一個高并發系統中對流量的把控是非常重要的，當巨大的流量直接請求到我們的服務器上沒多久就可能造成接口不可用，不處理的話甚至會造成整個應用不可用。

那么何為限流呢？顧名思義，限流就是限制流量，就像你寬帶包了1個G的流量，用完了就沒了。通過限流，我們可以很好地控制系統的qps，從而達到保護系統的目的。本篇文章將會介紹一下常用的限流算法以及他們各自的特點。

算法介紹

計數器法

計數器法是限流算法里最簡單也是最容易實現的一種算法。比如我們規定，對于A接口來說，我們1分鐘的訪問次數不能超過100個。那么我們可以這么做：在一開始的時候，我們可以設置一個計數器counter，每當一個請求過來的時候，counter就加1，如果counter的值大于100并且該請求與第一個請求的間隔時間還在1分鐘之內，那么說明請求數過多；如果該請求與第一個請求的間隔時間大于1分鐘，且counter的值還在限流范圍內，那么就重置counter，具體算法的示意圖如下：

具體的偽代碼如下：

public class CounterDemo {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 時間窗口內最大請求數
    public final long interval = 60000; // 時間窗口ms
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在時間窗口內
            reqCount++;
            // 判斷當前時間窗口內是否超過最大請求控制數
            return reqCount <= limit;
        }
        else {
            timeStamp = now;
            // 超時后重置
            reqCount = 1;
            return true;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

這個算法雖然簡單，但是有一個十分致命的問題，那就是臨界問題，我們看下圖：

從上圖中我們可以看到，假設有一個惡意用戶，他在0:59時，瞬間發送了100個請求，并且1:00又瞬間發送了100個請求，那么其實這個用戶在1秒里面，瞬間發送了200個請求。我們剛才規定的是1分鐘最多100個請求，也就是每秒鐘最多1.7個請求，用戶通過在時間窗口的重置節點處突發請求，可以瞬間超過我們的速率限制。用戶有可能通過算法的這個漏洞，瞬間壓垮我們的應用。

聰明的朋友可能已經看出來了，剛才的問題其實是因為我們統計的精度太低。那么如何很好地處理這個問題呢？或者說，如何將臨界問題的影響降低呢？我們可以看下面的滑動窗口算法。

滑動窗口

滑動窗口，又稱rolling window。為了解決這個問題，我們引入了滑動窗口算法。如果學過TCP網絡協議的話，那么一定對滑動窗口這個名詞不會陌生。下面這張圖，很好地解釋了滑動窗口算法：

在上圖中，整個紅色的矩形框表示一個時間窗口，在我們的例子中，一個時間窗口就是一分鐘。然后我們將時間窗口進行劃分，比如圖中，我們就將滑動窗口劃成了6格，所以每格代表的是10秒鐘。每過10秒鐘，我們的時間窗口就會往右滑動一格。每一個格子都有自己獨立的計數器counter，比如當一個請求在0:35秒的時候到達，那么0:30~0:39對應的counter就會加1。

那么滑動窗口怎么解決剛才的臨界問題的呢？我們可以看上圖，0:59到達的100個請求會落在灰色的格子中，而1:00到達的請求會落在橘黃色的格子中。當時間到達1:00時，我們的窗口會往右移動一格，那么此時時間窗口內的總請求數量一共是200個，超過了限定的100個，所以此時能夠檢測出來觸發了限流。

我再來回顧一下剛才的計數器算法，我們可以發現，計數器算法其實就是滑動窗口算法。只是它沒有對時間窗口做進一步地劃分，為60s。

由此可見，當滑動窗口的格子劃分的越多，那么滑動窗口的滾動就越平滑，限流的統計就會越精確。

public class CounterDemo {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 時間窗口內最大請求數
    public final long interval = 6000; // 時間窗口6ms,6格
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在時間窗口內
            reqCount++;
            // 判斷當前時間窗口內是否超過最大請求控制數
            return reqCount <= limit;
        }
        else {
            timeStamp = now;
            // 超時后重置
            reqCount = 1;
            return true;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

漏桶算法

漏桶算法，又稱leaky bucket。為了理解漏桶算法，我們看一下對于該算法的示意圖：

從圖中我們可以看到，整個算法其實十分簡單。首先，我們有一個固定容量的桶，有水流進來，也有水流出去。對于流進來的水來說，我們無法預計一共有多少水會流進來，也無法預計水流的速度。但是對于流出去的水來說，這個桶可以固定水流出的速率。而且，當桶滿了之后，多余的水將會溢出。

我們將算法中的水換成實際應用中的請求，我們可以看到漏桶算法天生就限制了請求的速度。當使用了漏桶算法，我們可以保證接口會以一個常速速率來處理請求。所以漏桶算法天生不會出現臨界問題。具體的偽代碼實現如下：

public class LeakyDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 水漏出的速度
    public Long water; // 當前水量(當前累積請求數)
    public boolean grant() {
        long now = getNowTime();
        water = Math.max(0L, water - (now - timeStamp) * rate); // 先執行漏水，計算剩余水量
        timeStamp = now;
        if ((water + 1) < capacity) {
            // 嘗試加水,并且水還未滿
            water += 1;
            return true;
        }
        else {
            // 水滿，拒絕加水
            return false;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

令牌桶算法

令牌桶算法，又稱token bucket。為了理解該算法，我們再來看一下算法的示意圖：

從圖中我們可以看到，令牌桶算法比漏桶算法稍顯復雜。首先，我們有一個固定容量的桶，桶里存放著令牌（token）。桶一開始是空的，token以一個固定的速率r往桶里填充，直到達到桶的容量，多余的令牌將會被丟棄。每當一個請求過來時，就會嘗試從桶里移除一個令牌，如果沒有令牌的話，請求無法通過。

具體的偽代碼實現如下：

public class TokenBucketDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 令牌放入速度
    public Long tokens; // 當前令牌數量
    public boolean grant() {
        long now = getNowTime();
        // 先添加令牌
        tokens = Math.min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            // 若不到1個令牌,則拒絕
            return false;
        }
        else {
            // 還有令牌，領取令牌
            tokens -= 1;
            return true;
        }
    }
    private static Long getNowTime(){
        return System.currentTimeMillis();
    }
}

RateLimiter實現

對于令牌桶的代碼實現，可以直接使用Guava包中的RateLimiter。

@Slf4j
public class RateLimiterExample1 {

    // 代表每秒最多2個
    // guava限流采用的是令牌桶的方式
    private static RateLimiter rateLimiter = RateLimiter.create(2);

    public static void main(String[] args) {
        for (int index = 0; index < 100; index++) {
            // 單位時間內獲取令牌
            if (rateLimiter.tryAcquire(190, TimeUnit.MILLISECONDS)) {
                handle(index);
            }
        }
    }
    private static void handle(int i) {
        log.info("{}", i);
    }

相關變種

若仔細研究算法，我們會發現我們默認從桶里移除令牌是不需要耗費時間的。如果給移除令牌設置一個延時時間，那么實際上又采用了漏桶算法的思路。google的guava庫下的SmoothWarmingUp類就采用了這個思路。

臨界問題

我們再來考慮一下臨界問題的場景。在0:59秒的時候，由于桶內積滿了100個token，所以這100個請求可以瞬間通過。但是由于token是以較低的速率填充的，所以在1:00的時候，桶內的token數量不可能達到100個，那么此時不可能再有100個請求通過。所以令牌桶算法可以很好地解決臨界問題。下圖比較了計數器（左）和令牌桶算法（右）在臨界點的速率變化。我們可以看到雖然令牌桶算法允許突發速率，但是下一個突發速率必須要等桶內有足夠的token后才能發生：