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

一 流控的場景

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

有的時候，流控服務于收費模式，比如某些云廠商會對調用 API 的頻次進行計費。既然涉及到錢，一般就不允許有超出閾值的調用量。

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

二 接口定義

為了方便，以下所有的示例代碼實現都是基于 Throttler 接口。

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

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

有些流控算法需要為每個 key 維護一個 Throttler 實例。

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

三 單機流控

1 簡單窗口

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

流控是為了限制指定時間間隔內能夠允許的訪問量，因此，最直觀的思路就是基于一個給定的時間窗口，維護一個計數器用于統計訪問次數，然后實現以下規則：

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

代碼實現 SimpleWindowThrottler

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

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

切換到多線程環境

在現實應用中，往往是多個線程來同時申請配額，為了比較簡潔地表達算法思路，示例代碼里面都沒有做并發同步控制。

以簡單窗口的實現為例，要轉換為多線程安全的流控算法，一種直接的辦法是將 tryAcquire 方法設置為 synchronized。

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

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

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

臨界突變問題

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

??

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

??

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

2 滑動窗口

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

??

如上圖所示，將一分鐘的時間窗口切分成 6 個子窗口，每個子窗口維護一個獨立的計數器用于統計 10 秒內的訪問量，每經過 10s，時間窗口向右滑動一格。

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

代碼實現(參考 Sentinel)

Sentinel 提供了一個輕量高性能的滑動窗口流控算法實現，看代碼的時候可以重點關注這幾個類：

1)功能插槽 StatisticSlot 負責記錄、統計不同緯度的 runtime 指標監控信息，例如 RT、QPS 等。

Sentinel 內部使用了 slot chain 的責任鏈設計模式，每個功能插槽 slot 有不同的功能(限流、降級、系統保護)，通過 ProcessorSlotChain 串聯在一起。

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

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

3)具體記錄用到的是 Metric 接口，對應實現類 ArrayMetric，背后真正的滑動窗口數據結構是LeapArray 。

4)LeapArray 內部維護了滑動窗口用到的關鍵屬性和結構，包括：

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

sampleCount = intervalInMs / windowLengthInMs

當前實現默認為 2，而總窗口大小默認是 1s，也就意味著默認的滑動窗口大小是 500ms。可以通過調整采樣數量來調整統計的精度。

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

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

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

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

??

以上的流程基于 3.9.21 版本的源碼，早先版本的 Sentinel 內部版本實現不盡相同，使用了一個叫SentinelRollingNumber 的數據結構，但原理是類似的。

精度問題

現在思考這么一個問題：滑動窗口算法能否精準地控制任意給定時間窗口 T 內的訪問量不大于 N?

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

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

平滑度問題

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

??

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

3 漏桶

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

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

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

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

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

??

附上一張網上常見的漏桶算法原題圖：

??

代碼實現 LeakyBucketThrottler

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

漏桶的問題

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

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

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

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

4 令牌桶

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

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

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

??

代碼實現 TokenBucketThrottler

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

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

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

漏桶、令牌桶的區別

雖然兩者本質上只是反轉了一下，不過在實際使用中，適用的場景稍有差別：

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

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

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

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

5 滑動日志

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

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

考慮到只需關心當前時間之前最長 T 時間內的記錄，因此隊列 q 的長度可以動態變化，并且隊列中最多只記錄 N 條訪問，因此隊列長度的最大值為 N。

滑動日志與滑動窗口非常像，區別在于滑動日志的滑動是根據日志記錄的時間做動態滑動，而滑動窗口是根據子窗口的大小，以子窗口維度滑動。

偽代碼實現

算法的偽代碼表示如下：

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

findWindowStart 的實現依賴于隊列 q 使用的數據結構，以簡單的數組為例，可以使用二分查找等方式。后面也會看到使用其他數據結構如何實現。

如果用數組實現，一個難點可能是如何截斷一個隊列，一種可行的思路是使用一組頭尾指針 head和 tail 分別指向數組中最近和最早的有效記錄索引來解決， findWindowStart 的實現就變成在tail 和 head 之間查找對應元素。

復雜度問題

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

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

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

四 分布式流控

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

雖然可以給每臺應用服務器平均分配流控配額，把問題轉換為單機流控，但如果碰到流量不均勻、機器宕機、臨時擴縮容等場景，這種做法的效果不佳。

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

1)中心化：配額由一個中心系統統一管控，應用進程通過向中心系統申請的方式獲取流控配額。

• 狀態的一致性在中心系統維護，實現簡單。
• 中心系統節點的不可用會導致流控出錯，需要有額外的保護。例如，中心化流控在中心存儲不可用時，往往會退化為單機流控。

2)去中心化：應用進程獨立保存和維護流控配額狀態，集群內周期性異步通訊以保持狀態一致。

• 相比中心化方案，去中心化方案能夠降低中心化單點可靠性帶來的影響，但實現上比較復雜，狀態的一致性難以保證。
• 在 CAP 中去中心化更加傾向于 A 而中心化更傾向于 C。

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

1 接入層入口流控

應用接入的網絡架構中，在應用服務器之前往往有一層 LVS 或 Nginx 做統一入口，可以在這一層做入口的流控。本質上這就是單機流控的場景。

以 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 指令時加上 burst 和 nodelay 參數來允許一定程度的突發，或者結合 geo 和 map 指令來實現黑白名單流控，具體可以參考 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 來專門來管控流控配額，包括統計總調用量，判斷單個請求是否允許等等，應用服務器作為客戶端與 TokenServer 通信來獲取配額。因為流控的邏輯在TokenServer 內部統一處理，因此單機流控中討論的算法同樣適用。

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

性能方面，單點的 TokenServer 很容易成為瓶頸，查 Sentinel 源碼，其中使用了 Netty 來做網絡通信，數據包采用自定義格式，其他性能優化能找到的不多。

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

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

目前 Sentinel 的 TokenServer 默認并沒有實現這些能力，需要定制或增加其他系統來實現，例如，采用一種分布式一致性協議來做集群選舉，或者借助一組 monitor 來監控狀態，實現成本還是挺高的。

3 存儲式流控

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

Tair 流控

比較簡單，直接上代碼實現。

public boolean tryAcquire(String key) { 
   // 以秒為單位構建tair的key 
   String wrappedKey = wrapKey(key); 
   // 每次請求+1，初始值為0，key的有效期設置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; 
 }

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

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

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

當然這種方式也有缺點：

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

打個比方，不同機器時間稍微差個 10ms，在時間窗口的間隔點上的統計就會產生比較大的誤差，比如說在同一時刻，一臺機器時間是 0.990，一臺是 1.000，兩者調用 incr 時操作的 key 不一樣，精度自然就會受影響。

Redis 流控

Redis 支持豐富的數據結構，性能也不錯，其“單進程”模型方便同步控制，因此非常適合用來做分布式流控的存儲。

1)簡單窗口實現

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

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

以簡單窗口為例，最簡單直接的實現如下：

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

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

如果不想每次都調用 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

計數器的有效期在第一次 INCR 時設置為 1s，因此不需要對 key 進行額外處理。

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

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

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

第三種方式是通過 Redis 的 list 結構來實現。更復雜一些但可以記錄下每次的請求。

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

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

上述的幾種方式還可以進一步優化，因為 INCR 和 RPUSH 這些命令都會返回操作后的計數器值，所以可以使用 set-then-get 的方式獲取計數器值。

將簡單窗口改造成滑動窗口也是類似的思路，把單一的 key 換成一個 hash 結構，hash 里面為每個子窗口保存一個計數值，在統計時，將同個 hash 中所有子窗口的計數值相加即可。

2)令牌桶/漏桶實現

用 Redis 實現令牌桶或者漏桶也非常簡單。以令牌桶為例，在實現上，可以用兩個 key 分別存儲每個用戶的可用 token 數和上次請求時間，另一種可能更好的辦法是使用 Redis 的 hash 數據結構。

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

??

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

一個示例如下：??

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

不做同步控制可能導致的問題示例：桶里只有一個 token，兩個客戶端同時請求時出現并發沖突，結果是請求都會放行。

??

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)滑動日志實現

得益于 Redis 的 Sorted Set 結構，實現滑動日志變得異常簡單。流程大致如下：

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

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

Sorted Set 可以根據時間窗口大小設置有效期，比如時間窗口為 1s 時設置過期時間 5s，在請求量不大時可以節省 Redis 服務器內存。

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

請求時間戳 t < 當前時間戳 now - 時間窗口大小 interval

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

d)使用 ZCOUNT 獲取當前剩余 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 實現的代碼示例：https://github.com/peterkhayes/rolling-rate-limiter/blob/master/index.js

由于滑動日志算法的空間復雜度較其他算法高，使用滑動日志算法時，需要注意監控 Redis 內存的使用量。

4)并發控制

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

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

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

4 擴展的一些思考

分布式流控帶來了網絡通信、加鎖同步等開銷，會對性能帶來一定影響。同時分布式環境的可靠性也會帶來更多挑戰。如何設計一個高性能、高可靠性的分布式流控系統?這可能是個涉及到整個系統方方面面的大話題。

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

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

2)選擇一個合適的緩存系統保存流控的動態數據，這個一般跟著公司的統一技術架構走。

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

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

5)很多時候對精度的要求沒那么高，因為一般都會允許一定的突發量。這時候可以做一些性能的優化。性能的最大瓶頸在于每次請求都會訪問一次緩存，我之前在設計時就采用了一種折中的辦法：

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

五 總結

分布式流控的算法其實是單機流控的延伸，算法本質是一樣的。這里按我的個人理解總結了上述幾種流控算法的復雜度和適用場景。

??