前言

昨晚對(duì)球迷來說簡直是盛宴（邊霍啤酒邊看了4場(chǎng)球），當(dāng)然也導(dǎo)致本篇沒寫完。

那么今天就來續(xù)一發(fā)吧。

高并發(fā)的業(yè)務(wù)系統(tǒng)經(jīng)常要接受大流量的考驗(yàn)，為了保證系統(tǒng)的響應(yīng)度和穩(wěn)定性，往往都需要對(duì)有風(fēng)險(xiǎn)的接口實(shí)施限流（rate limiting），更高大上的說法則是“流量整形”（traffic shaping）。限流的思想最初來源于計(jì)算機(jī)網(wǎng)絡(luò)，有兩種經(jīng)典的方法：漏桶和令牌桶。本文先來稍微研究一下它們。

漏桶（Leaky Bucket）

將請(qǐng)求想象成水龍頭里流出的水，接口中有一個(gè)底部開孔的桶，如下圖所示。

這樣就能使請(qǐng)求處理的速率有一個(gè)穩(wěn)定的上限。很顯然，如果進(jìn)水的速率比開孔出水的速率大的話，水（請(qǐng)求）就會(huì)逐漸在桶中積累。若一直積累直到溢出了，那些溢出去的水（請(qǐng)求）就會(huì)被直接丟棄，也就是拒絕服務(wù)（denial of service, DoS）。

漏桶的思路非常簡單直接，易于實(shí)現(xiàn)。但是如果當(dāng)前的網(wǎng)絡(luò)環(huán)境中充斥著短時(shí)流量尖峰，始終保持勻速的漏桶就無法很好地處理了，故后來又產(chǎn)生了令牌桶算法。

令牌桶（Token Bucket）

顧名思義，令牌桶里放的不再是請(qǐng)求，而是令牌，可以理解為處理請(qǐng)求的通行證。如下圖所示。

令牌以恒定的速率產(chǎn)生并放入桶中。桶的大小是有限的，也就是說桶滿了之后，多余的令牌就扔掉了。每當(dāng)請(qǐng)求到來時(shí)，需要從桶中獲取一個(gè)令牌才能真正地處理它。如果桶里沒有令牌，該請(qǐng)求就會(huì)被丟棄。

可見，由于桶里預(yù)先留有一定量的令牌，故可以保證在突發(fā)流量到來且令牌沒耗盡前平滑地處理，比漏桶更靈活一些。

在很久之前的文章《深入理解Spark Streaming流量控制及反壓機(jī)制》中，曾經(jīng)說過Spark Streaming的限流是靠令牌桶來實(shí)現(xiàn)的，具體來講是Google Guava提供的限流器——RateLimiter。它的設(shè)計(jì)比較聰明，下面簡單地看一看。

Guava RateLimiter

類圖如下，字有點(diǎn)多哈。

RateLimiter抽象類提供限流的所有功能，它的實(shí)現(xiàn)類只有SmoothRateLimiter。而SmoothRateLimiter的具體策略又由它的兩個(gè)內(nèi)部子類來實(shí)現(xiàn)。

• SmoothBursty：兼容突發(fā)流量的令牌桶實(shí)現(xiàn)，也就是上一節(jié)描述的經(jīng)典令牌桶算法。
• SmoothWarmingUp：帶預(yù)熱過程的令牌桶實(shí)現(xiàn)，即在桶較滿時(shí)產(chǎn)生令牌的速度較慢，隨著令牌的消耗慢慢增長到恒定速率。如下圖所示，x軸為令牌數(shù)，y軸為延遲，從右向左看的梯形區(qū)域就是令牌消耗的預(yù)熱過程。

本文以經(jīng)典的SmoothBursty為范本來講。先說明一下SmoothRateLimiter的4個(gè)屬性的含義，它們都非常重要。

• storedPermits：當(dāng)前桶里有的令牌數(shù)量。
• maxPermits：桶裝滿時(shí)的令牌數(shù)量，storedPermits不會(huì)比它大。
• stableIntervalMicros：產(chǎn)生令牌的頻率（時(shí)間間隔），單位為微秒。舉個(gè)栗子，如果我們想限制系統(tǒng)的QPS為10，亦即每秒有10個(gè)令牌放入桶中，那么stableIntervalMicros的值就是100000。
• nextFreeTicketMicros：下一個(gè)令牌可用的時(shí)間戳，也就是下一個(gè)請(qǐng)求能夠被處理的時(shí)間戳，單位為微秒。該值會(huì)隨著當(dāng)前請(qǐng)求獲得令牌而增大（因?yàn)闀r(shí)間是自然流動(dòng)的）。若當(dāng)前請(qǐng)求的令牌數(shù)超出可用令牌數(shù)，這個(gè)時(shí)間就被推后（需要時(shí)間產(chǎn)生新的令牌）。當(dāng)然，如果有一段時(shí)間沒有請(qǐng)求進(jìn)入的話，它就會(huì)保持在上次請(qǐng)求的過去時(shí)間戳。

RateLimiter要發(fā)揮作用，首先得產(chǎn)生令牌，由SmoothRateLimiter.resync()方法來實(shí)現(xiàn)。

  void resync(long nowMicros) {
    if (nowMicros > nextFreeTicketMicros) {
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
      storedPermits = min(maxPermits, storedPermits + newPermits);
      nextFreeTicketMicros = nowMicros;
    }
  }

  // SmoothBursty.coolDownIntervalMicros()
  @Override
  double coolDownIntervalMicros() {
    return stableIntervalMicros;
  }

在當(dāng)前時(shí)間戳大于nextFreeTicketMicros（即后者是一個(gè)過去的時(shí)間戳）的情況下，就用它們的時(shí)間差除以產(chǎn)生令牌的頻率，結(jié)果就是這段時(shí)間內(nèi)應(yīng)該產(chǎn)生的令牌數(shù)，進(jìn)而更新桶內(nèi)的現(xiàn)有令牌數(shù)storedPermits，以及將nextFreeTicketMicros更新到現(xiàn)在。

可見，RateLimiter的令牌是延遲（lazy）生成的，也就是說每次受理當(dāng)前請(qǐng)求時(shí)，如果系統(tǒng)已經(jīng)空閑了一定時(shí)間，才會(huì)計(jì)算上次請(qǐng)求到當(dāng)前時(shí)間應(yīng)該產(chǎn)生多少個(gè)令牌，而不是使用單獨(dú)的任務(wù)來定期產(chǎn)生令牌——因?yàn)槎〞r(shí)器無法保證較高的精度，并且性能不佳。當(dāng)然，如果令牌已經(jīng)“超支”，當(dāng)前就不需要再更新令牌了。

接下來則是獲取令牌，由SmoothRateLimiter.reserveEarliestAvailable()方法來實(shí)現(xiàn)，這個(gè)方法名非常self-explanatory了。

  @Override
  final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    resync(nowMicros);
    long returnValue = nextFreeTicketMicros;
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    double freshPermits = requiredPermits - storedPermitsToSpend;
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);

    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
  }

  // SmoothBursty.storedPermitsToWaitTime()
  @Override
  long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
    return 0L;
  }

這個(gè)方法的執(zhí)行流程如下：

1. 調(diào)用上述resync()方法產(chǎn)生令牌。
2. 計(jì)算實(shí)際能提供的令牌數(shù)storedPermitsToSpend，它其實(shí)就是本次請(qǐng)求需要的令牌數(shù)requiredPermits和桶中有的令牌數(shù)storedPermits的較小值。
3. 計(jì)算需要新產(chǎn)生的令牌數(shù)freshPermits。當(dāng)上一步桶中有的令牌不夠用時(shí)，該值就大于0。
4. 根據(jù)freshPermits計(jì)算新產(chǎn)生這批令牌需要多長時(shí)間，記為waitMicros。由于SmoothBursty始終以恒定速率產(chǎn)生令牌，只需要將它與令牌產(chǎn)生的速率簡單相乘就行。SmoothWarmingUp需要考慮預(yù)熱的延時(shí)，所以storedPermitsToWaitTime()方法實(shí)現(xiàn)要復(fù)雜得多。
5. 更新nextFreeTicketMicros和storedPermits的值。

弄明白了產(chǎn)生令牌和獲取令牌的細(xì)節(jié)，我們回到RateLimiter的頂層，看看它到底是如何發(fā)揮作用的。

Guava提供了多個(gè)靜態(tài)create()方法創(chuàng)建RateLimiter，其中創(chuàng)建SmoothBursty的源碼如下。

  public static RateLimiter create(double permitsPerSecond) {
    return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
  }

  @VisibleForTesting
  static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
    rateLimiter.setRate(permitsPerSecond);
    return rateLimiter;
  }

可見，我們創(chuàng)建RateLimiter時(shí)只需要指定期望的QPS。那么SmoothBursty構(gòu)造方法中的maxBurstSeconds參數(shù)有什么用？顧名思義，它表示在令牌桶滿時(shí)能夠承受的突發(fā)流量時(shí)長，這樣就能夠確定出桶的最大容量maxPermits了：

maxPermits = maxBurstSeconds * permitsPerSecond;

不過maxBurstSeconds當(dāng)前不支持自定義，Guava規(guī)定為1秒，故桶的最大容量總是與我們指定的QPS相同。

RateLimiter向用戶提供了acquire()方法用于獲取令牌，以及帶超時(shí)的tryAcquire()方法。下面的代碼示出從acquire()到reserveEarliestAvailable()的調(diào)用鏈，方法都很短。

  @CanIgnoreReturnValue
  public double acquire() {
    return acquire(1);
  }

  @CanIgnoreReturnValue
  public double acquire(int permits) {
    long microsToWait = reserve(permits);
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return 1.0 * microsToWait / SECONDS.toMicros(1L);
  }

  final long reserve(int permits) {
    checkPermits(permits);
    synchronized (mutex()) {
      return reserveAndGetWaitLength(permits, stopwatch.readMicros());
    }

  final long reserveAndGetWaitLength(int permits, long nowMicros) {
    long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
    return max(momentAvailable - nowMicros, 0);
  }

可見：

• 獲取令牌的過程是加鎖的。
• reserveAndGetWaitLength()返回的是獲取令牌需要等待的時(shí)間，在acquire()方法中會(huì)借助Stopwatch阻塞（睡眠）直到獲取成功。Stopwatch是Guava自行實(shí)現(xiàn)的一個(gè)高精度計(jì)時(shí)器。
• acquire()方法會(huì)將上述等待時(shí)間返回，但不需要用戶再處理了，所以該返回值可以忽略（即@CanIgnoreReturnValue注解的含義）。

最后舉個(gè)簡單的例子吧。

public class RateLimiterExample {
  public static void main(String[] args) throws Exception {
    RateLimiter rateLimiter = RateLimiter.create(10);
    Random random = new Random();
    for (int i = 0; i < 20; i++) {
      int numPermits = random.nextInt(20);
      System.out.println(numPermits + "\t" + rateLimiter.acquire(numPermits));
    }
  }
}

運(yùn)行結(jié)果如下。

2   0.0
13  0.198792
4   1.294088
6   0.39622
18  0.59516
12  1.797798
14  1.198664
14  1.397321
13  1.39626
16  1.299534
3   1.595453
9   0.299325
4   0.898857
18  0.394973
2   1.795835
13  0.195926
11  1.294851
2   1.09551
3   0.194857
6   0.297884

可見，每次獲取的令牌數(shù)和獲取時(shí)需要等待的時(shí)長是符合上面所述邏輯的預(yù)期的。

The End

今天大風(fēng)降溫，該把羽絨服毛衣之類的家伙搬出來了。

民那晚安。