180621-一個(gè)簡單的時(shí)間窗口設(shè)計(jì)與實(shí)現(xiàn)

XiNGRZ 發(fā)布于2019-08-16 12:33 / 3241人閱讀

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

如何設(shè)計(jì)一個(gè)計(jì)數(shù)的時(shí)間窗口

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

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

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

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

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

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

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

I. 方案設(shè)計(jì) 1. 基于隊(duì)列的輪詢刪除方式

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

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

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

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

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

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

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

2. 基于隊(duì)列的新增時(shí)刪除方式

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

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

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

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

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

II. 基于數(shù)組的時(shí)間窗口實(shí)現(xiàn)

針對上面第二種，基于數(shù)組給出一個(gè)簡單的實(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í)間窗口，該怎么來實(shí)現(xiàn)呢？能否用一個(gè)隊(duì)列就滿足所有的時(shí)間窗口的計(jì)算呢？關(guān)于這些留待下一篇給出

1. 時(shí)間輪計(jì)算器

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

固定長度，避免頻繁的新增和刪除對象

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

首先是需要實(shí)現(xiàn)一個(gè)時(shí)間輪計(jì)算器，根據(jù)傳入的時(shí)間，獲取需要刪除的過期數(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);
    }

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

        List removeIndexList = new ArrayList<>();
        int lastIndex = calculateIndex(lastInsertTime);
        int nowIndex = calculateIndex(nowInsertTime);
        if (lastIndex == nowIndex) {
            // 還沒有跨過這個(gè)時(shí)間片，則不需要刪除過期數(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)比較簡單，首先是指定時(shí)間窗口的長度(length),時(shí)間片(period)，其主要提供兩個(gè)方法

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

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

2. 時(shí)間輪容器

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

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

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

@Data
public class TimeWheelContainer {
    private TimeWheelCalculate calculate;

    /**
     * 歷史時(shí)間片計(jì)數(shù)，每個(gè)時(shí)間片對應(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í)間間隔超過一輪，則清空計(jì)數(shù)
            realTimeCount = amount;
            lastInsertTime = now;
            timeWheelCount = 0;
            clear();
            return;
        }

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

        // 跨過了時(shí)間片，則需要在總數(shù)中刪除過期的數(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;
        }
    }
}

3. 測試

主要就是驗(yàn)證上面的實(shí)現(xià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");


        // 減去過期的那個(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");
    }
}

III. 其他 1. 一灰灰Blog： https://liuyueyi.github.io/he...

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

2. 聲明

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

微博地址: 小灰灰Blog

QQ：一灰灰/3302797840

3. 掃描關(guān)注

GPU云服務(wù)器云服務(wù)器基于webrtc的視頻會議系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 基于防火墻技術(shù)的校園網(wǎng)絡(luò)安全設(shè)計(jì)與實(shí)現(xiàn) linux操作系統(tǒng)的web服務(wù)器的設(shè)計(jì)與實(shí)現(xiàn) 數(shù)據(jù)倉庫設(shè)計(jì)與實(shí)現(xiàn)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71290.html

發(fā)表評論

登陸后可評論

0條評論

XiNGRZ

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow-serving

閱讀 3036·2023-04-25 20:22
BFC(塊級格式化上下文)的特點(diǎn)和應(yīng)用場景

閱讀 3350·2019-08-30 11:14
頁面布局解決方案

閱讀 2602·2019-08-29 13:03
前端面試--性能優(yōu)化

閱讀 3191·2019-08-26 13:47
發(fā)布訂閱模式-實(shí)現(xiàn)公眾號訂閱/內(nèi)容發(fā)布/取消訂閱功能

閱讀 3235·2019-08-26 10:22
JS動態(tài)解析瀏覽器和網(wǎng)頁的各種寬高屬性

閱讀 1279·2019-08-23 18:26
看完這篇，你也可以實(shí)現(xiàn)一個(gè)360度全景插件

閱讀 628·2019-08-23 17:16
區(qū)塊鏈項(xiàng)目如何俘獲用戶芳心，這些用戶心聲你值得聽一聽

閱讀 1923·2019-08-23 17:01

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

180621-一個(gè)簡單的時(shí)間窗口設(shè)計(jì)與實(shí)現(xiàn)

相關(guān)文章

“怎么做好云遷移”? 深藍(lán)云海資深架構(gòu)師給你答案

TBSSQL 的那些事 | TiDB Hackathon 2018 優(yōu)秀項(xiàng)目分享

限流器及Guava實(shí)現(xiàn)分析

**vivo統(tǒng)一告警平臺設(shè)計(jì)與實(shí)踐**

發(fā)表評論

0條評論

XiNGRZ

男|高級講師

TA的文章

tensorflow-serving

BFC(塊級格式化上下文)的特點(diǎn)和應(yīng)用場景

頁面布局解決方案

前端面試--性能優(yōu)化

發(fā)布訂閱模式-實(shí)現(xiàn)公眾號訂閱/內(nèi)容發(fā)布/取消訂閱功能

JS動態(tài)解析瀏覽器和網(wǎng)頁的各種寬高屬性

看完這篇，你也可以實(shí)現(xiàn)一個(gè)360度全景插件

區(qū)塊鏈項(xiàng)目如何俘獲用戶芳心，這些用戶心聲你值得聽一聽

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

180621-一個(gè)簡單的時(shí)間窗口設(shè)計(jì)與實(shí)現(xiàn)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！