搞懂限流算法這一篇就夠了
TL;DR(too long don't read)
限流算法：計數器、滑動窗口、漏桶、令牌桶。
限流方案：Guava的RateLimiter、Alibaba Sentinel
大家都知道，對于高并發的業務場景，我們為了保障服務的穩定，經常會祭出三大利器：緩存、熔斷降級和服務限流。
服務限流作為一個核心的自保護機制，能夠在非常高并發的情況下，其他機制都無法保障降級的情況下，保護系統不崩潰，以免產生雪崩效應。
我們設想這么一個場景。
名詞解析，QPS(query per second 每秒查詢數)
單臺機器可以承受的最高QPS為 100，我們有5臺機器，日常服務 QPS 為 300。
那么其實我們是毫無壓力，根據前置的負載均衡服務器，每臺 300/5 = 60 。可以完美提供服務。
今天，老板突然搞了一波促銷，QPS 達到了 800。
好了，機器 A 的 QPS 達到了 160，已經完全扛不住了，直接宕機了。這時候集群只剩下4臺機器，QPS依然是 800。平均分配到剩下的 4 臺機器上，每臺機器 200。就這樣，機器一臺一臺倒下，雪崩了。
那如果我們的系統有限流，會是什么樣的場景呢?
QPS 達到了800。好了，機器 A 的 QPS 達到了 160，但因為限流了100，所以機器依然正常運行，只是損失了 60 QPS 的客戶，整個集群整體還是正常運行的。這時候就給開發和運營們留下時間開始降級擴容 bala bala....
可見，限流對于系統的自保護是非常重要的存在，然而很多工程師并沒有正視它，或者說只是會用，并不清楚背后的原理。先說下結論。
常見的限流算法有：計數器、滑動窗口、漏桶、令牌桶。
常見的限流方案有：Guava的RateLimiter、基于分布式鎖的令牌桶、Alibaba Sentinel
<計數器>
一般來說，計數器比較粗暴，就是看單位時間內，所接受的 QPS 的請求有多少，如果超過閾值，則直接拒絕服務。大概場景是這樣的。
有這么一個煎餅果子攤，攤主叫老王，上面的老板說你一分鐘只許賣 6 個餅(計數限流1分鐘6個)。如果在前 0.1 秒已經有人預定了6個餅而且老王剛好神來之筆也已經做完了，那么老王在接下來的 59.59 秒只能坐在凳子上，等待下一分鐘的到來。
看，簡單粗暴的計數器，在系統性能允許的情況下，可能會浪費非常多的資源
<滑動窗口>
滑動窗口可以看做計數器的精細化實現，之前只能一分鐘一分鐘往前趕，現在可以根據實現的精細化 一秒一秒往前趕，雖然整體原理還是靠計數器。既往不咎，是一個適當時間里懂得忘記的計數器。
<漏桶>
看這張圖可以看到漏桶的基礎原理，我們會用一個桶作為緩沖區，所有的請求都先丟到桶里。系統以恒定速率慢慢消化這些請求。比較常見的實現就是隊列，用一個緩沖區來保存沒處理的請求，然后消費者恒定速度抓取一些請求進行處理。
有這么一個煎餅果子攤，攤主叫老王，老王一秒鐘只能做一個餅。現在來了 100個顧客，那怎么辦呢?就排隊啊。老王的老婆啊潘，把這批顧客引導到了旁邊的空地上站著，并給他們一個一個標記了號碼。老王做完一個，就大喊一聲號碼，對應的的顧客就過來把餅拿走。
你看看這里的要求，要求有空地(桶)，而且顧客等得起(等待時間)。
<令牌桶>
我們會有一個令牌管理員，按照一定的策略往令牌桶里放令牌。系統每接受到一個請求的時候，都會請求要一個令牌。如果拿到令牌，那么就處理這個請求，拿不到就直接拒絕這個請求。那么只要令牌發放的策略正確，這個系統就不會被拖垮，也能對機器的利用率更高。
有這么一個煎餅果子攤，攤主叫老王，老王也不知道自己能做幾個餅。老王的老婆阿潘在老王旁邊放了一個桶，里邊放了一些牌子，并告訴老王，"我幫你看著，你看見有令牌你就做就是了"。 現在來了 100個顧客，老王挖糞涂墻，原來一秒鐘只能做一個，現在一秒鐘可以做好多個，老王不看顧客了，每次能拿到令牌就直接做。老王的老婆啊潘，眼睛一直看著老王，看看他手抖沒是不是要上廁所了。如果手抖了或者可能扛不住了，那就少放一點令牌歇一歇。但如果一次性來了五個 vip 客戶，那阿潘就不管那么多了，就直接丟多幾個令牌讓老王忙一點。
我們看到，令牌桶的方法可以根據系統負載，實時調節系統的處理能力，能夠允許一定量級的瞬時高峰流量的快速消化。
好嘞。方案和算法基本上就說完了，現在聊聊限流關于現有的實現，我們當然是非常希望可以不做過多的開發，開箱即用完事，幸運的是，我們已經有不少的開源實現，就算自己實現也不會特別難。
<RateLimiter>
- <dependency>
- <groupId>com.google.guava</groupId>
- <artifactId>guava</artifactId>
- <version>25.1-jre</version>
- </dependency>
使用Guava的RateLimiter進行限流控制，主要有兩種核心模式，SmoothBursty 和 SmoothWarmingUp。SmoothBursty 每秒鐘發放N個令牌，也允許預先借用一定數量的令牌。SmoothWarmingUp，在系統剛剛啟動的時候，只會按最低閾值發放令牌，然后逐漸增加到設定的最高閾值。
- RateLimiter smoothBuisty = RateLimiter.create(1);
- RateLimiter smoothWarmingUp = RateLimiter.create(1 , 1 , TimeUnit.SECONDS);
- smoothBuisty.acquire();
- smoothWarmingUp.acquire(5);
acquire() 方法會阻塞，直到令牌桶返回，還可以一次性拿到N個令牌。但是 RateLimiter 是單機版的，如果我們想要實現分布式，那可以基于 RateLimiter 的原理，實現以下分布式的，可以使用 Redis 等分布式鎖來進行實現。
<Alibaba Sentinel>
https://github.com/alibaba/Sentinel.git
Sentinel 是一個帶配置中心的分布式緩存，以 "資源名稱" 為統計點，提供了多種方式的限流方案，可以基于 QPS、線程數，甚至系統 load 進行集群規模的限流。Sentinel 在整個生態的位置是這樣的。
使用限流的代碼非常簡單，只需要定義一個 String 類型的資源，作為唯一標識，Sentinel 會根據規則進行限流。
- try (Entry entry = SphU.entry("HelloWorld")) {
- // Your business logic here.
- System.out.println("hello world");
- } catch (BlockException e) {
- // Handle rejected request.
- e.printStackTrace();
- }
定義限流規則的也代碼非常簡單，只需要定義一個 String 類型的資源，作為唯一標識，Sentinel 會根據規則進行限流。
- private static void initFlowRules(){
- 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);
- }
也提供了 DashBoard 進行實時規則調整。
最后總結一下今天的結論
限流算法：計數器、滑動窗口、漏桶、令牌桶。
限流方案：Guava的RateLimiter、基于分布式鎖的令牌桶、Alibaba Sentinel
