這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)如何進(jìn)行限流器及Guava實(shí)現(xiàn)分析，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

創(chuàng)新互聯(lián)公司從2013年創(chuàng)立，先為銅川等服務(wù)建站，銅川等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為銅川企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

限流

限流一詞常用于計(jì)算機(jī)網(wǎng)絡(luò)之中，定義如下：

In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks.

通過控制數(shù)據(jù)的網(wǎng)絡(luò)數(shù)據(jù)的發(fā)送或接收速率來防止可能出現(xiàn)的DOS攻擊。而實(shí)際的軟件服務(wù)過程中，限流也可用于API服務(wù)的保護(hù)。由于提供服務(wù)的計(jì)算機(jī)資源(包括CPU、內(nèi)存、磁盤及網(wǎng)絡(luò)帶寬等)是有限的，則其提供的API服務(wù)的QPS也是有限的，限流工具就是通過限流算法對(duì)API訪問進(jìn)行限制，保證服務(wù)不會(huì)超過其能承受的負(fù)載壓力。
本文主要涉及內(nèi)容包括：

• 常用限流算法的簡(jiǎn)單介紹及比較

• Guava包中限流工具的實(shí)現(xiàn)分析

<!-- more -->

常用限流算法

援引wiki中關(guān)于限流的Algorithms一小節(jié)的說明，常用的限流算法主要包括：

1. Token bucket-令牌桶

2. Leaky bucket-漏桶

3. Fixed window counter-固定窗口計(jì)數(shù)

4. Sliding window log-滑動(dòng)窗口日志

5. Sliding window counter-滑動(dòng)窗口計(jì)數(shù)

以上幾種方式其實(shí)可以簡(jiǎn)單的分為計(jì)數(shù)算法、漏桶算法和令牌桶算法。

計(jì)數(shù)限流算法

無論固定窗口還是滑動(dòng)窗口核心均是對(duì)請(qǐng)求進(jìn)行計(jì)數(shù)，區(qū)別僅僅在于對(duì)于計(jì)數(shù)時(shí)間區(qū)間的處理。

固定窗口計(jì)數(shù)

實(shí)現(xiàn)原理

固定窗口計(jì)數(shù)法思想比較簡(jiǎn)單，只需要確定兩個(gè)參數(shù)：計(jì)數(shù)周期T及周期內(nèi)最大訪問（調(diào)用）數(shù)N。請(qǐng)求到達(dá)時(shí)使用以下流程進(jìn)行操作：

固定窗口計(jì)數(shù)實(shí)現(xiàn)簡(jiǎn)單，并且只需要記錄上一個(gè)周期起始時(shí)間與周期內(nèi)訪問總數(shù)，幾乎不消耗額外的存儲(chǔ)空間。

算法缺陷

固定窗口計(jì)數(shù)缺點(diǎn)也非常明顯，在進(jìn)行周期切換時(shí)，上一個(gè)周期的訪問總數(shù)會(huì)立即置為0，這可能導(dǎo)致在進(jìn)行周期切換時(shí)可能出現(xiàn)流量突發(fā)，如下圖所示

滑動(dòng)窗口計(jì)數(shù)在固定窗口計(jì)數(shù)記錄數(shù)據(jù)基礎(chǔ)上，需要增加一個(gè)長(zhǎng)度為M的計(jì)數(shù)數(shù)組，用于記錄在窗口滑動(dòng)過程中各窗口訪問數(shù)據(jù)。其流程示例如下：
簡(jiǎn)單說明為：人為設(shè)定漏桶流出速度及漏桶的總?cè)萘浚谡?qǐng)求到達(dá)時(shí)判斷當(dāng)前漏桶容量是否已滿，不滿則可將請(qǐng)求存入桶中，否則拋棄請(qǐng)求。程序以設(shè)定的速率取出請(qǐng)求進(jìn)行處理。
根據(jù)描述，需要確定參數(shù)為漏桶流出速度r及漏桶容量N，流程如下：

算法特點(diǎn)

令牌桶算法通過設(shè)置令牌放入速率可以控制請(qǐng)求通過的平均速度，且由于設(shè)置的容量為N的桶對(duì)令牌進(jìn)行緩存，可以容忍一定流量的突發(fā)。

算法比較

以上提到四種算法，本小節(jié)主要對(duì)四種算法做簡(jiǎn)單比較算法進(jìn)行對(duì)比。

<style>
table th {

width: 100px;

}
</style>

算法名稱	需要確定參數(shù)	實(shí)現(xiàn)簡(jiǎn)介	空間復(fù)雜度	說明
固定窗口計(jì)數(shù)	計(jì)數(shù)周期T 周期內(nèi)最大訪問數(shù)N	使用計(jì)數(shù)器在周期內(nèi)累加訪問次數(shù)，達(dá)到最大次數(shù)后出發(fā)限流策略	O(1)，僅需要記錄周期內(nèi)訪問次數(shù)及周期開始時(shí)間	周期切換時(shí)可能出現(xiàn)訪問次數(shù)超過限定值
滑動(dòng)窗口計(jì)數(shù)	計(jì)數(shù)周期T 周期內(nèi)最大訪問數(shù)N 滑動(dòng)窗口數(shù)M	將時(shí)間周期分為M個(gè)小周期，分別記錄每個(gè)小周期內(nèi)訪問次數(shù)，并且根據(jù)時(shí)間滑動(dòng)刪除過期的小周期	O(M)，需要記錄每個(gè)小周期中的訪問數(shù)量	解決固定窗口算法周期切換時(shí)的訪問突發(fā)問題
漏桶算法	漏桶流出速度r 漏桶容量N	服務(wù)到達(dá)時(shí)直接放入漏桶，如當(dāng)前容量達(dá)到N，則觸發(fā)限流側(cè)率，程序以r的速度在漏桶中獲取訪問請(qǐng)求，知道漏桶為空	O(1)，僅需要記錄當(dāng)前漏桶中容量	平滑流量，保證服務(wù)請(qǐng)求到達(dá)服務(wù)方的速度恒定
令牌桶算法	令牌產(chǎn)生速度r 令牌桶容量N	程序以r的速度向令牌桶中增加令牌，直到令牌桶滿，請(qǐng)求到達(dá)時(shí)向令牌桶請(qǐng)求令牌，如有滿足需求的令牌則通過請(qǐng)求，否則觸發(fā)限流策略	O(1)，僅需要記錄當(dāng)前令牌桶中令牌數(shù)	能夠在限流的基礎(chǔ)上，處理一定量的突發(fā)請(qǐng)求

Guava包中限流工具的實(shí)現(xiàn)分析

概覽

上文簡(jiǎn)單介紹了常用的限流算法，在JAVA軟件開發(fā)過程中可使用Guava包中的限流工具進(jìn)行服務(wù)限流。Guava包中限流工具類圖如下所示：
RateLimiter類即承擔(dān)了builder的職責(zé)，也承擔(dān)了Product的職責(zé)。

簡(jiǎn)單使用示例

在實(shí)際的代碼編寫過程中，對(duì)GUAVA包限流工具的使用參考以下代碼：

final RateLimiter rateLimiter = RateLimiter.create(2.0); // rate is "2 permits per second"
void submitTasks(List<Runnable> tasks, Executor executor) {
  for (Runnable task : tasks) {
    rateLimiter.acquire(); // may wait
    executor.execute(task);
  }
}

以上代碼摘自GUAVA包RateLimiter類的說明文檔，首先使用create函數(shù)創(chuàng)建限流器，指定每秒生成2個(gè)令牌，在需要調(diào)用服務(wù)時(shí)使用acquire函數(shù)或取令牌。

RateLimiter實(shí)現(xiàn)分析

根據(jù)代碼示例，抽象類RateLimiter由于承擔(dān)了Product的職責(zé)，其已經(jīng)確定了暴露給編程人員使用的API函數(shù)，其中主要實(shí)現(xiàn)的核心函數(shù)為create及acquire。因此由此為入口進(jìn)行分析。

create函數(shù)分析

create函數(shù)具有兩個(gè)個(gè)重載，根據(jù)不同的重載可能創(chuàng)建不同的RateLimiter具體實(shí)現(xiàn)子類。目前可返回的實(shí)現(xiàn)子類包括SmoothBursty及SmoothWarmingUp兩種，具體不同下文詳細(xì)分析。

acquire函數(shù)分析

acquire函數(shù)也具有兩個(gè)重載類，但分析過程僅僅需要關(guān)系具有整形參數(shù)的函數(shù)重載即可，無參數(shù)的函數(shù)僅僅是acquire(1)的簡(jiǎn)便寫法。
在acquire(int permits)函數(shù)中主要完成三件事：

1. 預(yù)分配授權(quán)數(shù)量，此函數(shù)返回需要等待的時(shí)間，可能為0；

2. 根據(jù)等待時(shí)間進(jìn)行休眠；

3. 以秒為單位，返回獲取授權(quán)消耗的時(shí)間。

完成以上工作的過程中，RateLimiter類確定了獲取授權(quán)的過程骨架并且實(shí)現(xiàn)了一些通用的方法，這些通用方法中會(huì)調(diào)用為實(shí)現(xiàn)的抽象方法，開發(fā)人員根據(jù)不同的算法需求可實(shí)現(xiàn)特定子類對(duì)抽象方法進(jìn)行覆蓋。其調(diào)用流程如下圖：
其中橙色塊中reserveEarliestAvailable方法即為需要子類進(jìn)行實(shí)現(xiàn)的，下文以該函數(shù)為核心，分析RateLimiter類的子類是如何實(shí)現(xiàn)該方法的。

子類實(shí)現(xiàn)分析

代碼分析

根據(jù)上文的類圖可見，RateLimiter類在GUAVA包中的直接子類僅有SmoothRateLimiter，故以reserveEarliestAvailable函數(shù)為入口研究其具體實(shí)現(xiàn)，而在代碼實(shí)現(xiàn)的過程中需要使用SmoothRateLimiter類中的屬性，現(xiàn)將類中各屬性羅列出來：

序號(hào)	屬性名稱	屬性說明	是否為靜態(tài)屬性
1	storedPermits	當(dāng)前令牌桶中令牌數(shù)	否
2	maxPermits	令牌桶中最大令牌數(shù)	否
3	stableIntervalMicros	兩個(gè)令牌產(chǎn)生的時(shí)間間隔	否
4	nextFreeTicketMicros	下一次有空閑令牌產(chǎn)生的時(shí)刻	否

reserveEarliestAvailable源碼如下：

@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;
}

通過reserveEarliestAvailable的函數(shù)名稱可以知道，該函數(shù)能夠返回令牌可用的最早時(shí)間。函數(shù)需要的輸入?yún)?shù)有需求的令牌數(shù)requiredPermits，當(dāng)前時(shí)刻nowMicros。進(jìn)入函數(shù)后，首先調(diào)用名為resync的函數(shù)：

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;
  }
}

函數(shù)邏輯比較簡(jiǎn)單，首先獲取nextFreeTicketMicros，該值在上表中已經(jīng)說明，表示下一次有空閑令牌產(chǎn)生的時(shí)刻，如果當(dāng)前時(shí)刻小于等于nextFreeTicketMicros，說明在當(dāng)前時(shí)刻不可能有新的令牌產(chǎn)生，則直接返回。若當(dāng)前時(shí)刻大于nextFreeTicketMicros，則完成以下工作：

1. 計(jì)算到當(dāng)前時(shí)刻新產(chǎn)生的令牌數(shù)，其中涉及一個(gè)名為coolDownIntervalMicros 的函數(shù)，該函數(shù)返回創(chuàng)建一個(gè)新令牌需要的冷卻時(shí)間（注：該函數(shù)在當(dāng)前類中并未實(shí)現(xiàn)，具體實(shí)現(xiàn)下文說明）；

2. 更新storedPermits屬性，取產(chǎn)生的令牌和最大可存儲(chǔ)令牌之間的最小值；

3. 將nextFreeTicketMicros屬性置為當(dāng)前時(shí)刻。

可見，resync函數(shù)主要功能在于計(jì)算新產(chǎn)生的令牌數(shù)，并更新nextFreeTicketMicros屬性，nextFreeTicketMicros屬性取值是當(dāng)前時(shí)刻和nextFreeTicketMicros屬性的原始值中最大的一個(gè)。
完成resync函數(shù)的調(diào)用后，使用returnValue變量記錄更新令牌后的最近可用時(shí)間（即上文更新后的nextFreeTicketMicros屬性）。
使用storedPermitsToSpend變量記錄需要消耗以存儲(chǔ)的令牌數(shù)，其取值為請(qǐng)求令牌數(shù)和當(dāng)前存儲(chǔ)令牌數(shù)之間的最小值。
使用freshPermits變量記錄需要刷新的令牌數(shù)，其實(shí)現(xiàn)是用需求的令牌數(shù)減去之前計(jì)算的storedPermitsToSpend變量，可見freshPermits變量取值為需求令牌數(shù)與已存儲(chǔ)令牌數(shù)之間的差值，當(dāng)需求令牌數(shù)小于已存儲(chǔ)令牌數(shù)是則為0。
后續(xù)為該函數(shù)核心，計(jì)算需要等待的時(shí)間，計(jì)算等待時(shí)間主要分為兩個(gè)部分：消耗已經(jīng)存儲(chǔ)的令牌需要的時(shí)間及生成新令牌的時(shí)間，其中storedPermitsToWaitTime函數(shù)用于計(jì)算消耗已經(jīng)存儲(chǔ)的令牌需要的時(shí)間，該函數(shù)也是抽象函數(shù)，后文具體分析子類實(shí)現(xiàn)。
完成等待時(shí)間的計(jì)算后，程序更新nextFreeTicketMicros屬性，將最近可用時(shí)間與需要等待的時(shí)間相加。
最后在更新存儲(chǔ)的令牌數(shù)，將需要消耗額令牌數(shù)減去。

實(shí)現(xiàn)邏輯特點(diǎn)

根據(jù)以上的代碼分析可以發(fā)現(xiàn)，GUAVA對(duì)于令牌桶的實(shí)現(xiàn)跟理論有一點(diǎn)點(diǎn)小的區(qū)別。其當(dāng)前一次的請(qǐng)求消耗的令牌數(shù)并不會(huì)影響本次請(qǐng)求的等待時(shí)間，而是會(huì)影響下一次請(qǐng)求的等待時(shí)間。
根據(jù)以上分析，當(dāng)一次請(qǐng)求到達(dá)，最近可用時(shí)間返回當(dāng)前時(shí)間和上一次請(qǐng)求計(jì)算的最近可用時(shí)間的最大值，而本次請(qǐng)求需要的令牌數(shù)會(huì)更新下一次的最近可用時(shí)間。在這樣的設(shè)計(jì)下，如果每秒產(chǎn)生一個(gè)令牌，第一請(qǐng)求需求10個(gè)令牌，則當(dāng)?shù)谝淮握?qǐng)求調(diào)用acquire方法時(shí)能夠立即返回，而下一次請(qǐng)求（無論需要多少令牌）均需要等待到第一個(gè)請(qǐng)求之后的10秒以后，第三次請(qǐng)求等待時(shí)間則取決于第二次需求了多少令牌。這也是函數(shù)名稱中“reserve”的含義。

抽象函數(shù)分析

在以上文代碼分析中出現(xiàn)了兩個(gè)抽象函數(shù)coolDownIntervalMicros及storedPermitsToWaitTime，現(xiàn)分析這兩個(gè)抽象函數(shù)。

coolDownIntervalMicros函數(shù)

coolDownIntervalMicros函數(shù)在代碼中已經(jīng)有說明：

Returns the number of microseconds during cool down that we have to wait to get a new permit.

主要含義為生成一個(gè)令牌需要消耗的時(shí)間，該函數(shù)主要應(yīng)用于計(jì)算當(dāng)前時(shí)間可產(chǎn)生的令牌數(shù)。根據(jù)上文的UML圖SmoothRateLimiter類有兩個(gè)子類SmoothBursty及SmoothWarmingUp。
SmoothBursty類中對(duì)于coolDownIntervalMicros函數(shù)的實(shí)現(xiàn)如下：

@Override
double coolDownIntervalMicros() {
  return stableIntervalMicros;
}

可見實(shí)現(xiàn)非常簡(jiǎn)單，僅僅只是返回stableIntervalMicros屬性，即產(chǎn)生兩個(gè)令牌需要的時(shí)間間隔。
SmoothWarmingUp類中對(duì)于coolDownIntervalMicros函數(shù)的實(shí)現(xiàn)如下：

@Override
double coolDownIntervalMicros() {
  return warmupPeriodMicros / maxPermits;
}

其中maxPermits屬性上文已經(jīng)出現(xiàn)過，表示當(dāng)前令牌桶的最大容量。warmupPeriodMicros屬性屬于SmoothWarmingUp類的特有屬性，表示令牌桶中令牌從0到maxPermits需要經(jīng)過的時(shí)間，故warmupPeriodMicros / maxPermits表示在令牌數(shù)量達(dá)到maxPermits之前的令牌產(chǎn)生時(shí)間間隔。

storedPermitsToWaitTime函數(shù)

storedPermitsToWaitTime函數(shù)在代碼中已經(jīng)有說明：

Translates a specified portion of our currently stored permits which we want to spend/acquire,
into a throttling time. Conceptually, this evaluates the integral of the underlying function we
use, for the range of [(storedPermits - permitsToTake), storedPermits]

主要表示消耗存儲(chǔ)在令牌桶中的令牌需要的時(shí)間。
SmoothBursty類中對(duì)于storedPermitsToWaitTime函數(shù)的實(shí)現(xiàn)如下：

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

直接返回0，表示消耗令牌不需要時(shí)間。
SmoothBursty類中對(duì)于storedPermitsToWaitTime函數(shù)的實(shí)現(xiàn)如下：

@Override
long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
  double availablePermitsAboveThreshold = storedPermits - thresholdPermits;
  long micros = 0;
  // measuring the integral on the right part of the function (the climbing line)
  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;
  }
  // measuring the integral on the left part of the function (the horizontal line)
  micros += (long) (stableIntervalMicros * permitsToTake);
  return micros;
}

實(shí)現(xiàn)較為復(fù)雜，其核心思想在于計(jì)算消耗當(dāng)前存儲(chǔ)令牌時(shí)需要根據(jù)預(yù)熱設(shè)置區(qū)別對(duì)待。其中涉及到新變量thresholdPermits，該變量為令牌閾值，當(dāng)當(dāng)前存儲(chǔ)的令牌數(shù)大于該值時(shí)，消耗(storedPermits-thresholdPermits)范圍的令牌需要有預(yù)熱的過程（即消耗每個(gè)令牌的間隔時(shí)間慢慢減小），而消耗0~thresholdPermits個(gè)數(shù)的以存儲(chǔ)令牌，每個(gè)令牌消耗時(shí)間為固定值，即stableIntervalMicros。
而thresholdPermits取值需要考慮預(yù)熱時(shí)間及令牌產(chǎn)生速度兩個(gè)屬性，即thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;。可見閾值為預(yù)熱時(shí)間中能夠產(chǎn)生的令牌數(shù)的一半，并且根據(jù)注釋計(jì)算消耗閾值以上的令牌的時(shí)間可以轉(zhuǎn)換為計(jì)算預(yù)熱圖的梯形面積（實(shí)際為積分），本處不詳細(xì)展開。
使用此種設(shè)計(jì)可以保證在上次請(qǐng)求間隔時(shí)間較長(zhǎng)時(shí)，令牌桶中存儲(chǔ)了較多的令牌，當(dāng)消耗這些令牌時(shí)，最開始的令牌消耗時(shí)間較長(zhǎng)，后續(xù)時(shí)間慢慢縮短直到達(dá)到stableIntervalMicros的狀態(tài)，產(chǎn)生預(yù)熱的效果。

GUAVA限流器實(shí)現(xiàn)總結(jié)

以上分析GUAVA限流器實(shí)現(xiàn)，其使用了兩個(gè)抽象類及兩個(gè)具體子類完成了限流器實(shí)現(xiàn)，其中使用頂層抽象類承擔(dān)了創(chuàng)建者角色，將所有子類進(jìn)行了透明化，減少了程序員在使用工具過程中需要了解的類的數(shù)量。
在實(shí)現(xiàn)限流器的過程中，基于令牌桶的思想，并且增加了帶有預(yù)熱器的令牌桶限流器實(shí)現(xiàn)。被限流的線程使用其自帶的SleepingStopwatch工具類，最終使用的是Thread.sleep(ms, ns);方法，而線程使用sleep休眠時(shí)其持有的鎖并不會(huì)釋放，在多線程編程時(shí)此處需要注意。
最后，GUAVA的限流器觸發(fā)算法采用的是預(yù)定令牌的方式，即當(dāng)前請(qǐng)求需要的令牌數(shù)不會(huì)對(duì)當(dāng)前請(qǐng)求的等待時(shí)間造成影響，而是會(huì)影響下一次請(qǐng)求的等待時(shí)間。

上述就是小編為大家分享的如何進(jìn)行限流器及Guava實(shí)現(xiàn)分析了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

文章標(biāo)題：如何進(jìn)行限流器及Guava實(shí)現(xiàn)分析
本文URL：http://www.chinadenli.net/article10/joipgo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、小程序開發(fā)、微信小程序、網(wǎng)站建設(shè)、做網(wǎng)站、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)