Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

一、总体设计

1. 设计背景

(1)目前仅使用数据文件中预聚合信息加速聚合查询在文件增多时较为耗时;

(2)乱序数据会破坏预聚合信息的有效性,从而需要读取原始数据,使得查询速度变慢。

2. 设计阶段

(1)本阶段设计:默认分区关闭,即仅有1个分区,每一个序列有一个PISA索引—— 每个序列有一个索引管理器。

(2)下阶段设计:开启分区后,索引建立在分区内部,不跨分区;每一个序列,每一个分区有一个PISA索引—— 每个分区、每个序列各有一个索引管理器。

3. 设计目标

(1)使用线段树结构,对于树中的内部节点,不存储节点所覆盖的时间范围的最早或最晚时间戳,

...

在任意时间范围内获取准确的聚合结果,保证有乱序数据存在时,查询结果准确性。


二、索引的构建

1. 构建时间

(1)memtable flush落盘时,触发索引的构建。每写好一个叶子节点(达到配置或计算的窗口时间长度),就将该节点交给索引管理器。

...

假设1个分区为1周(604,800s),则每个窗口长度为37,800s。

2. 说明

(1)索引的构建从1970年1月1日0点开始,从1开始对LN进行编号。对于之前不存在的时间数据对应的节点,树的叶子节点编号保留,

...

(3)将所有的PISA索引存储到一个存储组中,便于针对索引的删除和更新的操作。

有无索引记录在 MTree 叶子节点

3. 构建步骤

(1)memtable flush落盘时,索引管理器根据此memtable、内存中保留的之前的memtable的“尾巴数据”(统计数据)和用户配置,

...

(3)计算可能的兄弟节点的节点号NN,若兄弟节点存在于内存中,则执行合并操作,逐层向上生成父亲节点。

4. 示例

如图所示,假设LN=1,2,7的窗口没有数据,NN=6,10,12,18的节点在内存中。

...

最终存在于内存中的节点为NN=6,14,18的三个节点。


三、乱序数据处理

有乱序数据写入内存时,将对应位置修改为1

(1)无分区情况下:LinkedList<byte[N]>,代表有没有被乱序修改。其中N = 每次申请空间的叶子节点个数 / 8

...

(3)后阶段:乱序的清除(对于一天前的数据,针对标志位为1的点,查询TimeseriesMetadata)

四、基于PISA的查询流程

1. 查询请求的处理步骤

(1)首先根据查询请求中的时间段计算出需要查询的节点和原始数据段,将查询划分为三部分;

...