Java 實(shí)現(xiàn)滑動(dòng)時(shí)間窗口限流算法，你見(jiàn)過(guò)嗎？
點(diǎn)擊上方“程序員大白”，選擇“星標(biāo)”公眾號(hào)
重磅干貨，第一時(shí)間送達(dá)
作者：dijia478
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<String, List<Long>> 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<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
// 如果隊(duì)列還沒(méi)滿(mǎn)，則允許通過(guò)，并添加當(dāng)前時(shí)間戳到隊(duì)列開(kāi)始位置
if (list.size() < count) {
list.add(0, nowTime);
return true;
}
// 隊(duì)列已滿(mǎn)（達(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í)間限制。
推薦閱讀
國(guó)產(chǎn)小眾瀏覽器因屏蔽視頻廣告，被索賠100萬(wàn)（后續(xù)）
年輕人“不講武德”：因看黃片上癮，把網(wǎng)站和786名女主播起訴了
關(guān)于程序員大白
程序員大白是一群哈工大，東北大學(xué)，西湖大學(xué)和上海交通大學(xué)的碩士博士運(yùn)營(yíng)維護(hù)的號(hào)，大家樂(lè)于分享高質(zhì)量文章，喜歡總結(jié)知識(shí)，歡迎關(guān)注[程序員大白]，大家一起學(xué)習(xí)進(jìn)步！