源碼分析:高性能限流器Guava RateLimiter

主題

本章我們來分析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ā)送令牌,漏桶算法會按照一定的速率自動將水漏掉肠骆。只要漏桶里面還能注入水算途,請求才能通過限流器。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末蚀腿,一起剝皮案震驚了整個濱河市嘴瓤,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌莉钙,老刑警劉巖廓脆,帶你破解...
    沈念sama閱讀 219,188評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異磁玉,居然都是意外死亡停忿,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,464評論 3 395
  • 文/潘曉璐 我一進店門蚊伞,熙熙樓的掌柜王于貴愁眉苦臉地迎上來席赂,“玉大人,你說我怎么就攤上這事时迫÷#” “怎么了?”我有些...
    開封第一講書人閱讀 165,562評論 0 356
  • 文/不壞的土叔 我叫張陵掠拳,是天一觀的道長癞揉。 經(jīng)常有香客問我,道長碳想,這世上最難降的妖魔是什么烧董? 我笑而不...
    開封第一講書人閱讀 58,893評論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮胧奔,結(jié)果婚禮上逊移,老公的妹妹穿的比我還像新娘。我一直安慰自己龙填,他們只是感情好胳泉,可當我...
    茶點故事閱讀 67,917評論 6 392
  • 文/花漫 我一把揭開白布拐叉。 她就那樣靜靜地躺著,像睡著了一般扇商。 火紅的嫁衣襯著肌膚如雪凤瘦。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,708評論 1 305
  • 那天案铺,我揣著相機與錄音蔬芥,去河邊找鬼。 笑死控汉,一個胖子當著我的面吹牛笔诵,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播姑子,決...
    沈念sama閱讀 40,430評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼乎婿,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了街佑?” 一聲冷哼從身側(cè)響起谢翎,我...
    開封第一講書人閱讀 39,342評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎沐旨,沒想到半個月后森逮,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,801評論 1 317
  • 正文 獨居荒郊野嶺守林人離奇死亡希俩,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,976評論 3 337
  • 正文 我和宋清朗相戀三年吊宋,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片颜武。...
    茶點故事閱讀 40,115評論 1 351
  • 序言:一個原本活蹦亂跳的男人離奇死亡璃搜,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出鳞上,到底是詐尸還是另有隱情这吻,我是刑警寧澤,帶...
    沈念sama閱讀 35,804評論 5 346
  • 正文 年R本政府宣布篙议,位于F島的核電站唾糯,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏鬼贱。R本人自食惡果不足惜移怯,卻給世界環(huán)境...
    茶點故事閱讀 41,458評論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望这难。 院中可真熱鬧舟误,春花似錦、人聲如沸姻乓。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,008評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至赖草,卻和暖如春学少,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背秧骑。 一陣腳步聲響...
    開封第一講書人閱讀 33,135評論 1 272
  • 我被黑心中介騙來泰國打工版确, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人腿堤。 一個月前我還...
    沈念sama閱讀 48,365評論 3 373
  • 正文 我出身青樓阀坏,卻偏偏與公主長得像如暖,于是被迫代替她去往敵國和親笆檀。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,055評論 2 355

推薦閱讀更多精彩內(nèi)容