主題

本章我們來分析Guava RateLimiter 是如何解決高并發(fā)場景下的限流問題的

Guava 是 Google 開源的 Java 類庫该镣， 提供了一個工具類RateLimiter 蚀狰。使用時候必須加入以下依賴：

        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>${version}</version>
        </dependency>

其中 ${version} 參考 
https://search.maven.org/search?q=g:com.google.guava%20AND%20a:guava&core=gav

我們先來看下RateLimiter 的使用辆苔，讓你對限流有個感官的印象。假設(shè)我們有一個線程池惨恭，它每秒只能處理兩個任務(wù)撕贞，如果提交任務(wù)過快，可能導(dǎo)致系統(tǒng)不穩(wěn)定，這個時候就需要用到限流罚渐。

先上代碼：

    public class LimiterMain {

    public static void main(String[] args) throws Exception {

        System.out.println("Limiter");
        //限流器流速：2個請求/秒
        RateLimiter limiter = RateLimiter.create(2);
        //執(zhí)行任務(wù)的線程池
        ExecutorService service = Executors.newSingleThreadExecutor();
        //記錄間隔時間
        final List<Long> list = Lists.newArrayList();

        for (int i = 0; i < 20; i++) {
            limiter.acquire();
            service.execute(() -> {
                long cur = System.currentTimeMillis();
                list.add(cur);
            });
        }
        //等待線程完全執(zhí)行完畢
        Thread.sleep(10000);
        //打印輸出間隔時間
        for (int i = 1; i < list.size(); i++) {
            System.out.println((list.get(i) - list.get(i - 1)));
        }
    }
}

輸出結(jié)果：
407
498
499
500
500
498
500
499
500
498
500
500
500
500
499
499
499
500
499

在上面的示例中却汉，我們創(chuàng)建了一個流速為2 個請求 / 秒的限流器， 這里的流速該怎么理解呢荷并？直觀的看病涨，2 個請求 / 秒指的是每秒最多允許 2 個請求通過限流器， 其實在Guava 中璧坟，流速還有更深一層的意思：是一種勻速的概念既穆，2個請求/秒等價于1個請求/500毫秒。

在向線程池提交任務(wù)之前雀鹃，調(diào)用acquire() 方法起到限流的作用幻工。所以可以看到輸出的結(jié)果 基本在 500毫秒輸出一次結(jié)果。

經(jīng)典限流算法：令牌桶算法

Guava 的限流器使用上還是很簡單的黎茎，那它是如何實現(xiàn)的呢囊颅？Guava 采用的是令牌桶算法，其核心思想是 要想通過限流器傅瞻，必須先拿到令牌踢代。也就是說，只要我們能夠限制發(fā)送令牌的速率嗅骄，那么就能控制流速了胳挎。令牌桶算法的詳細描述如下：

1. 令牌以固定的速率添加到令牌桶，假設(shè)限流的速率是 r/秒溺森，則令牌以每1/r秒會添加一個慕爬；
2. 假設(shè)令牌桶的容量是b，如果令牌桶已滿屏积，則新的令牌會被丟棄医窿；
3. 請求能夠通過限流器的前提是令牌桶中有令牌；

這個算法中限流的速率r還是比較容易理解的炊林，但是令牌桶的容量b該怎么理解呢姥卢？b 其實是 burst 的簡寫，意義是限流器允許的最大突發(fā)流量渣聚。比如b=10独榴， 而且令牌桶中的令牌已滿，此時限流器允許10個請求同時通過限流器饵逐，當然只是突發(fā)流量而已括眠，這 10個請求會帶走10個令牌，所以后續(xù)的流量只能按照速率r通過限流器倍权。

令牌桶這算法，如何用java實現(xiàn)呢？很可能直覺會告訴你 生產(chǎn)者-消費者模式：一個生產(chǎn)者線程定時向阻塞隊列添加令牌薄声，而試圖通過限流器的線程則作為消費者当船，只有從阻塞隊中中獲取到令牌，才能通過限流器默辨。

這個算法看上去非常完美德频，而且實現(xiàn)起來非常簡單。如果并發(fā)量不大珍促，這個實現(xiàn)并么有什么問題屈藐∷椭欤可實際情況是使用限流的場景大部分都是高并發(fā)場景，而且系統(tǒng)壓力已經(jīng)接近極限了钞护，此時這個實現(xiàn)就有問題了。問題出在定時器上爆办，在高并發(fā)場景下难咕，當系統(tǒng)壓力已經(jīng)臨近極限的時候，定時器精度誤差會非常大距辆，同時定時器本身會創(chuàng)建調(diào)度線程余佃，也會對系統(tǒng)的性能產(chǎn)生影響。

那還有什么好的實現(xiàn)方式呢跨算？當然有爆土，Guava 的現(xiàn)實就沒有通過定時器，下面我們看看它如何實現(xiàn)诸蚕。

Guava 如何實現(xiàn)令牌桶算法

Guava 實現(xiàn)令牌桶算法雾消， 用了一個很簡單的方法。其關(guān)鍵是記錄并動態(tài)計算下一次令牌發(fā)放的時間挫望。下面我們用一個簡單的場景來介紹該算法的執(zhí)行過程立润。假設(shè)令牌桶的容量為b=1， 限流速率 r = 1 個請求 / 秒媳板， 如下圖所示桑腮，如果當前令牌桶中沒有令牌， 下一個令牌的發(fā)放時間是在第 3 秒蛉幸， 而在第 2 秒的時候有一個線程 T1 請求令牌破讨，此時該如何處理呢？

img

對于這個請求令牌的線程而言奕纫，很顯然需要等待1秒提陶，因為1秒以后（第 3 秒） ，他就能拿到令牌了匹层。此時需要注意的是隙笆，下一個令牌的發(fā)放時間也要增加1秒，為什么呢？因為第3秒發(fā)放的令牌已經(jīng)被線程T1預(yù)占了撑柔，處理之后如下圖：

img

假設(shè)T1在預(yù)占了第3秒的令牌之后瘸爽，馬上又有一個線程T2請求令牌，如下圖所示：

img

很顯然由于下一個令牌的產(chǎn)生時間是第4秒铅忿，所以線程T2需要等待2秒的時間剪决，才能獲取到令牌。同時由于T2預(yù)占了第4秒的令牌檀训，所以下一令牌產(chǎn)生的時間增加1秒柑潦，完全處理之后，如下圖：

img

面線程 T1峻凫、T2 都是在下一令牌產(chǎn)生時間之前請求令牌渗鬼， 如果線程在下一令牌產(chǎn)生之后請求令牌會如何呢？假設(shè)在線程T1請求令牌之后的第5秒蔚晨，也就是第7秒乍钻，線程T3請求令牌，如下圖：

img

由于第5秒已經(jīng)產(chǎn)生了一個令牌铭腕，所以此時線程T3可以直接拿到令牌银择，而無需等待。在第7秒累舷，實際上限流器能夠產(chǎn)生3個令牌浩考，第5、6被盈、7秒各產(chǎn)生一個令牌析孽，由于我們假設(shè)令牌桶的容量是1，所以第6只怎、7秒產(chǎn)生的令牌就丟棄了袜瞬，其實等價的你也可以認為是保留了第7秒的令牌，丟棄的第5身堡、6秒的令牌邓尤。也就是說第7秒的令牌被線程T3占有了，于是下一令牌產(chǎn)生的時間應(yīng)該是8秒贴谎，如下圖所示：

img

通過上面的簡要分析你會發(fā)現(xiàn)汞扎，我們只需要記錄一個下一個令牌產(chǎn)生的時間，并動態(tài)更新它擅这，就能夠輕松完成限流功能澈魄。我們可以將上面的想法代碼化，依然假設(shè)令牌桶的容量是1仲翎，關(guān)鍵是reserve() 方法痹扇， 這個方法為請求令牌桶的線程預(yù)分配令牌铛漓，同時返回該線程能獲取令牌的時間，其實現(xiàn)邏輯：如果線程請求令牌時間在下一令牌產(chǎn)生時間之后那么該線程就可以立即獲取令牌帘营。反之請求時間在下一令牌產(chǎn)生之前票渠，那么該線程在下一令牌產(chǎn)生的時間獲取令牌逐哈。由于此時下一令牌已經(jīng)被該線程占有芬迄，所以下一令牌產(chǎn)生的時間需要加上1秒。

public class SimpleLimiter {
    /**
     * 下一令牌產(chǎn)生時間
     */
    long next     = System.nanoTime();

    /**
     * 發(fā)放令牌間隔：納秒
     */
    long interval = 1000_000_000;

    synchronized long reserve(long now) {
        //請求時間在下一令牌產(chǎn)生之后,重新計算下一令牌時間
        if (now > next) {
            //將下一令牌產(chǎn)生時間置為當前時間
            next = now;
        }
        //能夠獲取令牌的時間
        long at = next;
        //設(shè)置下一令牌產(chǎn)生時間
        next += interval;
        //返回線程需要等待時間
        return Math.max(at, 0L);
    }

    void acquire() {
        //申請令牌時間
        long now = System.nanoTime();
        //預(yù)占令牌
        long at = reserve(now);
        long waitTime = Math.max(at - now, 0L);
        //按照條件等待
        if (waitTime > 0) {
            try {
                TimeUnit.NANOSECONDS.sleep(waitTime);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

總結(jié)

經(jīng)典限流算法有兩個：一個是令牌桶算法昂秃，一個是漏桶算法禀梳。令牌桶算法是定時向令牌桶發(fā)送令牌，漏桶算法會按照一定的速率自動將水漏掉肠骆。只要漏桶里面還能注入水算途，請求才能通過限流器。