设计思路

在时间序列数据实际的应用场景中，用户的写入和查询经常有这样的特点：

  • 写入速度比合并速度快，即合并赶不上写入
  • 大部分查询总是查询一段时间从一个时间点到当前时间的数据，即热数据查询

但是在传统的合并策略中，总从老到新慢慢合并所有的文件，这就导致随着数据越写越多，来不及合并的数据越来越多，用户又经常进行热数据查询，这就导致合并实际提升不了查询性能。

如下图所示，假设用户进行的总是进行从 5 个 chunk 前到现在的热查询，合并每次合并两个小文件，每次合并的过程中能生成 4 个新文件

  • Status1：整个文件空间只有 3 个文件，此时未进行合并
  • Status2：此时完成了第 1 次合并，又生成了 3 个新文件，查询覆盖了合并完文件的一部分（合并还有一定的效果）
  • Status3：此时完成了第 2 次合并，又生成了 3 个新文件，查询覆盖不到任何合并完的文件（合并开始失去效果）

查询建模

合并对数据查询的加速原理

查询时，用户的范围查询性能主要受四个方面的制约：

  • 磁盘的 Seek 次数（使用 SSD 磁盘能直接解决这个问题，但是本文主要优化 HDD 磁盘的上的查询性能）
  • 磁盘 Seek 后顺序读文件耗时
  • 反序列化 Chunk 的时间（这里会占用大量 CPU 资源）
  • 其他内存时间（如过滤一个chunk不在查询范围内的数据）

如下图所示，在合并前查询 5 个 chunk，我们需要进行 5 次 Seek，而合并后，5 个 chunk 合并为了 1 个，如果继续查询这 5 个 chunk，我们仅需要进行 1 次 Seek

查询性能制约因素实验

实验机器

192.168.130.34

/root SSD

/data HDD

实验内容

查询10000000个点，调整单个文件大小，测试分别在 HDD 磁盘和 SSD 磁盘统计四个方面的耗时

  • 磁盘的 Seek 时间
  • 磁盘 Seek 后顺序读文件耗时
  • 反序列化 Chunk 的时间
  • 其他内存时间

实验结果


跨层级文件查询建模


相关参数

inner_compaction_strategy=DYNAMIC_COMPACTION # 新增空间内合并策略，动态合并

enable_compaction_dynamic_detect_query_interval=true # 常用查询范围是否动态检测

query_time_interval=3600000 # 作为默认的用户查询范围，当不动态检测常用查询范围或常用查询范围未被检测出时生效

enable_stat_monitor=true # 为了动态检测合并、写入速度，必须要打开 monitor

compaction_max_level=5 # 如果写入速度过慢或已经停止写入，则可能对同一个文件合并多次，如果一个文件合并过太多次，则不再合并该文件，防止写放大过高

合并过程

合并文件选择理念

保证合并后能尽可能减少用户热数据查询的 Seek 次数，这里需要考虑到合并所需的时间和写入的时间，因为如果写入过快，合并文件过多，可能等合并完的时候，已经生成了更多的新文件，合并完的文件无法对用户的查询产生性能优化，所以我们需要选择尽可能多的一批文件，这批文件合并完后能对用户的热数据查询产生最多的性能优化。

合并收益公式

其中 j 为合并后最多可能减少的 Seek 次数， f(i) 为减少 i 次 Seek 的段长度

如下图所示，假设一次合并 F1, F2, F3 三个文件，当合并完，系统已经新写入了 F4, F5, F6 三个新文件，合并完用户进行查询的范围是 Tqs-Tqe , 涵盖了 F1-F6 的所有文件

那么，如果未合并，用户查询这些文件需要 Seek 6次，合并后，只需要 Seek 4次，减少 Seek 次数为 2次

随着时间推移（T1-Tqs），用户会渐渐不再查询 F1，此时，如果未合并，用户查询这些文件需要 Seek 5次，合并后，需要 Seek 4次，减少 Seek 次数为 1次

依次类推直到本次合并不再减少用户查询文件的 Seek 次数

则本次合并收益为

1*(T2 -T1)+2*(T1-Tqs)

合并文件选择公式

选择哪些文件进行合并就是通过历史写入和合并数据预估本次合并完的文件情况，找出一个能使合并收益ω最大化的待合并文件列表

设在时间范围 [T-W, T] 内从后往前选择候选文件，假设找到的文件范围为 [Q1, Q2]，文件数量 N 个，每个文件的终止时间为[T1, T2, ..., TN]

文件总大小为 S，合并速率为 M，合并消耗时间为 S/M， 合并结束的时间点为 T+S/M，当前查询范围为 [T+S/M-W, T+S/M]

合并文件选择算法

F_list= []

倒序遍历顺序文件列表，对于每一个文件 F

  • if F.endTime < T-W
    • break
  • else
    • F_list.add(F)

result_list = []

max_revenue = 0

顺序遍历 F_list，对于每一个文件 F，作为 Fstart

  • 顺序遍历 F_list，对于每一个文件 F，作为Fend
    • 对于 [ Fstart, Fend ] 计算 合并收益ω
    • if ω > max_revenue
      • max_revenue = ω
      • result_list = F_list.subList(Fstart, Fend+1)

return result_list

合并执行算法

对于选择出来的 result_list, 如果有任何一个文件 level_time >= compaction_max_level

  • 则将合并策略自动变化为 SizeTiredCompaction 算法，见合并机制总体流程文档
  • 否则，将合并 result_list 中的所有文件合并为一个新文件 F'，见合并执行流程文档
  • 删除文件列表中在 result_list 中的文件，将 F' 放入文件列表

查询优化与写放大建模


热数据查询范围预估

相关数据统计节点

写入速度：每次文件封口时

合并速度：每次文件合并完时

热数据查询范围：每次用户进行热数据查询时，当用户查询没有 endTime，或者 endTime >= 现在系统时间 - 1min，则认定本次查询为热数据查询，将该查询长度记录

查询范围预估算法

采用有限查询范围 k-means 聚类后取平均的算法，预估当前用户的热查询范围

采用一个限制长度为 1000 的队列，每次有新的热数据查询长度就存储这个队列，满了就将老数据排出

每次插入一个新的查询长度，就进行一次 k-means 聚类，找出最大的一个类，求平均，设为当前的用户热查询范围 Tquery

性能测试

模拟算法的执行


IoTDB 基于 YCSB 负载的测试


对写入的影响


  • No labels