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

作者：dijia478
www.cnblogs.com/dijia478/p/13807826.html

在網(wǎng)上搜滑動(dòng)時(shí)間窗口限流算法，大多都太復(fù)雜了，本人實(shí)現(xiàn)了個(gè)簡單的，先上代碼：

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，取出對應(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)原理來說，任意通過2次內(nèi)的時(shí)間差，都不超過10秒：

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

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

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

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

4.陸續(xù)的又來了3個(gè)事件，隊(duì)列大小變成了5，先來的時(shí)間戳依次向后移動(dòng)。此時(shí)，第6個(gè)事件來了，時(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)，來的事件個(gè)數(shù)大于5了，所以本次不允許通過：

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

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

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

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

往后再來其他事件，就是重復(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í)間限制。

推薦閱讀
國產(chǎn)小眾瀏覽器因屏蔽視頻廣告，被索賠100萬（后續(xù)）
年輕人“不講武德”：因看黃片上癮，把網(wǎng)站和786名女主播起訴了
中國聯(lián)通官網(wǎng)被發(fā)現(xiàn)含木馬腳本，可向用戶推廣色情APP
張一鳴：每個(gè)逆襲的年輕人，都具備的底層能力

關(guān)于程序員大白

程序員大白是一群哈工大，東北大學(xué)，西湖大學(xué)和上海交通大學(xué)的碩士博士運(yùn)營維護(hù)的號(hào)，大家樂于分享高質(zhì)量文章，喜歡總結(jié)知識(shí)，歡迎關(guān)注[程序員大白]，大家一起學(xué)習(xí)進(jìn)步！