从一到无穷大 #34 从Columnar Storage Formats评估到时序存储格式的设计权衡

本文主要是介绍从一到无穷大 #34 从Columnar Storage Formats评估到时序存储格式的设计权衡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

本作品 (李兆龙 博文, 由 李兆龙 创作)，由 李兆龙 确认，转载请注明版权。

引言

随着 Parquet，ORC，TsFile等开源存储格式的发展，各家时序厂商的压缩比不再是核心竞争力，虽然仍旧有部分数据库厂商仍旧选择自定义存储格式，比如阿里云Lindorm，腾讯云CTSDBi，Tdengine等，其旨在在部分场景达到优于开源存储格式的压缩比和性能，但是不得承认在大多数领域开源存储格式的能力已经足够强大，足以替代自研存储格式。

本篇文章从[3]，[11]入手，分析Parquet，ORC，TsFile的数据格式和索引格式，并通过论文的实验来观察其更适合哪些场景，最后从时序数据库场景入手，推断在设计权衡下现有的存储格式是否可以满足多样化的时序场景（Metric，logging，traceing），是否需要更多的额外索引，是否需要使用开源格式本身提供的辅助结构与功能。

Parquet / ORC

功能与结构对比

1. 在格式效率方面，Parquet 和 ORC 没有明显的优胜者。Parquet 因其积极的字典编码而在文件大小上略胜一筹。此外，Parquet 的整数编码算法更简单，因此列解码速度更快，而 ORC 由于其 zone maps 的粒度更细，因此在选择剪枝方面更有效。
2. 现实世界数据集中的大多数列NDV（number of distinct values）值较低，非常适合字典编码。因此，整数编码算法（即压缩字典编码）的效率对文件的大小和解码速度至关重要。
3. 存储设备的速度越来越快，成本越来越低，这意味着使用更快的解码方案来降低计算成本，比追求更积极的压缩来节省 I/O 带宽要好。不应默认使用 general-purpose block compression，因为节省带宽并不能证明解压缩开销的合理性。
4. Parquet 和 ORC 为辅助数据结构（如zone maps、Bloom 过滤器）提供了简单的支持。随着瓶颈从存储转移到计算，有机会将更复杂的结构和预计算结果嵌入格式中，以更少的计算量换取更便宜的空间。

差异

这一节论文描述的很清楚，我从中提取出我比较感兴趣的几点：

1. Format Layout：均为行列混存，并存在多个row group用于并行读取，不过将逻辑块映射到物理块的逻辑不通，Parquet使用行数，默认1024*1024。而ORC使用固定的存储大小，默认64MB。
2. Block Compression：块压缩至少在2024.8最新版本的Arrow CPP实现中不是默认开启的，论文描述有点小问题；块压缩在Parquet中允许用户自己指定，ORC则没有；块压缩对于查询性能存在较大影响，只有在确定访问频率极低的情况下才有较好的综合收益。

Indexes and Filters

Parquet和ORC均包含zone maps 和 Bloom Filters。

1. zone maps：Parquet和ORC均包含文件级别和Row Group级别的zone maps，且文件级别的zone maps（Parquet叫Page index）存储在Footer前，可以用最小的IO知道文件是否应该被跳过。
2. Bloom Filters are useful only for point queries。Parquet中使用了SBBF，其拥有更好的缓存性能和SIMD支持[10]

文中还给出了其他索引的相关研究，随着存储不再是瓶颈，使用更多的索引结构可以带来更优秀的查询性能，这些引用还没来得及看，后续补上

1. column indexes： [4][5][6]
2. range filters： [7][8]

压缩影响

文中认为 NDV Ratio，Null Ratio，Value Range，Sortedness，Skew Pattern是影响压缩比的最重要因素，但是事实上不同的角度有不同的研究结论。

还记得两年前的文章[2]，在无损压缩的前提下，总结了影响时间序列数据压缩比，编码性能的因素，评估了各种压缩算法在不同因素下定性分析。在Benchmark上使用多组真实世界中有明显特征的数据和自动生成的基于不同的影响因素的数字和文本数据组成数据集，对比了各种压缩算法在不同场景下压缩比，insert time，select time上的差异。

在文章中IoTDB最终选择了TS_2DIFF作为实际的压缩算法，这种算法下， 值的方差以及值之间增量方差（delta variance）越小，或者增量差值平均数（delta mean values）越大的情况下表现优异。

以本文的角度看，在不同的数据特征下基本上差别不是非常大，而且Parquet允许列级别修改编码算法，所以其实这些差距都是可以拉平的。

TsFile

一图胜千言。

TsFile和Parquet/ORC的设计有着本质的区别。TsFile存在时间线概念。

虽然我一直认为时间线膨胀问题本身是一个伪命题，因为这个事情是站在时间线的角度讨论的，本质原因在于上一代时序存储的场景并不极端（设备，实例较少），为了查询的高效会在时间线级别建立索引，然而随着时代的发展，时间线逐渐膨胀，此时要做的事情是去除时间线概念，让多个时间线数据存储在一个Page中，去除膨胀的索引（倒排索引，存储文件中的索引）。

而TsFile是在用上一个时代的思路解决问题。不考虑TsFile引入的自研压缩算法，原则上TsFile和Influxdb的压缩级别是在一个量级（排除TSI和Series File模块）。

不可否认这种存储格式在时间线较少的情况下却是会存在优势，但是优势的原因是同一时间线的数据存储在一起，利用数据的各种相似性压缩比较高，问题是Parquet中相同时间线的数据也可以存储在一起，虽然Parquet的编码/压缩算法很难增加特化算法，但是现有的基础算法以及足够优秀。

我们通过一个访问路径来更加了解TsFile：

1. Series Index：分两层树，第一层从数据模型中的root到device node，称为密集索引；第二层从传感器索引到TSM
2. Chunk index：包含两部分，第一部分称为TSM，包含相应序列的名称和数据类型，以及整个文件中有关时间序列的综合统计信息；第二部分由一个或多个chunk meta组成，记录每个Chunk元数据存储统计信息和偏移量
3. Chunk Group：由TSM定位到数据块Chunk，并通过Page Header可以过滤部分页。

来看下TsFile在其擅长的领域和Parquet的对比。

其实看到这里就可以下结论TsFile肯定是不适合普适性的时序数据库的，没有IotDB的关系老老实实用Parquet就好了。

因为IotDB基本无法用在Metric，Logging，Traceing领域，其所有的设计都是针对于Iot领域的。其实肯定也是不适合高时间线。举个简单的例子，假设业务一分钟上报一次，时间线爆炸，memtable的写入基本在200ms就要下刷，这个时候tsfile每个时间线只有一条数据，可预期的压缩比会非常非常差。

基本可以认为influxdb和Tsfile的压缩比在一个级别，用同样的数据集对比Parquet和Influxdb，涉及保密，详细的列无法展示，只能给出压缩比的对比，如上所示，大部分场景下Parquet还是存在优势的。

当然这是在influxdb全索引，Parquet：

1. 未开启页面压缩
2. 未开启Page index / Offset index
3. 未开启 Split Block Bloom filters (SBBF)
4. 未调整压缩级别
5. 未调整列级别自定义编码（默认RLE_DICTIONARY）

总结

基本上以目前的实践看，高时间线行列混存，低时间线纯列存，并建立全量倒排索引是最佳实践。双引擎，甚至多引擎是必不可少的。

这是引擎不同的查询方式在不同的数据排列下查询性能有倍级别的差异，这可以会出现未来大量不同的细分场景都可以有不同的引擎数据排列格式，这其实也是我们现在的发展路线。

当然以场景的不同，比如时间间隔的不同是否选择共享时间戳，稀疏索引，时间索引，物化视图，降采样，Router Key，各级缓存等等其他的优化都是另外一码事了。

而且以我们的需求看，存储不是瓶颈，我们更需要高性能的查询，所以Parquet的Page index和布隆过滤器一定会开启的，而且会随着需求不同加入自研的索引结构。

influxdb和基于开源文件格式还有一点巨大的差异，即索引方式：

1. influxdb因为shard是一个独立引擎，一般配置时间较长（1d），可以认为先试粗粒度时间过滤，然后才是索引过滤，这就需要大量的索引来增加数据定位能力，否则会存在很多的无效IO，因为索引过滤后还需要过滤时间。本质是索引粒度太大。
2. 而使用开源存储格式一般索引是文件级别，而一个文件负责的时间范围很小，索引的粒度也很小。先是时间过滤，再是索引过滤。

参考：

1. PAX：一个 Cache 友好高效的行列混存方案
2. Time Series Data Encoding for Efficient Storage: A Comparative Analysis in Apache IoTDB vldb2022
3. An Empirical Evaluation of Columnar Storage Formats vldb2023
4. Column sketches: A scan accelerator for rapid and robust predicate evaluation
5. Bitweaving: Fast scans for main memory data processing
6. Column imprints: a secondary index structure
7. SNARF: a learning-enhanced range filter
8. Surf: Practical range query filtering with fast succinct tries.
9. Parquet doc
10. Querying Parquet with Millisecond Latency
11. Apache TsFile: An IoT-native Time Series File Format vldb2024

这篇关于从一到无穷大 #34 从Columnar Storage Formats评估到时序存储格式的设计权衡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---