不同的場景下所需的流控算法不盡相同，那應(yīng)該如何選擇適用的流控方案呢?本文分享單機(jī)及分布式流控場景下，簡單窗口、滑動窗口、漏桶、令牌桶、滑動日志等幾種流控算法的思路和代碼實(shí)現(xiàn)，并總結(jié)了各自的復(fù)雜度和適用場景。較長，同學(xué)們可收藏后再看。

一 流控的場景

流控的意義其實(shí)無需多言了。最常用的場景下，流控是為了保護(hù)下游有限的資源不被流量沖垮，保證服務(wù)的可用性，一般允許流控的閾值有一定的彈性，偶爾的超量訪問是可以接受的。

有的時(shí)候，流控服務(wù)于收費(fèi)模式，比如某些云廠商會對調(diào)用 API 的頻次進(jìn)行計(jì)費(fèi)。既然涉及到錢，一般就不允許有超出閾值的調(diào)用量。

這些不同的場景下，適用的流控算法不盡相同。大多數(shù)情況下，使用 Sentinel 中間件已經(jīng)能很好地應(yīng)對，但 Sentinel 也并不是萬能的，需要思考其他的流控方案。

二 接口定義

為了方便，以下所有的示例代碼實(shí)現(xiàn)都是基于 Throttler 接口。

Throttler 接口定義了一個通用的方法用于申請單個配額。

當(dāng)然你也可以定義一個 tryAcquire(String key, int permits) 簽名的方法用于一次申請多個配額，實(shí)現(xiàn)的思路是一樣的。

有些流控算法需要為每個 key 維護(hù)一個 Throttler 實(shí)例。

public interface Throttler { 
     /** 
      * 嘗試申請一個配額 
      * 
      * @param key     申請配額的key 
      * @return 申請成功則返回true，否則返回false 
      */ 
     boolean tryAcquire(String key); 
 }

三 單機(jī)流控

1 簡單窗口

簡單窗口是我自己的命名，有些地方也叫做固定窗口，主要是為了跟后面的滑動窗口區(qū)分。

流控是為了限制指定時(shí)間間隔內(nèi)能夠允許的訪問量，因此，最直觀的思路就是基于一個給定的時(shí)間窗口，維護(hù)一個計(jì)數(shù)器用于統(tǒng)計(jì)訪問次數(shù)，然后實(shí)現(xiàn)以下規(guī)則：

• 如果訪問次數(shù)小于閾值，則代表允許訪問，訪問次數(shù) +1。
• 如果訪問次數(shù)超出閾值，則限制訪問，訪問次數(shù)不增。
• 如果超過了時(shí)間窗口，計(jì)數(shù)器清零，并重置清零后的首次成功訪問時(shí)間為當(dāng)前時(shí)間。這樣就確保計(jì)數(shù)器統(tǒng)計(jì)的是最近一個窗口的訪問量。

代碼實(shí)現(xiàn) SimpleWindowThrottler

/** 
  * 毫秒為單位的時(shí)間窗口 
  */ 
 private final long windowInMs; 
 /** 
  * 時(shí)間窗口內(nèi)最大允許的閾值 
  */ 
 private final int threshold; 
 /** 
  * 最后一次成功請求時(shí)間 
  */ 
 private long lastReqTime = System.currentTimeMillis(); 
 /** 
  * 計(jì)數(shù)器 
  */ 
 private long counter; 
  
 public boolean tryAcquire(String key) { 
     long now = System.currentTimeMillis(); 
     // 如果當(dāng)前時(shí)間已經(jīng)超過了上一次訪問時(shí)間開始的時(shí)間窗口，重置計(jì)數(shù)器，以當(dāng)前時(shí)間作為新窗口的起始值 
     if (now - lastReqTime > windowInMs) {       #1 
         counter = 0; 
         lastReqTime = now;                  #2 
     } 
     if (counter < threshold) {                  #3 
         counter++;                          #4 
         return true; 
     } else { 
         return false; 
     } 
 }

另外一種常見的場景是根據(jù)不同的 key 來做流控，每個 key 有單獨(dú)的時(shí)間窗口、閾值配置，因此需要為每個 key 維護(hù)一個單獨(dú)的限流器實(shí)例。

切換到多線程環(huán)境

在現(xiàn)實(shí)應(yīng)用中，往往是多個線程來同時(shí)申請配額，為了比較簡潔地表達(dá)算法思路，示例代碼里面都沒有做并發(fā)同步控制。

以簡單窗口的實(shí)現(xiàn)為例，要轉(zhuǎn)換為多線程安全的流控算法，一種直接的辦法是將 tryAcquire 方法設(shè)置為 synchronized。

當(dāng)然一種感覺上更高效的辦法也可以是修改讀寫變量的類型：

private volatile long lastReqTime = System.currentTimeMillis(); 
 private LongAdder counter = new LongAdder();

不過這樣其實(shí)并不真正“安全”，設(shè)想以下的場景，兩個線程 A、線程 B 前后腳嘗試獲取配額，#1 位置的判斷條件滿足后，會同時(shí)走到 #2 位置修改 lastReqTime 值，線程 B 的賦值會覆蓋線程 A，導(dǎo)致時(shí)間窗口起始點(diǎn)向后偏移。同樣的，位置 #3 和 #4 也會構(gòu)成競爭條件。當(dāng)然如果對流控的精度要求不高，這種競爭也是能接受的。

臨界突變問題

簡單窗口的流控實(shí)現(xiàn)非常簡單，以 1 分鐘允許 100 次訪問為例，如果流量均勻保持 200 次/分鐘的訪問速率，系統(tǒng)的訪問量曲線大概是這樣的(按分鐘清零)：

??

但如果流量并不均勻，假設(shè)在時(shí)間窗口開始時(shí)刻 0:00 有幾次零星的訪問，一直到 0:50 時(shí)刻，開始以 10 次/秒的速度請求，就會出現(xiàn)這樣的訪問量圖線：

??

在臨界的 20 秒內(nèi)(0:50~1:10)系統(tǒng)承受的實(shí)際訪問量是 200 次，換句話說，最壞的情況下，在窗口臨界點(diǎn)附近系統(tǒng)會承受 2 倍的流量沖擊，這就是簡單窗口不能解決的臨界突變問題。

2 滑動窗口

如何解決簡單窗口算法的臨界突變問題?既然一個窗口統(tǒng)計(jì)的精度低，那么可以把整個大的時(shí)間窗口切分成更細(xì)粒度的子窗口，每個子窗口獨(dú)立統(tǒng)計(jì)。同時(shí)，每過一個子窗口大小的時(shí)間，就向右滑動一個子窗口。這就是滑動窗口算法的思路。

??

如上圖所示，將一分鐘的時(shí)間窗口切分成 6 個子窗口，每個子窗口維護(hù)一個獨(dú)立的計(jì)數(shù)器用于統(tǒng)計(jì) 10 秒內(nèi)的訪問量，每經(jīng)過 10s，時(shí)間窗口向右滑動一格。

回到簡單窗口出現(xiàn)臨界跳變的例子，結(jié)合上面的圖再看滑動窗口如何消除臨界突變。如果 0:50 到 1:00 時(shí)刻(對應(yīng)灰色的格子)進(jìn)來了 100 次請求，接下來 1:00~1:10 的 100 次請求會落到黃色的格子中，由于算法統(tǒng)計(jì)的是 6 個子窗口的訪問量總和，這時(shí)候總和超過設(shè)定的閾值 100，就會拒絕后面的這 100 次請求。

代碼實(shí)現(xiàn)(參考 Sentinel)

Sentinel 提供了一個輕量高性能的滑動窗口流控算法實(shí)現(xiàn)，看代碼的時(shí)候可以重點(diǎn)關(guān)注這幾個類：

1)功能插槽 StatisticSlot 負(fù)責(zé)記錄、統(tǒng)計(jì)不同緯度的 runtime 指標(biāo)監(jiān)控信息，例如 RT、QPS 等。

Sentinel 內(nèi)部使用了 slot chain 的責(zé)任鏈設(shè)計(jì)模式，每個功能插槽 slot 有不同的功能(限流、降級、系統(tǒng)保護(hù))，通過 ProcessorSlotChain 串聯(lián)在一起。

參考官方 Wiki：https://github.com/alibaba/Sentinel/wiki/Sentinel工作主流程

2)StatisticSlot 使用 StatisticNode#addPassRequest 記錄允許的請求數(shù)，包含秒和分鐘兩個維度。

3)具體記錄用到的是 Metric 接口，對應(yīng)實(shí)現(xiàn)類 ArrayMetric，背后真正的滑動窗口數(shù)據(jù)結(jié)構(gòu)是LeapArray 。

4)LeapArray 內(nèi)部維護(hù)了滑動窗口用到的關(guān)鍵屬性和結(jié)構(gòu)，包括：

a)總窗口大小 intervalInMs，滑動子窗口大小 windowLengthInMs，采樣數(shù)量sampleCount：

sampleCount = intervalInMs / windowLengthInMs

當(dāng)前實(shí)現(xiàn)默認(rèn)為 2，而總窗口大小默認(rèn)是 1s，也就意味著默認(rèn)的滑動窗口大小是 500ms。可以通過調(diào)整采樣數(shù)量來調(diào)整統(tǒng)計(jì)的精度。

b)滑動窗口的數(shù)組 array，數(shù)組中每個元素以 WindowWrap 表示，其中包含：

• windowStart：滑動窗口的開始時(shí)間。
• windowLength：滑動窗口的長度。
• value：滑動窗口記錄的內(nèi)容，泛型表示，關(guān)鍵的一類就是 MetricBucket，里面包含了一組LongAdder 用于記錄不同類型的數(shù)據(jù)，例如請求通過數(shù)、請求阻塞數(shù)、請求異常數(shù)等等。

記錄請求的邏輯說白了，就是根據(jù)當(dāng)前時(shí)間獲取所屬的滑動窗口，然后將該窗口的統(tǒng)計(jì)值 +1 即可。但實(shí)際上，獲取當(dāng)前所屬的時(shí)間窗口這一步隱含了不少細(xì)節(jié)，詳細(xì)的實(shí)現(xiàn)可以從LeapArray#currentWindow 中找到，源碼的注釋寫得很詳細(xì)，這里就不多提了。

這里借助一張其他同學(xué)畫的圖表述以上的流程：

??

以上的流程基于 3.9.21 版本的源碼，早先版本的 Sentinel 內(nèi)部版本實(shí)現(xiàn)不盡相同，使用了一個叫SentinelRollingNumber 的數(shù)據(jù)結(jié)構(gòu)，但原理是類似的。

精度問題

現(xiàn)在思考這么一個問題：滑動窗口算法能否精準(zhǔn)地控制任意給定時(shí)間窗口 T 內(nèi)的訪問量不大于 N?

答案是否定的，還是將 1 分鐘分成 6 個 10 秒大小的子窗口的例子，假設(shè)請求的速率現(xiàn)在是 20 次/秒，從 0:05 時(shí)刻開始進(jìn)入，那么在 0:05~0:10 時(shí)間段內(nèi)會放進(jìn) 100 個請求，同時(shí)接下來的請求都會被限流，直到 1:00 時(shí)刻窗口滑動，在 1:00~1:05 時(shí)刻繼續(xù)放進(jìn) 100 個請求。如果把 0:05~1:05 看作是 1 分鐘的時(shí)間窗口，那么這個窗口內(nèi)實(shí)際的請求量是 200，超出了給定的閾值 100。

如果要追求更高的精度，理論上只需要把滑動窗口切分得更細(xì)。像 Sentinel 中就可以通過修改單位時(shí)間內(nèi)的采樣數(shù)量 sampleCount 值來設(shè)置精度，這個值一般根據(jù)業(yè)務(wù)的需求來定，以達(dá)到在精度和內(nèi)存消耗之間的平衡。

平滑度問題

使用滑動窗口算法限制流量時(shí)，我們經(jīng)常會看到像下面一樣的流量曲線。

??

突發(fā)的大流量在窗口開始不久就直接把限流的閾值打滿，導(dǎo)致剩余的窗口內(nèi)所有請求都無法通過。在時(shí)間窗口的單位比較大時(shí)(例如以分為單位進(jìn)行流控)，這種問題的影響就比較大了。在實(shí)際應(yīng)用中我們要的限流效果往往不是把流量一下子掐斷，而是讓流量平滑地進(jìn)入系統(tǒng)當(dāng)中。

3 漏桶

滑動窗口無法很好地解決平滑度問題，再回過頭看我們對于平滑度的訴求，當(dāng)流量超過一定范圍后，我們想要的效果不是一下子切斷流量，而是將流量控制在系統(tǒng)能承受的一定的速度內(nèi)。假設(shè)平均訪問速率為 v, 那我們要做的流控其實(shí)是流速控制，即控制平均訪問速率 v ≤ N / T。

在網(wǎng)絡(luò)通信中常常用到漏桶算法來實(shí)現(xiàn)流量整形。漏桶算法的思路就是基于流速來做控制。想象一下上學(xué)時(shí)經(jīng)常做的水池一邊抽水一邊注水的應(yīng)用題，把水池?fù)Q成水桶(還是底下有洞一注水就開始漏的那種)，把請求看作是往桶里注水，桶底漏出的水代表離開緩沖區(qū)被服務(wù)器處理的請求，桶口溢出的水代表被丟棄的請求。在概念上類比：

• 最大允許請求數(shù) N：桶的大小
• 時(shí)間窗口大小 T：一整桶水漏完的時(shí)間
• 最大訪問速率 V：一整桶水漏完的速度，即 N/T
• 請求被限流：桶注水的速度比漏水的速度快，最終導(dǎo)致桶內(nèi)水溢出

假設(shè)起始時(shí)刻桶是空的，每次訪問都會往桶里注入一單位體積的水量，那么當(dāng)我們以小于等于 N/T 的速度往桶里注水時(shí)，桶內(nèi)的水就永遠(yuǎn)不會溢出。反之，一旦實(shí)際注水速度超過漏水速度，桶里就會產(chǎn)生越來越多的積水，直到溢出為止。同時(shí)漏水的速度永遠(yuǎn)被控制在 N/T 以內(nèi)，這就實(shí)現(xiàn)了平滑流量的目的。

漏桶算法的訪問速率曲線如下：

??

附上一張網(wǎng)上常見的漏桶算法原題圖：

??

代碼實(shí)現(xiàn) LeakyBucketThrottler

/** 
  * 當(dāng)前桶內(nèi)剩余的水 
  */ 
 private long left; 
 /** 
  * 上次成功注水的時(shí)間戳 
  */ 
 private long lastInjectTime = System.currentTimeMillis(); 
 /** 
  * 桶的容量 
  */ 
 private long capacity; 
 /** 
  * 一桶水漏完的時(shí)間 
  */ 
 private long duration; 
 /** 
  * 桶漏水的速度，即 capacity / duration 
  */ 
 private double velocity; 
  
 public boolean tryAcquire(String key) { 
     long now = System.currentTimeMillis(); 
     // 當(dāng)前剩余的水 = 之前的剩余水量 - 過去這段時(shí)間內(nèi)漏掉的水量 
     // 過去這段時(shí)間內(nèi)漏掉的水量 = (當(dāng)前時(shí)間-上次注水時(shí)間) * 漏水速度 
     // 如果當(dāng)前時(shí)間相比上次注水時(shí)間相隔太久（一直沒有注水），桶內(nèi)的剩余水量就是0（漏完了） 
     left = Math.max(0, left - (long)((now - lastInjectTime) * velocity)); 
     // 往當(dāng)前水量基礎(chǔ)上注一單位水，只要沒有溢出就代表可以訪問 
     if (left + 1 <= capacity) { 
         lastInjectTime = now; 
         left++; 
         return true; 
     } else { 
         return false; 
     } 
 }

漏桶的問題

漏桶的優(yōu)勢在于能夠平滑流量，如果流量不是均勻的，那么漏桶算法與滑動窗口算法一樣無法做到真正的精確控制。極端情況下，漏桶在時(shí)間窗口 T 內(nèi)也會放進(jìn)相當(dāng)于 2 倍閾值 N 的流量。

設(shè)想一下，如果訪問量相比窗口大小 N 大很多，在窗口(0~T)一開始的 0 時(shí)刻就直接涌進(jìn)來，使得漏桶在時(shí)間 t( 0≈t

雖然可以通過限制桶大小的方式使得訪問量控制在 N 以內(nèi)，但這樣做的副作用是流量在還未達(dá)到限制條件就被禁止。

還有一個隱含的約束是，漏桶漏水的速度最好是一個整數(shù)值(即容量 N 能夠整除時(shí)間窗口大小 T)，否則在計(jì)算剩余水量時(shí)會有些許誤差。

4 令牌桶

漏桶模型中，請求來了是往桶里注水，如果反一下，把請求放行變成從桶里抽水，對應(yīng)的，把注水看作是補(bǔ)充系統(tǒng)可承受流量的話，漏桶模型就變成了令牌桶模型。

理解漏桶之后，再看令牌桶就很簡單了，抄一段令牌桶的原理：

令牌桶算法的原理是系統(tǒng)以恒定的速率產(chǎn)生令牌，然后把令牌放到令牌桶中，令牌桶有一個容量，當(dāng)令牌桶滿了的時(shí)候，再向其中放令牌，那么多余的令牌會被丟棄;當(dāng)想要處理一個請求的時(shí)候，需要從令牌桶中取出一個令牌，如果此時(shí)令牌桶中沒有令牌，那么則拒絕該請求。

??

代碼實(shí)現(xiàn) TokenBucketThrottler

令牌桶與漏桶本質(zhì)上是一樣的，因此漏桶的代碼稍微改下就可以變成令牌桶。

long now = System.currentTimeMillis(); 
 left = Math.min(capacity, left + (long)((now - lastInjectTime) * velocity)); 
 if (left - 1 > 0) { 
     lastInjectTime = now; 
     left--; 
     return true; 
 } else { 
     return false; 
 }

生產(chǎn)環(huán)境中使用令牌桶的話，可以考慮借助 Guava 中提供的 RateLimiter。它的實(shí)現(xiàn)是多線程安全的，調(diào)用 RateLimiter#acquire 時(shí)，如果剩余令牌不足，會阻塞線程一段時(shí)間直至有足夠的可用令牌(而不是直接拒絕，這在某些場景下很有用)。除去默認(rèn)的 SmoothBursty 策略外，RateLimiter 還提供了一種叫 SmoothWarmingUp 的策略，支持設(shè)置一個熱身期，熱身期內(nèi)，RateLimiter 會平滑地將放令牌的速率加大，直致最大速率。設(shè)計(jì)這個的意圖是為了滿足那種資源提供方需要熱身時(shí)間，而不是每次訪問都能提供穩(wěn)定速率的服務(wù)的情況(比如帶緩存服務(wù)，需要定期刷新緩存) 。RateLimiter 有一個缺點(diǎn)是只支持 QPS 級別。

漏桶、令牌桶的區(qū)別

雖然兩者本質(zhì)上只是反轉(zhuǎn)了一下，不過在實(shí)際使用中，適用的場景稍有差別：

1)漏桶：用于控制網(wǎng)絡(luò)中的速率。在該算法中，輸入速率可以變化，但輸出速率保持恒定。常常配合一個 FIFO 隊(duì)列使用。

想象一下，漏桶的破洞是固定大小的，因此漏水的速率是可以保持恒定的。

2)令牌桶：按照固定速率往桶中添加令牌，允許輸出速率根據(jù)突發(fā)大小而變化。

舉個例子，一個系統(tǒng)限制 60 秒內(nèi)的最大訪問量是 60 次，換算速率是 1 次/秒，如果在一段時(shí)間內(nèi)沒有訪問量，那么對漏桶而言此刻是空的?，F(xiàn)在，一瞬間涌入 60 個請求，那么流量整形后，漏桶會以每秒 1 個請求的速度，花上 1 分鐘將 60 個請求漏給下游。換成令牌桶的話，則是從令牌桶中一次性取走 60 個令牌，一下子塞給下游。

5 滑動日志

一般情況下，上述的算法已經(jīng)能很好地用于大部分實(shí)際應(yīng)用場景了，很少有場景需要真正完全精確的控制(即任意給定時(shí)間窗口T內(nèi)請求量不大于 N )。如果要精確控制的話，我們需要記錄每一次用戶請求日志，當(dāng)每次流控判斷時(shí)，取出最近時(shí)間窗口內(nèi)的日志數(shù)，看是否大于流控閾值。這就是滑動日志的算法思路。

設(shè)想某一個時(shí)刻 t 有一個請求，要判斷是否允許，我們要看的其實(shí)是過去 t - N 時(shí)間段內(nèi)是否有大于等于 N 個請求被放行，因此只要系統(tǒng)維護(hù)一個隊(duì)列 q，里面記錄每一個請求的時(shí)間，理論上就可以計(jì)算出從 t - N 時(shí)刻開始的請求數(shù)。

考慮到只需關(guān)心當(dāng)前時(shí)間之前最長 T 時(shí)間內(nèi)的記錄，因此隊(duì)列 q 的長度可以動態(tài)變化，并且隊(duì)列中最多只記錄 N 條訪問，因此隊(duì)列長度的最大值為 N。

滑動日志與滑動窗口非常像，區(qū)別在于滑動日志的滑動是根據(jù)日志記錄的時(shí)間做動態(tài)滑動，而滑動窗口是根據(jù)子窗口的大小，以子窗口維度滑動。

偽代碼實(shí)現(xiàn)

算法的偽代碼表示如下：

# 初始化 
 counter = 0 
 q = [] 
  
 # 請求處理流程 
 # 1.找到隊(duì)列中第一個時(shí)間戳>=t-T的請求，即以當(dāng)前時(shí)間t截止的時(shí)間窗口T內(nèi)的最早請求 
 t = now 
 start = findWindowStart(q, t) 
  
 # 2.截?cái)嚓?duì)列，只保留最近T時(shí)間窗口內(nèi)的記錄和計(jì)數(shù)值 
 q = q[start, q.length - 1]  
 counter -= start 
  
 # 3.判斷是否放行，如果允許放行則將這次請求加到隊(duì)列 q 的末尾 
 if counter < threshold 
     push(q, t) 
     counter++ 
     # 放行 
 else 
     # 限流

findWindowStart 的實(shí)現(xiàn)依賴于隊(duì)列 q 使用的數(shù)據(jù)結(jié)構(gòu)，以簡單的數(shù)組為例，可以使用二分查找等方式。后面也會看到使用其他數(shù)據(jù)結(jié)構(gòu)如何實(shí)現(xiàn)。

如果用數(shù)組實(shí)現(xiàn)，一個難點(diǎn)可能是如何截?cái)嘁粋€隊(duì)列，一種可行的思路是使用一組頭尾指針 head和 tail 分別指向數(shù)組中最近和最早的有效記錄索引來解決， findWindowStart 的實(shí)現(xiàn)就變成在tail 和 head 之間查找對應(yīng)元素。

復(fù)雜度問題

雖然算法解決了精確度問題，但代價(jià)也是顯而易見的。

首先，我們要保存一個長度最大為 N 的隊(duì)列，這意味著空間復(fù)雜度達(dá)到 O(N)，如果要針對不同的 key 做流控，那么空間上會占用更多。當(dāng)然，可以對不活躍 key 的隊(duì)列進(jìn)行復(fù)用來降低內(nèi)存消耗。

其次，我們需要在隊(duì)列中確定時(shí)間窗口，即通過 findWindowStart 方法尋找不早于當(dāng)前時(shí)間戳 t - N 的請求記錄。以二分查找為例，時(shí)間復(fù)雜度是 O(logN)。

四 分布式流控

現(xiàn)實(shí)中的應(yīng)用服務(wù)往往是分布式部署的，如果共用的資源(例如數(shù)據(jù)庫)或者依賴的下游服務(wù)有流量限制，那么分布式流控就要派上用場了。

雖然可以給每臺應(yīng)用服務(wù)器平均分配流控配額，把問題轉(zhuǎn)換為單機(jī)流控，但如果碰到流量不均勻、機(jī)器宕機(jī)、臨時(shí)擴(kuò)縮容等場景，這種做法的效果不佳。

分布式環(huán)境下做流控的核心算法思路其實(shí)與單機(jī)流控是一致的，區(qū)別在于需要實(shí)現(xiàn)一種同步機(jī)制來保證全局配額。同步機(jī)制的實(shí)現(xiàn)可以有中心化和去中心化兩種思路：

1)中心化：配額由一個中心系統(tǒng)統(tǒng)一管控，應(yīng)用進(jìn)程通過向中心系統(tǒng)申請的方式獲取流控配額。

• 狀態(tài)的一致性在中心系統(tǒng)維護(hù)，實(shí)現(xiàn)簡單。
• 中心系統(tǒng)節(jié)點(diǎn)的不可用會導(dǎo)致流控出錯，需要有額外的保護(hù)。例如，中心化流控在中心存儲不可用時(shí)，往往會退化為單機(jī)流控。

2)去中心化：應(yīng)用進(jìn)程獨(dú)立保存和維護(hù)流控配額狀態(tài)，集群內(nèi)周期性異步通訊以保持狀態(tài)一致。

• 相比中心化方案，去中心化方案能夠降低中心化單點(diǎn)可靠性帶來的影響，但實(shí)現(xiàn)上比較復(fù)雜，狀態(tài)的一致性難以保證。
• 在 CAP 中去中心化更加傾向于 A 而中心化更傾向于 C。

去中心化方案在生產(chǎn)環(huán)境中沒有見過，因此下文只討論中心化流控的思路。

1 接入層入口流控

應(yīng)用接入的網(wǎng)絡(luò)架構(gòu)中，在應(yīng)用服務(wù)器之前往往有一層 LVS 或 Nginx 做統(tǒng)一入口，可以在這一層做入口的流控。本質(zhì)上這就是單機(jī)流控的場景。

以 Nginx 為例，Nginx 提供了 ngx_http_limit_req_module 模塊用于流控，底層使用的是漏桶算法。

一個 Nginx 流控配置的示例如下，表示每個 IP 地址每秒只能請求 10 次 /login/ 接口。

limit_req_zone $binary_remote_addr zone=mylimit:10m rate=10r/s; 
  
 server { 
     location /login/ { 
         limit_req zone=mylimit; 
  
         proxy_pass http://my_upstream; 
     } 
 }

Nginx 的流控指令還支持更多配置，比如說配置 limit_req 指令時(shí)加上 burst 和 nodelay 參數(shù)來允許一定程度的突發(fā)，或者結(jié)合 geo 和 map 指令來實(shí)現(xiàn)黑白名單流控，具體可以參考 Nginx 官方文檔：Rate Limiting with NGINX and NGINX Plus(https://www.nginx.com/blog/rate-limiting-nginx/)。

如果自帶的模塊不能滿足，那就上自定義的 lua 模塊吧，參考 OpenResty 提供的 Lua 限流模塊lua-resty-limit-traffic。

2 TokenServer 流控

這里借用了 Sentinel 中的 TokenServer 叫法，Sentinel 集群流控的介紹可以參考官方文檔：Sentinel集群流控(https://github.com/alibaba/Sentinel/wiki/集群流控)。

這類流控的思路是找一個 TokenServer 來專門來管控流控配額，包括統(tǒng)計(jì)總調(diào)用量，判斷單個請求是否允許等等，應(yīng)用服務(wù)器作為客戶端與 TokenServer 通信來獲取配額。因?yàn)榱骺氐倪壿嬙赥okenServer 內(nèi)部統(tǒng)一處理，因此單機(jī)流控中討論的算法同樣適用。

很自然地能想到，這類流控非常依賴于 TokenServer 的性能和可用性。

性能方面，單點(diǎn)的 TokenServer 很容易成為瓶頸，查 Sentinel 源碼，其中使用了 Netty 來做網(wǎng)絡(luò)通信，數(shù)據(jù)包采用自定義格式，其他性能優(yōu)化能找到的不多。

可用性方面，就像 Sentinel 官方文檔中講的，若在生產(chǎn)環(huán)境使用 TokenServer 集群限流，必須要解決以下問題：

• Token Server 自動管理、調(diào)度(分配/選舉 Token Server)
• Token Server 高可用，在某個 Server 不可用時(shí)自動 failover 到其它機(jī)器

目前 Sentinel 的 TokenServer 默認(rèn)并沒有實(shí)現(xiàn)這些能力，需要定制或增加其他系統(tǒng)來實(shí)現(xiàn)，例如，采用一種分布式一致性協(xié)議來做集群選舉，或者借助一組 monitor 來監(jiān)控狀態(tài)，實(shí)現(xiàn)成本還是挺高的。

3 存儲式流控

存儲式流控的思想是通過一個存儲系統(tǒng)來保存流控的計(jì)數(shù)值等統(tǒng)計(jì)信息，應(yīng)用從存儲中獲取統(tǒng)計(jì)信息，然后將最新的請求信息再寫入存儲中。存儲系統(tǒng)可以選擇現(xiàn)成的 MySQL 數(shù)據(jù)庫或者 Redis 緩存等，一般從性能出發(fā)選擇緩存的比較多。這里選擇 Tair 和 Redis 做例子。

Tair 流控

比較簡單，直接上代碼實(shí)現(xiàn)。

public boolean tryAcquire(String key) { 
   // 以秒為單位構(gòu)建tair的key 
   String wrappedKey = wrapKey(key); 
   // 每次請求+1，初始值為0，key的有效期設(shè)置5s 
   Result<Integer> result = tairManager.incr(NAMESPACE, wrappedKey, 1, 0, 5); 
   return result.isSuccess() && result.getValue() <= threshold; 
 } 
  
 private String wrapKey(String key) { 
   long sec = System.currentTimeMillis() / 1000L; 
   return key + ":" + sec; 
 }

是不是感覺太簡單了點(diǎn)?得益于 Tair 的高性能，這種方式可以很好地支撐大流量。

這種 Tair 流控的方案實(shí)際上用的簡單窗口的思路，每個 key 以每秒為一個時(shí)間窗口做 QPS 控制(QPM/QPD 原理類似)。關(guān)鍵在于用到了 Tair 的這個 API：

• incr
• Result incr(int namespace, Serializable key, int value, int defaultValue, int expireTime)
• 描述
• 增加計(jì)數(shù)。注意：incr 前不要 put!!
• 參數(shù)
• namespace - 申請時(shí)分配的 namespacekey - key 列表，不超過 1kvalue - 增加量defaultValue - 第一次調(diào)用 incr 時(shí)的 key 的 count 初始值，第一次返回的值為 defaultValue + value。expireTime - 數(shù)據(jù)過期時(shí)間，單位為秒，可設(shè)相對時(shí)間或絕對時(shí)間(Unix 時(shí)間戳)。expireTime = 0，表示數(shù)據(jù)永不過期。expireTime > 0，表示設(shè)置過期時(shí)間。若 expireTime > 當(dāng)前時(shí)間的時(shí)間戳，則表示使用絕對時(shí)間，否則使用相對時(shí)間。expireTime < 0，表示不關(guān)注過期時(shí)間，若之前設(shè)過過期時(shí)間，則已之前的過期時(shí)間為準(zhǔn)，若沒有，則作為永不過期處理，但當(dāng)前 mdb 統(tǒng)一當(dāng)做永不過期來處理。
• 返回值
• Result 對象，返回值可為負(fù)值。當(dāng) key 不存在時(shí)，第一次返回 defaultValue+ value。后續(xù)的 incr 基于該值增加 value。

當(dāng)然這種方式也有缺點(diǎn)：

• 簡單窗口的臨界突變問題。
• Tair 的可靠性問題，需要有降級方案。上面其實(shí)也說了，中心化的流控一般都需要搭配降級的單機(jī)流控。
• 集群機(jī)器的時(shí)間同步問題。由于生成 key 會用到集群機(jī)器的本地時(shí)間，因此要求機(jī)器時(shí)間必須是一致的。

打個比方，不同機(jī)器時(shí)間稍微差個 10ms，在時(shí)間窗口的間隔點(diǎn)上的統(tǒng)計(jì)就會產(chǎn)生比較大的誤差，比如說在同一時(shí)刻，一臺機(jī)器時(shí)間是 0.990，一臺是 1.000，兩者調(diào)用 incr 時(shí)操作的 key 不一樣，精度自然就會受影響。

Redis 流控

Redis 支持豐富的數(shù)據(jù)結(jié)構(gòu)，性能也不錯，其“單進(jìn)程”模型方便同步控制，因此非常適合用來做分布式流控的存儲。

1)簡單窗口實(shí)現(xiàn)

使用 Redis 實(shí)現(xiàn)簡單窗口流控的思路跟使用 Tair 是一致的。Redis 也提供了 INCR 命令用于計(jì)數(shù)，同時(shí) Redis 的“單進(jìn)程”模型也提供了很好的并發(fā)保護(hù)。Redis 的官方文檔就寫了如何使用INCR 來實(shí)現(xiàn) Rate Limiter，我這里稍作翻譯了下：

• Redis INCR key(https://redis.io/commands/incr)

以簡單窗口為例，最簡單直接的實(shí)現(xiàn)如下：

FUNCTION LIMIT_API_CALL(ip) 
 ts = CURRENT_UNIX_TIME() 
 keyname = ip+":"+ts 
 current = GET(keyname) 
 IF current != NULL AND current > 10 THEN 
     ERROR "too many requests per second" 
 ELSE 
     MULTI 
         INCR(keyname,1) 
         EXPIRE(keyname,10) 
     EXEC 
     PERFORM_API_CALL() 
 END

實(shí)現(xiàn)上與上述的 Tair 類似，也是對每個 key 以秒為單位維護(hù)一個計(jì)數(shù)器，差別在于因?yàn)?Redis 沒有提供原子的 INCR + EXPIRE 指令，所以在 INCR 之后需要再調(diào)用一次 EXPIRE 來設(shè)置 key 的有效期。同時(shí)在外層以 MULTI 和 EXEC 包裹以保證事務(wù)性。

如果不想每次都調(diào)用 EXPIRE，可以考慮第二種方式：

FUNCTION LIMIT_API_CALL(ip): 
 current = GET(ip) 
 IF current != NULL AND current > 10 THEN 
     ERROR "too many requests per second" 
 ELSE 
     value = INCR(ip) 
     IF value == 1 THEN 
         EXPIRE(ip,1) 
     END 
     PERFORM_API_CALL() 
 END

計(jì)數(shù)器的有效期在第一次 INCR 時(shí)設(shè)置為 1s，因此不需要對 key 進(jìn)行額外處理。

不過需要注意的是，這種方式存在一種隱藏的競爭條件。如果客戶端在第一次調(diào)用了 INCR 后，由于應(yīng)用崩潰或其他原因沒有調(diào)用 EXPIRE，計(jì)數(shù)器會一直存在。

針對方式二的這個問題，可以用 lua 腳本解決：

local current 
 current = redis.call("incr",KEYS[1]) 
 if tonumber(current) == 1 then 
     redis.call("expire",KEYS[1],1) 
 end

第三種方式是通過 Redis 的 list 結(jié)構(gòu)來實(shí)現(xiàn)。更復(fù)雜一些但可以記錄下每次的請求。

FUNCTION LIMIT_API_CALL(ip) 
 current = LLEN(ip) 
 IF current > 10 THEN 
     ERROR "too many requests per second" 
 ELSE 
     IF EXISTS(ip) == FALSE              #1 
         MULTI 
             RPUSH(ip,ip) 
             EXPIRE(ip,1) 
         EXEC 
     ELSE 
         RPUSHX(ip,ip) 
     END 
     PERFORM_API_CALL() 
 END

這里也有一個隱含的競爭條件，在執(zhí)行到 EXIST 判斷這一行(#1 位置)時(shí)，兩個客戶端的 EXIST命令可能都會返回 false，因此 MULTI/EXEC 塊里的命令會被執(zhí)行兩次，不過這種情況很少出現(xiàn)，不太會影響計(jì)數(shù)器的準(zhǔn)確性。

上述的幾種方式還可以進(jìn)一步優(yōu)化，因?yàn)?INCR 和 RPUSH 這些命令都會返回操作后的計(jì)數(shù)器值，所以可以使用 set-then-get 的方式獲取計(jì)數(shù)器值。

將簡單窗口改造成滑動窗口也是類似的思路，把單一的 key 換成一個 hash 結(jié)構(gòu)，hash 里面為每個子窗口保存一個計(jì)數(shù)值，在統(tǒng)計(jì)時(shí)，將同個 hash 中所有子窗口的計(jì)數(shù)值相加即可。

2)令牌桶/漏桶實(shí)現(xiàn)

用 Redis 實(shí)現(xiàn)令牌桶或者漏桶也非常簡單。以令牌桶為例，在實(shí)現(xiàn)上，可以用兩個 key 分別存儲每個用戶的可用 token 數(shù)和上次請求時(shí)間，另一種可能更好的辦法是使用 Redis 的 hash 數(shù)據(jù)結(jié)構(gòu)。

下圖的示例是一個用戶 user_1 當(dāng)前在 Redis 中保存的流控配額數(shù)據(jù)：令牌桶中當(dāng)前剩余 2 個 token，最近一次訪問的時(shí)間戳是 1490868000。

??

當(dāng)收到一個新請求時(shí)，Redis 客戶端要執(zhí)行的操作與我們在單機(jī)流控算法中看到的一樣。首先，從對應(yīng) hash 中獲得當(dāng)前配額數(shù)據(jù)(HGETALL)，根據(jù)當(dāng)前時(shí)間戳、上次請求的時(shí)間戳和 token 填充速度計(jì)算要填充的 token 數(shù);然后，判斷是否放行，更新新的時(shí)間戳和 token 數(shù)(HMSET)。

一個示例如下：??

同樣的，如果要求比較高的精度，這里必須要對客戶端的操作做并發(fā)控制。

不做同步控制可能導(dǎo)致的問題示例：桶里只有一個 token，兩個客戶端同時(shí)請求時(shí)出現(xiàn)并發(fā)沖突，結(jié)果是請求都會放行。

??

lua 代碼示例如下：

local tokens_key = KEYS[1] 
 local timestamp_key = KEYS[2] 
  
 local rate = tonumber(ARGV[1]) 
 local capacity = tonumber(ARGV[2]) 
 local now = tonumber(ARGV[3]) 
 local requested = tonumber(ARGV[4]) 
  
 local fill_time = capacity/rate 
 local ttl = math.floor(fill_time*2) 
  
 local last_tokens = tonumber(redis.call("get", tokens_key)) 
 if last_tokens == nil then 
   last_tokens = capacity 
 end 
  
 local last_refreshed = tonumber(redis.call("get", timestamp_key)) 
 if last_refreshed == nil then 
   last_refreshed = 0 
 end 
  
 local delta = math.max(0, now-last_refreshed) 
 local filled_tokens = math.min(capacity, last_tokens+(delta*rate)) 
 local allowed = filled_tokens >= requested 
 local new_tokens = filled_tokens 
 if allowed then 
   new_tokens = filled_tokens - requested 
 end 
  
 redis.call("setex", tokens_key, ttl, new_tokens) 
 redis.call("setex", timestamp_key, ttl, now) 
  
 return { allowed, new_tokens }

3)滑動日志實(shí)現(xiàn)

得益于 Redis 的 Sorted Set 結(jié)構(gòu)，實(shí)現(xiàn)滑動日志變得異常簡單。流程大致如下：

a)每個用戶有一個對應(yīng)的 Sorted Set 記錄請求日志。

其中每個元素的 key 和 value 可以是相同的，即請求的時(shí)間戳。

Sorted Set 可以根據(jù)時(shí)間窗口大小設(shè)置有效期，比如時(shí)間窗口為 1s 時(shí)設(shè)置過期時(shí)間 5s，在請求量不大時(shí)可以節(jié)省 Redis 服務(wù)器內(nèi)存。

b)當(dāng)收到一個新的用戶請求時(shí)，首先通過 ZREMRANGEBYSCORE 命令刪除 Sorted Set 中過期的元素，這里的過期即：

請求時(shí)間戳 t < 當(dāng)前時(shí)間戳 now - 時(shí)間窗口大小 interval

c)使用 ZADD 將當(dāng)前請求添加到 Set 中。

d)使用 ZCOUNT 獲取當(dāng)前剩余 Set 大小，判斷是否需要流控。

FUNCTION LIMIT_API_CALL(ip): 
 current = GET(ip) 
 IF current != NULL AND current > 10 THEN 
     ERROR "too many requests per second" 
 ELSE 
     value = INCR(ip) 
     IF value == 1 THEN 
         EXPIRE(ip,1) 
     END 
     PERFORM_API_CALL() 
 END

另一個 JS 實(shí)現(xiàn)的代碼示例：https://github.com/peterkhayes/rolling-rate-limiter/blob/master/index.js

由于滑動日志算法的空間復(fù)雜度較其他算法高，使用滑動日志算法時(shí)，需要注意監(jiān)控 Redis 內(nèi)存的使用量。

4)并發(fā)控制

上面的幾種算法都提到了不做并發(fā)控制可能帶來的競態(tài)條件，但額外的并發(fā)控制必然會帶來性能下降，通常需要在精度和性能之間做取舍。Redis 流控的并發(fā)控制常見的有幾類：

• 使用 Redis 事務(wù) MULTI/EXEC。
• 使用 RedLock(https://redis.io/topics/distlock) 等分布式鎖，要求每個客戶端操作前先獲取對應(yīng) key 的分布式鎖。
• Lua 腳本。

最好通過性能測試來決定使用哪一種方式。

4 擴(kuò)展的一些思考

分布式流控帶來了網(wǎng)絡(luò)通信、加鎖同步等開銷，會對性能帶來一定影響。同時(shí)分布式環(huán)境的可靠性也會帶來更多挑戰(zhàn)。如何設(shè)計(jì)一個高性能、高可靠性的分布式流控系統(tǒng)?這可能是個涉及到整個系統(tǒng)方方面面的大話題。

分享一下個人的一些思考，歡迎討論：

1)根據(jù)實(shí)際訴求，合理搭配不同層的多級流控是個不錯的方式，盡量把流量攔在外層。例如常見的接口層 Nginx 流控 + 應(yīng)用層流控。

2)選擇一個合適的緩存系統(tǒng)保存流控的動態(tài)數(shù)據(jù)，這個一般跟著公司的統(tǒng)一技術(shù)架構(gòu)走。

3)將流控的靜態(tài)配置放到配置中心(例如 Diamond)。

4)設(shè)計(jì)時(shí)要考慮分布式流控不可用的情況(例如緩存掛掉)，必要時(shí)切到單機(jī)流控，使用 Sentinel 成熟可靠。

5)很多時(shí)候?qū)鹊囊鬀]那么高，因?yàn)橐话愣紩试S一定的突發(fā)量。這時(shí)候可以做一些性能的優(yōu)化。性能的最大瓶頸在于每次請求都會訪問一次緩存，我之前在設(shè)計(jì)時(shí)就采用了一種折中的辦法：

• 將可用配額的一部分，按一定比例(例如 50%)，先預(yù)分配給集群內(nèi)的機(jī)器。一般是平均分配，如果預(yù)先就已經(jīng)知道每臺機(jī)器的流量權(quán)重，可以加權(quán)分配。每臺機(jī)器消耗配額的速率不同，中間也可能有機(jī)器宕機(jī)，可能有擴(kuò)縮容，因此預(yù)分配的比例不宜太大，當(dāng)然也不宜太小。
• 每臺機(jī)器在配額耗盡時(shí)，向中心系統(tǒng)請求配額，這里的一個優(yōu)化點(diǎn)是每臺機(jī)器會記錄自身配額消耗的速率(等同于承受的流量速率)，按照速率大小申請不同大小的配額，消耗速率大則一次性申請更多。
• 在整體可用配額不足一定比例時(shí)(例如 10%)，限制每臺機(jī)器一次可申請的配額數(shù)，按剩余窗口大小計(jì)算發(fā)放配額的大小，并且每次發(fā)放量不超過剩余配額的一定比例(例如 50%)，使得剩余的流量能夠平滑地過渡。

五 總結(jié)

分布式流控的算法其實(shí)是單機(jī)流控的延伸，算法本質(zhì)是一樣的。這里按我的個人理解總結(jié)了上述幾種流控算法的復(fù)雜度和適用場景。

??