高性能限流器 Guava RateLimiter
大家好,我是不才陳某~
今天來聊一聊 Guava RateLimiter 是如何解決高併發場景下的限流問題的。
Guava 是 Google 開源的 Java 類庫,提供了一個工具類 RateLimiter。我們先來看看 RateLimiter 的使用,讓你對限流有個感官的印象。假設我們有一個線程池,它每秒只能處理兩個任務,如果提交的任務過快,可能導致系統不穩定,這個時候就需要用到限流。
在下面的示例代碼中,我們創建了一個流速爲 2 個請求 / 秒的限流器,這裏的流速該怎麼理解呢?直觀地看,2 個請求 / 秒指的是每秒最多允許 2 個請求通過限流器,其實在 Guava 中,流速還有更深一層的意思:是一種勻速的概念,2 個請求 / 秒等價於 1 個請求 /500 毫秒。
在向線程池提交任務之前,調用 acquire()
方法就能起到限流的作用。通過示例代碼的執行結果,任務提交到線程池的時間間隔基本上穩定在 500 毫秒。
//限流器流速:2個請求/秒
RateLimiter limiter =
RateLimiter.create(2.0);
//執行任務的線程池
ExecutorService es = Executors
.newFixedThreadPool(1);
//記錄上一次執行時間
prev = System.nanoTime();
//測試執行20次
for (int i=0; i<20; i++){
//限流器限流
limiter.acquire();
//提交任務異步執行
es.execute(()->{
long cur=System.nanoTime();
//打印時間間隔:毫秒
System.out.println(
(cur-prev)/1000_000);
prev = cur;
});
}
輸出結果:
...
500
499
499
500
499
經典限流算法:令牌桶算法
Guava 的限流器使用上還是很簡單的,那它是如何實現的呢?Guava 採用的是令牌桶算法,其核心是要想通過限流器,必須拿到令牌。也就是說,只要我們能夠限制發放令牌的速率,那麼就能控制流速了。令牌桶算法的詳細描述如下:
-
令牌以固定的速率添加到令牌桶中,假設限流的速率是 r/ 秒,則令牌每 1/r 秒會添加一個;
-
假設令牌桶的容量是 b ,如果令牌桶已滿,則新的令牌會被丟棄;
-
請求能夠通過限流器的前提是令牌桶中有令牌。
這個算法中,限流的速率 r 還是比較容易理解的,但令牌桶的容量 b 該怎麼理解呢?b 其實是 burst 的簡寫,意義是限流器允許的最大突發流量。比如 b=10,而且令牌桶中的令牌已滿,此時限流器允許 10 個請求同時通過限流器,當然只是突發流量而已,這 10 個請求會帶走 10 個令牌,所以後續的流量只能按照速率 r 通過限流器。
令牌桶這個算法,如何用 Java 實現呢?很可能你的直覺會告訴你生產者 - 消費者模式:一個生產者線程定時向阻塞隊列中添加令牌,而試圖通過限流器的線程則作爲消費者線程,只有從阻塞隊列中獲取到令牌,才允許通過限流器。
這個算法看上去非常完美,而且實現起來非常簡單,如果併發量不大,這個實現並沒有什麼問題。可實際情況卻是使用限流的場景大部分都是高併發場景,而且系統壓力已經臨近極限了,此時這個實現就有問題了。問題就出在定時器上,在高併發場景下,當系統壓力已經臨近極限的時候,定時器的精度誤差會非常大,同時定時器本身會創建調度線程,也會對系統的性能產生影響。
那還有什麼好的實現方式呢?當然有,Guava 的實現就沒有使用定時器,下面我們就來看看它是如何實現的。
Guava 如何實現令牌桶算法
Guava 實現令牌桶算法,用了一個很簡單的辦法,其關鍵是記錄並動態計算下一令牌發放的時間。
下面我們以一個最簡單的場景來介紹該算法的執行過程。假設令牌桶的容量爲 b=1,限流速率 r = 1 個請求 / 秒,如下圖所示,如果當前令牌桶中沒有令牌,下一個令牌的發放時間是在第 3 秒,而在第 2 秒的時候有一個線程 T1 請求令牌,此時該如何處理呢?
線程 T1 請求令牌示意圖
對於這個請求令牌的線程而言,很顯然需要等待 1 秒,因爲 1 秒以後(第 3 秒)它就能拿到令牌了。此時需要注意的是,下一個令牌發放的時間也要增加 1 秒,爲什麼呢?因爲第 3 秒發放的令牌已經被線程 T1 預佔了。處理之後如下圖所示。
線程 T1 請求結束示意圖
假設 T1 在預佔了第 3 秒的令牌之後,馬上又有一個線程 T2 請求令牌,如下圖所示。
線程 T2 請求結束示意圖
上面線程 T1、T2 都是在下一令牌產生時間之前請求令牌,如果線程在下一令牌產生時間之後請求令牌會如何呢?假設在線程 T1 請求令牌之後的 5 秒,也就是第 7 秒,線程 T3 請求令牌,如下圖所示。
線程 T3 請求令牌示意圖
由於在第 5 秒已經產生了一個令牌,所以此時線程 T3 可以直接拿到令牌,而無需等待。在第 7 秒,實際上限流器能夠產生 3 個令牌,第 5、6、7 秒各產生一個令牌。由於我們假設令牌桶的容量是 1,所以第 6、7 秒產生的令牌就丟棄了,其實等價地你也可以認爲是保留的第 7 秒的令牌,丟棄的第 5、6 秒的令牌,也就是說第 7 秒的令牌被線程 T3 佔有了,於是下一令牌的的產生時間應該是第 8 秒,如下圖所示。
線程 T3 請求結束示意圖
通過上面簡要地分析,你會發現,我們只需要記錄一個下一令牌產生的時間,並動態更新它,就能夠輕鬆完成限流功能。我們可以將上面的這個算法代碼化,示例代碼如下所示,依然假設令牌桶的容量是 1。關鍵是 reserve()
方法,這個方法會爲請求令牌的線程預分配令牌,同時返回該線程能夠獲取令牌的時間。其實現邏輯就是上面提到的:如果線程請求令牌的時間在下一令牌產生時間之後,那麼該線程立刻就能夠獲取令牌;反之,如果請求時間在下一令牌產生時間之前,那麼該線程是在下一令牌產生的時間獲取令牌。由於此時下一令牌已經被該線程預佔,所以下一令牌產生的時間需要加上 1 秒。
class SimpleLimiter {
//下一令牌產生時間
long next = System.nanoTime();
//發放令牌間隔:納秒
long interval = 1000_000_000;
//預佔令牌,返回能夠獲取令牌的時間
synchronized long reserve(long now){
//請求時間在下一令牌產生時間之後
//重新計算下一令牌產生時間
if (now > next){
//將下一令牌產生時間重置爲當前時間
next = now;
}
//能夠獲取令牌的時間
long at=next;
//設置下一令牌產生時間
next += interval;
//返回線程需要等待的時間
return Math.max(at, 0L);
}
//申請令牌
void acquire() {
//申請令牌時的時間
long now = System.nanoTime();
//預佔令牌
long at=reserve(now);
long waitTime=max(at-now, 0);
//按照條件等待
if(waitTime > 0) {
try {
TimeUnit.NANOSECONDS
.sleep(waitTime);
}catch(InterruptedException e){
e.printStackTrace();
}
}
}
}
如果令牌桶的容量大於 1,又該如何處理呢?按照令牌桶算法,令牌要首先從令牌桶中出,所以我們需要按需計算令牌桶中的數量,當有線程請求令牌時,先從令牌桶中出。具體的代碼實現如下所示。我們增加了一個 resync()
方法,在這個方法中,如果線程請求令牌的時間在下一令牌產生時間之後,會重新計算令牌桶中的令牌數,新產生的令牌的計算公式是:(now-next)/interval
,你可對照上面的示意圖來理解。reserve() 方法中,則增加了先從令牌桶中出令牌的邏輯,不過需要注意的是,如果令牌是從令牌桶中出的,那麼 next 就無需增加一個 interval 了。
class SimpleLimiter {
//當前令牌桶中的令牌數量
long storedPermits = 0;
//令牌桶的容量
long maxPermits = 3;
//下一令牌產生時間
long next = System.nanoTime();
//發放令牌間隔:納秒
long interval = 1000_000_000;
//請求時間在下一令牌產生時間之後,則
// 1.重新計算令牌桶中的令牌數
// 2.將下一個令牌發放時間重置爲當前時間
void resync(long now) {
if (now > next) {
//新產生的令牌數
long newPermits=(now-next)/interval;
//新令牌增加到令牌桶
storedPermits=min(maxPermits,
storedPermits + newPermits);
//將下一個令牌發放時間重置爲當前時間
next = now;
}
}
//預佔令牌,返回能夠獲取令牌的時間
synchronized long reserve(long now){
resync(now);
//能夠獲取令牌的時間
long at = next;
//令牌桶中能提供的令牌
long fb=min(1, storedPermits);
//令牌淨需求:首先減掉令牌桶中的令牌
long nr = 1 - fb;
//重新計算下一令牌產生時間
next = next + nr*interval;
//重新計算令牌桶中的令牌
this.storedPermits -= fb;
return at;
}
//申請令牌
void acquire() {
//申請令牌時的時間
long now = System.nanoTime();
//預佔令牌
long at=reserve(now);
long waitTime=max(at-now, 0);
//按照條件等待
if(waitTime > 0) {
try {
TimeUnit.NANOSECONDS
.sleep(waitTime);
}catch(InterruptedException e){
e.printStackTrace();
}
}
}
}
總結
經典的限流算法有兩個,一個是令牌桶算法(Token Bucket),另一個是漏桶算法(Leaky Bucket)。令牌桶算法是定時向令牌桶發送令牌,請求能夠從令牌桶中拿到令牌,然後才能通過限流器;
而漏桶算法裏,請求就像水一樣注入漏桶,漏桶會按照一定的速率自動將水漏掉,只有漏桶裏還能注入水的時候,請求才能通過限流器。令牌桶算法和漏桶算法很像一個硬幣的正反面,所以你可以參考令牌桶算法的實現來實現漏桶算法。
上面我們介紹了 Guava 是如何實現令牌桶算法的,我們的示例代碼是對 Guava RateLimiter 的簡化,Guava RateLimiter 擴展了標準的令牌桶算法,比如還能支持預熱功能。對於按需加載的緩存來說,預熱後緩存能支持 5 萬 TPS 的併發,但是在預熱前 5 萬 TPS 的併發直接就把緩存擊垮了,所以如果需要給該緩存限流,限流器也需要支持預熱功能,在初始階段,限制的流速 r 很小,但是動態增長的。預熱功能的實現非常複雜,Guava 構建了一個積分函數來解決這個問題,如果你感興趣,可以繼續深入研究。
碼猿技術專欄 前螞蟻 P8,純粹的技術人,掘金優秀作者,以專欄的形式分享技術,只寫外面看不到的乾貨,你想要的都在這裏……
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/SkvrEFCEv3GKmZWRNelSOg