一 流控的場景
流控的意義其實無需多言了。最常用的場景下，流控是為了保護下遊有限的資源不被流量沖垮，保證服務的可用性，一般允許流控的門檻值有一定的彈性，偶爾的超量通路是可以接受的。
有的時候，流控服務于收費模式，比如某些雲廠商會對調用 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 - 申請時配置設定的 namespace
key - key 清單，不超過 1k
value - 增加量
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 大小，判斷是否需要流控。
long now = System.currentTimeMillis();
long maxScoreMs = now - windowInSecond * 1000;
Transaction redis = jedisPool.getResource().multi();
redis.zremrangeByScore(key, 0, maxScoreMs);
redis.zadd(key, now, now + "-" + Math.random()); // 加入一個随機值使得member不重複
redis.expire(key, windowInSecond);
redis.exec(); 另一個 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%），使得剩餘的流量能夠平滑地過渡。
五 總結
分布式流控的算法其實是單機流控的延伸，算法本質是一樣的。這裡按我的個人了解總結了上述幾種流控算法的複雜度和适用場景。