簡單的java實現滑動時間窗口限流算法

在網上搜滑動時間窗口限流算法，大多都太複雜了，本人實現了個簡單的，先上代碼：

import java.time.LocalTime;import java.util.ArrayList;import java.util.List;import java.util.Map;import java.util.Random;import java.util.concurrent.ConcurrentHashMap;/** * 滑動時間窗口限流工具 * 本限流工具只適用於單機版，如果想要做全局限流，可以按本程序的思想，用redis的List結構去實現 * * @author dijia478 * @date 2020-10-13 10:53 */public class SlideWindow { /** 隊列id和隊列的映射關係，隊列裡面存儲的是每一次通過時候的時間戳，這樣可以使得程序裡有多個限流隊列 */ private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>(); private SlideWindow() {} public static void main(String[] args) throws InterruptedException { while (true) { // 任意10秒內，只允許2次通過 System.out.println(LocalTime.now().toString() + SlideWindow.isGo("ListId", 2, 10000L)); // 睡眠0-10秒 Thread.sleep(1000 * new Random().nextInt(10)); } } /** * 滑動時間窗口限流算法 * 在指定時間窗口，指定限制次數內，是否允許通過 * * @param listId 隊列id * @param count 限制次數 * @param timeWindow 時間窗口大小 * @return 是否允許通過 */ public static synchronized boolean isGo(String listId, int count, long timeWindow) { // 獲取當前時間 long nowTime = System.currentTimeMillis(); // 根據隊列id，取出對應的限流隊列，若沒有則創建 List<Long> list = MAP.computeIfAbsent(listId, k -> new ArrayList<>()); // 如果隊列還沒滿，則允許通過，並添加當前時間戳到隊列開始位置 if (list.size() < count) { list.add(0, nowTime); return true; } // 隊列已滿（達到限制次數），則獲取隊列中最早添加的時間戳 Long farTime = list.get(count - 1); // 用當前時間戳 減去 最早添加的時間戳 if (nowTime - farTime <= timeWindow) { // 若結果小於等於timeWindow，則說明在timeWindow內，通過的次數大於count // 不允許通過 return false; } else { // 若結果大於timeWindow，則說明在timeWindow內，通過的次數小於等於count // 允許通過，並刪除最早添加的時間戳，將當前時間添加到隊列開始位置 list.remove(count - 1); list.add(0, nowTime); return true; } }}

運行可以看到，任意10秒內，通過的次數不超過2次。或者按照實現原理來說，任意通過2次內的時間差，都不超過10秒：

這裡畫圖做說明，為什麼這樣可以做到滑動窗口限流，假設10秒內允許通過5次

1.這條線就是隊列list，當第一個事件進來，隊列大小是0，時間是第1秒：

2.因為size=0，小於5，都沒有到限制的次數，完全不用考慮時間窗口，直接把這次事件的時間戳放到0的位置：

3.第2.8秒的時候，第二個事件來了。因為此時size=1，還是小於5，把這次事件的時間戳放到0的位置，原來第1秒來的事件時間戳會往後移動一格：

4.陸續的又來了3個事件，隊列大小變成了5，先來的時間戳依次向後移動。此時，第6個事件來了，時間是第8秒：

5.因為size=5，不小於5，此時已經達到限制次數，以後都需要考慮時間窗口了。所以取出位置4的時間（離現在最遠的時間），和第6個事件的時間戳做比較：

6.得到的差是7秒，小於時間窗口10秒，說明在10秒內，來的事件個數大於5了，所以本次不允許通過：

7.接下來即便來上100個事件，只要時間差小於等於10秒，都同上，拒絕通過：

8.第11.1秒，第101次事件過來了。因為size=5，不小於5，所以取出位置4的時間（離現在最遠的時間），和第101個事件的時間戳做比較：

9.得到的差是10.1秒，大於時間窗口10秒，說明在10秒內，來的事件個數小於等於5了，所以本次允許通過：

10.刪除位置4的時間（離現在最遠的時間），把這次事件的時間戳放到0的位置，後面的時間戳依次向後移動：

往後再來其他事件，就是重複4-10的步驟，即可實現，在任意滑動時間窗口內，限制通過的次數

其本質思想是轉換概念，將原本問題的確定時間大小，進行次數限制。轉換成確定次數大小，進行時間限制。