詳解5種Java中常見限流算法
1.瞬時(shí)流量過高,服務(wù)被壓垮?
2.惡意用戶高頻光顧,導(dǎo)致服務(wù)器宕機(jī)?
3.消息消費(fèi)過快,導(dǎo)致數(shù)據(jù)庫(kù)壓力過大,性能下降甚至崩潰?
......
在高并發(fā)系統(tǒng)中,出于系統(tǒng)保護(hù)角度考慮,通常會(huì)對(duì)流量進(jìn)行限流;不但在工作中要頻繁使用,而且也是面試中的高頻考點(diǎn)。
今天我們將圖文并茂地對(duì)常見的限流算法分別進(jìn)行介紹,通過各個(gè)算法的特點(diǎn),給出限流算法選型的一些建議,并給出Java語(yǔ)言實(shí)現(xiàn)的代碼示例。
01固定窗口
固定窗口又稱固定窗口(又稱計(jì)數(shù)器算法,F(xiàn)ixed Window)限流算法,是最簡(jiǎn)單的限流算法,通過在單位時(shí)間內(nèi)維護(hù)的計(jì)數(shù)器來控制該時(shí)間單位內(nèi)的最大訪問量。
假設(shè)限制每分鐘請(qǐng)求量不超過60,設(shè)置一個(gè)計(jì)數(shù)器,當(dāng)請(qǐng)求到達(dá)時(shí)如果計(jì)數(shù)器到達(dá)閾值,則拒絕請(qǐng)求,否則計(jì)數(shù)器加1;每分鐘重置計(jì)數(shù)器為0。代碼實(shí)現(xiàn)如下:
public class CounterRateLimiter extends MyRateLimiter { /** * 每秒限制請(qǐng)求數(shù) */ private final long permitsPerSecond; /** * 上一個(gè)窗口的開始時(shí)間 */ public long timestamp = System.currentTimeMillis(); /** * 計(jì)數(shù)器 */ private int counter; public CounterRateLimiter(long permitsPerSecond) { this.permitsPerSecond = permitsPerSecond; } @Override public synchronized boolean tryAcquire() { long now = System.currentTimeMillis(); // 窗口內(nèi)請(qǐng)求數(shù)量小于閾值,更新計(jì)數(shù)放行,否則拒絕請(qǐng)求 if (now - timestamp < 1000) { if (counter < permitsPerSecond) { counter++; return true; } else { return false; } } // 時(shí)間窗口過期,重置計(jì)數(shù)器和時(shí)間戳 counter = 0; timestamp = now; return true; } }
固定窗口最大的優(yōu)點(diǎn)在于易于實(shí)現(xiàn);并且內(nèi)存占用小,我們只需要存儲(chǔ)時(shí)間窗口中的計(jì)數(shù)即可;它能夠確保處理更多的最新請(qǐng)求,不會(huì)因?yàn)榕f請(qǐng)求的堆積導(dǎo)致新請(qǐng)求被餓死。當(dāng)然也面臨著臨界問題,當(dāng)兩個(gè)窗口交界處,瞬時(shí)流量可能為2n。
02滑動(dòng)窗口
為了防止瞬時(shí)流量,可以把固定窗口近一步劃分成多個(gè)格子,每次向后移動(dòng)一小格,而不是固定窗口大小,這就是滑動(dòng)窗口(Sliding Window)。
比如每分鐘可以分為6個(gè)10秒中的單元格,每個(gè)格子中分別維護(hù)一個(gè)計(jì)數(shù)器,窗口每次向前滑動(dòng)一個(gè)單元格。每當(dāng)請(qǐng)求到達(dá)時(shí),只要窗口中所有單元格的計(jì)數(shù)總和不超過閾值都可以放行。TCP協(xié)議中數(shù)據(jù)包的傳輸,同樣也是采用滑動(dòng)窗口來進(jìn)行流量控制。
實(shí)現(xiàn)如下:
public class SlidingWindowRateLimiter extends MyRateLimiter { /** * 每分鐘限制請(qǐng)求數(shù) */ private final long permitsPerMinute; /** * 計(jì)數(shù)器, k-為當(dāng)前窗口的開始時(shí)間值秒,value為當(dāng)前窗口的計(jì)數(shù) */ private final TreeMap<Long, Integer> counters; public SlidingWindowRateLimiter(long permitsPerMinute) { this.permitsPerMinute = permitsPerMinute; this.counters = new TreeMap<>(); } @Override public synchronized boolean tryAcquire() { // 獲取當(dāng)前時(shí)間的所在的子窗口值; 10s一個(gè)窗口 long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / 10 * 10; // 獲取當(dāng)前窗口的請(qǐng)求總量 int currentWindowCount = getCurrentWindowCount(currentWindowTime); if (currentWindowCount >= permitsPerMinute) { return false; } // 計(jì)數(shù)器 + 1 counters.merge(currentWindowTime, 1, Integer::sum); return true; } /** * 獲取當(dāng)前窗口中的所有請(qǐng)求數(shù)(并刪除所有無(wú)效的子窗口計(jì)數(shù)器) * * @param currentWindowTime 當(dāng)前子窗口時(shí)間 * @return 當(dāng)前窗口中的計(jì)數(shù) */ private int getCurrentWindowCount(long currentWindowTime) { // 計(jì)算出窗口的開始位置時(shí)間 long startTime = currentWindowTime - 50; int result = 0; // 遍歷當(dāng)前存儲(chǔ)的計(jì)數(shù)器,刪除無(wú)效的子窗口計(jì)數(shù)器,并累加當(dāng)前窗口中的所有計(jì)數(shù)器之和 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 { result += entry.getValue(); } } return result; } }
滑動(dòng)窗口解決了計(jì)數(shù)器中的瞬時(shí)流量高峰問題,其實(shí)計(jì)數(shù)器算法也是滑動(dòng)窗口的一種,只不過窗口沒有進(jìn)行更細(xì)粒度單元的劃分。對(duì)比計(jì)數(shù)器可見,當(dāng)窗口劃分的粒度越細(xì),則流量控制更加精準(zhǔn)和嚴(yán)格。
不過當(dāng)窗口中流量到達(dá)閾值時(shí),流量會(huì)瞬間切斷,在實(shí)際應(yīng)用中我們要的限流效果往往不是把流量一下子掐斷,而是讓流量平滑地進(jìn)入系統(tǒng)當(dāng)中。
03漏桶算法
如何更加平滑的限流?不妨看看漏桶算法(Leaky Bucket),請(qǐng)求就像水一樣以任意速度注入漏桶,而桶會(huì)按照固定的速率將水漏掉;當(dāng)注入速度持續(xù)大于漏出的速度時(shí),漏桶會(huì)變滿,此時(shí)新進(jìn)入的請(qǐng)求將會(huì)被丟棄。限流和整形是漏桶算法的兩個(gè)核心能力。
實(shí)現(xiàn)如下:
public class LeakyBucketRateLimiter extends MyRateLimiter { // 桶的容量 private final int capacity; // 漏出速率 private final int permitsPerSecond; // 剩余水量 private long leftWater; // 上次注入時(shí)間 private long timeStamp = System.currentTimeMillis(); public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) { this.capacity = capacity; this.permitsPerSecond = permitsPerSecond; } @Override public synchronized boolean tryAcquire() { //1. 計(jì)算剩余水量 long now = System.currentTimeMillis(); long timeGap = (now - timeStamp) / 1000; leftWater = Math.max(0, leftWater - timeGap * permitsPerSecond); timeStamp = now; // 如果未滿,則放行;否則限流 if (leftWater < capacity) { leftWater += 1; return true; } return false; } }
這并不是一個(gè)完整的漏桶算法的實(shí)現(xiàn),以上代碼中只是對(duì)流量是否會(huì)被拋棄進(jìn)行校驗(yàn),即tryAcquire返回true表示漏桶未滿,否則表示漏桶已滿丟棄請(qǐng)求。
想要以恒定的速率漏出流量,通常還應(yīng)配合一個(gè)FIFO隊(duì)列來實(shí)現(xiàn),當(dāng)tryAcquire返回true時(shí),將請(qǐng)求入隊(duì),然后再以固定頻率從隊(duì)列中取出請(qǐng)求進(jìn)行處理。示例代碼如下:
@Test public void testLeakyBucketRateLimiter() throws InterruptedException { ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor(); ExecutorService singleThread = Executors.newSingleThreadExecutor(); LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(20, 20); // 存儲(chǔ)流量的隊(duì)列 Queue<Integer> queue = new LinkedList<>(); // 模擬請(qǐng)求 不確定速率注水 singleThread.execute(() -> { int count = 0; while (true) { count++; boolean flag = rateLimiter.tryAcquire(); if (flag) { queue.offer(count); System.out.println(count + "--------流量被放行--------"); } else { System.out.println(count + "流量被限制"); } try { Thread.sleep((long) (Math.random() * 1000)); } catch (InterruptedException e) { e.printStackTrace(); } } }); // 模擬處理請(qǐng)求 固定速率漏水 scheduledExecutorService.scheduleAtFixedRate(() -> { if (!queue.isEmpty()) { System.out.println(queue.poll() + "被處理"); } }, 0, 100, TimeUnit.MILLISECONDS); // 保證主線程不會(huì)退出 while (true) { Thread.sleep(10000); } }
漏桶算法存在目的主要是用來平滑突發(fā)的流量,提供一種機(jī)制來確保網(wǎng)絡(luò)中的突發(fā)流量被整合成平滑穩(wěn)定的額流量。
不過由于漏桶對(duì)流量的控制過于嚴(yán)格,在有些場(chǎng)景下不能充分使用系統(tǒng)資源,因?yàn)槁┩暗穆┏鏊俾适枪潭ǖ模词乖谀骋粫r(shí)刻下游能夠處理更大的流量,漏桶也不允許突發(fā)流量通過。
04令牌桶
如何在夠限制流量速率的前提下,又能夠允許突發(fā)流量呢?令牌桶算法了解一下!令牌桶算法是以恒定速率向令牌桶發(fā)送令牌,請(qǐng)求到達(dá)時(shí),嘗試從令牌桶中拿令牌,只有拿到令牌才能夠放行,否則將會(huì)被拒絕。
令牌桶具有以下特點(diǎn):
1.以恒定的速率發(fā)放令牌,假設(shè)限流速率為v/s,則表示每1/v秒發(fā)放一個(gè)令牌
2.假設(shè)令牌桶容量是b,如果令牌桶已滿,則新的令牌會(huì)被丟棄
3.請(qǐng)求能夠通過限流器的前提是令牌桶中有令牌
令牌桶算法中值得關(guān)注的參數(shù)有兩個(gè),即限流速率v/s,和令牌桶容量b;速率a表示限流器一般情況下的限流速率,而b則是burst的簡(jiǎn)寫,表示限流器允許的最大突發(fā)流量。
比如b=10,當(dāng)令牌桶滿的時(shí)候有10個(gè)可用令牌,此時(shí)允許10個(gè)請(qǐng)求同時(shí)通過限流器(允許流量一定程度的突發(fā)),這10個(gè)請(qǐng)求瞬間消耗完令牌后,后續(xù)的流量只能按照速率r通過限流器。
實(shí)現(xiàn)如下:
public class TokenBucketRateLimiter extends MyRateLimiter { /** * 令牌桶的容量「限流器允許的最大突發(fā)流量」 */ private final long capacity; /** * 令牌發(fā)放速率 */ private final long generatedPerSeconds; /** * 最后一個(gè)令牌發(fā)放的時(shí)間 */ long lastTokenTime = System.currentTimeMillis(); /** * 當(dāng)前令牌數(shù)量 */ private long currentTokens; public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) { this.generatedPerSeconds = generatedPerSeconds; this.capacity = capacity; } /** * 嘗試獲取令牌 * * @return true表示獲取到令牌,放行;否則為限流 */ @Override public synchronized boolean tryAcquire() { /** * 計(jì)算令牌當(dāng)前數(shù)量 * 請(qǐng)求時(shí)間在最后令牌是產(chǎn)生時(shí)間相差大于等于額1s(為啥時(shí)1s?因?yàn)樯闪钆频淖钚r(shí)間單位時(shí)s),則 * 1. 重新計(jì)算令牌桶中的令牌數(shù) * 2. 將最后一個(gè)令牌發(fā)放時(shí)間重置為當(dāng)前時(shí)間 */ long now = System.currentTimeMillis(); if (now - lastTokenTime >= 1000) { long newPermits = (now - lastTokenTime) / 1000 * generatedPerSeconds; currentTokens = Math.min(currentTokens + newPermits, capacity); lastTokenTime = now; } if (currentTokens > 0) { currentTokens--; return true; } return false; } }
需要主意的是,非常容易被想到的實(shí)現(xiàn)是生產(chǎn)者消費(fèi)者模式;用一個(gè)生產(chǎn)者線程定時(shí)向阻塞隊(duì)列中添加令牌,而試圖通過限流器的線程則作為消費(fèi)者線程,只有從阻塞隊(duì)列中獲取到令牌,才允許通過限流器。
由于線程調(diào)度的不確定性,在高并發(fā)場(chǎng)景時(shí),定時(shí)器誤差非常大,同時(shí)定時(shí)器本身會(huì)創(chuàng)建調(diào)度線程,也會(huì)對(duì)系統(tǒng)的性能產(chǎn)生影響。
05滑動(dòng)日志
滑動(dòng)日志是一個(gè)比較“冷門”,但是確實(shí)好用的限流算法。滑動(dòng)日志限速算法需要記錄請(qǐng)求的時(shí)間戳,通常使用有序集合來存儲(chǔ),我們可以在單個(gè)有序集合中跟蹤用戶在一個(gè)時(shí)間段內(nèi)所有的請(qǐng)求。
假設(shè)我們要限制給定T時(shí)間內(nèi)的請(qǐng)求不超過N,我們只需要存儲(chǔ)最近T時(shí)間之內(nèi)的請(qǐng)求日志,每當(dāng)請(qǐng)求到來時(shí)判斷最近T時(shí)間內(nèi)的請(qǐng)求總數(shù)是否超過閾值。
實(shí)現(xiàn)如下:
public class SlidingLogRateLimiter extends MyRateLimiter { /** * 每分鐘限制請(qǐng)求數(shù) */ private static final long PERMITS_PER_MINUTE = 60; /** * 請(qǐng)求日志計(jì)數(shù)器, k-為請(qǐng)求的時(shí)間(秒),value當(dāng)前時(shí)間的請(qǐng)求數(shù)量 */ private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>(); @Override public synchronized boolean tryAcquire() { // 最小時(shí)間粒度為s long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC); // 獲取當(dāng)前窗口的請(qǐng)求總數(shù) int currentWindowCount = getCurrentWindowCount(currentTimestamp); if (currentWindowCount >= PERMITS_PER_MINUTE) { return false; } // 請(qǐng)求成功,將當(dāng)前請(qǐng)求日志加入到日志中 requestLogCountMap.merge(currentTimestamp, 1, Integer::sum); return true; } /** * 統(tǒng)計(jì)當(dāng)前時(shí)間窗口內(nèi)的請(qǐng)求數(shù) * * @param currentTime 當(dāng)前時(shí)間 * @return - */ private int getCurrentWindowCount(long currentTime) { // 計(jì)算出窗口的開始位置時(shí)間 long startTime = currentTime - 59; // 遍歷當(dāng)前存儲(chǔ)的計(jì)數(shù)器,刪除無(wú)效的子窗口計(jì)數(shù)器,并累加當(dāng)前窗口中的所有計(jì)數(shù)器之和 return requestLogCountMap.entrySet() .stream() .filter(entry -> entry.getKey() >= startTime) .mapToInt(Map.Entry::getValue) .sum(); } }
滑動(dòng)日志能夠避免突發(fā)流量,實(shí)現(xiàn)較為精準(zhǔn)的限流;同樣更加靈活,能夠支持更加復(fù)雜的限流策略,如多級(jí)限流,每分鐘不超過100次,每小時(shí)不超過300次,每天不超過1000次,我們只需要保存最近24小時(shí)所有的請(qǐng)求日志即可實(shí)現(xiàn)。
靈活并不是沒有代價(jià)的,帶來的缺點(diǎn)就是占用存儲(chǔ)空間要高于其他限流算法。
06分布式限流
以上幾種限流算法的實(shí)現(xiàn)都僅適合單機(jī)限流。雖然給每臺(tái)機(jī)器平均分配限流配額可以達(dá)到限流的目的,但是由于機(jī)器性能,流量分布不均以及計(jì)算數(shù)量動(dòng)態(tài)變化等問題,單機(jī)限流在分布式場(chǎng)景中的效果總是差強(qiáng)人意。
分布式限流最簡(jiǎn)單的實(shí)現(xiàn)就是利用中心化存儲(chǔ),即將單機(jī)限流存儲(chǔ)在本地的數(shù)據(jù)存儲(chǔ)到同一個(gè)存儲(chǔ)空間中,如常見的Redis等。
當(dāng)然也可以從上層流量入口進(jìn)行限流,Nginx代理服務(wù)就提供了限流模塊,同樣能夠?qū)崿F(xiàn)高性能,精準(zhǔn)的限流,其底層是漏桶算法。
07總結(jié)
1.固定窗口算法實(shí)現(xiàn)簡(jiǎn)單,性能高,但是會(huì)有臨界突發(fā)流量問題,瞬時(shí)流量最大可以達(dá)到閾值的2倍。
2.為了解決臨界突發(fā)流量,可以將窗口劃分為多個(gè)更細(xì)粒度的單元,每次窗口向右移動(dòng)一個(gè)單元,于是便有了滑動(dòng)窗口算法。
滑動(dòng)窗口當(dāng)流量到達(dá)閾值時(shí)會(huì)瞬間掐斷流量,所以導(dǎo)致流量不夠平滑。
3.想要達(dá)到限流的目的,又不會(huì)掐斷流量,使得流量更加平滑?可以考慮漏桶算法!需要注意的是,漏桶算法通常配置一個(gè)FIFO的隊(duì)列使用以達(dá)到允許限流的作用。
由于速率固定,即使在某個(gè)時(shí)刻下游處理能力過剩,也不能得到很好的利用,這是漏桶算法的一個(gè)短板。
4.限流和瞬時(shí)流量其實(shí)并不矛盾,在大多數(shù)場(chǎng)景中,短時(shí)間突發(fā)流量系統(tǒng)是完全可以接受的。令牌桶算法就是不二之選了,令牌桶以固定的速率v產(chǎn)生令牌放入一個(gè)固定容量為n的桶中,當(dāng)請(qǐng)求到達(dá)時(shí)嘗試從桶中獲取令牌。
當(dāng)桶滿時(shí),允許最大瞬時(shí)流量為n;當(dāng)桶中沒有剩余流量時(shí)則限流速率最低,為令牌生成的速率v。
5.如何實(shí)現(xiàn)更加靈活的多級(jí)限流呢?滑動(dòng)日志限流算法了解一下!這里的日志則是請(qǐng)求的時(shí)間戳,通過計(jì)算制定時(shí)間段內(nèi)請(qǐng)求總數(shù)來實(shí)現(xiàn)靈活的限流。
當(dāng)然,由于需要存儲(chǔ)時(shí)間戳信息,其占用的存儲(chǔ)空間要比其他限流算法要大得多。
不管黑貓白貓,能抓到老鼠的就是好貓。限流算法并沒有絕對(duì)的好劣之分,如何選擇合適的限流算法呢?不妨從性能,是否允許超出閾值,落地成本,流量平滑度,是否允許突發(fā)流量以及系統(tǒng)資源大小限制多方面考慮。
當(dāng)然,市面上也有比較成熟的限流工具和框架。如Google出品的Guava中基于令牌桶實(shí)現(xiàn)的限流組件,拿來即用;以及alibaba開源的面向分布式服務(wù)架構(gòu)的流量控制框架Sentinel更會(huì)讓你愛不釋手,它是基于滑動(dòng)窗口實(shí)現(xiàn)的。
以上就是詳解5種Java中常見限流算法的詳細(xì)內(nèi)容,更多關(guān)于Java限流算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
基于Spring Web Jackson對(duì)RequestBody反序列化失敗的解決
這篇文章主要介紹了基于Spring Web Jackson對(duì)RequestBody反序列化失敗的解決,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-09-09Java利用IO流實(shí)現(xiàn)簡(jiǎn)易的記事本功能
本文將利用Java中IO流編寫一個(gè)模擬日記本的程序,通過在控制臺(tái)輸入指令,實(shí)現(xiàn)在本地新建文件,打開日記本和修改日記本等功能,感興趣的可以了解一下2022-05-05使用Spring安全表達(dá)式控制系統(tǒng)功能訪問權(quán)限問題
從spring security 3.0開始已經(jīng)可以使用spring Expression表達(dá)式來控制授權(quán),允許在表達(dá)式中使用復(fù)雜的布爾邏輯來控制訪問的權(quán)限。這篇文章主要介紹了使用Spring安全表達(dá)式控制系統(tǒng)功能訪問權(quán)限,需要的朋友可以參考下2019-11-11SpringBoot接口返回?cái)?shù)據(jù)脫敏(Mybatis、Jackson)
有時(shí)候,我們接口返回的數(shù)據(jù)需要做一些處理,有一些敏感數(shù)據(jù),本文主要介紹了SpringBoot接口返回?cái)?shù)據(jù)脫敏(Mybatis、Jackson),具有一定的參考價(jià)值,感興趣的可以了解一下2024-07-07IDEA最新激活碼2021(IDEA2020.3.2最新永久激活方法)
這篇文章主要介紹了IDEA最新激活碼2021(IDEA2020.3.2最新永久激活方法),本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-12-12SpringBoot中@Insert、@Update實(shí)現(xiàn)批量新增更新的使用示例
本文主要介紹了SpringBoot中@Insert、@Update實(shí)現(xiàn)批量新增更新的使用,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-10-10SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式
這篇文章主要介紹了SpringMVC @RequestBody Date類型的Json轉(zhuǎn)換方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-10-10