主題
本章我們來分析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ā)送令牌的速率嗅骄,那么就能控制流速了胳挎。令牌桶算法的詳細描述如下:
- 令牌以固定的速率添加到令牌桶,假設(shè)限流的速率是 r/秒溺森,則令牌以每1/r秒會添加一個慕爬;
- 假設(shè)令牌桶的容量是b,如果令牌桶已滿屏积,則新的令牌會被丟棄医窿;
- 請求能夠通過限流器的前提是令牌桶中有令牌;
這個算法中限流的速率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 請求令牌破讨,此時該如何處理呢?
對于這個請求令牌的線程而言奕纫,很顯然需要等待1秒提陶,因為1秒以后(第 3 秒) ,他就能拿到令牌了匹层。此時需要注意的是隙笆,下一個令牌的發(fā)放時間也要增加1秒,為什么呢?因為第3秒發(fā)放的令牌已經(jīng)被線程T1預(yù)占了撑柔,處理之后如下圖:
假設(shè)T1在預(yù)占了第3秒的令牌之后瘸爽,馬上又有一個線程T2請求令牌,如下圖所示:
很顯然由于下一個令牌的產(chǎn)生時間是第4秒铅忿,所以線程T2需要等待2秒的時間剪决,才能獲取到令牌。同時由于T2預(yù)占了第4秒的令牌檀训,所以下一令牌產(chǎn)生的時間增加1秒柑潦,完全處理之后,如下圖:
面線程 T1峻凫、T2 都是在下一令牌產(chǎn)生時間之前請求令牌渗鬼, 如果線程在下一令牌產(chǎn)生之后請求令牌會如何呢?假設(shè)在線程T1請求令牌之后的第5秒蔚晨,也就是第7秒乍钻,線程T3請求令牌,如下圖:
由于第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秒贴谎,如下圖所示:
通過上面的簡要分析你會發(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ā)送令牌,漏桶算法會按照一定的速率自動將水漏掉肠骆。只要漏桶里面還能注入水算途,請求才能通過限流器。