話說在 Spring Cloud Gateway 問世之前，Spring Cloud 的微服務世界裡，閘道器一定非 Netflix Zuul 莫屬。但是由於 Zuul 1。x 存在的一些問題，比如阻塞式的 API，不支援 WebSocket 等，一直被人所詬病，而且 Zuul 升級新版本依賴於 Netflix 公司，經過幾次跳票之後，Spring 開源社群決定推出自己的閘道器元件，替代 Netflix Zuul。
從 18 年 6 月 Spring Cloud 釋出的 Finchley 版本開始，Spring Cloud Gateway 逐漸嶄露頭角，它基於 Spring 5。0、Spring Boot 2。0 和 Project Reactor 等技術開發，不僅支援響應式和無阻塞式的技術 API，而且支援 WebSocket，和 Spring 框架緊密整合。儘管 Zuul 後來也推出了 2。x 版本，在底層使用了非同步無阻塞式的 API，大大改善了其效能，但是目前看來 Spring 並沒有打算繼續整合它的計劃。
根據官網的描述，Spring Cloud Gateway 的主要特性如下：
Built on Spring Framework 5， Project Reactor and Spring Boot 2。0
Able to match routes on any request attribute
Predicates and filters are specific to routes
Hystrix Circuit Breaker integration
Spring Cloud DiscoveryClient integration
Easy to write Predicates and Filters
Request Rate Limiting
Path Rewriting
可以看出 Spring Cloud Gateway 可以很方便地和 Spring Cloud 生態中的其他元件進行整合（比如：斷路器和伺服器），而且提供了一套簡單易寫的
斷言
（
Predicates
，有的地方也翻譯成
謂詞
）和
過濾器
（
Filters
）機制，可以對每個
路由
（
Routes
）進行特殊請求處理。
最近在專案中使用了什麼 Spring Cloud Gateway，並在它的基礎上實現了一些高階特性，如限流和留痕，在閘道器的使用過程中遇到了不少的挑戰，於是趁著專案結束，抽點時間系統地學習並總結下。這篇文章主要學習限流技術，首先我會介紹一些常見的限流場景和限流演算法，然後介紹一些關於限流的開源專案，學習別人是如何實現限流的，最後介紹我是如何在閘道器中實現限流的，並分享一些實現過程中的經驗和遇到的坑。
一、常見的限流場景
快取
、
降級
和
限流
被稱為高併發、分散式系統的三駕馬車，閘道器作為整個分散式系統中的第一道關卡，限流功能自然必不可少。透過限流，可以控制服務請求的速率，從而提高系統應對突發大流量的能力，讓系統更具彈性。限流有著很多實際的應用場景，比如雙十一的秒殺活動， 12306 的搶票等。
1。1 限流的物件
透過上面的介紹，我們對限流的概念可能感覺還是比較模糊，到底限流限的是什麼？顧名思義，限流就是限制流量，但這裡的流量是一個比較籠統的概念。如果考慮各種不同的場景，限流是非常複雜的，而且和具體的業務規則密切相關，可以考慮如下幾種常見的場景：
限制某個介面一分鐘內最多請求 100 次
限制某個使用者的下載速度最多 100KB/S
限制某個使用者同時只能對某個介面發起攻擊 5 路請求
限制某個 IP 來源禁止訪問任何請求
從上面的例子可以看出，根據不同的請求者和請求資源，可以組合出不同的限流規則。可以根據請求者的 IP 來進行限流，或者根據請求對應的使用者來限流，又或者根據某個特定的請求引數來限流。而限流的物件可以是請求的頻率，傳輸的速率，或者併發量等，其中最常見的兩個限流物件是請求頻率和併發量，他們對應的限流被稱為
請求頻率限流
（Request rate limiting）和
併發量限流
（Concurrent requests limiting）。
傳輸速率限流
在下載場景下比較常用，比如一些資源下載站會限制普通使用者的下載速度，只有購買會員才能提速，這種限流的做法實際上和請求頻率限流類似，只不過一個限制的是請求量的多少，一個限制的是請求資料報文的大小。這篇文章主要介紹請求頻率限流和併發量限流。
1。2 限流的處理方式
在系統中設計限流方案時，有一個問題值得設計者去仔細考慮，當請求者被限流規則攔截之後，我們該如何返回結果。一般我們有下面三種限流的處理方式：
拒絕服務
排隊等待
服務降級
最簡單的做法是拒絕服務，直接丟擲異常，返回錯誤資訊（比如返回 HTTP 狀態碼 429 Too Many Requests），或者給前端返回 302 重定向到一個錯誤頁面，提示使用者資源沒有了或稍後再試。但是對於一些比較重要的介面不能直接拒絕，比如秒殺、下單等介面，我們既不希望使用者請求太快，也不希望請求失敗，這種情況一般會將請求放到一個訊息佇列中排隊等待，訊息佇列可以起到削峰和限流的作用。第三種處理方式是服務降級，當觸發限流條件時，直接返回兜底資料，比如查詢商品庫存的介面，可以預設返回有貨。
1。3 限流的架構
針對不同的系統架構，需要使用不同的限流方案。如下圖所示，服務部署的方式一般可以分為單機模式和叢集模式：
單機模式的限流非常簡單，可以直接基於記憶體就可以實現，而叢集模式的限流必須依賴於某個“中心化”的元件，比如閘道器或 Redis，從而引出兩種不同的限流架構：
閘道器層限流
和
中介軟體限流
。
閘道器作為整個分散式系統的入口，承擔了所有的使用者請求，所以在閘道器中進行限流是最合適不過的。閘道器層限流有時也被稱為
接入層限流
。除了我們使用的 Spring Cloud Gateway，最常用的閘道器層元件還有 Nginx，可以透過它的
ngx_http_limit_req_module
模組，使用 limit_conn_zone、limit_req_zone、limit_rate 等指令很容易地實現併發量限流、請求頻率限流和傳輸速率限流。這裡不對 Nginx 作過多的說明，關於這幾個指令的詳細資訊可以 參考 Nginx 的官方文件。
另一種限流架構是
中介軟體限流
，可以將限流的邏輯下沉到服務層。但是叢集中的每個服務必須將自己的流量資訊統一彙總到某個地方供其他服務讀取，一般來說用 Redis 的比較多，Redis 提供的過期特性和 lua 指令碼執行非常適合做限流。除了 Redis 這種中介軟體，還有很多類似的分散式快取系統都可以使用，如 Hazelcast、Apache Ignite、Infinispan 等。
我們可以更進一步擴充套件上面的架構，將閘道器改為叢集模式，雖然這還是閘道器層限流架構，但是由於閘道器變成了叢集模式，所以閘道器必須依賴於中介軟體進行限流，這和上面討論的中介軟體限流沒有區別。關注公眾號架構之路，回覆：666，可獲取一份 2TB 架構師資料。
二、常見的限流演算法
透過上面的學習，我們知道限流可以分為請求頻率限流和併發量限流，根據系統架構的不同，又可以分為閘道器層限流和分散式限流。在不同的應用場景下，我們需要採用不同的限流演算法。這一節將介紹一些主流的限流演算法。
有一點要注意的是，利用池化技術也可以達到限流的目的，比如執行緒池或連線池，但這不是本文的重點。
2。1 固定視窗演算法（Fixed Window）
固定視窗演算法是一種最簡單的限流演算法，它根據限流的條件，將請求時間對映到一個時間視窗，再使用計數器累加訪問次數。譬如限流條件為每分鐘 5 次，那麼就按照分鐘為單位對映時間視窗，假設一個請求時間為 11：00：45，時間視窗就是 11：00：00 ~ 11：00：59，在這個時間視窗內設定一個計數器，每來一個請求計數器加一，當這個時間視窗的計數器超過 5 時，就觸發限流條件。當請求時間落在下一個時間視窗內時（11：01：00 ~ 11：01：59），上一個視窗的計數器失效，當前的計數器清零，重新開始計數。
計數器演算法非常容易實現，在單機場景下可以使用 AtomicLong、LongAdder 或 Semaphore 來實現計數，而在分散式場景下可以透過 Redis 的 INCR 和 EXPIRE 等命令並結合 EVAL 或 lua 指令碼來實現，Redis 官網提供了幾種簡單的實現方式。無論是請求頻率限流還是併發量限流都可以使用這個演算法。
不過這個演算法的缺陷也比較明顯，那就是存在嚴重的臨界問題。由於每過一個時間視窗，計數器就會清零，這使得限流效果不夠平滑，惡意使用者可以利用這個特點繞過我們的限流規則。如下圖所示，我們的限流條件本來是每分鐘 5 次，但是惡意使用者在 11：00：00 ~ 11：00：59 這個時間視窗的後半分鐘發起 5 次請求，接下來又在 11：01：00 ~ 11：01：59 這個時間視窗的前半分鐘發起 5 次請求，這樣我們的系統就在 1 分鐘內承受了 10 次請求。
2。2 滑動視窗演算法（Rolling Window 或 Sliding Window）
為了解決固定視窗演算法的臨界問題，可以將時間視窗劃分成更小的時間視窗，然後隨著時間的滑動刪除相應的小視窗，而不是直接滑過一個大視窗，這就是滑動視窗演算法。我們為每個小時間視窗都設定一個計數器，大時間視窗的總請求次數就是每個小時間視窗的計數器的和。如下圖所示，我們的時間視窗是 5 秒，可以按秒進行劃分，將其劃分成 5 個小視窗，時間每過一秒，時間視窗就滑過一秒：
每次處理請求時，都需要計算所有小時間視窗的計數器的和，考慮到效能問題，劃分的小時間視窗不宜過多，譬如限流條件是每小時 N 個，可以按分鐘劃分為 60 個視窗，而不是按秒劃分成 3600 個。當然如果不考慮效能問題，劃分粒度越細，限流效果就越平滑。相反，如果劃分粒度越粗，限流效果就越不精確，出現臨界問題的可能性也就越大，當劃分粒度為 1 時，滑動視窗演算法就退化成了固定視窗演算法。由於這兩種演算法都使用了計數器，所以也被稱為
計數器演算法
（Counters）。
進一步思考我們發現，如果劃分粒度最粗，也就是隻有一個時間視窗時，滑動視窗演算法退化成了固定視窗演算法；那如果我們把劃分粒度調到最細，又會如何呢？那麼怎樣才能讓劃分的時間視窗最細呢？時間視窗細到一定地步時，意味著每個時間視窗中只能容納一個請求，這樣我們可以省略計數器，只記錄每個請求的時間，然後統計一段時間內的請求數有多少個即可。具體的實現可以參考Redis sorted set 技巧 和Sliding window log 演算法。
2。3 漏桶演算法（Leaky Bucket）
除了計數器演算法，另一個很自然的限流思路是將所有的請求快取到一個佇列中，然後按某個固定的速度慢慢處理，這其實就是
漏桶演算法
（Leaky Bucket）。漏桶演算法假設將請求裝到一個桶中，桶的容量為 M，當桶滿時，請求被丟棄。在桶的底部有一個洞，桶中的請求像水一樣按固定的速度（每秒 r 個）漏出來。我們用下面這個形象的圖來表示漏桶演算法：
桶的上面是個水龍頭，我們的請求從水龍頭流到桶中，水龍頭流出的水速不定，有時快有時慢，這種忽快忽慢的流量叫做
Bursty flow
。如果桶中的水滿了，多餘的水就會溢位去，相當於請求被丟棄。從桶底部漏出的水速是固定不變的，可以看出漏桶演算法可以平滑請求的速率。
漏桶演算法可以透過一個佇列來實現，如下圖所示：
當請求到達時，不直接處理請求，而是將其放入一個佇列，然後另一個執行緒以固定的速率從佇列中讀取請求並處理，從而達到限流的目的。注意的是這個佇列可以有不同的實現方式，比如設定請求的存活時間，或將佇列改造成 PriorityQueue，根據請求的優先順序排序而不是先進先出。當然佇列也有滿的時候，如果佇列已經滿了，那麼請求只能被丟棄了。漏桶演算法有一個缺陷，在處理突發流量時效率很低，於是人們又想出了下面的令牌桶演算法。
2。4 令牌桶演算法（Token Bucket）
令牌桶演算法
（Token Bucket）是目前應用最廣泛的一種限流演算法，它的基本思想由兩部分組成：
生成令牌
和
消費令牌
。
生成令牌：假設有一個裝令牌的桶，最多能裝 M 個，然後按某個固定的速度（每秒 r 個）往桶中放入令牌，桶滿時不再放入；
消費令牌：我們的每次請求都需要從桶中拿一個令牌才能放行，當桶中沒有令牌時即觸發限流，這時可以將請求放入一個緩衝佇列中排隊等待，或者直接拒絕；
令牌桶演算法的圖示如下：
在上面的圖中，我們將請求放在一個緩衝佇列中，可以看出這一部分的邏輯和漏桶演算法幾乎一模一樣，只不過在處理請求上，一個是以固定速率處理，一個是從桶中獲取令牌後才處理。
仔細思考就會發現，令牌桶演算法有一個很關鍵的問題，就是桶大小的設定，正是這個引數可以讓令牌桶演算法具備處理突發流量的能力。譬如將桶大小設定為 100，生成令牌的速度設定為每秒 10 個，那麼在系統空閒一段時間的之後（桶中令牌一直沒有消費，慢慢的會被裝滿），突然來了 50 個請求，這時系統可以直接按每秒 50 個的速度處理，隨著桶中的令牌很快用完，處理速度又會慢慢降下來，和生成令牌速度趨於一致。這是令牌桶演算法和漏桶演算法最大的區別，漏桶演算法無論來了多少請求，只會一直以每秒 10 個的速度進行處理。當然，處理突發流量雖然提高了系統性能，但也給系統帶來了一定的壓力，如果桶大小設定不合理，突發的大流量可能會直接壓垮系統。
透過上面對令牌桶的原理分析，一般會有兩種不同的實現方式。第一種方式是啟動一個內部執行緒，不斷的往桶中新增令牌，處理請求時從桶中獲取令牌，和上面圖中的處理邏輯一樣。第二種方式不依賴於內部執行緒，而是在每次處理請求之前先實時計算出要填充的令牌數並填充，然後再從桶中獲取令牌。下面是第二種方式的一種經典實現，其中 capacity 表示令牌桶大小，refillTokensPerOneMillis 表示填充速度，每毫秒填充多少個，availableTokens 表示令牌桶中還剩多少個令牌，lastRefillTimestamp 表示上一次填充時間。
1public class TokenBucket { 2 3 private final long capacity； 4 private final double refillTokensPerOneMillis； 5 private double availableTokens； 6 private long lastRefillTimestamp； 7 8 public TokenBucket（long capacity， long refillTokens， long refillPeriodMillis） { 9 this。capacity = capacity；10 this。refillTokensPerOneMillis = （double） refillTokens / （double） refillPeriodMillis；11 this。availableTokens = capacity；12 this。lastRefillTimestamp = System。currentTimeMillis（）；13 }1415 synchronized public boolean tryConsume（int numberTokens） {16 refill（）；17 if （availableTokens < numberTokens） {18 return false；19 } else {20 availableTokens -= numberTokens；21 return true；22 }23 }2425 private void refill（） {26 long currentTimeMillis = System。currentTimeMillis（）；27 if （currentTimeMillis > lastRefillTimestamp） {28 long millisSinceLastRefill = currentTimeMillis - lastRefillTimestamp；29 double refill = millisSinceLastRefill * refillTokensPerOneMillis；30 this。availableTokens = Math。min（capacity， availableTokens + refill）；31 this。lastRefillTimestamp = currentTimeMillis；32 }33 }34}
可以像下面這樣建立一個令牌桶（桶大小為 100，且每秒生成 100 個令牌）：
1TokenBucket limiter = new TokenBucket（100， 100， 1000）；
從上面的程式碼片段可以看出，令牌桶演算法的實現非常簡單也非常高效，僅僅通過幾個變數的運算就實現了完整的限流功能。核心邏輯在於 refill（） 這個方法，在每次消費令牌時，計算當前時間和上一次填充的時間差，並根據填充速度計算出應該填充多少令牌。在重新填充令牌後，再判斷請求的令牌數是否足夠，如果不夠，返回 false，如果足夠，則減去令牌數，並返回 true。
在實際的應用中，往往不會直接使用這種原始的令牌桶演算法，一般會在它的基礎上作一些改進，比如，填充速率支援動態調整，令牌總數支援透支，基於 Redis 支援分散式限流等，不過總體來說還是符合令牌桶演算法的整體框架，我們在後面學習一些開源專案時對此會有更深的體會。
三、一些開源專案
有很多開源專案中都實現了限流的功能，這一節透過一些開源專案的學習，瞭解限流是如何實現的。
3。1 Guava 的 RateLimiter
Google Guava 是一個強大的核心庫，包含了很多有用的工具類，例如：集合、快取、併發庫、字串處理、I/O 等等。其中在併發庫中，Guava 提供了兩個和限流相關的類：RateLimiter 和 SmoothRateLimiter。Guava 的 RateLimiter 基於令牌桶演算法實現，不過在傳統的令牌桶演算法基礎上做了點改進，支援兩種不同的限流方式：
平滑突發限流
（SmoothBursty） 和
平滑預熱限流
（SmoothWarmingUp）。
下面的方法可以建立一個平滑突發限流器（SmoothBursty）：
1RateLimiter limiter = RateLimiter。create（5）；
RateLimiter。create（5） 表示這個限流器容量為 5，並且每秒生成 5 個令牌，也就是每隔 200 毫秒生成一個。我們可以使用 limiter。acquire（） 消費令牌，如果桶中令牌足夠，返回 0，如果令牌不足，則阻塞等待，並返回等待的時間。我們連續請求幾次：
1System。out。println（limiter。acquire（））；2System。out。println（limiter。acquire（））；3System。out。println（limiter。acquire（））；4System。out。println（limiter。acquire（））；
輸出結果如下：
10。020。19823930。19608340。200609
可以看出限流器建立之後，初始會有一個令牌，然後每隔 200 毫秒生成一個令牌，所以第一次請求直接返回 0，後面的請求都會阻塞大約 200 毫秒。另外，SmoothBursty 還具有應對突發的能力，而且 還允許消費未來的令牌，比如下面的例子：
1RateLimiter limiter = RateLimiter。create（5）；2System。out。println（limiter。acquire（10））；3System。out。println（limiter。acquire（1））；4System。out。println（limiter。acquire（1））；
會得到類似下面的輸出：
10。021。99742830。19227340。200616
限流器建立之後，初始令牌只有一個，但是我們請求 10 個令牌竟然也通過了，只不過看後面請求發現，第二次請求花了 2 秒左右的時間把前面的透支的令牌給補上了。
Guava 支援的另一種限流方式是平滑預熱限流器（SmoothWarmingUp），可以透過下面的方法建立：
1RateLimiter limiter = RateLimiter。create（2， 3， TimeUnit。SECONDS）；2System。out。println（limiter。acquire（1））；3System。out。println（limiter。acquire（1））；4System。out。println（limiter。acquire（1））；5System。out。println（limiter。acquire（1））；6System。out。println（limiter。acquire（1））；
第一個引數還是每秒建立的令牌數量，這裡是每秒 2 個，也就是每 500 毫秒生成一個，後面的引數表示從冷啟動速率過渡到平均速率的時間間隔，也就是所謂的熱身時間間隔（warm up period）。我們看下輸出結果：
10。021。32928930。99437540。66288850。501287
第一個請求還是立即得到令牌，但是後面的請求和上面平滑突發限流就完全不一樣了，按理來說 500 毫秒就會生成一個令牌，但是我們發現第二個請求卻等了 1。3s，而不是 0。5s，後面第三個和第四個請求也等了一段時間。不過可以看出，等待時間在慢慢的接近 0。5s，直到第五個請求等待時間才開始變得正常。從第一個請求到第五個請求，這中間的時間間隔就是熱身階段，可以算出熱身的時間就是我們設定的 3 秒。
更多架構乾貨請關注公眾號“架構之路”。
架構之路
最有價值的架構師圈子和社群，我們分享各種網際網路架構技術乾貨，探討架構設計和實戰經驗，不定期送書、分享學習資料與面試題等。關注學習，早日成為架構師。8篇原創內容
公眾號
3。2 Bucket4j
Bucket4j是一個基於令牌桶演算法實現的強大的限流庫，它不僅支援單機限流，還支援透過諸如 Hazelcast、Ignite、Coherence、Infinispan 或其他相容 JCache API （JSR 107） 規範的分散式快取實現分散式限流。
在使用 Bucket4j 之前，我們有必要先了解 Bucket4j 中的幾個核心概念：
Bucket
Bandwidth
Refill
Bucket 介面代表了令牌桶的具體實現，也是我們操作的入口。它提供了諸如 tryConsume 和 tryConsumeAndReturnRemaining 這樣的方法供我們消費令牌。可以透過下面的構造方法來建立Bucket：
1Bucket bucket = Bucket4j。builder（）。addLimit（limit）。build（）；2if（bucket。tryConsume（1）） {3 System。out。println（“ok”）；4} else {5 System。out。println（“error”）；6}
Bandwidth 的意思是頻寬， 可以理解為限流的規則。Bucket4j 提供了兩種方法來建立 Bandwidth：simple 和 classic。下面是 simple 方式建立的 Bandwidth，表示桶大小為 10，填充速度為每分鐘 10 個令牌：
1Bandwidth limit = Bandwidth。simple（10， Duration。ofMinutes（1））；
simple方式桶大小和填充速度是一樣的，classic 方式更靈活一點，可以自定義填充速度，下面的例子表示桶大小為 10，填充速度為每分鐘 5 個令牌：
1Refill filler = Refill。greedy（5， Duration。ofMinutes（1））；2Bandwidth limit = Bandwidth。classic（10， filler）；
其中，Refill 用於填充令牌桶，可以透過它定義填充速度，Bucket4j 有兩種填充令牌的策略：間隔策略（intervally） 和 貪婪策略（greedy）。在上面的例子中我們使用的是貪婪策略，如果使用間隔策略可以像下面這樣建立 Refill：
1Refill filler = Refill。intervally（5， Duration。ofMinutes（1））；
所謂間隔策略指的是每隔一段時間，一次性的填充所有令牌，比如上面的例子，會每隔一分鐘，填充 5 個令牌，如下所示：
而貪婪策略會盡可能貪婪的填充令牌，同樣是上面的例子，會將一分鐘劃分成 5 個更小的時間單元，每隔 12 秒，填充 1 個令牌，如下所示：
在瞭解了 Bucket4j 中的幾個核心概念之後，我們再來看看官網介紹的一些特性：
基於令牌桶演算法
高效能，無鎖實現
不存在精度問題，所有計算都是基於整型的
支援透過符合 JCache API 規範的分散式快取系統實現分散式限流
支援為每個 Bucket 設定多個 Bandwidth
支援同步和非同步 API
支援可插拔的監聽 API，用於整合監控和日誌
不僅可以用於限流，還可以用於簡單的排程
Bucket4j 提供了豐富的文件，推薦在使用 Bucket4j 之前，先把官方文件中的 基本用法 和 高階特性 仔細閱讀一遍。另外，關於 Bucket4j 的使用，推薦這篇文章 Rate limiting Spring MVC endpoints with bucket4j，這篇文章詳細的講解了如何在 Spring MVC 中使用攔截器和 Bucket4j 打造業務無侵入的限流方案，另外還講解了如何使用 Hazelcast 實現分散式限流；另外，Rate Limiting a Spring API Using Bucket4j 這篇文章也是一份很好的入門教程，介紹了 Bucket4j 的基礎知識，在文章的最後還提供了 Spring Boot Starter 的整合方式，結合 Spring Boot Actuator 很容易將限流指標整合到監控系統中。
和 Guava 的限流器相比，Bucket4j 的功能顯然要更勝一籌，畢竟 Guava 的目的只是用作通用工具類，而不是用於限流的。使用 Bucket4j 基本上可以滿足我們的大多數要求，不僅支援單機限流和分散式限流，而且可以很好的整合監控，搭配 Prometheus 和 Grafana 簡直完美。值得一提的是，有很多開源專案譬如 JHipster API Gateway 就是使用 Bucket4j 來實現限流的。
Bucket4j 唯一不足的地方是它只支援請求頻率限流，不支援併發量限流，另外還有一點，雖然 Bucket4j 支援分散式限流，但它是基於 Hazelcast 這樣的分散式快取系統實現的，不能使用 Redis，這在很多使用 Redis 作快取的專案中就很不爽，所以我們還需要在開源的世界裡繼續探索。
3。3 Resilience4j
Resilience4j 是一款輕量級、易使用的高可用框架。用過 Spring Cloud 早期版本的同學肯定都聽過 Netflix Hystrix，Resilience4j 的設計靈感就來自於它。自從 Hystrix 停止維護之後，官方也推薦大家使用 Resilience4j 來代替 Hystrix。
Resilience4j 的底層採用 Vavr，這是一個非常輕量級的 Java 函式式庫，使得 Resilience4j 非常適合函數語言程式設計。Resilience4j 以裝飾器模式提供對函式式介面或 lambda 表示式的封裝，提供了一波高可用機制：
重試（Retry）
、
熔斷（Circuit Breaker）
、
限流（Rate Limiter）
、
限時（Timer Limiter）
、
隔離（Bulkhead）
、
快取（Caceh）
和
降級（Fallback）
。我們重點關注這裡的兩個功能：限流（Rate Limiter） 和 隔離（Bulkhead），Rate Limiter 是請求頻率限流，Bulkhead 是併發量限流。
Resilience4j 提供了兩種限流的實現：
SemaphoreBasedRateLimiter
和
AtomicRateLimiter
。
SemaphoreBasedRateLimiter
基於訊號量實現，使用者的每次請求都會申請一個訊號量，並記錄申請的時間，申請透過則允許請求，申請失敗則限流，另外有一個內部執行緒會定期掃描過期的訊號量並釋放，很顯然這是令牌桶的演算法。
AtomicRateLimiter
和上面的經典實現類似，不需要額外的執行緒，在處理每次請求時，根據距離上次請求的時間和生成令牌的速度自動填充。關於這二者的區別可以參考文章 Rate Limiter Internals in Resilience4j。
Resilience4j 也提供了兩種隔離的實現：
SemaphoreBulkhead
和
ThreadPoolBulkhead
，透過訊號量或執行緒池控制請求的併發數，具體的用法參考官方文件，這裡不再贅述。
下面是一個同時使用限流和隔離的例子：
1// 建立一個 Bulkhead，最大併發量為 150 2BulkheadConfig bulkheadConfig = BulkheadConfig。custom（） 3 。maxConcurrentCalls（150） 4 。maxWaitTime（100） 5 。build（）； 6Bulkhead bulkhead = Bulkhead。of（“backendName”， bulkheadConfig）； 7 8// 建立一個 RateLimiter，每秒允許一次請求 9RateLimiterConfig rateLimiterConfig = RateLimiterConfig。custom（）10 。timeoutDuration（Duration。ofMillis（100））11 。limitRefreshPeriod（Duration。ofSeconds（1））12 。limitForPeriod（1）13 。build（）；14RateLimiter rateLimiter = RateLimiter。of（“backendName”， rateLimiterConfig）；1516// 使用 Bulkhead 和 RateLimiter 裝飾業務邏輯17Supplier
Resilience4j 在功能特性上比 Bucket4j 強大不少，而且還支援併發量限流。不過最大的遺憾是，Resilience4j 不支援分散式限流。
更多架構乾貨請關注公眾號“架構之路”。
架構之路
最有價值的架構師圈子和社群，我們分享各種網際網路架構技術乾貨，探討架構設計和實戰經驗，不定期送書、分享學習資料與面試題等。關注學習，早日成為架構師。8篇原創內容
公眾號
3。4 其他
網上還有很多限流相關的開源專案，不可能一一介紹，這裡列出來的只是冰山之一角：
https：//github。com/mokies/ratelimitj
https：//github。com/wangzheng0822/ratelimiter4j
https：//github。com/wukq/rate-limiter
https：//github。com/marcosbarbero/spring-cloud-zuul-ratelimit
https：//github。com/onblog/SnowJena
https：//gitee。com/zhanghaiyang/spring-boot-starter-current-limiting
https：//github。com/Netflix/concurrency-limits
可以看出，限流技術在實際專案中應用非常廣泛，大家對實現自己的限流演算法樂此不疲，新演算法和新實現層出不窮。但是找來找去，目前還沒有找到一款開源專案完全滿足我的需求。
我的需求其實很簡單，需要同時滿足兩種不同的限流場景：請求頻率限流和併發量限流，並且能同時滿足兩種不同的限流架構：單機限流和分散式限流。
下面我們就開始在 Spring Cloud Gateway 中實現這幾種限流，透過前面介紹的那些專案，我們取長補短，基本上都能用比較成熟的技術實現，只不過對於最後一種情況，分散式併發量限流，網上沒有搜到現成的解決方案，在和同事討論了幾個晚上之後，想出一種新型的基於雙視窗滑動的限流演算法，我在這裡拋磚引玉，歡迎大家批評指正，如果大家有更好的方法，也歡迎討論。
關注公眾號架構之路，回覆：666，可獲取一份 2TB 架構師資料。
四、在閘道器中實現限流
在文章一開始介紹 Spring Cloud Gateway 的特性時，我們注意到其中有一條 Request Rate Limiting，說明閘道器自帶了限流的功能，但是 Spring Cloud Gateway 自帶的限流有很多限制，譬如不支援單機限流，不支援併發量限流，而且它的請求頻率限流也是不盡人意，這些都需要我們自己動手來解決。
4。1 實現單機請求頻率限流
Spring Cloud Gateway 中定義了關於限流的一個介面 RateLimiter，如下：
1public interface RateLimiter
這個介面就一個方法 isAllowed，第一個引數 routeId 表示請求路由的 ID，根據 routeId 可以獲取限流相關的配置，第二個引數 id 表示要限流的物件的唯一標識，可以是使用者名稱，也可以是 IP，或者其他的可以從 ServerWebExchange 中得到的資訊。我們看下 RequestRateLimiterGatewayFilterFactory 中對 isAllowed 的呼叫邏輯：
1@Override 2public GatewayFilter apply（Config config） { 3 // 從配置中得到 KeyResolver 4 KeyResolver resolver = getOrDefault（config。keyResolver， defaultKeyResolver）； 5 // 從配置中得到 RateLimiter 6 RateLimiter
從上面的的邏輯可以看出，透過實現 KeyResolver 介面的 resolve 方法就可以自定義要限流的物件了。
1public interface KeyResolver {2 Mono
比如下面的 HostAddrKeyResolver 可以根據 IP 來限流：
1public interface KeyResolver { 2 Mono
我們繼續看 Spring Cloud Gateway 的程式碼發現，RateLimiter 介面只提供了一個實現類 RedisRateLimiter：
很顯然是基於 Redis 實現的限流，雖說透過 Redis 也可以實現單機限流，但是總感覺有些大材小用，而且對於那些沒有 Redis 的環境很不友好。所以，我們要實現真正的本地限流。
我們從 Spring Cloud Gateway 的 pull request 中發現了一個新特性 Feature/local-rate-limiter，而且看提交記錄，這個新特性很有可能會合併到 3。0。0 版本中。我們不妨來看下這個 local-rate-limiter 的實現：LocalRateLimiter。java，可以看出它是基於 Resilience4有意思的是，這個類 還有一個早期版本，是基於 Bucket4j 實現的：
1public Mono
有意思的是，這個類 還有一個早期版本，是基於 Bucket4j 實現的：
1public Mono
實現方式都是類似的，在上面對 Bucket4j 和 Resilience4j 已經作了比較詳細的介紹，這裡不再贅述。不過從這裡也可以看出 Spring 生態圈對 Resilience4j 是比較看好的，我們也可以將其引入到我們的專案中。
4。2 實現分散式請求頻率限流
上面介紹瞭如何實現單機請求頻率限流，接下來再看下分散式請求頻率限流。這個就比較簡單了，因為上面說了，Spring Cloud Gateway 自帶了一個限流實現，就是 RedisRateLimiter，可以用於分散式限流。它的實現原理依然是基於令牌桶演算法的，不過實現邏輯是放在一段 lua 指令碼中的，我們可以在 src/main/resources/META-INF/scripts 目錄下找到該指令碼檔案 request_rate_limiter。lua：
1local tokens_key = KEYS［1］ 2local timestamp_key = KEYS［2］ 3 4local rate = tonumber（ARGV［1］） 5local capacity = tonumber（ARGV［2］） 6local now = tonumber（ARGV［3］） 7local requested = tonumber（ARGV［4］） 8 9local fill_time = capacity/rate10local ttl = math。floor（fill_time*2）1112local last_tokens = tonumber（redis。call（“get”， tokens_key））13if last_tokens == nil then14 last_tokens = capacity15end1617local last_refreshed = tonumber（redis。call（“get”， timestamp_key））18if last_refreshed == nil then19 last_refreshed = 020end2122local delta = math。max（0， now-last_refreshed）23local filled_tokens = math。min（capacity， last_tokens+（delta*rate））24local allowed = filled_tokens >= requested25local new_tokens = filled_tokens26local allowed_num = 027if allowed then28 new_tokens = filled_tokens - requested29 allowed_num = 130end3132if ttl > 0 then33 redis。call（“setex”， tokens_key， ttl， new_tokens）34 redis。call（“setex”， timestamp_key， ttl， now）35end3637return { allowed_num， new_tokens }
這段程式碼和上面介紹令牌桶演算法時用 Java 實現的那段經典程式碼幾乎是一樣的。這裡使用 lua 指令碼，主要是利用了 Redis 的單執行緒特性，以及執行 lua 指令碼的原子性，避免了併發訪問時可能出現請求量超出上限的現象。想象目前令牌桶中還剩 1 個令牌，此時有兩個請求同時到來，判斷令牌是否足夠也是同時的，兩個請求都認為還剩 1 個令牌，於是兩個請求都被允許了。
有兩種方式來配置 Spring Cloud Gateway 自帶的限流。第一種方式是透過配置檔案，比如下面所示的程式碼，可以對某個 route 進行限流：
1spring： 2 cloud： 3 gateway： 4 routes： 5 - id： test 6 uri： http：//httpbin。org：80/get 7 filters： 8 - name： RequestRateLimiter 9 args：10 key-resolver： ‘#{@hostAddrKeyResolver}’11 redis-rate-limiter。replenishRate： 112 redis-rate-limiter。burstCapacity： 3
其中，key-resolver 使用 SpEL 表示式 #{@beanName} 從 Spring 容器中獲取 hostAddrKeyResolver 物件，burstCapacity 表示令牌桶的大小，replenishRate 表示每秒往桶中填充多少個令牌，也就是填充速度。
第二種方式是透過下面的程式碼來配置：
1@Bean 2public RouteLocator myRoutes（RouteLocatorBuilder builder） { 3 return builder。routes（） 4 。route（p -> p 5 。path（“/get”） 6 。filters（filter -> filter。requestRateLimiter（） 7 。rateLimiter（RedisRateLimiter。class， rl -> rl。setBurstCapacity（3）。setReplenishRate（1））。and（）） 8 。uri（“http：//httpbin。org：80”）） 9 。build（）；10}
這樣就可以對某個 route 進行限流了。但是這裡有一點要注意，Spring Cloud Gateway 自帶的限流器有一個很大的坑，replenishRate 不支援設定小數，也就是說往桶中填充的 token 的速度最少為每秒 1 個，所以，如果我的限流規則是每分鐘 10 個請求（按理說應該每 6 秒填充一次，或每秒填充 1/6 個 token），這種情況 Spring Cloud Gateway 就沒法正確的限流。網上也有人提了 issue，support greater than a second resolution for the rate limiter，但還沒有得到解決。
4。3 實現單機併發量限流
上面學習 Resilience4j 的時候，我們提到了 Resilience4j 的一個功能特性，叫
隔離（Bulkhead）
。Bulkhead 這個單詞的意思是船的艙壁，利用艙壁可以將不同的船艙隔離起來，這樣如果一個船艙破損進水，那麼只損失這一個船艙，其它船艙可以不受影響。借鑑造船行業的經驗，這種模式也被引入到軟體行業，我們把它叫做 艙壁模式（Bulkhead pattern）。艙壁模式一般用於服務隔離，對於一些比較重要的系統資源，如 CPU、記憶體、連線數等，可以為每個服務設定各自的資源限制，防止某個異常的服務把系統的所有資源都消耗掉。這種服務隔離的思想同樣可以用來做併發量限流。
正如前文所述，Resilience4j 提供了兩種 Bulkhead 的實現：SemaphoreBulkhead 和 ThreadPoolBulkhead，這也正是艙壁模式常見的兩種實現方案：一種是帶計數的訊號量，一種是固定大小的執行緒池。考慮到多執行緒場景下的執行緒切換成本，預設推薦使用訊號量。
在作業系統基礎課程中，我們學習過兩個名詞：
互斥量（Mutex）
和
訊號量（Semaphores）
。互斥量用於執行緒的互斥，它和臨界區有點相似，只有擁有互斥物件的執行緒才有訪問資源的許可權，由於互斥物件只有一個，因此任何情況下只會有一個執行緒在訪問此共享資源，從而保證了多執行緒可以安全的訪問和操作共享資源。而訊號量是用於執行緒的同步，這是由荷蘭科學家 E。W。Dijkstra 提出的概念，它和互斥量不同，訊號允許多個執行緒同時使用共享資源，但是它同時設定了訪問共享資源的執行緒最大數目，從而可以進行併發量控制。
下面是使用訊號量限制併發訪問的一個簡單例子：
1public class SemaphoreTest { 2 3 private static ExecutorService threadPool = Executors。newFixedThreadPool（100）； 4 private static Semaphore semaphore = new Semaphore（10）； 5 6 public static void main（String［］ args） { 7 for （int i = 0； i < 100； i++） { 8 threadPool。execute（new Runnable（） { 9 @Override10 public void run（） {11 try {12 semaphore。acquire（）；13 System。out。println（“Request processing 。。。”）；14 semaphore。release（）；15 } catch （InterruptedException e） {16 e。printStack（）；17 }18 }19 }）；20 }21 threadPool。shutdown（）；22 }23}
這裡我們建立了 100 個執行緒同時執行，但是由於訊號量計數為 10，所以同時只能有 10 個執行緒在處理請求。說到計數，實際上，在 Java 裡除了 Semaphore 還有很多類也可以用作計數，比如 AtomicLong 或 LongAdder，這在併發量限流中非常常見，只是無法提供像訊號量那樣的阻塞能力：
1public class AtomicLongTest { 2 3 private static ExecutorService threadPool = Executors。newFixedThreadPool（100）； 4 private static AtomicLong atomic = new AtomicLong（）； 5 6 public static void main（String［］ args） { 7 for （int i = 0； i < 100； i++） { 8 threadPool。execute（new Runnable（） { 9 @Override10 public void run（） {11 try {12 if（atomic。incrementAndGet（） > 10） {13 System。out。println（“Request rejected 。。。”）；14 return；15 }16 System。out。println（“Request processing 。。。”）；17 atomic。decrementAndGet（）；18 } catch （InterruptedException e） {19 e。printStack（）；20 }21 }22 }）；23 }24 threadPool。shutdown（）；25 }26}
4.4 實現分散式併發量限流
透過在單機實現併發量限流，我們掌握了幾種常用的手段：訊號量、執行緒池、計數器，這些都是單機上的概念。那麼稍微拓展下，如果能實現分散式訊號量、分散式執行緒池、分散式計數器，那麼實現分散式併發量限流不就易如反掌了嗎？
關於分散式執行緒池，是我自己杜撰的詞，在網上並沒有找到類似的概念，比較接近的概念是資源排程和分發，但是又感覺不像，這裡直接忽略吧。
關於分散式訊號量，還真有這樣的東西，比如 Apache Ignite 就提供了 IgniteSemaphore 用於建立分散式訊號量，它的使用方式和 Semaphore 非常類似。使用 Redis 的 ZSet 也可以實現分散式訊號量，比如 這篇部落格介紹的方法，還有《Redis in Action》這本電子書中也提到了這樣的例子，教你如何實現 Counting semaphores。另外，Redisson 也實現了基於 Redis 的分散式訊號量 RSemaphore，用法也和 Semaphore 類似。使用分散式訊號量可以很容易實現分散式併發量限流，實現方式和上面的單機併發量限流幾乎是一樣的。
最後，關於分散式計數器，實現方案也是多種多樣。比如使用 Redis 的 INCR 就很容易實現，更有甚者，使用 MySQL 資料庫也可以實現。只不過使用計數器要注意操作的原子性，每次請求時都要經過這三步操作：取計數器當前的值、判斷是否超過閾值，超過則拒絕、將計數器的值自增。這其實和訊號量的 P 操作是一樣的，而釋放就對應 V 操作。
所以，利用分散式訊號量和計數器就可以實現併發量限流了嗎？問題當然沒有這麼簡單。實際上，上面透過訊號量和計數器實現單機併發量限流的程式碼片段有一個嚴重 BUG：
1semaphore。acquire（）；2System。out。println（“Request processing 。。。”）；3semaphore。release（）；
想象一下如果在處理請求時出現異常了會怎麼樣？很顯然，訊號量被該執行緒獲取了，但是卻永遠不會釋放，如果請求異常多了，這將導致訊號量被佔滿，最後一個請求也進不來。在單機場景下，這個問題可以很容易解決，加一個 finally 就行了：
1try {2 semaphore。acquire（）；3 System。out。println（“Request processing 。。。”）；4} catch （InterruptedException e） {5 e。printStack（）；6} finally {7 semaphore。release（）；8}
由於無論出現何種異常，finally 中的程式碼一定會執行，這樣就保證了訊號量一定會被釋放。但是在分散式系統中，就不是加一個 finally 這麼簡單了。這是因為在分散式系統中可能存在的異常不一定是可被捕獲的程式碼異常，還有可能是服務崩潰或者不可預知的系統宕機，就算是正常的服務重啟也可能導致分散式訊號量無法釋放。
對於這個問題，我和幾個同事連續討論了幾個晚上，想出了兩種解決方法：第一種方法是使用帶 TTL 的計數器，第二種方法是基於雙視窗滑動的一種比較 tricky 的演算法。
第一種方法比較容易理解，我們為每個請求賦予一個唯一 ID，並在 Redis 裡寫入一個鍵值對，key 為 requests_xxx（xxx 為請求 ID），value 為 1，並給這個 key 設定一個 TTL（如果你的應用中存在耗時非常長的請求，譬如對於一些 WebSockket 請求可能會持續幾個小時，還需要開一個執行緒定期去重新整理這個 key 的 TTL）。然後在判斷併發量時，使用 KEYS 命令查詢 requests_* 開頭的 key 的個數，就可以知道當前一共有多少個請求，如果超過併發量上限則拒絕請求。這種方法可以很好的應對服務崩潰或重啟的問題，由於每個 key 都設定了 TTL，所以經過一段時間後，這些 key 就會自動消失，就不會出現訊號量佔滿不釋放的情況了。但是這裡使用 KEYS 命令查詢請求個數是一個非常低效的做法，在請求量比較多的情況下，閘道器的效能會受到嚴重影響。我們可以把 KEYS 命令換成 SCAN，效能會得到些許提升，但總體來說效果還是很不理想的。
針對第一種方法，我們可以進一步最佳化，不用為每個請求寫一個鍵值對，而是為每個分散式系統中的每個例項賦予一個唯一 ID，並在 Redis 裡寫一個鍵值對，key 為 instances_xxx（xxx 為例項 ID），value 為這個例項當前的併發量。同樣的，我們為這個 key 設定一個 TTL，並且開啟一個執行緒定期去重新整理這個 TTL。每接受一個請求後，計數器加一，請求結束，計數器減一，這和單機場景下的處理方式一樣，只不過在判斷併發量時，還是需要使用 KEYS 或 SCAN 獲取所有的例項，並計算出併發量的總和。不過由於例項個數是有限的，效能比之前的做法有了明顯的提升。
第二種方法我稱之為
雙視窗滑動演算法
，結合了 TTL 計數器和滑動視窗演算法。我們按分鐘來設定一個時間視窗，在 Redis 裡對應 202009051130 這樣的一個 key，value 為計數器，表示請求的數量。當接受一個請求後，在當前的時間視窗中加一，當請求結束，在當前的時間視窗中減一，注意，接受請求和請求結束的時間視窗可能不是同一個。另外，我們還需要一個本地列表來記錄當前例項正在處理的所有請求和請求對應的時間視窗，並透過一個小於時間視窗的定時執行緒（如 30 秒）來遷移過期的請求，所謂過期，指的是請求的時間視窗和當前時間視窗不一致。那麼具體如何遷移呢？我們首先需要統計列表中一共有多少請求過期了，然後將列表中的過期請求時間更新為當前時間視窗，並從 Redis 中上一個時間視窗移動相應數量到當前時間視窗，也就是上一個時間視窗減 X，當前時間視窗加 X。由於遷移執行緒定期執行，所以過期的請求總是會被移動到當前視窗，最終 Redis 中只有當前時間視窗和上個時間視窗這兩個時間視窗中有資料，再早一點的視窗時間中的資料會被往後遷移，所以可以給這個 key 設定一個 3 分鐘或 5 分鐘的 TTL。判斷併發量時，由於只有兩個 key，只需要使用 MGET 獲取兩個值相加即可。下面的流程圖詳細描述了演算法的執行過程：
其中有幾個需要注意的細節：
請求結束時，直接在 Redis 中當前時間視窗減一即可，就算是負數也沒關係。請求列表中的該請求不用急著刪除，可以打上結束標記，在遷移執行緒中統一刪除（當然，如果請求的開始時間和結束時間在同一個視窗，可以直接刪除）；
遷移的時間間隔要小於時間視窗，一般設定為 30s；
Redis 中的 key 一定要設定 TTL，時間至少為 2 個時間視窗，一般設定為 3 分鐘；
遷移過程涉及到“從上一個時間視窗減”和“在當前時間視窗加”兩個操作，要注意操作的原子性；
獲取當前併發量可以透過 MGET 一次性讀取兩個時間視窗的值，不用 GET 兩次；
獲取併發量和判斷併發量是否超限，這個過程也要注意操作的原子性。
總結
閘道器作為微服務架構中的重要一環，充當著一夫當關萬夫莫開的角色，所以對閘道器服務的穩定性要求和效能要求都非常高。為保證閘道器服務的穩定性，一代又一代的程式設計師們前仆後繼，想出了十八般武藝：限流、熔斷、隔離、快取、降級、等等等等。這篇文章從限流入手，詳細介紹了限流的場景和演算法，以及原始碼實現和可能踩到的坑。儘管限流只是閘道器的一個非常小的功能，但卻影響到閘道器的方方面面，在系統架構的設計中至關重要。
雖然我試著從不同的角度希望把限流介紹的更完全，但終究是管中窺豹，只見一斑，還有很多的內容沒有介紹到，比如阿里開源的 Sentinel 元件也可以用於限流，因為篇幅有限未能展開。另外前文提到的 Netflix 不再維護 Hystrix 專案，這是因為他們把精力放到另一個限流專案 concurrency-limits 上了，這個專案的目標是打造一款自適應的，極具彈性的限流元件，它借鑑了 TCP 擁塞控制的演算法（TCP congestion control algorithm），實現系統的自動限流，感興趣的同學可以去它的專案主頁瞭解更多內容。
