今天來(lái)聊一聊Guava RateLimiter 是如何解決高并發(fā)場(chǎng)景下的限流問題的。

Guava 是 Google 開源的 Java 類庫(kù)，提供了一個(gè)工具類 RateLimiter。我們先來(lái)看看 RateLimiter 的使用，讓你對(duì)限流有個(gè)感官的印象。假設(shè)我們有一個(gè)線程池，它每秒只能處理兩個(gè)任務(wù)，如果提交的任務(wù)過快，可能導(dǎo)致系統(tǒng)不穩(wěn)定，這個(gè)時(shí)候就需要用到限流。

在下面的示例代碼中，我們創(chuàng)建了一個(gè)流速為 2 個(gè)請(qǐng)求 / 秒的限流器，這里的流速該怎么理解呢？直觀地看，2 個(gè)請(qǐng)求 / 秒指的是每秒最多允許 2 個(gè)請(qǐng)求通過限流器，其實(shí)在 Guava 中，流速還有更深一層的意思：是一種勻速的概念，2 個(gè)請(qǐng)求 / 秒等價(jià)于 1 個(gè)請(qǐng)求 /500 毫秒。

在向線程池提交任務(wù)之前，調(diào)用 acquire() 方法就能起到限流的作用。通過示例代碼的執(zhí)行結(jié)果，任務(wù)提交到線程池的時(shí)間間隔基本上穩(wěn)定在 500 毫秒。

//限流器流速：2個(gè)請(qǐng)求/秒
RateLimiter limiter = 
  RateLimiter.create(2.0);
//執(zhí)行任務(wù)的線程池
ExecutorService es = Executors
  .newFixedThreadPool(1);
//記錄上一次執(zhí)行時(shí)間
prev = System.nanoTime();
//測(cè)試執(zhí)行20次
for (int i=0; i<20; i++){
  //限流器限流
  limiter.acquire();
  //提交任務(wù)異步執(zhí)行
  es.execute(()->{
    long cur=System.nanoTime();
    //打印時(shí)間間隔：毫秒
    System.out.println(
      (cur-prev)/1000_000);
    prev = cur;
  });
}

輸出結(jié)果：
...
500
499
499
500
499

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

Guava 的限流器使用上還是很簡(jiǎn)單的，那它是如何實(shí)現(xiàn)的呢？Guava 采用的是令牌桶算法，其核心是要想通過限流器，必須拿到令牌。也就是說，只要我們能夠限制發(fā)放令牌的速率，那么就能控制流速了。令牌桶算法的詳細(xì)描述如下：

• 令牌以固定的速率添加到令牌桶中，假設(shè)限流的速率是 r/ 秒，則令牌每 1/r 秒會(huì)添加一個(gè)；
• 假設(shè)令牌桶的容量是 b ，如果令牌桶已滿，則新的令牌會(huì)被丟棄；
• 請(qǐng)求能夠通過限流器的前提是令牌桶中有令牌。

這個(gè)算法中，限流的速率 r 還是比較容易理解的，但令牌桶的容量 b 該怎么理解呢？b 其實(shí)是 burst 的簡(jiǎn)寫，意義是限流器允許的最大突發(fā)流量。比如 b=10，而且令牌桶中的令牌已滿，此時(shí)限流器允許 10 個(gè)請(qǐng)求同時(shí)通過限流器，當(dāng)然只是突發(fā)流量而已，這 10 個(gè)請(qǐng)求會(huì)帶走 10 個(gè)令牌，所以后續(xù)的流量只能按照速率 r 通過限流器。

令牌桶這個(gè)算法，如何用 Java 實(shí)現(xiàn)呢？很可能你的直覺會(huì)告訴你生產(chǎn)者 - 消費(fèi)者模式：一個(gè)生產(chǎn)者線程定時(shí)向阻塞隊(duì)列中添加令牌，而試圖通過限流器的線程則作為消費(fèi)者線程，只有從阻塞隊(duì)列中獲取到令牌，才允許通過限流器。

這個(gè)算法看上去非常完美，而且實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單，如果并發(fā)量不大，這個(gè)實(shí)現(xiàn)并沒有什么問題?？蓪?shí)際情況卻是使用限流的場(chǎng)景大部分都是高并發(fā)場(chǎng)景，而且系統(tǒng)壓力已經(jīng)臨近極限了，此時(shí)這個(gè)實(shí)現(xiàn)就有問題了。問題就出在定時(shí)器上，在高并發(fā)場(chǎng)景下，當(dāng)系統(tǒng)壓力已經(jīng)臨近極限的時(shí)候，定時(shí)器的精度誤差會(huì)非常大，同時(shí)定時(shí)器本身會(huì)創(chuàng)建調(diào)度線程，也會(huì)對(duì)系統(tǒng)的性能產(chǎn)生影響。

那還有什么好的實(shí)現(xiàn)方式呢？當(dāng)然有，Guava 的實(shí)現(xiàn)就沒有使用定時(shí)器，下面我們就來(lái)看看它是如何實(shí)現(xiàn)的。

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

Guava 實(shí)現(xiàn)令牌桶算法，用了一個(gè)很簡(jiǎn)單的辦法，其關(guān)鍵是記錄并動(dòng)態(tài)計(jì)算下一令牌發(fā)放的時(shí)間。

下面我們以一個(gè)最簡(jiǎn)單的場(chǎng)景來(lái)介紹該算法的執(zhí)行過程。假設(shè)令牌桶的容量為 b=1，限流速率 r = 1 個(gè)請(qǐng)求 / 秒，如下圖所示，如果當(dāng)前令牌桶中沒有令牌，下一個(gè)令牌的發(fā)放時(shí)間是在第 3 秒，而在第 2 秒的時(shí)候有一個(gè)線程 T1 請(qǐng)求令牌，此時(shí)該如何處理呢？

線程 T1 請(qǐng)求令牌示意圖

對(duì)于這個(gè)請(qǐng)求令牌的線程而言，很顯然需要等待 1 秒，因?yàn)?1 秒以后（第 3 秒）它就能拿到令牌了。此時(shí)需要注意的是，下一個(gè)令牌發(fā)放的時(shí)間也要增加 1 秒，為什么呢？因?yàn)榈?3 秒發(fā)放的令牌已經(jīng)被線程 T1 預(yù)占了。處理之后如下圖所示。

線程 T1 請(qǐng)求結(jié)束示意圖

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

線程 T2 請(qǐng)求結(jié)束示意圖

上面線程 T1、T2 都是在下一令牌產(chǎn)生時(shí)間之前請(qǐng)求令牌，如果線程在下一令牌產(chǎn)生時(shí)間之后請(qǐng)求令牌會(huì)如何呢？假設(shè)在線程 T1 請(qǐng)求令牌之后的 5 秒，也就是第 7 秒，線程 T3 請(qǐng)求令牌，如下圖所示。

線程 T3 請(qǐng)求令牌示意圖

由于在第 5 秒已經(jīng)產(chǎn)生了一個(gè)令牌，所以此時(shí)線程 T3 可以直接拿到令牌，而無(wú)需等待。在第 7 秒，實(shí)際上限流器能夠產(chǎn)生 3 個(gè)令牌，第 5、6、7 秒各產(chǎn)生一個(gè)令牌。由于我們假設(shè)令牌桶的容量是 1，所以第 6、7 秒產(chǎn)生的令牌就丟棄了，其實(shí)等價(jià)地你也可以認(rèn)為是保留的第 7 秒的令牌，丟棄的第 5、6 秒的令牌，也就是說第 7 秒的令牌被線程 T3 占有了，于是下一令牌的的產(chǎn)生時(shí)間應(yīng)該是第 8 秒，如下圖所示。

線程 T3 請(qǐng)求結(jié)束示意圖

通過上面簡(jiǎn)要地分析，你會(huì)發(fā)現(xiàn)，我們只需要記錄一個(gè)下一令牌產(chǎn)生的時(shí)間，并動(dòng)態(tài)更新它，就能夠輕松完成限流功能。我們可以將上面的這個(gè)算法代碼化，示例代碼如下所示，依然假設(shè)令牌桶的容量是 1。關(guān)鍵是 reserve() 方法，這個(gè)方法會(huì)為請(qǐng)求令牌的線程預(yù)分配令牌，同時(shí)返回該線程能夠獲取令牌的時(shí)間。其實(shí)現(xiàn)邏輯就是上面提到的：如果線程請(qǐng)求令牌的時(shí)間在下一令牌產(chǎn)生時(shí)間之后，那么該線程立刻就能夠獲取令牌；反之，如果請(qǐng)求時(shí)間在下一令牌產(chǎn)生時(shí)間之前，那么該線程是在下一令牌產(chǎn)生的時(shí)間獲取令牌。由于此時(shí)下一令牌已經(jīng)被該線程預(yù)占，所以下一令牌產(chǎn)生的時(shí)間需要加上 1 秒。

class SimpleLimiter {
  //下一令牌產(chǎn)生時(shí)間
  long next = System.nanoTime();
  //發(fā)放令牌間隔：納秒
  long interval = 1000_000_000;
  //預(yù)占令牌，返回能夠獲取令牌的時(shí)間
  synchronized long reserve(long now){
    //請(qǐng)求時(shí)間在下一令牌產(chǎn)生時(shí)間之后
    //重新計(jì)算下一令牌產(chǎn)生時(shí)間
    if (now > next){
      //將下一令牌產(chǎn)生時(shí)間重置為當(dāng)前時(shí)間
      next = now;
    }
    //能夠獲取令牌的時(shí)間
    long at=next;
    //設(shè)置下一令牌產(chǎn)生時(shí)間
    next += interval;
    //返回線程需要等待的時(shí)間
    return Math.max(at, 0L);
  }
  //申請(qǐng)令牌
  void acquire() {
    //申請(qǐng)令牌時(shí)的時(shí)間
    long now = System.nanoTime();
    //預(yù)占令牌
    long at=reserve(now);
    long waitTime=max(at-now, 0);
    //按照條件等待
    if(waitTime > 0) {
      try {
        TimeUnit.NANOSECONDS
          .sleep(waitTime);
      }catch(InterruptedException e){
        e.printStackTrace();
      }
    }
  }
}

如果令牌桶的容量大于 1，又該如何處理呢？按照令牌桶算法，令牌要首先從令牌桶中出，所以我們需要按需計(jì)算令牌桶中的數(shù)量，當(dāng)有線程請(qǐng)求令牌時(shí)，先從令牌桶中出。具體的代碼實(shí)現(xiàn)如下所示。我們?cè)黾恿艘粋€(gè) resync() ?方法，在這個(gè)方法中，如果線程請(qǐng)求令牌的時(shí)間在下一令牌產(chǎn)生時(shí)間之后，會(huì)重新計(jì)算令牌桶中的令牌數(shù)，新產(chǎn)生的令牌的計(jì)算公式是：(now-next)/interval，你可對(duì)照上面的示意圖來(lái)理解。reserve() 方法中，則增加了先從令牌桶中出令牌的邏輯，不過需要注意的是，如果令牌是從令牌桶中出的，那么 next 就無(wú)需增加一個(gè) interval 了。

class SimpleLimiter {
  //當(dāng)前令牌桶中的令牌數(shù)量
  long storedPermits = 0;
  //令牌桶的容量
  long maxPermits = 3;
  //下一令牌產(chǎn)生時(shí)間
  long next = System.nanoTime();
  //發(fā)放令牌間隔：納秒
  long interval = 1000_000_000;
  
  //請(qǐng)求時(shí)間在下一令牌產(chǎn)生時(shí)間之后,則
  // 1.重新計(jì)算令牌桶中的令牌數(shù)
  // 2.將下一個(gè)令牌發(fā)放時(shí)間重置為當(dāng)前時(shí)間
  void resync(long now) {
    if (now > next) {
      //新產(chǎn)生的令牌數(shù)
      long newPermits=(now-next)/interval;
      //新令牌增加到令牌桶
      storedPermits=min(maxPermits, 
        storedPermits + newPermits);
      //將下一個(gè)令牌發(fā)放時(shí)間重置為當(dāng)前時(shí)間
      next = now;
    }
  }
  //預(yù)占令牌，返回能夠獲取令牌的時(shí)間
  synchronized long reserve(long now){
    resync(now);
    //能夠獲取令牌的時(shí)間
    long at = next;
    //令牌桶中能提供的令牌
    long fb=min(1, storedPermits);
    //令牌凈需求：首先減掉令牌桶中的令牌
    long nr = 1 - fb;
    //重新計(jì)算下一令牌產(chǎn)生時(shí)間
    next = next + nr*interval;
    //重新計(jì)算令牌桶中的令牌
    this.storedPermits -= fb;
    return at;
  }
  //申請(qǐng)令牌
  void acquire() {
    //申請(qǐng)令牌時(shí)的時(shí)間
    long now = System.nanoTime();
    //預(yù)占令牌
    long at=reserve(now);
    long waitTime=max(at-now, 0);
    //按照條件等待
    if(waitTime > 0) {
      try {
        TimeUnit.NANOSECONDS
          .sleep(waitTime);
      }catch(InterruptedException e){
        e.printStackTrace();
      }
    }
  }
}

總結(jié)

經(jīng)典的限流算法有兩個(gè)，一個(gè)是令牌桶算法（Token Bucket），另一個(gè)是漏桶算法（Leaky Bucket）。令牌桶算法是定時(shí)向令牌桶發(fā)送令牌，請(qǐng)求能夠從令牌桶中拿到令牌，然后才能通過限流器；

而漏桶算法里，請(qǐng)求就像水一樣注入漏桶，漏桶會(huì)按照一定的速率自動(dòng)將水漏掉，只有漏桶里還能注入水的時(shí)候，請(qǐng)求才能通過限流器。令牌桶算法和漏桶算法很像一個(gè)硬幣的正反面，所以你可以參考令牌桶算法的實(shí)現(xiàn)來(lái)實(shí)現(xiàn)漏桶算法。

上面我們介紹了 Guava 是如何實(shí)現(xiàn)令牌桶算法的，我們的示例代碼是對(duì) Guava RateLimiter 的簡(jiǎn)化，Guava RateLimiter 擴(kuò)展了標(biāo)準(zhǔn)的令牌桶算法，比如還能支持預(yù)熱功能。對(duì)于按需加載的緩存來(lái)說，預(yù)熱后緩存能支持 5 萬(wàn) TPS 的并發(fā)，但是在預(yù)熱前 5 萬(wàn) TPS 的并發(fā)直接就把緩存擊垮了，所以如果需要給該緩存限流，限流器也需要支持預(yù)熱功能，在初始階段，限制的流速 r 很小，但是動(dòng)態(tài)增長(zhǎng)的。預(yù)熱功能的實(shí)現(xiàn)非常復(fù)雜，Guava 構(gòu)建了一個(gè)積分函數(shù)來(lái)解決這個(gè)問題，如果你感興趣，可以繼續(xù)深入研究。