摘要：如何設(shè)計(jì)一個(gè)計(jì)數(shù)的時(shí)間窗口時(shí)間窗口，通常對(duì)于一些實(shí)時(shí)信息展示中用得比較多，比如維持一個(gè)五分鐘的交易明細(xì)時(shí)間窗口，就需要記錄當(dāng)前時(shí)間，到五分鐘之前的所有交易明細(xì)，而五分鐘之前的數(shù)據(jù)，則丟掉一個(gè)簡(jiǎn)單的實(shí)現(xiàn)就是用一個(gè)隊(duì)列來(lái)做，新的數(shù)據(jù)在對(duì)頭添加同

時(shí)間窗口，通常對(duì)于一些實(shí)時(shí)信息展示中用得比較多，比如維持一個(gè)五分鐘的交易明細(xì)時(shí)間窗口，就需要記錄當(dāng)前時(shí)間，到五分鐘之前的所有交易明細(xì)，而五分鐘之前的數(shù)據(jù)，則丟掉

一個(gè)簡(jiǎn)單的實(shí)現(xiàn)就是用一個(gè)隊(duì)列來(lái)做，新的數(shù)據(jù)在對(duì)頭添加；同時(shí)起一個(gè)線程，不斷的詢問(wèn)隊(duì)尾的數(shù)據(jù)是否過(guò)期，如果過(guò)期則丟掉

另外一中場(chǎng)景需要利用到這個(gè)時(shí)間窗口內(nèi)的數(shù)據(jù)進(jìn)行計(jì)算，如計(jì)算著五分鐘交易中資金的流入流出總和，如果依然用上面的這種方式，會(huì)有什么問(wèn)題？

如果時(shí)間窗口大，需要存儲(chǔ)大量的明細(xì)數(shù)據(jù)

我們主要關(guān)心的只有資金流入流出；存這些明細(xì)數(shù)據(jù)得不償失

每次新增or刪除過(guò)期數(shù)據(jù)時(shí)，實(shí)時(shí)計(jì)算流入流出消耗性能

針對(duì)這種特殊的場(chǎng)景，是否有什么取巧的實(shí)現(xiàn)方式呢？

將時(shí)間窗口分割成一個(gè)一個(gè)的時(shí)間片，每個(gè)時(shí)間片中記錄資金的流入流出總數(shù)，然后總的流入流出就是所有時(shí)間片的流入流出的和

新增數(shù)據(jù)：

若未跨時(shí)間片，則更新隊(duì)頭的值

若跨時(shí)間片，新增一個(gè)隊(duì)列頭

刪除數(shù)據(jù)：

輪詢?nèi)蝿?wù)，判斷隊(duì)列尾是否過(guò)期

隊(duì)尾過(guò)期，則刪除隊(duì)尾，此時(shí)若隊(duì)頭數(shù)據(jù)未加入計(jì)算，也需要加入計(jì)算

相比較前面的輪詢方式，這個(gè)的應(yīng)用場(chǎng)景為另外一種，只有在新增數(shù)據(jù)時(shí)，確保數(shù)據(jù)的準(zhǔn)確性即可，不需要輪詢的任務(wù)去刪除過(guò)期的數(shù)據(jù)

簡(jiǎn)單來(lái)說(shuō)，某些場(chǎng)景下（比如能確保數(shù)據(jù)不會(huì)斷續(xù)的進(jìn)來(lái)，即每個(gè)時(shí)間片都至少有一個(gè)數(shù)據(jù)過(guò)來(lái)），此時(shí)希望我的時(shí)間窗口數(shù)據(jù)是由新增的數(shù)據(jù)來(lái)驅(qū)動(dòng)并更新

新增數(shù)據(jù)：

未跨時(shí)間片，則更新隊(duì)頭值

跨時(shí)間片，新塞入一個(gè)，并刪除舊的數(shù)據(jù)

針對(duì)上面第二種，基于數(shù)組給出一個(gè)簡(jiǎn)單的實(shí)現(xiàn)，本篇主要是給出一個(gè)基礎(chǔ)的時(shí)間窗口的設(shè)計(jì)與實(shí)現(xiàn)方式，當(dāng)然也需要有進(jìn)階的case，比如上面的資金流入流出中，我需要分別計(jì)算5min,10min,30min,1h,3h,6h,12h,24h的時(shí)間窗口，該怎么來(lái)實(shí)現(xiàn)呢？能否用一個(gè)隊(duì)列就滿足所有的時(shí)間窗口的計(jì)算呢？關(guān)于這些留待下一篇給出

前面用隊(duì)列的方式比較好理解，這里為什么用數(shù)組方式來(lái)實(shí)現(xiàn)？

固定長(zhǎng)度，避免頻繁的新增和刪除對(duì)象

定位和更新數(shù)據(jù)方便

首先是需要實(shí)現(xiàn)一個(gè)時(shí)間輪計(jì)算器，根據(jù)傳入的時(shí)間，獲取需要?jiǎng)h除的過(guò)期數(shù)據(jù)

@Data
public class TimeWheelCalculate {
    private static final long START = 0;

    private int period;
    private int length;

    /**
     * 劃分的時(shí)間片個(gè)數(shù)
     */
    private int cellNum;

    private void check() {
        if (length % period != 0) {
            throw new IllegalArgumentException(
                    "length % period should be zero but not! now length: " + length + " period: " + period);
        }
    }

    public TimeWheelCalculate(int period, int length) {
        this.period = period;
        this.length = length;

        check();

        this.cellNum = length / period;
    }

    public int calculateIndex(long time) {
        return (int) ((time - START) % length / period);
    }

    /**
     * 獲取所有過(guò)期的時(shí)間片索引
     *
     * @param lastInsertTime 上次更新時(shí)間輪的時(shí)間戳
     * @param nowInsertTime  本次更新時(shí)間輪的時(shí)間戳
     * @return
     */
    public List getExpireIndexes(long lastInsertTime, long nowInsertTime) {
        if (nowInsertTime - lastInsertTime >= length) {
            // 已經(jīng)過(guò)了一輪，過(guò)去的數(shù)據(jù)全部丟掉
            return null;
        }

        List removeIndexList = new ArrayList<>();
        int lastIndex = calculateIndex(lastInsertTime);
        int nowIndex = calculateIndex(nowInsertTime);
        if (lastIndex == nowIndex) {
            // 還沒(méi)有跨過(guò)這個(gè)時(shí)間片，則不需要?jiǎng)h除過(guò)期數(shù)據(jù)
            return Collections.emptyList();
        } else if (lastIndex < nowIndex) {
            for (int tmp = lastIndex; tmp < nowIndex; tmp++) {
                removeIndexList.add(tmp);
            }
        } else {
            for (int tmp = lastIndex; tmp < cellNum; tmp++) {
                removeIndexList.add(tmp);
            }

            for (int tmp = 0; tmp < nowIndex; tmp++) {
                removeIndexList.add(tmp);
            }
        }
        return removeIndexList;
    }
}

這個(gè)計(jì)算器的實(shí)現(xiàn)比較簡(jiǎn)單，首先是指定時(shí)間窗口的長(zhǎng)度(length),時(shí)間片(period)，其主要提供兩個(gè)方法

calculateIndex 根據(jù)當(dāng)前時(shí)間，確定過(guò)期的數(shù)據(jù)在數(shù)組的索引

getExpireIndexes 根據(jù)上次插入的時(shí)間，和當(dāng)前插入的時(shí)間，計(jì)算兩次插入時(shí)間之間，所有的過(guò)期數(shù)據(jù)索引

容器內(nèi)保存的時(shí)間窗口下的數(shù)據(jù)，包括實(shí)時(shí)數(shù)據(jù)，和過(guò)去n個(gè)時(shí)間片的數(shù)組，其主要的核心就是在新增數(shù)據(jù)時(shí)，需要判斷

若跨時(shí)間片，則刪除過(guò)期數(shù)據(jù)，更新實(shí)時(shí)數(shù)據(jù)，更新總數(shù)

若未跨時(shí)間片，則直接更新實(shí)時(shí)數(shù)據(jù)即可

@Data
public class TimeWheelContainer {
    private TimeWheelCalculate calculate;

    /**
     * 歷史時(shí)間片計(jì)數(shù)，每個(gè)時(shí)間片對(duì)應(yīng)其中的一個(gè)元素
     */
    private int[] counts;

    /**
     * 實(shí)時(shí)的時(shí)間片計(jì)數(shù)
     */
    private int realTimeCount;

    /**
     * 整個(gè)時(shí)間輪計(jì)數(shù)
     */
    private int timeWheelCount;

    private Long lastInsertTime;


    public TimeWheelContainer(TimeWheelCalculate calculate) {
        this.counts = new int[calculate.getCellNum()];
        this.calculate = calculate;
        this.realTimeCount = 0;
        this.timeWheelCount = 0;
        this.lastInsertTime = null;
    }

    public void add(long now, int amount) {
        if (lastInsertTime == null) {
            realTimeCount = amount;
            lastInsertTime = now;
            return;
        }


        List removeIndex = calculate.getExpireIndexes(lastInsertTime, now);
        if (removeIndex == null) {
            // 兩者時(shí)間間隔超過(guò)一輪，則清空計(jì)數(shù)
            realTimeCount = amount;
            lastInsertTime = now;
            timeWheelCount = 0;
            clear();
            return;
        }

        if (removeIndex.isEmpty()) {
            // 沒(méi)有跨過(guò)時(shí)間片，則只更新實(shí)時(shí)計(jì)數(shù)
            realTimeCount += amount;
            lastInsertTime = now;
            return;
        }

        // 跨過(guò)了時(shí)間片，則需要在總數(shù)中刪除過(guò)期的數(shù)據(jù)，并追加新的數(shù)據(jù)
        for (int index : removeIndex) {
            timeWheelCount -= counts[index];
            counts[index] = 0;
        }
        timeWheelCount += realTimeCount;
        counts[calculate.calculateIndex(lastInsertTime)] = realTimeCount;
        lastInsertTime = now;
        realTimeCount = amount;
    }

    private void clear() {
        for (int i = 0; i < counts.length; i++) {
            counts[i] = 0;
        }
    }
}

主要就是驗(yàn)證上面的實(shí)現(xiàn)有沒(méi)有明顯的問(wèn)題，為什么是明顯的問(wèn)題？

深層次的bug在實(shí)際的使用中，更容易暴露

public class CountTimeWindow {

    public static void main(String[] args) {
        TimeWheelContainer timeWheelContainer = new TimeWheelContainer(new TimeWheelCalculate(2, 20));

        timeWheelContainer.add(0, 1);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 0, "first");

        timeWheelContainer.add(1, 1);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 0, "first");

        timeWheelContainer.add(2, 1);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 2, "second");
        Assert.isTrue(timeWheelContainer.getCounts()[0] == 2, "second");

        for (int i = 3; i < 20; i++) {
            timeWheelContainer.add(i, 1);
            System.out.println("add index: " + i + " count: " + timeWheelContainer.getTimeWheelCount());
        }

        // 剛好一輪

        timeWheelContainer.add(20, 3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 20, "third");
        timeWheelContainer.add(21, 3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 20, "third");


        // 減去過(guò)期的那個(gè)數(shù)據(jù)
        timeWheelContainer.add(22, 3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 26 - 2, "fourth");
        Assert.isTrue(timeWheelContainer.getCounts()[0] == 6, "fourth");


        timeWheelContainer.add(26, 3);
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 24 - 2 - 2 + 3, "fifth");
        System.out.println(Arrays.toString(timeWheelContainer.getCounts()));


        timeWheelContainer.add(43, 3);
        System.out.println(Arrays.toString(timeWheelContainer.getCounts()));
        Assert.isTrue(timeWheelContainer.getTimeWheelCount() == 6, "six");
    }
}

一灰灰的個(gè)人博客，記錄所有學(xué)習(xí)和工作中的博文，歡迎大家前去逛逛

盡信書則不如，已上內(nèi)容，純屬一家之言，因個(gè)人能力有限，難免有疏漏和錯(cuò)誤之處，如發(fā)現(xiàn)bug或者有更好的建議，歡迎批評(píng)指正，不吝感激

微博地址: 小灰灰Blog

QQ： 一灰灰/3302797840