一、总体设计

1. 设计背景

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

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

2. 设计阶段

（1）本阶段设计：默认分区关闭，即仅有1个分区，每一个序列有一个PISA索引—— 每个序列有一个索引管理器。

（2）下阶段设计：开启分区后，索引建立在分区内部，不跨分区；每一个序列，每一个分区有一个PISA索引—— 每个分区、每个序列各有一个索引管理器。

3. 设计目标

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

而是通过定义节点号和叶子号，避免从磁盘读取不必要的数据，减少聚合查询延迟。

（2）考虑时间序列数据库的应用场景，充分利用顺序数据和乱序数据的特点，

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


二、索引的构建

1. 构建时间

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

未写入该叶子节点的“尾巴数据”（统计数据）缓存到内存里，下一个memtable来的时候合并。

（2）用户配置：用户可以配置窗口时间长度t = te - ts

* 注意：开启分区后，用户需要配置“叶子结点个数”（要求为以2为底的幂，如16 = 24），窗口时间长度通过计算得到，

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

2. 说明

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

用查询恢复前面的根节点（假设当前时间为t，则查询0~t，根节点保存在内存中，确保后续建树正确性）。

之后出现该时间窗口的乱序数据时，可以直接构建。

（2）每一条时间序列的PISA索引也存储为一条时间序列，LN作为时间戳timestamp，摘要summary中的各种聚合值以byte的形式作为value。

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

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

3. 构建步骤

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

计算待写入的叶子节点的开始时间ts、结束时间te ，并计算窗口时间为[ts, te)内的所有叶子节点的统计数据Sseq

（2）写好一个叶子节点后，索引管理器根据开始时间和终止时间计算窗口的叶子号LN（leaf number）和节点号NN（node number）

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

4. 示例

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

服务器根据刷入的memtable写好的叶子结点开始时间为t7s，截止时间为t7e。

按照LN和NN的计算方法，计算出顺序数据窗口的叶子号LN=7，节点号NN=11。

NN=11的节点的兄弟节点节点号NN=12，查询内存得到NN=12的节点存在于内存中，因此合并NN=11，12的两个节点为NN=13；

NN=13的节点的兄弟节点节点号NN=10，查询内存得到NN=10的节点存在于内存中，因此合并NN=10，13的两个节点为NN=14的节点；

NN=14的节点可能的兄弟节点节点号为7和11，查询内存发现NN=7和NN=11的节点都不存在，合并终止。

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


三、乱序数据处理

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

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

默认：256（即每次为2048个叶子节点申请了“记录该叶子结点是否乱序”的空间）

* 注意：有分区情况下：只需要byte[N]，其中N = 每个分区中的叶子节点个数 / 8，根据用户配置获得，无需额外配置。

（2）持久化：每一条时间序列的 LinkedList 也存储为一条时间序列 <起始时间, byte[N]>

（3）后阶段：乱序的清除（对于一天前的数据，针对标志位为1的点，查询TimeseriesMetadata）

四、基于PISA的查询流程

1. 查询请求的处理步骤

（1）首先根据查询请求中的时间段计算出需要查询的节点和原始数据段，将查询划分为三部分；

（2）找出所对应的需要计算的节点（包括内存中的根节点和磁盘中的一些节点），加入候选节点集合Cs；

（3）根据根节点判断当前生效的PISA段可以得出乱序时间段，计算相关聚合值；

（4）将Cs中的聚合值和乱序时间段的聚合值合并。

2. 示例

如图所示，内存中有NN=6，10，12，18的节点，标记为乱序状态的节点为NN=11，13，14的节点。

当进行查询（t3e < qs < t4s, t9e < qe < t10s）时，首先确定需要查询的原始数据段；

对于t4s～t9e，按以下步骤A～F找出所对应的需要计算的节点：

A：t9e对应节点NN=16，其前继节点NN=12，将NN=12加入；

B：NN=12前继节点NN=11，但不存在于磁盘中，该段为乱序数据段；

C：NN=11前继节点NN=9；

D：NN=9找出NN=10，将NN=10加入Cs；

E：NN=10的节点可以覆盖到NN=8，NN=9；

F：NN=8前继节点NN=5，将NN=5加入Cs。

最终Cs={5, 10, 12, 16}，计算中各个节点的其聚合值；计算[t7s, t7e)乱序数据段为的聚合值；将Cs中的聚合值和乱序时间段的聚合值合并。



  • No labels