服務限流概念
随着現在微服務、分布式系統的發展，各個服務之間的互相調用越來越複雜。為了保證自身服務的穩定性與高可用，需要對超出自身服務處理能力之外的請求進行攔截。
限流的主要目标：
- 防止服務被突發流量沖垮
- 防止惡意請求和攻擊
- 限流的處理方式：
- 拒絕服務
- 排隊等待
- 服務降級
最簡單的做法是拒絕服務，直接抛出異常，傳回錯誤資訊（比如傳回 HTTP 狀态碼 429 Too Many Requests），或者給前端傳回 302 重定向到一個錯誤頁面，提示使用者資源沒有了或稍後再試。但是對于一些比較重要的接口不能直接拒絕，比如秒殺、下單等接口，我們既不希望使用者請求太快，也不希望請求失敗，這種情況一般會将請求放到一個消息隊列中排隊等待，消息隊列可以起到削峰和限流的作用。第三種處理方式是服務降級，當觸發限流條件時，直接傳回兜底資料，比如查詢商品庫存的接口，可以預設傳回有貨。
限流的架構
針對不同的系統架構，需要使用不同的限流方案。如下圖所示，服務部署的方式一般可以分為單機模式和叢集模式：
單機模式的限流非常簡單，可以直接基于記憶體就可以實作，而叢集模式的限流必須依賴于某個“中心化”的元件，比如網關或 Redis。叢集中的每個服務必須将自己的流量資訊統一彙總到某個地方供其他服務讀取，一般來說用 Redis 的比較多，Redis 提供的過期特性和 lua 腳本執行非常适合做限流。
常用限流算法
1 固定視窗計數器
固定視窗計數器(Fixed Window)算法的實作思路非常簡單，首先維護一個計數器，将機關時間段當做一個視窗，計數器記錄這個視窗接收請求的次數。
- 當次數少于限流閥值，就允許通路，并且計數器+1
- 當次數大于限流閥值，就拒絕通路
- 目前的時間視窗過去之後，計數器清零
假設機關時間是1秒，限流閥值為3。在機關時間1秒内，每來一個請求,計數器就加1，如果計數器累加的次數超過限流閥值3，後續的請求全部拒絕。等到1s結束後，計數器清0，重新開始計數。如下圖：
計數器算法在單機場景下可以使用 AtomicLong、LongAdder 或 Semaphore 來實作計數，而在分布式場景下可以通過 Redis 的 INCR 和 EXPIRE 等指令并結合 EVAL 或 lua 腳本來實作。
主要優點：實作簡單，容易了解
主要缺點：
- 一段時間内（不超過時間視窗）系統服務不可用
比如視窗大小為1s，限流大小為5，然後恰好在某個視窗的第1ms來了5個請求，然後第2ms-999ms的請求就都會被拒絕，這段時間使用者會感覺系統服務不可用。
- 存在臨界問題，視窗切換時，可能會産生兩倍于門檻值流量的請求
比如視窗大小為1s，限流大小為5，然後恰好在某個視窗的第0.8-1s來了5個請求，視窗前期沒有請求，是以這5個請求都會通過。再恰好，下一個視窗的第0-0.2s又來了5個請求，也全部通過了，那也就是在0.4s之内通過了10個請求，而我們設定的門檻值是5，通過的請求達到了門檻值的兩倍。
代碼實作：
/*** 固定視窗計數器法*/publicclassRateLimiterSimpleWindow {// 門檻值 privatestatic Integer QPS = 5;// 時間視窗（毫秒） privatestaticlong TIME_WINDOWS = 1000;// 計數器 privatestatic AtomicInteger REQ_COUNT = new AtomicInteger(); privatestaticlong LAST_REQUEST_TIME = System.currentTimeMillis(); publicsynchronizedstaticbooleantryAcquire() {if ((System.currentTimeMillis() - LAST_REQUEST_TIME) > TIME_WINDOWS) { REQ_COUNT.set(0); LAST_REQUEST_TIME = System.currentTimeMillis(); }return REQ_COUNT.incrementAndGet() <= QPS; } publicstaticvoidmain(String[] args) throws InterruptedException {for (int i = 0; i < 10; i++) { Thread.sleep(100); LocalTime now = LocalTime.now();if (!tryAcquire()) { System.out.println(now + " 被限流"); } else { System.out.println(now + " 做點什麼"); } } }} 2 滑動視窗計數器
滑動視窗算法是固定視窗算法的改進，解決了固定視窗切換時可能會産生兩倍于門檻值流量請求的缺點。
滑動視窗算法在固定視窗的基礎上，将一個計時視窗分成了若幹個小視窗，然後每個小視窗維護一個獨立的計數器。當請求的時間大于目前視窗的最大時間時，則将計時視窗向右平移一個小視窗。平移時，将最左邊小視窗的資料丢棄，将新的請求放在最右邊的小視窗中。同時要保證整個視窗中所有小視窗的請求數目之和不能超過設定的門檻值。
一張圖解釋滑動視窗算法，如下：
假設機關時間還是1s，滑動視窗算法把它劃分為5個小周期，也就是滑動視窗（機關時間）被劃分為5個小格子。每格表示0.2s。每過0.2s，時間視窗就會往右滑動一格。然後呢，每個小周期，都有自己獨立的計數器，如果請求是0.83s到達的，0.8~1.0s對應的計數器就會加1。
我們來看下滑動視窗是如何解決臨界問題的？
假設我們1s内的限流門檻值還是5個請求，0.8~1.0s内（比如0.9s的時候）來了5個請求，落在黃色格子裡。時間過了1.0s這個點之後，又來5個請求，落在紫色格子裡。如果**是固定視窗算法，是不會被限流的**，但是**滑動視窗的話，每過一個小周期，它會右移一個小格**。過了1.0s這個點後，會右移一小格，目前的機關時間段是0.2~1.2s，這個區域的請求已經超過限定的5了，已觸發限流啦，實際上，紫色格子的請求都被拒絕啦。
TIPS: 當滑動視窗的格子周期劃分的越多，那麼滑動視窗的滾動就越平滑，限流的統計就會越精确。
主要優點：避免了計數器固定視窗算法固定視窗切換時可能會産生兩倍于門檻值流量請求的問題；
主要缺點：
- 流量超過就必須抛棄或者走降級邏輯
- 對流量控制不夠精細，不能限制集中在短時間内的流量，也不能削峰填谷
代碼實作：
packagecom.wdbyte.rate.limiter;importjava.time.LocalDateTime;importjava.time.ZoneOffset;importjava.util.Iterator;importjava.util.Map;importjava.util.TreeMap;/*** 滑動視窗限流工具類** @author https://www.wdbyte.com*/publicclassRateLimitSlideWindow { /** * 每個小格子的時間視窗大小（機關時間是1分鐘，10s一個小格子視窗，一共6個格子） */ privateint SUB_CYCLE = 10; /** * 每分鐘限流請求數 */ privateint thresholdPerMin = 10; /** * 計數器, key為目前視窗的開始時間值秒，value為目前視窗的計數 */ privatefinal TreeMap<Long, Integer> counters = new TreeMap<>(); /** * 滑動視窗時間算法實作 */ publicbooleanslidingWindowsTryAcquire() { //擷取目前時間在哪個小周期視窗 long currentTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC); long currentWindowTime = currentTime / SUB_CYCLE * SUB_CYCLE; //目前視窗總請求數 int currentWindowNum = countCurrentWindow(currentWindowTime); //超過閥值限流 if (currentWindowNum >= thresholdPerMin) { returnfalse; } //計數器+1 counters.merge(currentWindowTime, 1, Integer::sum); returntrue; } /** * 統計目前視窗的請求數 */ privateintcountCurrentWindow(long currentWindowTime) { //計算滑動視窗第一格的開始位置 long startTime = currentWindowTime - (long) SUB_CYCLE * (60 / SUB_CYCLE - 1); int count = 0; //周遊存儲的計數器 Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Long, Integer> entry = iterator.next(); // 删除無效過期的子視窗計數器 if (entry.getKey() < startTime) { iterator.remove(); } else { //累加目前視窗的所有計數器之和 count = count + entry.getValue(); } } return count; } publicstaticvoidmain(String[] args) throws Exception { RateLimitSlideWindow rateLimitSlideWindow = new RateLimitSlideWindow(); int i = 0; while (i++ < 10) { boolean res = rateLimitSlideWindow.slidingWindowsTryAcquire(); System.out.println("第"+ i + "次請求結果：" + res + rateLimitSlideWindow.counters); } }} 3 漏桶算法
如下圖所示，水滴持續滴入漏桶中，底部定速流出。如果水滴滴入的速率大于流出的速率，當存水超過桶的大小的時候就會溢出。規則如下：
- 請求來了放入桶中
- 桶内請求量滿了拒絕請求
- 服務定速從桶内拿請求處理
可以看到水滴對應的就是請求。它的特點就是**寬進嚴出**，無論請求多少，請求的速率有多大，都按照固定的速率流出，對應的就是服務按照固定的速率處理請求。面對突發請求，服務的處理速度和平時是一樣的。
主要優點：漏桶的漏出速率是固定的，可以起到整流的作用
雖然請求的流量可能具有随機性，忽大忽小，但是經過漏鬥算法之後，變成了有固定速率的穩定流量，進而對下遊的系統起到保護作用。可以削峰填谷。
漏鬥算法一般用于保護第三方的系統，比如自身的系統需要調用第三方的接口，為了保護第三方的系統不被自身的調用打垮，便可以通過漏鬥算法進行限流，保證自身的流量平穩的打到第三方的接口上。
缺點：響應延遲，并且不能解決流量突發的問題
如果突增的流量對于系統來說完全沒有壓力，使用漏桶算法，其實是對系統性能的浪費。
代碼實作：
publicclassLeakBucketLimiter {
/**
* 每秒處理請求數（出水率）
*/
privatelong rate = 2;
/**
* 桶容量
*/
privatelong capacity = 10;
/**
* 桶内剩餘水量
*/
privatelong currentWater;
/**
* 上一次請求時間
*/
privatelong refreshTime = System.currentTimeMillis();
/**
* 漏桶算法
*
* @return
*/
publicsynchronizedbooleantryAcquire() {
//擷取系統目前時間
long currentTime = System.currentTimeMillis();
//流出的水量 =(目前時間-上次重新整理時間)* 出水率
long outWater = (currentTime - refreshTime) / 1000 * rate;
// 目前桶内剩餘水量 = 之前的桶内水量-流出的水量，不能小于0
currentWater = Math.max(0, currentWater - outWater);
// 重新整理時間
refreshTime = currentTime;
// 目前剩餘水量還是小于桶的容量，則請求放行
if (currentWater < capacity) {
currentWater++;
returntrue;
}
// 目前剩餘水量大于等于桶的容量，限流
returnfalse;
}
} 4 令牌桶算法
令牌桶和漏桶的原理類似，不過漏桶是**定速地流出**，而令牌桶是**定速地往桶裡塞入令牌**，然後請求隻有拿到了令牌才能通過，之後再被伺服器處理。當然令牌桶的大小也是有限制的，假設桶裡的令牌滿了之後，定速生成的令牌會丢棄。規則：
- 定速的往桶内放入令牌
- 令牌數量超過桶的限制，丢棄
- 請求來了先向桶内索要令牌，索要成功則通過被處理，反之拒絕
可以看出令牌桶在應對突發流量的時候，桶内假如有 100 個令牌，那麼這 100 個令牌可以馬上被取走，而不像漏桶那樣勻速的消費。是以在“應對突發流量的時候令牌桶表現的更佳”。
特點分析：
令牌桶算法是對漏桶算法的一種改進，除了能夠限制調用的平均速率，還允許一定程度的流量突發。一般用于保護自身的系統，對調用者進行限流，保護自身的系統不被突發的流量打垮。
代碼實作：
publicclassTokenBucketLimiter {
/**
* 每秒處理數（放入令牌數量）
*/
privatelong putTokenRate = 1;
/**
* 最後重新整理時間
*/
privatelong refreshTime = System.currentTimeMillis();
/**
* 令牌桶容量
*/
privatelong capacity = 10;
/**
* 目前桶内令牌數
*/
privatelong currentToken = 0L;
/**
* 漏桶算法
*
* @return
*/
booleantokenBucketTryAcquire() {
//擷取系統目前時間
long currentTime = System.currentTimeMillis();
//生成的令牌 =(目前時間-上次重新整理時間)* 放入令牌速率
long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate;
// 目前令牌數量 = 之前的桶内令牌數量+放入的令牌數量
currentToken = Math.min(capacity, generateToken + currentToken);
// 重新整理時間
refreshTime = currentTime;
//桶裡面還有令牌，請求正常處理
if (currentToken > 0) {
currentToken--; //令牌數量-1
returntrue;
}
returnfalse;
}
} 開源限流方案
1 RateLimiter
Guava的`RateLimiter`提供了令牌桶算法實作：平滑突發限流(SmoothBursty)和平滑預熱限流(SmoothWarmingUp)實作。
Guava 位址：https://github.com/google/guava
1、SmoothBursty：令牌的生成速度恒定。使用 RateLimiter.create(double permitsPerSecond) 建立的是 SmoothBursty 執行個體。
2、SmoothWarmingUp：令牌的生成速度持續提升，直到達到一個穩定的值。WarmingUp，顧名思義就是有一個熱身的過程。使用 RateLimiter.create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) 時建立就是 SmoothWarmingUp 執行個體，其中 warmupPeriod 就是熱身達到穩定速度的時間。
如下：建立一個限流器，設定每秒放置的令牌數為5個。傳回的RateLimiter對象可以保證1秒内不會給超過5個令牌，并且以固定速率進行放置，達到平滑輸出的效果。
publicvoidtestSmoothBursty() {
// 限流器容量為5，并且每秒生成5個令牌
RateLimiter r = RateLimiter.create(5);
for (int i = 0; i++ < 2; ) {
System.out.println("get 5 tokens: " + r.acquire(5) + "s");
System.out.println("get 1 tokens: " + r.acquire(1) + "s");
System.out.println("get 1 tokens: " + r.acquire(1) + "s");
System.out.println("get 1 tokens: " + r.acquire(1) + "s");
System.out.println("end");
}
/**
* 控制台輸出
* get 5 tokens: 0.0s 初始化時桶是空的，直接從空桶擷取5個令牌
* get 1 tokens: 0.998068s 滞後效應，需要替前一個請求進行等待
* get 1 tokens: 0.196288s
* get 1 tokens: 0.200394s
* end
* get 5 tokens: 0.195756s
* get 1 tokens: 0.995625s 滞後效應，需要替前一個請求進行等待
* get 1 tokens: 0.194603s
* get 1 tokens: 0.196866s
* end
*/
} 第一次請求之是以不需要等待是因為令牌桶的預消費特性。
2 Bucket4j
基于令牌桶算法實作的限流庫，Bucket4j 位址：https://github.com/vladimir-bukhtoyarov/bucket4j
Bucket4j不僅支援單機限流，還支援通過諸如 Hazelcast、Ignite、Coherence、Infinispan 或其他相容 JCache API (JSR 107) 規範的分布式緩存實作分布式限流。
缺點：隻支援請求頻率限流；不能使用redis做分布式限流。
Refill – 令牌的填充速度。
Bandwidth – 帶寬，也就是每秒能夠通過的流量，自動維護令牌生産。
Bucket – 桶，不論狀态，或是令牌的消費，`bucket`是我們操作的入口。
tryConsume：嘗試消費n個令牌，傳回布爾值，表示能夠消費或者不能夠消費，給我們判斷依據。
使用示例：建立一個容量為10的存儲桶，每秒填充5個令牌：
publicstaticvoidmain(String[] args) {
Bandwidth limit = Bandwidth.simple(10, Duration.ofSeconds(1));
Bucket bucket = Bucket4j.builder().addLimit(limit).build();
if(bucket.tryConsume(1)){
System.out.println("do something");
}else{
System.out.println("do nothing");
}
} 3 Hystrix
Netflix開源的熔斷元件，支援兩種資源隔離政策：THREAD（預設）或者SEMAPHORE
- 線程池：每個command運作在一個線程中，限流是通過線程池的大小來控制的
- 信号量：command是運作在調用線程中，但是通過信号量的容量來進行限流
Hystrix預設是線程池政策，對每一個資源建立一個線程池以進行流量管控，優點是資源隔離徹底，缺點增加了線程切換的成本，還需要預先給各個資源做線程池大小的配置設定。
使用樣例：
// HelloWorldHystrixCommand要使用Hystrix功能publicclassHelloWorldHystrixCommandextends HystrixCommand { privatefinal String name; publicHelloWorldHystrixCommand(String name) { super(HystrixCommandGroupKey.Factory.asKey("ExampleGroup")); this.name = name; } // 如果繼承的是HystrixObservableCommand，要重寫Observable construct() @Override protected String run() { return"Hello " + name; }} 調用該command：
String result = new HelloWorldHystrixCommand("HLX").execute();
System.out.println(result); // 列印出Hello HLX Hystrix已經在2018年停止開發，官方推薦替代項目[Resilience4j](https://resilience4j.readme.io/)
4 Sentinel
Sentinel 是阿裡巴巴提供的一種限流、熔斷中間件，與RateLimiter相比，Sentinel提供了豐富的限流、熔斷功能。它支援控制台配置限流、熔斷規則，支援叢集限流，并可以将相應服務調用情況可視化。文檔位址：https://sentinelguard.io/zh-cn/docs/introduction.html。
底層統計采用滑動視窗算法，限流方面有兩種使用方式：API調用和注解，内部采責任鍊來統計和執行校驗規則。通過為方法增加注解`@SentinelResource(String name)`或者手動調用`SphU.entry(String name)`方法開啟流控。
Sentinel基本概念：
-資源：被保護的邏輯，可以是一個服務，服務裡的方法，也可以是一段代碼，用`SphU.entry("HelloWorld")`和`entry.exit()`包圍起來
-規則：圍繞資源的實時狀态設定的規則，可以包括流量控制規則、熔斷降級規則以及系統保護規則。所有規則可以動态實時調整。
使用API手動調用流控示例：
publicstaticvoidmain(String[] args) { // 配置規則. initFlowRules(); while (true) { // 1.5.0 版本開始可以直接利用 try-with-resources 特性 try (Entry entry = SphU.entry("HelloWorld")) { // 被保護的邏輯 System.out.println("hello world"); } catch (BlockException ex) { // 處理被流控的邏輯 System.out.println("blocked!"); } }} //資源 HelloWorld 每秒最多隻能通過 20 個請求。 privatestaticvoidinitFlowRules(){ List<FlowRule> rules = new ArrayList<>(); FlowRule rule = new FlowRule(); rule.setResource("HelloWorld"); rule.setGrade(RuleConstant.FLOW_GRADE_QPS); // Set limit QPS to 20. rule.setCount(20); rules.add(rule); FlowRuleManager.loadRules(rules); } 分布式限流
分布式限流針對的分布式/微服務應用架構應用，在這種架構下，單機限流就不适用了，因為會存在多種服務，并且一種服務也可能會被部署多份。
分布式限流常見的方案：
-借助中間件件限流**：可以借助 Sentinel 或者使用 Redis 來自己實作對應的限流邏輯。
-網關層限流：比較常用的一種方案，直接在網關層把限流給安排上了。不過，通常網關層限流通常也需要借助到中間件/架構。就比如 Spring Cloud Gateway 的分布式限流實作`RedisRateLimiter`就是基于 Redis+Lua 來實作的，再比如 Spring Cloud Gateway 還可以整合 Sentinel 來做限流。
如果你要基于 Redis 來手動實作限流邏輯的話，建議配合 Lua 腳本來做。
為什麼建議 Redis+Lua 的方式？
主要有兩點原因：
-減少了網絡開銷：我們可以利用 Lua 腳本來批量執行多條 Redis 指令，這些 Redis 指令會被送出到 Redis 伺服器一次性執行完成，大幅減小了網絡開銷。
-原子性：一段 Lua 腳本可以視作一條指令執行，一段 Lua 腳本執行過程中不會有其他腳本或 Redis 指令同時執行，保證了操作不會被其他指令插入或打擾。
Redis通過lua腳本實作令牌桶
實作思路是擷取令牌後，用SET記錄“請求時間”和“剩餘token數量”。
每次請求令牌時，通過這兩個參數和請求的時間、流速等參數進行計算，傳回是否擷取令牌成功。
擷取令牌lua腳本：
local ratelimit_info = redis.pcall('HMGET',KEYS[1],'last_time','current_token')local last_time = ratelimit_info[1]local current_token = tonumber(ratelimit_info[2])local max_token = tonumber(ARGV[1])local token_rate = tonumber(ARGV[2])local current_time = tonumber(ARGV[3])local reverse_time = 1000/token_rateif current_token == nilthen current_token = max_token last_time = current_timeelselocal past_time = current_time-last_timelocal reverse_token = math.floor(past_time/reverse_time)current_token = current_token+reverse_tokenlast_time = reverse_time*reverse_token+last_timeif current_token>max_token then current_token = max_token endendlocal result = 0if(current_token>0) then result = 1 current_token = current_token-1endredis.call('HMSET',KEYS[1],'last_time',last_time,'current_token',current_token)redis.call('pexpire',KEYS[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))return result 初始化令牌桶lua腳本：
local result=1redis.pcall("HMSET",KEYS[1],"last_mill_second",ARGV[1],"curr_permits",ARGV[2],"max_burst",ARGV[3],"rate",ARGV[4])return result 作者:聶丹穎
來源:微信公衆号:系統工程實驗室
出處:https://mp.weixin.qq.com/s/lBXb9my6RcP84qqIoCjrUQ