文档章节

180621-一个简单的时间窗口设计与实现

小灰灰Blog
 小灰灰Blog
发布于 06/21 19:29
字数 1827
阅读 24
收藏 10

logo

如何设计一个计数的时间窗口

时间窗口,通常对于一些实时信息展示中用得比较多,比如维持一个五分钟的交易明细时间窗口,就需要记录当前时间,到五分钟之前的所有交易明细,而五分钟之前的数据,则丢掉

一个简单的实现就是用一个队列来做,新的数据在对头添加;同时起一个线程,不断的询问队尾的数据是否过期,如果过期则丢掉

另外一中场景需要利用到这个时间窗口内的数据进行计算,如计算着五分钟交易中资金的流入流出总和,如果依然用上面的这种方式,会有什么问题?

  • 如果时间窗口大,需要存储大量的明细数据
  • 我们主要关心的只有资金流入流出;存这些明细数据得不偿失
  • 每次新增or删除过期数据时,实时计算流入流出消耗性能

针对这种特殊的场景,是否有什么取巧的实现方式呢?

<!-- more -->

I. 方案设计

1. 基于队列的轮询删除方式

将时间窗口分割成一个一个的时间片,每个时间片中记录资金的流入流出总数,然后总的流入流出就是所有时间片的流入流出的和

新增数据:

  • 若未跨时间片,则更新队头的值
  • 若跨时间片,新增一个队列头

删除数据:

  • 轮询任务,判断队列尾是否过期
  • 队尾过期,则删除队尾,此时若队头数据未加入计算,也需要加入计算

image.png

2. 基于队列的新增时删除方式

相比较前面的轮询方式,这个的应用场景为另外一种,只有在新增数据时,确保数据的准确性即可,不需要轮询的任务去删除过期的数据

简单来说,某些场景下(比如能确保数据不会断续的进来,即每个时间片都至少有一个数据过来),此时希望我的时间窗口数据是由新增的数据来驱动并更新

新增数据:

  • 未跨时间片,则更新队头值
  • 跨时间片,新塞入一个,并删除旧的数据

image.png

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<Integer> getExpireIndexes(long lastInsertTime, long nowInsertTime) {
        if (nowInsertTime - lastInsertTime >= length) {
            // 已经过了一轮,过去的数据全部丢掉
            return null;
        }

        List<Integer> 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<Integer> 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. 一灰灰Bloghttps://liuyueyi.github.io/hexblog

一灰灰的个人博客,记录所有学习和工作中的博文,欢迎大家前去逛逛

2. 声明

尽信书则不如,已上内容,纯属一家之言,因个人能力有限,难免有疏漏和错误之处,如发现bug或者有更好的建议,欢迎批评指正,不吝感激

3. 扫描关注

blogInfoV2.png

© 著作权归作者所有

共有 人打赏支持
小灰灰Blog
粉丝 170
博文 172
码字总数 287892
作品 0
武汉
程序员
2、Java并发性和多线程-多线程的优点

以下内容转自http://ifeve.com/benefits/: 尽管面临很多挑战,多线程有一些优点使得它一直被使用。这些优点是: 资源利用率更好 程序设计在某些情况下更简单 程序响应更快 资源利用率更好 ...

easonjim
2017/06/14
0
0
Emacs Application Framework

Emacs Application Framework 的折腾之路 用了Emacs将近13年了, Emacs的使用时间几乎等于我的编程生涯, 可以说这么多年的编程能力和专注力都是靠Emacs来帮我增长的. Emacs最大的威力是, 一旦...

ManateeLazyCat
08/06
0
0
Android应用内悬浮窗的实现方案

1、悬浮窗的基本介绍 悬浮窗,大家应该也不陌生,凌驾于应用之上的一个小弹窗,实现上很简单,就是添加一个系统级别的窗口,Android中通过WindowManagerService( WMS)来管理所有的窗口,对...

C6C
2017/08/01
0
0
180621 简书互联网优质内容推荐日报

【专题推荐】 创始人说 收录CEO们的创业笔记和行业思考 点击关注:https://www.jianshu.com/c/1cc0b2ea91c7 【营销理论】 我花了100+小时,找到3种模型,教你打造高粘性产品。 作者: 康熙师...

简书大婶
06/21
0
0
stream-window

介绍 window(窗口)是Flink流处理中非常重要的概念,本篇我们来对窗口相关的概念以及关联的实现进行解析。本篇的内容主要集中在package org.apache.flink.streaming.api.windowing下。 Wind...

苗栋栋
2017/11/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用Newtonsoft将DataTable转Json

使用Newtonsoft将DataTable转Json Newtonsoft提供的将DataTable转成Json: /// <summary> /// DataTable转Json /// </summary> /// <param name="dt"></param> /// <ret......

DemonsI
20分钟前
1
0
centos7安装zookeeper3.4.6

注:zookeeper充当注册中心 下载地址 http://mirror.bit.edu.cn/apache/zookeeper/zookeeper-3.4.6/ 单机 下载完成后,将安装包上传值服务器,解压 tar xvzf zookeeper-3.4.6.tar.gz 进入解...

码代码的小司机
21分钟前
1
0
136. Single Number

136. Single Number 题意:一个数组中所有数字都是两两相同,只有一个数字是单独的,求出这个数字的值。 很简单的题,使用异或就能处理。 异或介绍:bit位上的值不同,异或后,值为1.否则为0...

117
23分钟前
1
0
Hash和HashCode深入理解

目录介绍 1.Hash的作用介绍 1.1 Hash的定义 1.2 Hash函数特性 1.3 Hash的使用场景 2.如何判断两个对象相等 2.1 判断两个字符串 2.2 判断两个int数值 2.3 其他基本类型 3.HashCode深入分析 3....

潇湘剑雨
29分钟前
1
0
ecshop 漏洞如何修复 补丁升级与安全修复详情

目前ecshop漏洞大面积爆发,包括最新版的ecshop 3.0,ecshop 4.0,ecshop2.7.3全系列版本都存在着高危网站漏洞,导致网站被黑,被篡改,被挂马,许多商城系统深受其漏洞的攻击,给商城的运营者...

网站安全
29分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部