我們首先講一個場景，假如一個接口只能支持每秒5次訪問速率，假如要實現(xiàn)這個功能要如何實現(xiàn)？通用的方法我們知道有計數器，漏斗，令牌桶等方法，本文主要介紹Guava如何是如何實現(xiàn)限流的

Guava是使用令牌桶算法來實現(xiàn)限流功能的，但也有自己的一些特點：

1. 在每次有請求來獲取token的時候，會同時添加令牌到令牌桶中，并不是通過異步任務固定速率添加令牌到令牌桶中，是一個惰性的方法。
2. 超額信用消費，即用將來時間產生的令牌，來滿足當前的請求，這樣能應對一定的瞬間流量

可以帶著這兩個特點來繼續(xù)閱讀下文，首先看下Guava是如何使用的，簡單代碼如下（創(chuàng)建每秒5次的限流器）：

RateLimiter limiter = RateLimiter.create(5.0); //創(chuàng)建每秒一次的限流器 
double timeWaited = limiter.acquire(); //獲取令牌，返回值為獲取令牌等待的時間 System.out.println("time waited: " + timeWaited);

上面的代碼使用時很簡單的，下面來剖析下代碼實現(xiàn)，Guava 中的限流器有兩種實現(xiàn)，

1. SmoothBursty，顧名思義，該實現(xiàn)主要通過令牌桶方法實現(xiàn)，能夠應對突發(fā)流量
2. SmoothWarmingUp，實現(xiàn)也是通過令牌桶方法，但在應對突發(fā)流量與流量整形中取了折中，能應對一定的突發(fā)流量，同時具有一定的流量整形功能

首先我們先看下整體的類結構，下圖是類圖：

image.jpeg

首先介紹下基類SmoothRateLimiter的關鍵屬性：

SmoothBursty限流實現(xiàn)分析

SmoothBursty類中有一個自己的屬性：maxBurstSeconds，值默認為1，表示流量最大持續(xù)時間，maxPermits = maxBurstSeconds * permitsPerSecond，permitsPerSecond表示每秒qps

此時一次請求token的請求會首先到acquire()方法中，該方法會順序執(zhí)行以下三個步驟

1. 補充token到令牌桶中，若當前時間nowMicros大于nextFreeTicketMicros，說明有新的token可以產生，并可以加入到令牌桶中的，具體方法在SmoothRateLimiter#resync
2. 獲取token，并計算獲取這些token需要等待的時間，具體方法在SmoothRateLimiter#reserveEarliestAvailable
3. 根據獲取token時返回的等待時間，阻塞當前線程，直到指定的等待時間，具體執(zhí)行入口是在acquire()中的stopwatch.sleepMicrosUninterruptibly(microsToWait)觸發(fā)

拋開代碼實現(xiàn)流程，從token的數據處理流程得到下圖：

image.jpeg

上面的各個屬性可以參考一開始的表格，如上圖，當在nowMicros時間點請求requiredPermits個token時，會先判斷nowMicros是否大于nextFreeTicketMicros，

1. 若大于則會多走一步step1，計算出在[nextFreeTicketMicros,nowMicros]產生的tokens，并將這些token加到令牌桶總數中storedPermits，同時將nextFreeTicketMicros設置為當前時間，其中coolDownIntervalMicros這個方法是獲取產生一個token所需要的時間間隔

2. step2不管怎樣都會被執(zhí)行，在步驟中會計算獲取token所需要的等待時間，同時更新nextFreeTicketMicros時間，即下一次可以獲取token的時間點：

3. storedPermitsToSpend表示可以從令牌桶中獲取的token數量

4. freshPermits表示需要新生成的token數量

5. waitMicros表示獲取requiredPermits個token所需要的消耗時間，該等待時間是由兩部分組成，一個是新生成freshPermits個token需要的時間，以及消耗令牌桶已經存在的storedPermitsToSpend個token所需要的時間，即方法storedPermitsToWaitTime（這個地方可能會有人產生疑問，為啥令牌都已經產生了，直接使用還需要消耗時間，這個會在后面介紹）

現(xiàn)在重點從代碼分析介紹：

acquire方法，獲取token的入口

public double acquire(int permits) {
//更新token同時返回本次請求需要等待的時間，即 nowMicros-nextFreeTicketMicros（注意該時間為step1后的值）
 long microsToWait = reserve(permits);  
//返回本次請求阻塞等待的時間
 stopwatch.sleepMicrosUninterruptibly(microsToWait);
 return 1.0 * microsToWait / SECONDS.toMicros(1L); 
 }

reserve方法會調用reserveAndGetWaitLength方法，

final long reserveAndGetWaitLength(int permits, long nowMicros) { 
//表示當前時間開始，要等到哪個時間點，即為（momentAvailable），才獲取permits個toke，
  long momentAvailable = reserveEarliestAvailable(permits, nowMicros); 
 return max(momentAvailable - nowMicros, 0); }

reserve方法，最終會進入到reserveEarliestAvailable方法中，注意storedPermitsToWaitTime方法在SmoothBursty中是默認返回0

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
 resync(nowMicros); //執(zhí)行step1步驟，更新令牌桶數據
 long returnValue = nextFreeTicketMicros;//保存此刻的nextFreeTicketMicros值 
//獲取本次請求中可以從令牌桶中獲取的token數量
 double storedPermitsToSpend = min(requiredPermits, this.storedPermits); 
//本次請求中，需要新生成的token數量，即令牌桶的令牌不夠用了 
 double freshPermits = requiredPermits - storedPermitsToSpend; 
 long waitMicros = //計算獲取requiredPermits所消耗的總時間 
 storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) + (long) (freshPermits * 
 stableIntervalMicros);
//更新nextFreeTicketMicros，表示下次可以產生token的時間點
 this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros); 
 this.storedPermits -= storedPermitsToSpend; //更新令牌桶，減去被消耗的令牌數據
 return returnValue;
 }

resync方法，更新令牌桶數量和nextFreeTicketMicros，coolDownIntervalMicros用來獲取產生令牌的時間間隔，在SmoothBursty中，該方法默認返回stableIntervalMicros

void resync(long nowMicros) {
  // if nextFreeTicket is in the past, resync to now
  if (nowMicros > nextFreeTicketMicros) {
    double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
    storedPermits = min(maxPermits, storedPermits + newPermits);
    nextFreeTicketMicros = nowMicros;
  }
}

以上就是SmoothBursty限流的實現(xiàn)方法，從上面我們可以看出nextFreeTicketMicros可能是大于當前時間的，即用將來的時間產生token來滿足當前的token需求

SmoothWarmingUp 限流實現(xiàn)分析

以上其實還有一個未解問題，為啥會有storedPermitsToWaitTime方法（雖然在SmoothBursty中是默認返回0，所以在SmoothBursty實現(xiàn)中是沒有任何意義的），為啥使用令牌桶中已經存在的token還要消耗時間？

首先引入一個問題：SmoothBursty實現(xiàn)能夠很好的應對突發(fā)流量，但瞬時流量來了，后端服務是否準備好了？服務中的數據是否“熱起來了”，會不會造成緩存擊穿等問題。所以瞬時流量對服務還是有一定隱患存在的

為了解決這個問題，Guava提供了另外一個限流實現(xiàn)，SmoothWarmingUp，如名字一樣，請求會被緩慢放行，即使使用已經存在存在的令牌，也是要消耗時間的，假設令牌桶的token是滿的，說明在當前時間訪問服務的請求是很少的，此時服務是處于一個“冷狀態(tài)”，所以更不能一下放行大量請求進來，SmoothWarmingUp實現(xiàn)的主流程是和SmoothBursty一樣的，只不過針對storedPermitsToWaitTime和coolDownIntervalMicros有不同的實現(xiàn)

SmoothWarmingUp關鍵屬性：

1. warmupPeriodMicros，表示處于平滑過渡的時間長度
2. slope ，在平滑過渡時間段是，coldInterval隨著storedPermits變化的變化率
3. thresholdPermits，平滑過渡時間段與正常時間段的分界點
4. coldFactor，coldInterval = coldFactor * stableInterval 表示coldInterval與stableInterval倍數關系

image.png

先看下上面這個圖，圖中橫坐標表示令牌桶中可用數量，縱坐標表示使用當前令牌所消耗的時間，所以storedPermitsToWaitTime(storedPermits, storedPermitsToSpend)方法返回的是從令牌桶中使用storedPermitsToSpend個token所需要的時間，而該時間可以表示為上圖中橫坐標為[storedPermits-storedPermitsToSpend,storedPermits]對應的面積。

storedPermitsToWaitTime方法具體源碼：

long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
  double availablePermitsAboveThreshold = storedPermits - thresholdPermits;
  long micros = 0;
  // 假如permitsToTake大于thresholdPermits，則計算【thresholdPermits，storedPermits】的梯形面積
  if (availablePermitsAboveThreshold > 0.0) {
    double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);
    // TODO(cpovirk): Figure out a good name for this variable.
    double length =
        permitsToTime(availablePermitsAboveThreshold)
            + permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake);
    micros = (long) (permitsAboveThresholdToTake * length / 2.0);
    permitsToTake -= permitsAboveThresholdToTake;
  }
  // 計算【storedPermits - thresholdPermits，thresholdPermits】的面積
  micros += (long) (stableIntervalMicros * permitsToTake);
  return micros;
}

在SmoothWarmingUp限流實現(xiàn)中會在doSetRate方法中進行屬性的初始化

void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
  double oldMaxPermits = maxPermits;
  double coldIntervalMicros = stableIntervalMicros * coldFactor;
  thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;  
  maxPermits =
      thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);
  slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);
  if (oldMaxPermits == Double.POSITIVE_INFINITY) {
    // if we don't special-case this, we would get storedPermits == NaN, below
    storedPermits = 0.0;
  } else {
    storedPermits =
        (oldMaxPermits == 0.0)
            ? maxPermits // initial state is cold
            : storedPermits * maxPermits / oldMaxPermits;
  }
}

doSetRate方法解釋：

1. thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros; 我們默認為warmupPeriodMicros平滑過渡的時間長度是正常時間長度的2倍，而如圖所示，在正常階段，thresholdPermits個令牌與與stableInterval的乘積就是產生thresholdPermits令牌的總時間
2. slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits)，表示在平滑過渡時間段是，coldInterval隨著storedPermits變化的變化率

參考文檔：

1. https://segmentfault.com/a/1190000016240755
2. https://www.lagou.com/lgeduarticle/66250.html