文档章节

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

小灰灰Blog
 小灰灰Blog
发布于 06/21 19:29
字数 1827
阅读 5
收藏 10
点赞 0
评论 0

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
粉丝 163
博文 163
码字总数 271153
作品 0
武汉
程序员
180621 简书互联网优质内容推荐日报

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

简书大婶
06/21
0
0
2、Java并发性和多线程-多线程的优点

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

easonjim
2017/06/14
0
0
Android应用内悬浮窗的实现方案

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

C6C
2017/08/01
0
0
【Java并发性和多线程】多线程的优点

本文为转载学习 原文链接:http://tutorials.jenkov.com/java-concurrency/benefits.html 译文链接:http://ifeve.com/benefits/ 尽管面临很多挑战,多线程有一些优点使得它一直被使用。这些...

heroShane
2014/01/28
0
0
stream-window

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

苗栋栋
2017/11/19
0
0
Beginning WF4读书笔记(一):创建一个简单的工作流

让我们以创建一个简单的工作流开始。开启Visual Studio (VS) 2010,选择New Project。在已经安装的模版下面,选择Visual C#-Workflow,你会看到提供了四个模版。 选择Workflow Console Appl...

晨曦之光
2012/03/09
0
0
Cocoa教学:Windows OOP与Cocoa MVC之对比

封装不封装,这是个问题。 今天我在看Cocoa开发者邮件列表的时候,看到一个帖子,求助如何在两个View之间互相通信的问题。做Windows程序员的时间长的我都不好意思说了,我意识到,这个问题在...

长平狐
2013/03/19
51
0
[Beautifulzzzz的博客目录] 快速索引点这儿O(∩_∩)O~~,红色标记的是不错的(⊙o⊙)哦~

3D相关开发 [direct-X] 1、direct-X最小框架 [OpenGL] 1、环境搭建及最小系统 [OpenGL] 2、企业版VC6.0自带的Win32-OpenGL工程浅析 51单片机 [51单片机] 1602液晶显示控制代码 [51单片机] 1...

史迪奇2号
2017/08/01
0
0
高性能计算引擎--Cubert

Cubert是一个用于复杂大数据分析的高性能计算引擎。这是为分析师和数据科学家编写的一个框架,提供“手动编写Java程序的所有效率优势,并提供了一个简单的、类似脚本的用户接口,用于解决各种...

三桂sg
2014/12/24
2.9K
0
数据库设计思路和要点

基本概念 单库 分片 解决单个数据表数据量太大的问题,将单个表的数据均匀的放入多个表中 复制 用于实现主从同步,主库的更新操作(insert/update/delete)向从库(1个或多个)进行同步,同步...

真爱2015
2016/09/28
11
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

回想过往,分析当下,着眼未来

好久没有真正的在纸质笔记本上写过东西了,感觉都快不会写字了,笔画都不知道怎么写了。接下来就说说咱们的正事。 2018年7月22日,我做了一个决定,那就是去参加安全培训(可能是我职业生涯中...

yeahlife
31分钟前
1
0
关于工作中的人际交往

关于工作中的人际交往 Intro 写了篇发泄情绪的博客,但不会发布出来。 大概就是,要么忍,要么滚。 以及一些不那么符合社会主义核心价值观,不满于大资本家与小资本家剥削的废话。

uniqptr
36分钟前
0
0
springMVC的流程

1.用户发送请求至前端控制器DispatcherServlet 2.DispatcherServlet收到请求调用HandlerMapping处理器映射器。 3.处理器映射器根据请求url找到具体的处理器,生成处理器对象及处理器拦截器(...

JavaSon712
52分钟前
0
0
大数据教程(3.2):Linux系统软件安装之自动化脚本

博主前面文章有介绍过软件的安装,可以帮助IT人员顺利的完成功能软件安装;但是,对于我们运维人员或者需要管理软件安装的项目经理来说,有些应用一次行需要搭建很多台相同的软件环境(如tom...

em_aaron
今天
0
1
Spring Boot 2.0.3 JDBC整合Oracle 12

整合步骤 1. Oracle驱动引入 Oracle驱动一般不能通过maven仓库直接下载得到,需自行下载并导入到项目的lib目录下,建议通过如下pom依赖引入下载的Oracle驱动 <!-- Oracle 驱动 -->...

OSC_fly
今天
0
0
java 8 并行流 - 1

下面创建一个并行流,与顺序流 //顺序流Stream.iterate(0L, i -> i + 1) .limit(Integer.MAX_VALUE) .reduce(0L, Long::sum);//并行流Stream.iterate(0L, i -> i......

Canaan_
今天
0
0
数据结构与算法5

二分法采用向下取整的方法 使用有序数组的好处是查找的速度比无序数组快的多,不好的方面是因为要将所有靠后的数据移开,所以速度较慢,有序数组和无序数组的删除操作都很慢。 有序数组在查找...

沉迷于编程的小菜菜
昨天
1
1
SpringBoot | 第十一章:Redis的集成和简单使用

前言 上几节讲了利用Mybatis-Plus这个第三方的ORM框架进行数据库访问,在实际工作中,在存储一些非结构化或者缓存一些临时数据及热点数据时,一般上都会用上mongodb和redis进行这方面的需求。...

oKong
昨天
5
0
对基于深度神经网络的Auto Encoder用于异常检测的一些思考

一、前言 现实中,大部分数据都是无标签的,人和动物多数情况下都是通过无监督学习获取概念,故而无监督学习拥有广阔的业务场景。举几个场景:网络流量是正常流量还是攻击流量、视频中的人的...

冷血狂魔
昨天
0
0
并发设计之A系统调用B系统

A-->B A在发送请求之前,用乐观锁,减少对B的重复调用,这样一定程度上是幂等性。 比如A系统支付功能,要调用B系统进行支付操作,但是前端对"支付"按钮不进行控制,即用户会不断多次点击支付...

汉斯-冯-拉特
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部