在網(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ǔ)的是每一次通過時(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次通過
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)，是否允許通過
*
* @param listId 隊(duì)列id
* @param count 限制次數(shù)
* @param timeWindow 時(shí)間窗口大小
* @return 是否允許通過
*/
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ì)列，若沒有則創(chuàng)建
List<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
// 如果隊(duì)列還沒滿，則允許通過，并添加當(dāng)前時(shí)間戳到隊(duì)列開始位置
if (list.size() < count) {
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，則說明在timeWindow內(nèi)，通過的次數(shù)大于count
// 不允許通過
return false;
} else {
// 若結(jié)果大于timeWindow，則說明在timeWindow內(nèi)，通過的次數(shù)小于等于count
// 允許通過，并刪除最早添加的時(shí)間戳，將當(dāng)前時(shí)間添加到隊(duì)列開始位置
list.remove(count - 1);
list.add(0, nowTime);
return true;
}
}
}
運(yùn)行可以看到，任意10秒內(nèi)，通過的次數(shù)不超過2次。
或者按照實(shí)現(xiàn)原理來(lái)說，任意通過2次內(nèi)的時(shí)間差，都不超過10秒：
這里畫圖做說明，為什么這樣可以做到滑動(dòng)窗口限流，假設(shè)10秒內(nèi)允許通過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，都沒有到限制的次數(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秒，說明在10秒內(nèi)，來(lái)的事件個(gè)數(shù)大于5了，所以本次不允許通過：
7.接下來(lái)即便來(lái)上100個(gè)事件，只要時(shí)間差小于等于10秒，都同上，拒絕通過：
8.第11.1秒，第101次事件過來(lái)了。
因?yàn)閟ize=5，不小于5，所以取出位置4的時(shí)間（離現(xiàn)在最遠(yuǎn)的時(shí)間），和第101個(gè)事件的時(shí)間戳做比較：
9.得到的差是10.1秒，大于時(shí)間窗口10秒，說明在10秒內(nèi)，來(lái)的事件個(gè)數(shù)小于等于5了，所以本次允許通過：
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)，限制通過的次數(shù)
其本質(zhì)思想是轉(zhuǎn)換概念，將原本問題的確定時(shí)間大小，進(jìn)行次數(shù)限制。
轉(zhuǎn)換成確定次數(shù)大小，進(jìn)行時(shí)間限制。
