限流作為現(xiàn)在微服務(wù)中常見的穩(wěn)定性措施，在面試中肯定也是經(jīng)常會(huì)被問到的，我在面試的時(shí)候也經(jīng)常喜歡問一下你對(duì)限流算法知道哪一些？有看過源碼嗎？實(shí)現(xiàn)原理是什么？

第一部分先講講限流算法，最后再講講源碼的實(shí)現(xiàn)原理。

限流算法

關(guān)于限流的算法大體上可以分為四類：固定窗口計(jì)數(shù)器、滑動(dòng)窗口計(jì)數(shù)器、漏桶(也有稱漏斗，英文Leaky bucket)、令牌桶(英文Token bucket)。

固定窗口

固定窗口，相比其他的限流算法，這應(yīng)該是最簡(jiǎn)單的一種。

它簡(jiǎn)單地對(duì)一個(gè)固定的時(shí)間窗口內(nèi)的請(qǐng)求數(shù)量進(jìn)行計(jì)數(shù)，如果超過請(qǐng)求數(shù)量的閾值，將被直接丟棄。

這個(gè)簡(jiǎn)單的限流算法優(yōu)缺點(diǎn)都很明顯。優(yōu)點(diǎn)的話就是簡(jiǎn)單，缺點(diǎn)舉個(gè)例子來說。

比如我們下圖中的黃色區(qū)域就是固定時(shí)間窗口，默認(rèn)時(shí)間范圍是60s，限流數(shù)量是100。

如圖中括號(hào)內(nèi)所示，前面一段時(shí)間都沒有流量，剛好后面30秒內(nèi)來了100個(gè)請(qǐng)求，此時(shí)因?yàn)闆]有超過限流閾值，所以請(qǐng)求全部通過，然后下一個(gè)窗口的20秒內(nèi)同樣通過了100個(gè)請(qǐng)求。

所以變相的相當(dāng)于在這個(gè)括號(hào)的40秒的時(shí)間內(nèi)就通過了200個(gè)請(qǐng)求，超過了我們限流的閾值。

限流

<figcaption style="margin-top: 5px; text-align: center; color: #888; font-size: 12px;">限流</figcaption>

滑動(dòng)窗口

為了優(yōu)化這個(gè)問題，于是有了滑動(dòng)窗口算法，顧名思義，滑動(dòng)窗口就是時(shí)間窗口在隨著時(shí)間推移不停地移動(dòng)。

滑動(dòng)窗口把一個(gè)固定時(shí)間窗口再繼續(xù)拆分成N個(gè)小窗口，然后對(duì)每個(gè)小窗口分別進(jìn)行計(jì)數(shù)，所有小窗口請(qǐng)求之和不能超過我們?cè)O(shè)定的限流閾值。

以下圖舉例子來說，假設(shè)我們的窗口拆分成了3個(gè)小窗口，小窗口都是20s，同樣基于上面的例子，當(dāng)在第三個(gè)20s的時(shí)候來了100個(gè)請(qǐng)求，可以通過。

然后時(shí)間窗口滑動(dòng)，下一個(gè)20s請(qǐng)求又來了100個(gè)請(qǐng)求，此時(shí)我們滑動(dòng)窗口的60s范圍內(nèi)請(qǐng)求數(shù)量肯定就超過100了啊，所以請(qǐng)求被拒絕。

image

漏桶Leaky bucket

漏桶算法，人如其名，他就是一個(gè)漏的桶，不管請(qǐng)求的數(shù)量有多少，最終都會(huì)以固定的出口流量大小勻速流出，如果請(qǐng)求的流量超過漏桶大小，那么超出的流量將會(huì)被丟棄。

也就是說流量流入的速度是不定的，但是流出的速度是恒定的。

這個(gè)和MQ削峰填谷的思想比較類似，在面對(duì)突然激增的流量的時(shí)候，通過漏桶算法可以做到勻速排隊(duì)，固定速度限流。

漏桶算法的優(yōu)勢(shì)是勻速，勻速是優(yōu)點(diǎn)也是缺點(diǎn)，很多人說漏桶不能處理突增流量，這個(gè)說法并不準(zhǔn)確。

漏桶本來就應(yīng)該是為了處理間歇性的突增流量，流量一下起來了，然后系統(tǒng)處理不過來，可以在空閑的時(shí)候去處理，防止了突增流量導(dǎo)致系統(tǒng)崩潰，保護(hù)了系統(tǒng)的穩(wěn)定性。

但是，換一個(gè)思路來想，其實(shí)這些突增的流量對(duì)于系統(tǒng)來說完全沒有壓力，你還在慢慢地勻速排隊(duì)，其實(shí)是對(duì)系統(tǒng)性能的浪費(fèi)。

所以，對(duì)于這種有場(chǎng)景來說，令牌桶算法比漏桶就更有優(yōu)勢(shì)。

令牌桶token bucket

令牌桶算法是指系統(tǒng)以一定地速度往令牌桶里丟令牌，當(dāng)一個(gè)請(qǐng)求過來的時(shí)候，會(huì)去令牌桶里申請(qǐng)一個(gè)令牌，如果能夠獲取到令牌，那么請(qǐng)求就可以正常進(jìn)行，反之被丟棄。

現(xiàn)在的令牌桶算法，像Guava和Sentinel的實(shí)現(xiàn)都有冷啟動(dòng)/預(yù)熱的方式，為了避免在流量激增的同時(shí)把系統(tǒng)打掛，令牌桶算法會(huì)在最開始一段時(shí)間內(nèi)冷啟動(dòng)，隨著流量的增加，系統(tǒng)會(huì)根據(jù)流量大小動(dòng)態(tài)地調(diào)整生成令牌的速度，最終直到請(qǐng)求達(dá)到系統(tǒng)的閾值。

源碼舉例

我們以sentinel舉例，sentinel中統(tǒng)計(jì)用到了滑動(dòng)窗口算法，然后也有用到漏桶、令牌桶算法。

滑動(dòng)窗口

sentinel中就使用到了滑動(dòng)窗口算法來進(jìn)行統(tǒng)計(jì)，不過他的實(shí)現(xiàn)和我上面畫的圖有點(diǎn)不一樣，實(shí)際上sentinel中的滑動(dòng)窗口用一個(gè)圓形來描述更合理一點(diǎn)。

前期就是創(chuàng)建節(jié)點(diǎn)，然后slot串起來就是一個(gè)責(zé)任鏈模式，StatisticSlot通過滑動(dòng)窗口來統(tǒng)計(jì)數(shù)據(jù)，F(xiàn)lowSlot是真正限流的邏輯，還有一些降級(jí)、系統(tǒng)保護(hù)的措施，最終形成了整個(gè)sentinel的限流方式。

就看看官方圖吧，這圓形畫起來好惡心

<figcaption style="margin-top: 5px; text-align: center; color: #888; font-size: 12px;">就看看官方圖吧，這圓形畫起來好惡心</figcaption>

滑動(dòng)窗口的實(shí)現(xiàn)主要可以看LeapArray的代碼，默認(rèn)的話定義了時(shí)間窗口的相關(guān)參數(shù)。

對(duì)于sentinel來說其實(shí)窗口分為秒和分鐘兩個(gè)級(jí)別，秒的話窗口數(shù)量是2，分鐘則是60個(gè)窗口，每個(gè)窗口的時(shí)間長(zhǎng)度是1s，總的時(shí)間周期就是60s，分成60個(gè)窗口，這里我們就以分鐘級(jí)別的統(tǒng)計(jì)來說。

<pre class="custom" data-tool="mdnice編輯器" style="margin-top: 10px; margin-bottom: 10px; box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px; max-width: 100%; border-radius: 4px; margin: 10px auto 0 auto;">public abstract class LeapArray<T> { //窗口時(shí)間長(zhǎng)度，毫秒數(shù)，默認(rèn)1000ms protected int windowLengthInMs; //窗口數(shù)量，默認(rèn)60 protected int sampleCount; //毫秒時(shí)間周期，默認(rèn)60*1000 protected int intervalInMs; //秒級(jí)時(shí)間周期，默認(rèn)60 private double intervalInSecond; //時(shí)間窗口數(shù)組 protected final AtomicReferenceArray<WindowWrap<T>> array; </pre>

然后我們要看的就是它是怎么計(jì)算出當(dāng)前窗口的，其實(shí)源碼里寫的聽清楚的，但是如果你按照之前想象把他當(dāng)做一條直線延伸去想的話估計(jì)不太好理解。

首先計(jì)算數(shù)組索引下標(biāo)和時(shí)間窗口時(shí)間這個(gè)都比較簡(jiǎn)單，難點(diǎn)應(yīng)該大部分在于第三點(diǎn)窗口大于old這個(gè)是什么鬼，詳細(xì)說下這幾種情況。

1. 數(shù)組中的時(shí)間窗口是是空的，這個(gè)說明時(shí)間走到了我們初始化的時(shí)間之后了，此時(shí)new一個(gè)新的窗口通過CAS的方式去更新，然后返回這個(gè)新的窗口就好了。
2. 第二種情況是剛好時(shí)間窗口的時(shí)間相等，那么直接返回，沒啥好說的
3. 第三種情況就是比較難以理解的，可以參看兩條時(shí)間線的圖，就比較好理解了，第一次時(shí)間窗口走完了達(dá)到1200，然后圓形時(shí)間窗口開始循環(huán)，新的時(shí)間起始位置還是1200，然后時(shí)間窗口的時(shí)間來到1676，B2的位置如果還是老的窗口那么就是600，所以我們要重置之前的時(shí)間窗口的時(shí)間為當(dāng)前的時(shí)間。
4. 最后一種一般情況不太可能發(fā)生，除非時(shí)鐘回?fù)苓@樣子

從這個(gè)我們可以發(fā)現(xiàn)就是針對(duì)每個(gè)WindowWrap時(shí)間窗口都進(jìn)行了統(tǒng)計(jì)，最后實(shí)際上在后面的幾個(gè)地方都會(huì)用到時(shí)間窗口統(tǒng)計(jì)的QPS結(jié)果，這里就不再贅述了，知道即可。

<pre class="custom" data-tool="mdnice編輯器" style="margin-top: 10px; margin-bottom: 10px; box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px; max-width: 100%; border-radius: 4px; margin: 10px auto 0 auto;">`private int calculateTimeIdx(/@Valid/ long timeMillis) {
long timeId = timeMillis / windowLengthInMs;
// Calculate current index so we can map the timestamp to the leap array.
return (int) (timeId % array.length());
}

protected long calculateWindowStart(/@Valid/ long timeMillis) {
return timeMillis - timeMillis % windowLengthInMs;
}

public WindowWrap<T> currentWindow(long timeMillis) {
//當(dāng)前時(shí)間如果小于0，返回空
if (timeMillis < 0) {
return null;
}
//計(jì)算時(shí)間窗口的索引
int idx = calculateTimeIdx(timeMillis);
// 計(jì)算當(dāng)前時(shí)間窗口的開始時(shí)間
long windowStart = calculateWindowStart(timeMillis);

while (true) {
    //在窗口數(shù)組中獲得窗口
    WindowWrap<T> old = array.get(idx);
    if (old == null) {
        /*
         *     B0       B1      B2    NULL      B4
         * ||_______|_______|_______|_______|_______||___
         * 200     400     600     800     1000    1200  timestamp
         *                             ^
         *                          time=888
         * 比如當(dāng)前時(shí)間是888，根據(jù)計(jì)算得到的數(shù)組窗口位置是個(gè)空，所以直接創(chuàng)建一個(gè)新窗口就好了
         */
        WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
        if (array.compareAndSet(idx, null, window)) {
            // Successfully updated, return the created bucket.
            return window;
        } else {
            // Contention failed, the thread will yield its time slice to wait for bucket available.
            Thread.yield();
        }
    } else if (windowStart == old.windowStart()) {
        /*
         *     B0       B1      B2     B3      B4
         * ||_______|_______|_______|_______|_______||___
         * 200     400     600     800     1000    1200  timestamp
         *                             ^
         *                          time=888
         * 這個(gè)更好了，剛好等于，直接返回就行
         */
        return old;
    } else if (windowStart > old.windowStart()) {
        /*
         *     B0       B1      B2     B3      B4
         * |_______|_______|_______|_______|_______||___
         * 200     400     600     800     1000    1200  timestamp
         *             B0       B1      B2    NULL      B4
         * |_______||_______|_______|_______|_______|_______||___
         * ...    1200     1400    1600    1800    2000    2200  timestamp
         *                              ^
         *                           time=1676
         * 這個(gè)要當(dāng)成圓形理解就好了，之前如果是1200一個(gè)完整的圓形，然后繼續(xù)從1200開始，如果現(xiàn)在時(shí)間是1676，落在在B2的位置，
         * 窗口開始時(shí)間是1600，獲取到的old時(shí)間其實(shí)會(huì)是600，所以肯定是過期了，直接重置窗口就可以了
         */
        if (updateLock.tryLock()) {
            try {
                // Successfully get the update lock, now we reset the bucket.
                return resetWindowTo(old, windowStart);
            } finally {
                updateLock.unlock();
            }
        } else {
            Thread.yield();
        }
    } else if (windowStart < old.windowStart()) {
        // 這個(gè)不太可能出現(xiàn)，嗯。。時(shí)鐘回?fù)?        return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
    }
}

}` </pre>

漏桶

sentinel主要根據(jù)FlowSlot中的流控進(jìn)行流量控制，其中RateLimiterController就是漏桶算法的實(shí)現(xiàn)，這個(gè)實(shí)現(xiàn)相比其他幾個(gè)還是簡(jiǎn)單多了，稍微看一下應(yīng)該就明白了。

1. 首先計(jì)算出當(dāng)前請(qǐng)求平攤到1s內(nèi)的時(shí)間花費(fèi)，然后去計(jì)算這一次請(qǐng)求預(yù)計(jì)時(shí)間
2. 如果小于當(dāng)前時(shí)間的話，那么以當(dāng)前時(shí)間為主，返回即可
3. 反之如果超過當(dāng)前時(shí)間的話，這時(shí)候就要進(jìn)行排隊(duì)等待了，等待的時(shí)候要判斷是否超過當(dāng)前最大的等待時(shí)間，超過就直接丟棄
4. 沒有超過就更新上一次的通過時(shí)間，然后再比較一次是否超時(shí)，還超時(shí)就重置時(shí)間，反之在等待時(shí)間范圍之內(nèi)的話就等待，如果都不是那就可以通過了

<pre class="custom" data-tool="mdnice編輯器" style="margin-top: 10px; margin-bottom: 10px; box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px; max-width: 100%; border-radius: 4px; margin: 10px auto 0 auto;">`public class RateLimiterController implements TrafficShapingController {
//最大等待超時(shí)時(shí)間，默認(rèn)500ms
private final int maxQueueingTimeMs;
//限流數(shù)量
private final double count;
//上一次的通過時(shí)間
private final AtomicLong latestPassedTime = new AtomicLong(-1);

@Override
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
// Pass when acquire count is less or equal than 0.
if (acquireCount <= 0) {
return true;
}
// Reject when count is less or equal than 0.
// Otherwise,the costTime will be max of long and waitTime will overflow in some cases.
if (count <= 0) {
return false;
}

  long currentTime = TimeUtil.currentTimeMillis();
  //時(shí)間平攤到1s內(nèi)的花費(fèi)
  long costTime = Math.round(1.0 * (acquireCount) / count * 1000); // 1 / 100 * 1000 = 10ms

  //計(jì)算這一次請(qǐng)求預(yù)計(jì)的時(shí)間
  long expectedTime = costTime + latestPassedTime.get();

  //花費(fèi)時(shí)間小于當(dāng)前時(shí)間，pass，最后通過時(shí)間 = 當(dāng)前時(shí)間
  if (expectedTime <= currentTime) {
      latestPassedTime.set(currentTime);
      return true;
  } else {
      //預(yù)計(jì)通過的時(shí)間超過當(dāng)前時(shí)間，要進(jìn)行排隊(duì)等待，重新獲取一下，避免出現(xiàn)問題，差額就是需要等待的時(shí)間
      long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis();
      //等待時(shí)間超過最大等待時(shí)間，丟棄
      if (waitTime > maxQueueingTimeMs) {
          return false;
      } else {
          //反之，可以更新最后一次通過時(shí)間了
          long oldTime = latestPassedTime.addAndGet(costTime);
          try {
              waitTime = oldTime - TimeUtil.currentTimeMillis();
              //更新后再判斷，還是超過最大超時(shí)時(shí)間，那么就丟棄，時(shí)間重置
              if (waitTime > maxQueueingTimeMs) {
                  latestPassedTime.addAndGet(-costTime);
                  return false;
              }
              //在時(shí)間范圍之內(nèi)的話，就等待
              if (waitTime > 0) {
                  Thread.sleep(waitTime);
              }
              return true;
          } catch (InterruptedException e) {
          }
      }
  }
  return false;

}

}` </pre>

令牌桶

最后是令牌桶，這個(gè)不在于實(shí)現(xiàn)的復(fù)制，而是你看源碼會(huì)發(fā)現(xiàn)都算的些啥玩意兒。。。sentinel的令牌桶實(shí)現(xiàn)基于Guava，代碼在WarmUpController中。

這個(gè)算法那些各種計(jì)算邏輯其實(shí)我們可以不管（因?yàn)槲乙矝]看懂。。），但是流程上我們是清晰的就可以了。

幾個(gè)核心的參數(shù)看注釋，構(gòu)造方法里那些計(jì)算邏輯暫時(shí)不管他是怎么算的（我也沒整明白，但是不影響我們理解），關(guān)鍵看canPass是怎么做的。

1. 拿到當(dāng)前窗口和上一個(gè)窗口的QPS
2. 填充令牌，也就是往桶里丟令牌，然后我們先看填充令牌的邏輯

<pre class="custom" data-tool="mdnice編輯器" style="margin-top: 10px; margin-bottom: 10px; box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px; max-width: 100%; border-radius: 4px; margin: 10px auto 0 auto;">`public class WarmUpController implements TrafficShapingController {
//限流QPS
protected double count;
//冷啟動(dòng)系數(shù)，默認(rèn)=3
private int coldFactor;
//警戒的令牌數(shù)
protected int warningToken = 0;
//最大令牌數(shù)
private int maxToken;
//斜率，產(chǎn)生令牌的速度
protected double slope;

//存儲(chǔ)的令牌數(shù)量
protected AtomicLong storedTokens = new AtomicLong(0);
//最后一次填充令牌時(shí)間
protected AtomicLong lastFilledTime = new AtomicLong(0);

public WarmUpController(double count, int warmUpPeriodInSec, int coldFactor) {
    construct(count, warmUpPeriodInSec, coldFactor);
}

public WarmUpController(double count, int warmUpPeriodInSec) {
    construct(count, warmUpPeriodInSec, 3);
}

private void construct(double count, int warmUpPeriodInSec, int coldFactor) {
    if (coldFactor <= 1) {
        throw new IllegalArgumentException("Cold factor should be larger than 1");
    }
    this.count = count;
    this.coldFactor = coldFactor;

    //stableInterval 穩(wěn)定產(chǎn)生令牌的時(shí)間周期，1/QPS
    //warmUpPeriodInSec 預(yù)熱/冷啟動(dòng)時(shí)間 ,默認(rèn) 10s
    warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1);
    maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor));
//斜率的計(jì)算參考Guava，當(dāng)做一個(gè)固定改的公式
    slope = (coldFactor - 1.0) / count / (maxToken - warningToken);
}

@Override
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
    //當(dāng)前時(shí)間窗口通過的QPS
    long passQps = (long) node.passQps();
    //上一個(gè)時(shí)間窗口QPS
    long previousQps = (long) node.previousPassQps();
    //填充令牌
    syncToken(previousQps);

    // 開始計(jì)算它的斜率
    // 如果進(jìn)入了警戒線，開始調(diào)整他的qps
    long restToken = storedTokens.get();
    if (restToken >= warningToken) {
        //當(dāng)前的令牌超過警戒線，獲得超過警戒線的令牌數(shù)
        long aboveToken = restToken - warningToken;
        // 消耗的速度要比warning快，但是要比慢
        // current interval = restToken*slope+1/count
        double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count));
        if (passQps + acquireCount <= warningQps) {
            return true;
        }
    } else {
        if (passQps + acquireCount <= count) {
            return true;
        }
    }

    return false;
}

}` </pre>

填充令牌的邏輯如下：

1. 拿到當(dāng)前的時(shí)間，然后去掉毫秒數(shù)，得到的就是秒級(jí)時(shí)間
2. 判斷時(shí)間小于這里就是為了控制每秒丟一次令牌
3. 然后就是coolDownTokens去計(jì)算我們的冷啟動(dòng)/預(yù)熱是怎么計(jì)算填充令牌的
4. 后面計(jì)算當(dāng)前剩下的令牌數(shù)這個(gè)就不說了，減去上一次消耗的就是桶里剩下的令牌

<pre class="custom" data-tool="mdnice編輯器" style="margin-top: 10px; margin-bottom: 10px; box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px; max-width: 100%; border-radius: 4px; margin: 10px auto 0 auto;">`protected void syncToken(long passQps) {
long currentTime = TimeUtil.currentTimeMillis();
//去掉當(dāng)前時(shí)間的毫秒
currentTime = currentTime - currentTime % 1000;
long oldLastFillTime = lastFilledTime.get();
//控制每秒填充一次令牌
if (currentTime <= oldLastFillTime) {
return;
}
//當(dāng)前的令牌數(shù)量
long oldValue = storedTokens.get();
//獲取新的令牌數(shù)量，包含添加令牌的邏輯，這就是預(yù)熱的邏輯
long newValue = coolDownTokens(currentTime, passQps);
if (storedTokens.compareAndSet(oldValue, newValue)) {
//存儲(chǔ)的令牌數(shù)量當(dāng)然要減去上一次消耗的令牌
long currentValue = storedTokens.addAndGet(0 - passQps);
if (currentValue < 0) {
storedTokens.set(0L);
}
lastFilledTime.set(currentTime);
}

}` </pre>

1. 最開始的事實(shí)因?yàn)?code>lastFilledTime和oldValue都是0，所以根據(jù)當(dāng)前時(shí)間戳?xí)玫揭粋€(gè)非常大的數(shù)字，最后和maxToken取小的話就得到了最大的令牌數(shù)，所以第一次初始化的時(shí)候就會(huì)生成maxToken的令牌
2. 之后我們假設(shè)系統(tǒng)的QPS一開始很低，然后突然飆高。所以開始的時(shí)候回一直走到高于警戒線的邏輯里去，然后passQps又很低，所以會(huì)一直處于把令牌桶填滿的狀態(tài)（currentTime - lastFilledTime.get()會(huì)一直都是1000，也就是1秒），所以每次都會(huì)填充最大QPScount數(shù)量的令牌
3. 然后突增流量來了，QPS瞬間很高，慢慢地令牌數(shù)量就會(huì)消耗到警戒線之下，走到我們if的邏輯里去，然后去按照count數(shù)量增加令牌

<pre class="custom" data-tool="mdnice編輯器" style="margin-top: 10px; margin-bottom: 10px; box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px; max-width: 100%; border-radius: 4px; margin: 10px auto 0 auto;">`private long coolDownTokens(long currentTime, long passQps) {
long oldValue = storedTokens.get();
long newValue = oldValue;

//水位低于警戒線，就生成令牌
if (oldValue < warningToken) {
//如果桶中令牌低于警戒線，根據(jù)上一次的時(shí)間差，得到新的令牌數(shù)，因?yàn)槿サ袅撕撩耄?秒生成的令牌就是閾值count
//第一次都是0的話，會(huì)生成count數(shù)量的令牌
newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
} else if (oldValue > warningToken) {
//反之，如果是高于警戒線，要判斷QPS。因?yàn)镼PS越高，生成令牌就要越慢，QPS低的話生成令牌要越快
if (passQps < (int)count / coldFactor) {
newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
}
}
//不要超過最大令牌數(shù)
return Math.min(newValue, maxToken);
}` </pre>

上面的邏輯理順之后，我們就可以繼續(xù)看限流的部分邏輯：

1. 令牌計(jì)算的邏輯完成，然后判斷是不是超過警戒線，按照上面的說法，低QPS的狀態(tài)肯定是一直超過的，所以會(huì)根據(jù)斜率來計(jì)算出一個(gè)warningQps，因?yàn)槲覀兲幱诶鋯?dòng)的狀態(tài)，所以這個(gè)階段就是要根據(jù)斜率來計(jì)算出一個(gè)QPS數(shù)量，讓流量慢慢地達(dá)到系統(tǒng)能承受的峰值。舉個(gè)例子，如果count是100，那么在QPS很低的情況下，令牌桶一直處于滿狀態(tài)，但是系統(tǒng)會(huì)控制QPS，實(shí)際通過的QPS就是warningQps，根據(jù)算法可能只有10或者20（怎么算的不影響理解）。QPS主鍵提高的時(shí)候，aboveToken再逐漸變小，整個(gè)warningQps就在逐漸變大，直到走到警戒線之下，到了else邏輯里。
2. 流量突增的情況，就是else邏輯里低于警戒線的情況，我們令牌桶在不停地根據(jù)count去增加令牌，這時(shí)候消耗令牌的速度超過我們生成令牌的速度，可能就會(huì)導(dǎo)致一直處于警戒線之下，這時(shí)候判斷當(dāng)然就需要根據(jù)最高QPS去判斷限流了。

<pre class="custom" data-tool="mdnice編輯器" style="margin-top: 10px; margin-bottom: 10px; box-shadow: rgba(170, 170, 170, 0.48) 0px 0px 6px 0px; max-width: 100%; border-radius: 4px; margin: 10px auto 0 auto;">long restToken = storedTokens.get(); if (restToken >= warningToken) { //當(dāng)前的令牌超過警戒線，獲得超過警戒線的令牌數(shù) long aboveToken = restToken - warningToken; // 消耗的速度要比warning快，但是要比慢 // current interval = restToken*slope+1/count double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count)); if (passQps + acquireCount <= warningQps) { return true; } } else { if (passQps + acquireCount <= count) { return true; } } </pre>

所以，按照低QPS到突增高QPS的流程，來想象一下這個(gè)過程：

1. 剛開始，系統(tǒng)的QPS非常低，初始化我們就直接把令牌桶塞滿了
2. 然后這個(gè)低QPS的狀態(tài)持續(xù)了一段時(shí)間，因?yàn)槲覀円恢睍?huì)填充最大QPS數(shù)量的令牌（因?yàn)槿∽钚≈?，所以其?shí)桶里令牌基本不會(huì)有變化），所以令牌桶一直處于滿的狀態(tài)，整個(gè)系統(tǒng)的限流也處于一個(gè)比較低的水平

這以上的部分一直處于警戒線之上，實(shí)際上就是叫做冷啟動(dòng)/預(yù)熱的過程。

3. 接著系統(tǒng)的QPS突然激增，令牌消耗速度太快，就算我們每次增加最大QPS數(shù)量的令牌任然無法維持消耗，所以桶里的令牌在不斷低減少，這個(gè)時(shí)候，冷啟動(dòng)階段的限制QPS也在不斷地提高，最后直到桶里的令牌低于警戒線
4. 低于警戒線之后，系統(tǒng)就會(huì)按照最高QPS去限流，這個(gè)過程就是系統(tǒng)在逐漸達(dá)到最高限流的過程

那這樣一來，實(shí)際就達(dá)到了我們處理突增流量的目的，整個(gè)系統(tǒng)在漫漫地適應(yīng)突然飆高的QPS，然后最終達(dá)到系統(tǒng)的QPS閾值。

5. 最后，如果QPS回復(fù)正常，那么又會(huì)逐漸回到警戒線之上，就回到了最開始的過程。

image

總結(jié)

因?yàn)樗惴ㄈ绻麊为?dú)說的話都比較簡(jiǎn)單，一說大家都可以聽明白，不需要幾個(gè)字就能說明白，所以還是得弄點(diǎn)源碼看看別人是怎么玩的，所以盡管我很討厭放源碼，但是還是不得不干。

光靠別人說一點(diǎn)其實(shí)有點(diǎn)看不明白，按照順序讀一遍的話心里就有數(shù)了。

那源碼的話最難以理解的就是令牌桶的實(shí)現(xiàn)了，說實(shí)話那幾個(gè)計(jì)算的邏輯我看了好幾遍不知道他算的什么鬼，但是思想我們理解就行了，其他的邏輯相對(duì)來說就比較容易理解。