Persistent Index for Segmented Aggregations (PISA)

一、总体设计

1. 设计背景

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

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

2. 设计阶段

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

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

3. 设计目标

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

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

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

在任意时间范围内获取准确的聚合结果，减少乱序数据对于查询速度的干扰。

二、索引的构建

1. 构建时间

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

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

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

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

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

2. 说明

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

不构建上层的内部节点（用查询恢复前面的根节点）。之后出现该时间窗口的乱序数据时，可以直接构建。

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

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

3. 构建步骤

（1）memtable flush落盘时，向索引管理器发送一个新的窗口摘要S_seq，索引管理器解析开始时间、截止时间和数据摘要信息

（2）记开始时间为t_s，截止时间为t_e ，则其窗口时间为[t_s, t_e)。根据开始时间和终止时间计算窗口的叶子号（leaf number）和节点号（node number）

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

4. 示例

如图所示，假设LN=1，2，7的窗口没有数据，NN=6，10，12，18的节点在内存中。服务器向索引管理器发送一个新的窗口摘要，该分区的开始时间为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=21的节点都不存在，合并终止。

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

三、乱序数据处理