基于Hbase散列概要森林对时序数据进行索引的方法

摘要

本发明公开了一种基于Hbase散列概要森林对时序数据进行索引的方法，包括以下步骤：(1)根据时间粒度建立每棵时间单元树；(2)求取每棵时间单元树的散列码，并将带有散列码的时间单元树组成基于Hbase的散列概要森林；(3)将采集的时序数据根据散列码插入到散列概要森林中；(4)根据时间范围查询读取存储的时序数据。本发明通过结合概要森林树形索引方案，提高时序数据聚合操作的查询速度，同时通过生成散列码为单元树提供散列索引，解决Hbase分布式存储时序数据产生热点问题。

说明书

技术领域

本发明涉及存储技术领域，具体涉及一种基于Hbase散列概要森林对时序数据进行索引的方法。

背景技术

时序数据为以时间序列索引的连续数据，随着计算机应用的普及，时序数据在各个领域也得到了广泛的应用。例如：随着金融领域与互联网的结合越来越紧密，金融领域大量的量化回撤操作对时序数据的聚合操作性能需求越来越大。例如：对期货中一个季度时间范围内的某种商品合约的市价、盘口价格或成交量等进行统计，进行求和或计算最大值等聚合操作。这样的应用场景在金融量化中出现频繁，并且由于数据量巨大，如何快速准确地计算t1～t2时间内的金融时序数据的聚合操作结果变得十分重要。

以对Au金属期货交易数据中一定时间范围内市价的求和操作为例：

Select SUM(Last Price)From‘Au’WHERE time>t1AND time<t2

在这样的应用场景下，必须支持在海量的时序数据中快速取得聚合操作结果。

传统关系型数据库主要采用物化视图或概要表的方式达到加速聚合查询的目的。物化视图是对涉及表连接的查询命令进行预处理，并将结果保存在视图表中，查询时直接取出预处理好的结果。概要表则是在写入数据的同时，计算并保存相应的概要信息，从而发生查询时，直接从概要表中查询并返回结果。此类方法提高了查询效率，但是缺点是增加了数据库的膨胀率。在NoSQL数据库中，一些数据库采用MapReduce和聚合管道的方式来处理这些聚合操作，其都是实时计算的代表，虽然没有增加数据库的膨胀率，但查询过程中产生了大量的磁盘和计算开销，低效耗时，无法满足即席查询的需求。一些NoSQL数据库将树型索引结构融合，提高了查询效率，减少了磁盘访问次数。

发明内容

鉴于上述，本发明提出了一种基于Hbase散列概要森林对时序数据进行索引的方法，通过建立树形索引加快了时序数据的查询时间，并通过散列码避免了时序数据在分布式数据库中顺序存储产生的空间分配不均的问题。

一种基于Hbase散列概要森林对时序数据进行索引的方法，包括以下步骤：

(1)根据时间粒度建立每棵时间单元树；

(2)求取每棵时间单元树的散列码，并将带有散列码的时间单元树组成基于Hbase的散列概要森林；

(3)将采集的时序数据根据散列码插入到散列概要森林中；

(4)根据时间范围查询读取存储的时序数据。

步骤(1)中，建立时间单元树的过程为：首先，预先确定时间单元树的时间粒度；然后以根节点开始进行递归，每次建立一个新的节点，接下来，递归建立此节点的左右孩子节点，当创建的节点超出预先计算的范围时停止递归，完成整棵树的建立过程。

在步骤(1)中，每棵时间单元树是一棵线段树，且包含一个固定时间粒度。通过控制每棵树的树高来控制时间粒度。线段树节点存储该节点范围的概要信息，主要包括：LBound、RBound、LNode、RNode以及Data；其中，LBound、RBound分别表示该节点包含时间范围的起始时间点和终止时间点；LNode、RNode分别表示该节点左孩子和右孩子节点包含时间点的中点；Data表示该节点存放的概要数据值，此时建立的时间单元树的每个节点的Data是空的。

每棵树的根节点表示这棵树携带的t时间长度内时序数据的聚合结果，第二层节点携带t/2时间长度内时序数据的聚合结果，类推每层节点携带上一层节点一半时间长度的索引数据。通过控制树高从而实现包含固定时间粒度的时间单元树可以方便用同一个散列码聚合每棵树的节点，实现热点的负载均衡。

一棵时间单元树表示一个单元时间粒度范围的聚合结果，每棵树的叶子节点表示最细粒度范围的聚合概要信息。粒度可根据实际需求调整。

时间单元树覆盖时间(TreeBound)计算公式：

TreeBound＝(2^(TreeMaxLevel-1))*Leaf Bound

其中，TreeMaxLevel为最大树高，LeafBound为叶子节点表示的时间范围。例如：一棵时间单元树时间范围定为一天，树高定为9层，叶子节点表示6分钟的概要信息。所以一棵树共管辖1536分钟的聚合数据，实现一棵时间单元树覆盖一天的时间范围。

在步骤(2)中，求取每棵时间单元树的散列码的方式有很多，作为优选，选取通过对每棵树的信息进行md5转码处理生成此时间单元树的对应散列码(Hash)，并将其写入tree hash表中；计算散列码的具体方式为：

Hash＝md5(tree Info+tree low bound)

tree info为数据标识简要信息，例如：此数据代表Au金属元素期货数据，则标注为Au，tree low bound为时间单元树的起始时间点。

多棵时间单元树组成散列概要森林，整个散列概要森林所索引的数据的时间范围为组成他的时间单元树所表示的时间范围之和。

基于Hbase的散列概要森林由tree-hash和tree-node两个Hbase表组成，其中，tree-hash表用于查找时间单元树的散列码，tree-node表存储所有的时间单元树的树节点，且tree-hash表与tree-node表是单独存储，即将每棵时间单元树的散列码与每棵时间单元树载有的时序数据分开单独存储，并且将拥有相同散列码的时间单元树载有的时序数据集中存储。

在步骤(3)中，所述的时序数据可以是金融时序数据、期货交易数据等任一时序数据。

在步骤(3)中，将时序数据插入到散列概要森林的具体过程为：

(3-1)通过时序数据的所属于的时间在tree-hash表中找到此时序数据所在的时间单元树的tree hash值；

(3-2)找到该tree hash值所对应的tree-node表，将时序数据递归插入到此tree-node表中，具体过程为：

首先，根据tree hash值找到所处时间单元树的根节点开始递归，然后进行时序数据的时间点与当前查询节点的时间对比，当时序数据的时间点小于该节点的时间时，向该节点的左孩子递归插入时序数据，当时序数据的时间点大于该节点时间时，则该节点的右孩子递归插入时序数据；直到插入到时间单元树的叶子节点为止。

在步骤(4)中，在数据查询时，散列概要森林由于同一个时间单元树中的数据的rowkey拥有同样的散列码，所以hbase范围查询可以快速找出整棵时间单元树并存入内存中，这大大节省对树进行递归后的磁盘IO操作。

进行数据查询的过程为：

(a)判断查询时间范围(t1,t2)是否属于同一个时间单元树范围，若是，执行步骤(b)，若否，执行步骤(c)；

(b)查询操作为Query(t1,t2)；

(c)查询操作为Query(t1,EndUnitTime(t1))、Query(midUnitTime)以及Query(StartUnitTime(t2),t2)；

其中，StartUnitTime(t1)为时间点t1所处的时间单元的起始时间点；

EndUnitTime(t2)为时间点t2所处的时间单元的结束时间点；

midUnitTime为t1与t2所处的时间单元树的时间范围之间的若干单元树的时间范围；

Query(t1,t2)表示为在同一棵时间单元树中查询时间范围(t1,t2)的执行查询操作；

Query(t1,EndUnitTime(t1))表示在查询范围中的第一棵单元树中执行查询操作；

Query(midUnitTime)表示在查询范围中的第二棵到第倒数第二棵单元树中执行查询操作；

Query(StartUnitTime(t2),t2)表示在查询范围中的最后一棵单元树中执行查询操作。

Query(t1,t2)的具体过程为：

(a)通过查找项的时间推算出其所属时间单元树的散列码并定位到此时间单元树，并将此时间单元树的根节点作为当前根节点；

(b)从当前根节点开始递归查询，查询任务从(t1,t2)开始；

(c)递归查询到当前节点时，解析出该节点包含的时间范围的起始时间点LBound、中间时间点midTime以及终止时间点RBound；

(d)判断t1与t2是否满足t1＝LBound且t2＝RBound，若是，记录该节点结果并退出递归，若否，执行步骤(e)；

(e)判断t1与t2是否满足t1≤midTime且t2≤midTime，若是，将该节点的左孩子节点作为当前根节点，跳转执行步骤(b)～步骤(d)，若否，执行步骤(f)；

(f)判断t1与t2是否满足t1≥midTime且t2≥midTime，若是，将该节点的右孩子节点作为当前根节点，执行步骤(b)～步骤(d)；若否，执行步骤(g)；

(g)判断时间t2是否满足LBound<t2<midTime，若是，将左孩子作为当前节点，将midTime作为t2，执行步骤(b)～步骤(d)；将右孩子节点作为当前节点，将midTime作为t1，执行步骤(b)～步骤(d)。

本发明通过结合概要森林树形索引方案，提高时序数据聚合操作的查询速度，同时通过生成散列码为单元树提供散列索引，解决Hbase分布式存储时序数据产生热点问题。

附图说明

图1为本发明基于Hbase散列概要森林对时序数据进行索引的方法的流程图；

图2为建立的时间单元树的结构示意图；

图3为本发明实施例1中写入数据吞吐量对比图；

图4为本发明实施例2中大跨度时间范围聚合查询耗时对比图；

图5为本发明实施例3中散列概要深林方法与非散列概要深林方法查询耗时对比图。

具体实施方式

为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技术方案进行详细说明。

如图1所示，基于Hbase散列概要森林对时序数据进行索引的方法的具体步骤为：

步骤1，建立每棵时间单元树：首先，预先确定时间单元树的时间范围；然后以根节点开始进行递归，每次建立一个新的节点，接下来，递归建立此节点的左右孩子节点，当创建的节点超出预先计算的范围时停止递归，完成整棵树的建立过程，并将每个节点写入tree node表中，建立的时间单元树如图2所示；

此步骤中，建立的每棵时间单元树是一棵线段树，且包含一个固定时间粒度。通过控制每棵树的树高来控制时间粒度。线段树节点存储该节点范围的概要信息，主要包括：LBound、RBound、LNode、RNode以及Data；其中，LBound、RBound分别表示该节点包含时间范围的起始时间点和终止时间点；LNode、RNode分别表示该节点左孩子和右孩子节点包含时间点的中点；Data表示该节点存放的概要数据值，此时建立的时间单元树的每个节点的Data是空的。

每棵树的根节点表示这棵树携带的t时间长度内时序数据的聚合结果，第二层节点携带t/2时间长度内时序数据的聚合结果，类推每层节点携带上一层节点一半时间长度的索引数据。通过控制树高从而实现包含固定时间粒度的时间单元树可以方便用同一个散列码聚合每棵树的节点，实现热点的负载均衡。

一棵时间单元树表示一个单元时间粒度范围的聚合结果，每棵树的叶子节点表示最细粒度范围的聚合概要信息。粒度可根据实际需求调整。

时间单元树覆盖时间(TreeBound)计算公式：

TreeBound＝(2^(TreeMaxLevel-1))*Leaf Bound

其中，TreeMaxLevel为树最大树高，LeafBound为叶子节点表示的时间范围。

步骤2，求取每棵时间单元树的散列码，并将带有散列码的时间单元树组成基于Hbase的散列概要森林；

此步骤中，计算散列码的具体方式为：

Hash＝md5(tree Info+tree low bound)

tree info为数据标识简要信息，例如此数据代表Au金属元素期货数据，则标注为Au；tree low bound为时间单元树的起始时间点，将求得Hash值写入tree hash表中；

步骤3，将采集的时序数据插入到散列概要森林中，插入过程为：

步骤3-1，通过时序数据的所属于的时间在tree-hash表中找到此时序数据所在的时间单元树的tree hash值；

步骤3-2，找到该tree hash值所对应的tree-node表，将时序数据递归插入到此tree-node表中，具体过程为：

首先，根据tree hash值找到所处时间单元树的根节点开始递归，然后进行时序数据的时间点与当前查询节点的时间对比，当时序数据的时间点小于该节点的时间时，向该节点的左孩子递归插入时序数据，当时序数据的时间点大于该节点时间时，则该节点的右孩子递归插入时序数据；直到插入到时间单元树的叶子节点为止。

步骤4，根据时间范围查询读取存储的时序数据，查询的过程为：

步骤4-1，判断查询时间范围(t1,t2)是否属于同一个时间单元树范围，若是，执行步骤4-2，若否，执行步骤4-3；

步骤4-2，查询操作为Query(t1,t2)；

步骤4-3，查询操作为Query(t1,EndUnitTime(t1))、Query(midUnitTime)以及Query(StartUnitTime(t2),t2)。

实施例1

利用本发明方法、Opentsdb开源时序数据库方法以及原始Hbase方法对相同的时序数据进行数据写入，并记录每种方法的写入吞吐量，如图3所示，从图3可以得到本发明方法由于有索引(散列码)和建树过程，所以数据写入速度比原始Hbase方法直接存入原始数据慢，但比opentsdb开源时序数据库方法写入速度快。

表1显示的是本发明方法进行数据写入时，Hbase中的region的分裂情况。

从表1可以看出散列概要森林在触发Hbase的region分裂后按散列值分裂为多个region。拥有相同散列值的同一棵时间单元树会分在同一个region中。散列值随机生成，新建的树均匀负载地散列在不同的region中，避免了热点问题。

实施例2

利用本发明方法、Opentsdb开源时序数据库方法以及原始Hbase方法对数据进行大跨度时间范围的聚合查询操作，图4为三种方法在长时间范围聚合查询耗时对比图，从图4可以得到在大跨度时间范围的聚合查询操作中，本发明方法表现较好。同时可以看出原始Hbase方法在查询200000条数据的聚合结果时，耗时数十秒，无法满足快速即席查询需求。Opentsdb开源时序数据库方法由于缓存以及索引机制速度大大提升。本发明方法比Opentsdb查询速度更快，且随着查询范围增大，查询耗时增幅较其他方案更缓慢。说明利用hbase的rowkey设计，使用范围查询将整棵树查出放入内存对查询性能有优化作用，节约了磁盘开销。

实施例3

利用本发明方法与非散列方法对数据进行聚合查询操作，图5为散列概要森林方法以及非散列方法查询耗时对比图。从图5可以得到非散列方案rowkey缺少散列字段，并且查询搜索线段树每次递归时对hbase进行随机查询。同一棵线段树可能分散在不同的region中，本发明方法的查询耗时小于非散列方法，且随着查询范围的增大优势越明显。

以上所述的具体实施方式对本发明的技术方案和有益效果进行了详细说明，应理解的是以上所述仅为本发明的最优选实施例，并不用于限制本发明，凡在本发明的原则范围内所做的任何修改、补充和等同替换等，均应包含在本发明的保护范围之内。