Versions Compared

Key

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

...

(2)考虑时间序列数据库的应用场景,充分利用顺序数据和乱序数据的特点,

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


二、索引的构建

1. 构建时间

(1)memtable flush落盘时,触发索引的构建。每写好一个叶子节点(达到配置或计算的窗口时间长度),就将该节点交给索引管理器。未写入该叶子节点的“尾巴数据”缓存到内存里,下一个memtable来的时候合并。

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

(2)用户配置:用户可以配置窗口时间长度t = te - ts

...

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

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

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

...

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

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


三、乱序数据处理

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

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

...

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

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

(3)后阶段:乱序的清除(对于一天前的数据,针对标志位为1的点,查询TimeseriesMetadata)(2)序列化:为每一条时间序列匹配一个文件,文件中序列化此LinkedList

四、基于PISA的查询流程

1. 查询请求的处理步骤

...