Java 實(shí)現(xiàn)滑動(dòng)時(shí)間窗口限流算法，你見(jiàn)過(guò)嗎？

作者：dijia478
來(lái)源：www.cnblogs.com/dijia478/p/13807826.html

在網(wǎng)上搜滑動(dòng)時(shí)間窗口限流算法，大多都太復(fù)雜了，本人實(shí)現(xiàn)了個(gè)簡(jiǎ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;

/**
?*?滑動(dòng)時(shí)間窗口限流工具
?*?本限流工具只適用于單機(jī)版，如果想要做全局限流，可以按本程序的思想，用redis的List結(jié)構(gòu)去實(shí)現(xiàn)
?*
?*?@author?dijia478
?*?@date?2020-10-13?10:53
?*/
public?class?SlideWindow?{

????/**?隊(duì)列id和隊(duì)列的映射關(guān)系，隊(duì)列里面存儲(chǔ)的是每一次通過(guò)時(shí)候的時(shí)間戳，這樣可以使得程序里有多個(gè)限流隊(duì)列?*/
????private?volatile?static?Map>?MAP?=?new?ConcurrentHashMap<>();

????private?SlideWindow()?{}

????public?static?void?main(String[]?args)?throws?InterruptedException?{
????????while?(true)?{
????????????//?任意10秒內(nèi)，只允許2次通過(guò)
????????????System.out.println(LocalTime.now().toString()?+?SlideWindow.isGo("ListId",?2,?10000L));
????????????//?睡眠0-10秒
????????????Thread.sleep(1000?*?new?Random().nextInt(10));
????????}
????}

????/**
?????*?滑動(dòng)時(shí)間窗口限流算法
?????*?在指定時(shí)間窗口，指定限制次數(shù)內(nèi)，是否允許通過(guò)
?????*
?????*?@param?listId?????隊(duì)列id
?????*?@param?count??????限制次數(shù)
?????*?@param?timeWindow?時(shí)間窗口大小
?????*?@return?是否允許通過(guò)
?????*/
????public?static?synchronized?boolean?isGo(String?listId,?int?count,?long?timeWindow)?{
????????//?獲取當(dāng)前時(shí)間
????????long?nowTime?=?System.currentTimeMillis();
????????//?根據(jù)隊(duì)列id，取出對(duì)應(yīng)的限流隊(duì)列，若沒(méi)有則創(chuàng)建
????????List?list?=?MAP.computeIfAbsent(listId,?k?->?new?LinkedList<>());
????????//?如果隊(duì)列還沒(méi)滿，則允許通過(guò)，并添加當(dāng)前時(shí)間戳到隊(duì)列開(kāi)始位置
????????if?(list.size()?????????????list.add(0,?nowTime);
????????????return?true;
????????}

????????//?隊(duì)列已滿（達(dá)到限制次數(shù)），則獲取隊(duì)列中最早添加的時(shí)間戳
????????Long?farTime?=?list.get(count?-?1);
????????//?用當(dāng)前時(shí)間戳?減去?最早添加的時(shí)間戳
????????if?(nowTime?-?farTime?<=?timeWindow)?{
????????????//?若結(jié)果小于等于timeWindow，則說(shuō)明在timeWindow內(nèi)，通過(guò)的次數(shù)大于count
????????????//?不允許通過(guò)
????????????return?false;
????????}?else?{
????????????//?若結(jié)果大于timeWindow，則說(shuō)明在timeWindow內(nèi)，通過(guò)的次數(shù)小于等于count
????????????//?允許通過(guò)，并刪除最早添加的時(shí)間戳，將當(dāng)前時(shí)間添加到隊(duì)列開(kāi)始位置
????????????list.remove(count?-?1);
????????????list.add(0,?nowTime);
????????????return?true;
????????}
????}

}

運(yùn)行可以看到，任意10秒內(nèi)，通過(guò)的次數(shù)不超過(guò)2次。

或者按照實(shí)現(xiàn)原理來(lái)說(shuō)，任意通過(guò)2次內(nèi)的時(shí)間差，都不超過(guò)10秒：

這里畫(huà)圖做說(shuō)明，為什么這樣可以做到滑動(dòng)窗口限流，假設(shè)10秒內(nèi)允許通過(guò)5次

1.這條線就是隊(duì)列l(wèi)ist，當(dāng)?shù)谝粋€(gè)事件進(jìn)來(lái)，隊(duì)列大小是0，時(shí)間是第1秒：

2.因?yàn)閟ize=0，小于5，都沒(méi)有到限制的次數(shù)，完全不用考慮時(shí)間窗口，直接把這次事件的時(shí)間戳放到0的位置：

3.第2.8秒的時(shí)候，第二個(gè)事件來(lái)了。因?yàn)榇藭r(shí)size=1，還是小于5，把這次事件的時(shí)間戳放到0的位置，原來(lái)第1秒來(lái)的事件時(shí)間戳?xí)笠苿?dòng)一格：

4.陸續(xù)的又來(lái)了3個(gè)事件，隊(duì)列大小變成了5，先來(lái)的時(shí)間戳依次向后移動(dòng)。此時(shí)，第6個(gè)事件來(lái)了，時(shí)間是第8秒：

5.因?yàn)閟ize=5，不小于5，此時(shí)已經(jīng)達(dá)到限制次數(shù)，以后都需要考慮時(shí)間窗口了。所以取出位置4的時(shí)間（離現(xiàn)在最遠(yuǎn)的時(shí)間），和第6個(gè)事件的時(shí)間戳做比較：

6.得到的差是7秒，小于時(shí)間窗口10秒，說(shuō)明在10秒內(nèi)，來(lái)的事件個(gè)數(shù)大于5了，所以本次不允許通過(guò)：

7.接下來(lái)即便來(lái)上100個(gè)事件，只要時(shí)間差小于等于10秒，都同上，拒絕通過(guò)：

8.第11.1秒，第101次事件過(guò)來(lái)了。因?yàn)閟ize=5，不小于5，所以取出位置4的時(shí)間（離現(xiàn)在最遠(yuǎn)的時(shí)間），和第101個(gè)事件的時(shí)間戳做比較：

9.得到的差是10.1秒，大于時(shí)間窗口10秒，說(shuō)明在10秒內(nèi)，來(lái)的事件個(gè)數(shù)小于等于5了，所以本次允許通過(guò)：

10.刪除位置4的時(shí)間（離現(xiàn)在最遠(yuǎn)的時(shí)間），把這次事件的時(shí)間戳放到0的位置，后面的時(shí)間戳依次向后移動(dòng)：

往后再來(lái)其他事件，就是重復(fù)4-10的步驟，即可實(shí)現(xiàn)，在任意滑動(dòng)時(shí)間窗口內(nèi)，限制通過(guò)的次數(shù)

其本質(zhì)思想是轉(zhuǎn)換概念，將原本問(wèn)題的確定時(shí)間大小，進(jìn)行次數(shù)限制。轉(zhuǎn)換成確定次數(shù)大小，進(jìn)行時(shí)間限制。

戳原文，獲取精選面試題！