180621-一個簡單的時間窗口設計與實現

XiNGRZ 發布于2019-08-16 12:33 / 3229人閱讀

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

如何設計一個計數的時間窗口

時間窗口，通常對于一些實時信息展示中用得比較多，比如維持一個五分鐘的交易明細時間窗口，就需要記錄當前時間，到五分鐘之前的所有交易明細，而五分鐘之前的數據，則丟掉

一個簡單的實現就是用一個隊列來做，新的數據在對頭添加；同時起一個線程，不斷的詢問隊尾的數據是否過期，如果過期則丟掉

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

如果時間窗口大，需要存儲大量的明細數據

我們主要關心的只有資金流入流出；存這些明細數據得不償失

每次新增or刪除過期數據時，實時計算流入流出消耗性能

針對這種特殊的場景，是否有什么取巧的實現方式呢？

I. 方案設計 1. 基于隊列的輪詢刪除方式

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

新增數據：

若未跨時間片，則更新隊頭的值

若跨時間片，新增一個隊列頭

刪除數據：

輪詢任務，判斷隊列尾是否過期

隊尾過期，則刪除隊尾，此時若隊頭數據未加入計算，也需要加入計算

2. 基于隊列的新增時刪除方式

相比較前面的輪詢方式，這個的應用場景為另外一種，只有在新增數據時，確保數據的準確性即可，不需要輪詢的任務去刪除過期的數據

簡單來說，某些場景下（比如能確保數據不會斷續的進來，即每個時間片都至少有一個數據過來），此時希望我的時間窗口數據是由新增的數據來驅動并更新

新增數據：

未跨時間片，則更新隊頭值

跨時間片，新塞入一個，并刪除舊的數據

II. 基于數組的時間窗口實現

針對上面第二種，基于數組給出一個簡單的實現，本篇主要是給出一個基礎的時間窗口的設計與實現方式，當然也需要有進階的case，比如上面的資金流入流出中，我需要分別計算5min,10min,30min,1h,3h,6h,12h,24h的時間窗口，該怎么來實現呢？能否用一個隊列就滿足所有的時間窗口的計算呢？關于這些留待下一篇給出

1. 時間輪計算器

前面用隊列的方式比較好理解，這里為什么用數組方式來實現？

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

定位和更新數據方便

首先是需要實現一個時間輪計算器，根據傳入的時間，獲取需要刪除的過期數據

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

    private int period;
    private int length;

    /**
     * 劃分的時間片個數
     */
    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);
    }

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

        List removeIndexList = new ArrayList<>();
        int lastIndex = calculateIndex(lastInsertTime);
        int nowIndex = calculateIndex(nowInsertTime);
        if (lastIndex == nowIndex) {
            // 還沒有跨過這個時間片，則不需要刪除過期數據
            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;
    }
}

這個計算器的實現比較簡單，首先是指定時間窗口的長度(length),時間片(period)，其主要提供兩個方法

calculateIndex 根據當前時間，確定過期的數據在數組的索引

getExpireIndexes 根據上次插入的時間，和當前插入的時間，計算兩次插入時間之間，所有的過期數據索引

2. 時間輪容器

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

若跨時間片，則刪除過期數據，更新實時數據，更新總數

若未跨時間片，則直接更新實時數據即可

@Data
public class TimeWheelContainer {
    private TimeWheelCalculate calculate;

    /**
     * 歷史時間片計數，每個時間片對應其中的一個元素
     */
    private int[] counts;

    /**
     * 實時的時間片計數
     */
    private int realTimeCount;

    /**
     * 整個時間輪計數
     */
    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) {
            // 兩者時間間隔超過一輪，則清空計數
            realTimeCount = amount;
            lastInsertTime = now;
            timeWheelCount = 0;
            clear();
            return;
        }

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

        // 跨過了時間片，則需要在總數中刪除過期的數據，并追加新的數據
        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. 測試

主要就是驗證上面的實現有沒有明顯的問題，為什么是明顯的問題？

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

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");


        // 減去過期的那個數據
        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...

一灰灰的個人博客，記錄所有學習和工作中的博文，歡迎大家前去逛逛

2. 聲明

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

微博地址: 小灰灰Blog

QQ：一灰灰/3302797840

3. 掃描關注

云服務器 GPU云服務器基于webrtc的視頻會議系統的設計與實現基于防火墻技術的校園網絡安全設計與實現 linux操作系統的web服務器的設計與實現數據倉庫設計與實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71290.html

“怎么做好云遷移”? 深藍云海資深架構師給你答案

摘要：基于云遷移的三個階段細分為八個主要步驟，評估階段主要包括項目啟動現狀梳理以及應用系統關聯關系分析三個步驟，設計階段包括云架構優化設計和云遷移方案設計，實施階段包括目標架構遷移演練及實施和試運行三個步驟。在云計算市場規模不斷擴大的大背景下，云遷移的需求越來越大且面臨挑戰。云遷移不是一個遷移軟件工具，而是一種服務。前IBM資深架構師姜亞杰從云遷移的三個階段、四個維度到八個步驟的方法，簡述...

kk_miles 2019-06-21 16:47 評論0 收藏0
TBSSQL 的那些事 | TiDB Hackathon 2018 優秀項目分享

摘要：當我們正準備做前期調研和設計的時候，主辦方把唐長老拉去做現場導師，參賽規則規定導師不能下場比賽，囧，于是就這樣被被動放了鴿子。川總早早來到現場。本文作者是來自 TiBoys 隊的崔秋同學，他們的項目 TBSSQL 在 TiDB Hackathon 2018 中獲得了一等獎。TiDB Batch and Streaming SQL（簡稱 TBSSQL）擴展了 TiDB 的 SQL 引擎...

KnewOne 2019-06-25 19:00 評論0 收藏0
限流器及Guava實現分析

摘要：計數限流算法無論固定窗口還是滑動窗口核心均是對請求進行計數，區別僅僅在于對于計數時間區間的處理。令牌桶限流實現原理令牌桶限流的實現原理在有詳細說明。因此由此為入口進行分析。目前可返回的實現子類包括及兩種，具體不同下文詳細分析。限流限流一詞常用于計算機網絡之中，定義如下： In computer networks, rate limiting is used to control t...

xcc3641 2019-08-19 11:05 評論0 收藏0
vivo統一告警平臺設計與實踐

摘要：告警當一個問題通過告警系統將消息以短信電話郵件等方式告知給用戶時，我們稱之為一條告警。圖統一告警系統結構圖告警收斂對于告警平臺每天會產生數以萬計的告警，這些告警對于運維或開發人員都需要去分析甄別優先級并處理故障。一、背景一套監控系統檢測和告警是密不可分的，檢測用來發現異常，告警用來將問題信息發送給相應的人。v...

Rocko 2021-11-22 14:56 評論0 收藏0