Java 實現(xiàn)滑動時間窗口限流算法，你見過嗎？
package?cn.dijia478.util;
import?java.time.LocalTime;
import?java.util.LinkedList;
import?java.util.List;
import?java.util.Map;
import?java.util.Random;
import?java.util.concurrent.ConcurrentHashMap;
/**
?*?滑動時間窗口限流工具
?*?本限流工具只適用于單機版，如果想要做全局限流，可以按本程序的思想，用redis的List結(jié)構(gòu)去實現(xiàn)
?*
?*?@author?dijia478
?*?@date?2020-10-13?10:53
?*/
public?class?SlideWindow?{
????/**?隊列id和隊列的映射關(guān)系，隊列里面存儲的是每一次通過時候的時間戳，這樣可以使得程序里有多個限流隊列?*/
????private?volatile?static?Map>?MAP?=?new?ConcurrentHashMap<>();
????private?SlideWindow()?{}
????public?static?void?main(String[]?args)?throws?InterruptedException?{
????????while?(true)?{
????????????//?任意10秒內(nèi)，只允許2次通過
????????????System.out.println(LocalTime.now().toString()?+?SlideWindow.isGo("ListId",?2,?10000L));
????????????//?睡眠0-10秒
????????????Thread.sleep(1000?*?new?Random().nextInt(10));
????????}
????}
????/**
?????*?滑動時間窗口限流算法
?????*?在指定時間窗口，指定限制次數(shù)內(nèi)，是否允許通過
?????*
?????*?@param?listId?????隊列id
?????*?@param?count??????限制次數(shù)
?????*?@param?timeWindow?時間窗口大小
?????*?@return?是否允許通過
?????*/
????public?static?synchronized?boolean?isGo(String?listId,?int?count,?long?timeWindow)?{
????????//?獲取當(dāng)前時間
????????long?nowTime?=?System.currentTimeMillis();
????????//?根據(jù)隊列id，取出對應(yīng)的限流隊列，若沒有則創(chuàng)建
????????List?list?=?MAP.computeIfAbsent(listId,?k?->?new?LinkedList<>());
????????//?如果隊列還沒滿，則允許通過，并添加當(dāng)前時間戳到隊列開始位置
????????if?(list.size()?????????????list.add(0,?nowTime);
????????????return?true;
????????}
????????//?隊列已滿（達(dá)到限制次數(shù)），則獲取隊列中最早添加的時間戳
????????Long?farTime?=?list.get(count?-?1);
????????//?用當(dāng)前時間戳?減去?最早添加的時間戳
????????if?(nowTime?-?farTime?<=?timeWindow)?{
????????????//?若結(jié)果小于等于timeWindow，則說明在timeWindow內(nèi)，通過的次數(shù)大于count
????????????//?不允許通過
????????????return?false;
????????}?else?{
????????????//?若結(jié)果大于timeWindow，則說明在timeWindow內(nèi)，通過的次數(shù)小于等于count
????????????//?允許通過，并刪除最早添加的時間戳，將當(dāng)前時間添加到隊列開始位置
????????????list.remove(count?-?1);
????????????list.add(0,?nowTime);
????????????return?true;
????????}
????}
}
運行可以看到，任意10秒內(nèi)，通過的次數(shù)不超過2次?；蛘甙凑諏崿F(xiàn)原理來說，任意通過2次內(nèi)的時間差，都不超過10秒：
這里畫圖做說明，為什么這樣可以做到滑動窗口限流，假設(shè)10秒內(nèi)允許通過5次
1.這條線就是隊列l(wèi)ist，當(dāng)?shù)谝粋€事件進(jìn)來，隊列大小是0，時間是第1秒：
2.因為size=0，小于5，都沒有到限制的次數(shù)，完全不用考慮時間窗口，直接把這次事件的時間戳放到0的位置：
3.第2.8秒的時候，第二個事件來了。因為此時size=1，還是小于5，把這次事件的時間戳放到0的位置，原來第1秒來的事件時間戳?xí)笠苿右桓瘢?/p>
4.陸續(xù)的又來了3個事件，隊列大小變成了5，先來的時間戳依次向后移動。此時，第6個事件來了，時間是第8秒：
5.因為size=5，不小于5，此時已經(jīng)達(dá)到限制次數(shù)，以后都需要考慮時間窗口了。所以取出位置4的時間（離現(xiàn)在最遠(yuǎn)的時間），和第6個事件的時間戳做比較：
6.得到的差是7秒，小于時間窗口10秒，說明在10秒內(nèi)，來的事件個數(shù)大于5了，所以本次不允許通過：
7.接下來即便來上100個事件，只要時間差小于等于10秒，都同上，拒絕通過：
8.第11.1秒，第101次事件過來了。因為size=5，不小于5，所以取出位置4的時間（離現(xiàn)在最遠(yuǎn)的時間），和第101個事件的時間戳做比較：
9.得到的差是10.1秒，大于時間窗口10秒，說明在10秒內(nèi)，來的事件個數(shù)小于等于5了，所以本次允許通過：
10.刪除位置4的時間（離現(xiàn)在最遠(yuǎn)的時間），把這次事件的時間戳放到0的位置，后面的時間戳依次向后移動：
往后再來其他事件，就是重復(fù)4-10的步驟，即可實現(xiàn)，在任意滑動時間窗口內(nèi)，限制通過的次數(shù)
其本質(zhì)思想是轉(zhuǎn)換概念，將原本問題的確定時間大小，進(jìn)行次數(shù)限制。轉(zhuǎn)換成確定次數(shù)大小，進(jìn)行時間限制。
作者 |?dijia478
最近熬夜給大家準(zhǔn)備了515套Java代碼，有一些是業(yè)務(wù)類的小項目，比如Java博客項目，也有腳手架、也有平時用一些的工具類、21套小程序代碼，也有一些游戲類的項目。
掃以下二維碼并回復(fù)“828”即可獲取
或者在本公眾號對話框回復(fù)【828】馬上獲取
