Blog of Samperson

论文#6 | Dual-PISA - An index for aggregation operations on time series data

2019-10-14

以下是论文Dual-PISA: An index for aggregation operations on time series data的笔记。

用什么方法解决什么问题?

  • 使用方法：使用线段树结构，但是对于树中的内部节点，不存储节点所覆盖的时间范围的最早或最晚时间戳，而是定义代码号(code number)和序列号(serial number)，存储在每个内部节点和叶节点
  • 解决问题：对于聚合查询来说，插入速度快、延迟低

为什么有效?

  • 在任意时间范围内获取聚集值 —— 使用类似于段树的基于树的结构
  • 按顺序插入新的数据点 —— 森林结构和插入算法
  • 避免从磁盘读取不必要的数据 —— 定义代码号和序列号

隐藏问题

  • 定长Chunk设计
  • 第6章最后关于seq和unseq数据的同时间窗口内聚合结果如何merge只用一句话带过：“Finally, we merge all the aggregations and return the final result.”能否直接merge？
  • IoTDB也维护了局部数据的聚合结果 (ChunkMetadata和PageHeader中都有保存一个Chunk / Page内的聚合结果max, min, first, sum, last；chunk和page的关系：一个chunk内有1个或多个pages)，不同在于IoTDB的局部数据不是以固定时间的窗口来划分的，每个chunk / page其实还有统计startTime / minTime & endTime / maxTime。我好奇的问题是：DPISA方法用到IoTDB中会比原来IoTDB中实现时间范围内聚合查询的方法更有优势吗？DPISA方法能避免从磁盘读取不必要的窗口结点，只从磁盘读那些一定与查询时间范围相交的窗口结点。IoTDB应该是要从磁盘读出所有的ChunkMetadata / PageHeader，读出来之后才能判断是不是与查询的时间范围段有重叠，进而丢弃或者取用其中的聚合统计信息。但问题是后者应该算比较合理的设计了，所以在已经比较合理的设计上再有提升应该是难度更高。

已有方法及改进

[1] Summary tables(synopsis table)摘要表 / 概要表，或者基于MapReduce的方法：速度慢

[2] segment tree线段树：静态结构

  • 需要预先知道每个数据点的所有时间戳。SB-tree 和 Balanced tree可以解决
  • 树的大小可能会超过可用内存的容量，因此树会被存储在磁盘上。对于每个插入操作，都需要更新许多内部节点；支持无序数据插入可能会导致IO成本巨大

[3] FlatFAT 和 FlatFIT可以用于聚合连续查询

  • 关注计数中的最新数据和基于时间的窗口
  • 需要在内存中的一个窗口中缓存所有数据点

改进

[1] 数据结构

  • 森林，在适当的时间将两棵树结合起来的插入算法(insertion algorithm)
  • 放弃对树的遍历和对内部节点的逐级读取，通过在节点中使用标记，避免读取不必要的节点，并且只访问作为结果一部分的节点
  • PISA存储在磁盘而非内存

[2] 当数据库接收到数据点的时间窗口(如2018.4.1的8:00至8:15)时，PISA预先计算其聚合值，然后相应地更新索引

  • 构建内部节点或叶时，PISA在节点中存储代码号和序列号
  • 在给定的时间范围内，PISA将时间范围划分为子范围，然后根据索引中的标记找到相关的树节点

PISA

[1] 窗口(Window) W：用来划分时间序列为计算聚合值的基本单元
所有的窗口需要有相同的窗口长度(时间间隔)r，开始时间s，结束时间s+r
时间序列需要互不相交


[2] 窗口摘要(window summary) S = A(W)
存储窗口的聚合结果，作为PISA中的持久化值，存储在磁盘
好处：减少索引中叶子节点的数量（可以不在每个叶子节点只存放一个数据）
叶子节点的数量只与窗口长度和时间序列覆盖的时间有关

持久线段树PST

[1] 结构：完全二叉树
[2] 序列号SN：从1开始，每一个叶子节点包括一个独一无二的序列号，最大序列号为窗口摘要的个数。内部节点没有序列号。
[3] 代码号CN：从1开始，索引每新增一个新的叶子节点或内部节点就会增加1.节点根据后续遍历获得其代码号。


[4] 叶子节点包括：长度为r的窗口摘要Sti，窗口摘要的开始时间，序列号SN=j，表示为LF(ti)
内部节点包括：长度为2^nr的窗口摘要，代码号CN=i，表示为INi
树根据跟节点的代码号CN命名和表示
[5] 例子：3PST，PISA = {Tree7, Tree10, Tree11}

存储

[1] 内存中仅保存根节点
长度为n*r的时间序列，最大根节点数量为log(n/k)+1
PISA的总节点数不超过2m-1，m为叶子节点数量


[2] 存储引擎需要支持：

  • 在磁盘上序列化叶子节点和内部节点：IO.write(LF), IO.write(IN)
  • 通过叶子节点的开始时间或者内部节点的代码号CN可以快速获得节点：LF(ti) = IO.get(ti), INi = IO.get(i), IO.batch_get({i, j, …})
  • 获得开始时间多于或少于给定时间戳的叶子节点：IO.gt(ti), IO.ls(ti)

[3] 将所有叶子节点存储在一起，并根据开始时间戳进行排序。

插入

[1] 合并的条件

[2] SN和CN的计算

汉明重量(Hamming Weight)是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是1的个数。

1
2
3
4
5
6
7
public int hammingWeight(int n) {
  int res = 0;
  for(; n != 0; n = n & (n-1)) {
    res++;
  }
  return res;
}

JDK实现(Integer类)：

1
2
3
4
5
6
7
8
public static int bitCount(int i) {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}

ones(i)表示i的汉明重量，最佳实现算法复杂度为O(1)。
cn(i) = 2i - ones(i) [if i % 2 == 1], = 2(i-1) - ones(i-1) + 1 [if i % 2 == 0]
root(i) = 2i - ones(i)
CNs(i) = {root(i) - k|k = 0, 1, …, root(i) - cn(i)}


[3] 插入算法：只读内存中的PISA根节点，不需要读磁盘
使用栈root_stack维护根节点，当两个根节点符合合并的条件，就pop后生成新节点，再压栈。
如果节点为空，则不需要持久化，该窗口没有点。
PISA会保存最大序列号max_serial和所有的根节点root_stack，不需要持久化空的叶子节点。

查询

[1] 查询范围划分方法：

前继窗口◁(pt)，后继窗口▷(pt)
例子：t1s < tqs < t1e 且 t11s < tqe < t11e
D(tqe ,tqs)划分为三段：D(tqs ,t2s) , D(t2s ,t10e) 和 D(t10e ,tqe)

[2] 一个内部节点可以覆盖的叶节点集，根节点可以覆盖树中所有叶节点。
最左叶节点LLF(IN)是可以覆盖的最左边的叶节点。
如果cn(LF) ≤ cn(LLF(IN))，那么叶节点LF可以覆盖内部节点IN。


[3] 公式

  • 给定序列号i为偶数的叶节点LFcn(i)，得到叶节点带来的所有内部节点的代码号CNs(i)和这些节点的深度depth(j) = j − cn(i)
  • 给定一个内部节点，得到内部节点可以覆盖的最左边的叶节点。
    ⊣(INj) = LF[j+2−2^(depth(j)+1)]
  • 假设叶节点LF存储S[k(s)]，那么叶节点的前继和后继为：
    ◁(LF)=LF’, s.t.LF.SN=LF.SN−1
    ▷(LF)=LF’, s.t.LF.SN=LF.SN+1

[4] 查询算法

  • 扫描[tqs,t2s) 和 [t10e,tqe)，计算聚合值，回答查询QAleft 和 QAright
  • 计算PISA中需要被读的点的代码号，代码号集合CS （在内存中进行）
    只需要两个端点叶节点（LF1和LF19）的序列号，记录开始时间和窗口长度，从而得到其序列号
    最后从磁盘中读到CS的摘要从而得到QAindex。
  • 合并QAleft，QAright 和 QAindex得到最终结果。

复杂度：O(log(n/r))

Dual-PISA

[1] 乱序数据：97%的无序数据在4小时内具有过时的时间间隔，需要和有序数据一起管理；长尾数据（即剩余的3%数据）可能会被丢弃，因为它太陈旧以至于数据的业务价值丢失。
陈旧性约束E：需要容忍的数据的陈旧性。给定时间戳为tl的最新数据点，所有时间戳大于等于tl - E的数据点都需要索引。


[2] 两个PISA indice：标准PISA和影子PISA，可容忍一系列无序数据，节约内存

  • 标准PISA正常负责顺序数据
  • 影子PISA（SPISA）只负责记录无序数据的汇总信息
  • 在给定时间范围聚合查询的情况下，DPISA将时间范围拆分为子范围，然后根据两个索引中的标记查找相关的树节点

[3] SPISA在内存中维护连续的⌈E/r⌉个活动窗口来确保陈旧性约束E可以全部被覆盖。
[4] 滑动操作：计算最旧窗口的窗口摘要并将其插入SPISA的树林结构中，然后在内存中生成一个新的活动窗口。


[5] 建立：SPISA的最新活动窗口总是在PISA的活动窗口之后，且相连，示例：

新的数据点进入(tc + r)，将摘要插入PISA的活动窗口并创建新的活动窗口，同时进行SPISA的滑动操作，将最不活跃的窗口插入森林结构。
如果所有的数据点都按照顺序到达，SPISA中无数据，不会被持久化到磁盘，DPISA结构即成为PISA结构。


[6] 查询：如果PISA与DPISA有相同的代码号，就说明他们们都代表了同一个时间区间的一部分摘要信息，计算时考虑两种PISA的相关点后进行合并，获得最终结果。

Tags: 数据库索引
← 论文#5 | Workload-Driven Fragment Allocation for Partially Replicated Databases Using Linear Programming Hadoop HA相关部署和配置 →