An Empirical Evaluation of Columnar Storage Formats - 阅读笔记

An Empirical Evaluation of Columnar Storage Formats 主要对比介绍了 Parquet 和 ORC 两种列存存储格式，通过一个基于真实世界数据集的基准测试，评估了它们的性能和空间效率。

列存格式的演进

• 早期大数据生态系统中的文件格式：2010 年代初期，大数据生态系统催生了多种开源文件格式。Apache Hadoop 最先引入了两种面向行的格式：SequenceFile，以键值对的形式组织；以及基于 JSON 的 Avro。
• 列式数据库系统的兴起：与此同时，C-Store、MonetDB 和 VectorWise 等面向列的数据库管理系统（DBMS）开发了高效分析查询处理的基础方法，包括列式压缩、矢量化处理和延迟物化。
• Hadoop 社区采纳列式存储思想：Hadoop 社区随后从列式系统中借鉴了这些思想，并开发了更高效的格式。
• RCFile 的发布：2011 年，Facebook/Meta 发布了用于 Hadoop 的面向列的格式 RCFile。
• ORC 格式的出现：两年后，Meta 对 RCFile 进行了改进，并发布了基于 PAX（Partition Attribute Across）模型的 ORC（Optimized Record Columnar File）格式。
• Parquet 格式的出现：在 ORC 发布一个月后，Twitter 和 Cloudera 发布了第一个版本的 Parquet。Parquet 借鉴了早期列式存储研究的见解，例如 PAX 模型以及 Google Dremel 的记录切分和组装算法。
• Parquet 和 ORC 的发展现状：此后，Parquet 和 ORC 都成为 Apache 基金会的顶级项目。它们也得到了大多数数据处理平台的支持，包括 Hive、Presto/Trino 和 Spark。即使是具有专有存储格式的数据库产品（例如 Redshift、Snowflake、ClickHouse 和 BigQuery）也通过外部表支持 Parquet 和 ORC。
• 其他开源列式格式：华为的 CarbonData 是另一种开源列式格式，它提供了内置的倒排索引和列组。但由于其与 Spark 的关系更为密切，之前的研究未能独立评估该格式。最近的研究表明，与 Parquet 和 ORC 相比，CarbonData 的性能较差，并且社区活跃度较低。
• 专有列式格式：许多大型公司在过去十年中开发了自己的专有列式格式。Google 的 Capacitor 格式被其许多系统使用，包括 BigQuery 和 Napa。它基于 Dremel 和 Abadi 等人 的技术，这些技术根据工作负载行为优化布局。YouTube 在 2019 年为 Procella DBMS 开发了 Artus 格式，该格式支持自适应编码，无需块压缩，并针对嵌套模式的查找时间进行了优化。Meta 的 DWRF 是 ORC 的变体，可更好地支持读取和加密嵌套数据。Meta 最近开发了 Alpha，以改善机器学习（ML）应用程序的训练工作负载。
• Arrow 格式：Arrow 是一种内存中的列式格式，旨在实现不同应用程序进程之间或库 API 边界之间的高效数据交换，且序列化程度有限或没有序列化。与 Parquet 或 ORC 不同，Arrow 支持随机访问，因此在读取时不需要基于块的解码。由于 Arrow 不适用于长期磁盘存储，因此本文不对其进行评估。
• Lakehouse 趋势：最近的 lakehouse 趋势导致了格式的扩展，以支持更好的元数据管理（例如，ACID 事务）。代表性项目包括 Delta Lake、Apache Iceberg 和 Apache Hudi。它们添加了一个辅助元数据层，并且不直接修改底层的列式文件格式。
• 科学数据存储格式：还有用于 HPC 工作负载的科学数据存储格式，包括 HDF5、BP5、NetCDF 和 Zarr。它们的目标是具有复杂文件结构、类型和组织的异构数据。它们的数据通常是多维数组，不支持按列编码。尽管它们公开了多个语言 API，但由于缺乏列式存储功能，很少有 DBMS 支持这些格式。

Parquet 和 ORC 的核心特性比较

这里主要介绍了列式存储格式（如 Parquet 和 ORC）的核心功能，并详细对比了这两种格式在不同功能上的设计差异。该部分内容旨在建立一个用于理解和比较列式存储格式的框架，为后续的性能评估和未来格式的设计提供基础。

• 内部布局（Internal Layout）
  • PAX 格式：Parquet 和 ORC 都采用 PAX（Partition Attribute Across） 格式。这种格式首先将表水平划分为行组（Row Group），然后在每个行组内按列存储数据，每个属性形成一个列块（Column Chunk）。这种混合列式布局使得 DBMS 可以使用矢量化查询处理，并减轻行组中元组重建的开销。
  • 逻辑块到物理存储的映射：虽然 Parquet 和 ORC 的布局相似，但它们在逻辑块到物理存储的映射方式上有所不同。Parquet 使用基于行数的行组大小（例如 100 万行），而 ORC 使用固定的物理存储大小（例如 64MB）。Parquet 试图保证一个行组内有足够的条目来利用矢量化查询处理，但它可能导致较大的内存占用，尤其是在宽表的情况下。另一方面，ORC 限制了行组的物理大小以更好地控制内存使用，但它可能导致具有大属性的条目不足。
  • 压缩单元：Parquet 将其压缩单元映射到最小的区域映射（smallest zone map）。ORC 在调整块压缩算法的性能空间权衡方面提供了灵活性。但是，最小的区域映射和压缩单元之间的不对齐会在查询处理期间增加额外的复杂性。
• 编码变体（Encoding Variants）
  • 轻量级压缩方案：Parquet 和 ORC 都支持标准的 OLAP 压缩技术，例如字典编码（Dictionary Encoding）、游程编码（Run-Length Encoding，RLE）和位打包（Bitpacking）。
  • 字典编码：Parquet 默认对每个列应用字典编码，无论数据类型如何，而 ORC 仅将其用于字符串。它们都在字典代码上应用另一层整数编码。Parquet 为每个列块的字典大小设置了一个限制（默认情况下为 1MB），当字典已满时，后续值将回退到“plain”（即，无编码）。另一方面，ORC 计算列的 NDV 比率（即，NDV/行数）以确定是否对其应用字典编码。如果列的 NDV 比率大于预定义的阈值（例如，0.8），则 ORC 将禁用编码。
  • 整数编码：对于整数列，Parquet 首先进行字典编码，然后对字典代码应用 RLE 和位打包的混合。如果相同的值连续重复 ≥ 8 次，则使用 RLE；否则，使用位打包。ORC 的整数编码器使用基于规则的贪婪算法为每个值子序列选择最佳方案。ORC 的整数编码方案包括 RLE、Delta 编码、位打包和 PFOR 的变体。ORC 的整数编码算法比 Parquet 的更复杂，能够抓住更多的压缩机会，但是在四种编码方案之间切换会减慢解码过程。
• 压缩（Compression）
  • 块压缩：Parquet 和 ORC 默认都启用块压缩。每个格式支持的算法在表1中列出。块压缩算法与类型无关，它将任何数据视为字节流。大多数块压缩算法包含用于配置“压缩级别”的参数，以在压缩率和压缩/解压缩速度之间进行权衡。
  • Parquet 直接向用户公开这些调整旋钮，而 ORC 为每个算法提供了两个预配置的选项，“针对速度优化”和“针对压缩优化”。
• 类型系统（Type System）
  • Parquet 的类型系统：Parquet 提供了一组最小的原始类型（例如，INT32、FLOAT、BYTE_ARRAY）。Parquet 中所有其他支持的类型（例如，INT8、日期、时间戳）都是使用这些原始类型实现的。
  • ORC 的类型系统：ORC 中的每个类型都有一个单独的实现，具有专用的读取器和写入器。尽管这可以带来更多特定于类型的优化，但会使实现变得臃肿。
  • 复杂类型：Parquet 和 ORC 都支持 Struct、List 和 Map，但 Parquet 不像 ORC 那样提供 Union 类型。
• 区域映射/索引（Zone Map / Index）
  • 区域映射：Parquet 和 ORC 都包含区域映射和可选的布隆过滤器以启用选择修剪。区域映射包含文件中预定义范围内最小值、最大值和行数。如果区域的值范围不满足谓词，则可以在表扫描期间跳过整个区域。Parquet 和 ORC 都在文件级别和行组级别包含区域映射。
  • 最小区域映射粒度：Parquet 中最小区域映射粒度是物理页（即压缩单元），而 ORC 中是表示行数的可配置值（默认情况下为 10000 行）。是否构建最小区域映射在 Parquet 中是可选的。
  • Parquet 的 PageIndex：在 Parquet 的早期版本中，最小的区域映射存储在页面标头中，这导致了大量的随机 I/O。在 Parquet 的最新版本（2.9.0）中，通过一个名为 PageIndex 的可选组件解决了这个问题，该组件存储在文件页脚之前，以保存所有最小的区域映射。ORC 将其最小的区域映射存储在每个行组的开头。
  • Bloom Filter：Bloom Filter 在 Parquet 和 ORC 中都是可选的。ORC 中的 Bloom Filter 与最小的区域映射具有相同的粒度，并且它们彼此位于同一位置。但是，Parquet 中的 Bloom Filter 仅在列块级别创建，部分原因是 Parquet 中的 PageIndex（即，最小的区域映射）是可选的。
• 嵌套数据模型（Nested Data Model）
  • Parquet 的 Dremel 模型：Parquet 中的嵌套数据模型基于 Dremel。Parquet 将每个原子字段的值（图 3a 中分层模式中的叶节点）存储为单独的列。每个列都与两个相同长度的整数序列相关联，称为重复级别（R）和定义级别（D），以编码结构。R 将值链接到它们对应的“重复字段”，而 D 跟踪“非必需字段”中的 NULL。
  • ORC 的长度和存在模型：另一方面，ORC 采用基于长度和存在的更直观的模型来编码嵌套数据。ORC 将一个布尔列与每个可选字段相关联，以指示值的存在。对于每个重复字段，ORC 包括一个额外的整数列来记录重复长度。

Lessions Learned

实验评估部分总结的经验教训和未来方向，为下一代列式存储格式的设计提供了重要的指导，主要包括以下几点：

• 字典编码（Dictionary Encoding）：字典编码对于各种数据类型（甚至是浮点数值）都非常有效，因为大多数真实世界的数据都具有较低的 NDV（不同值的数量）比率。 未来格式应继续积极应用此技术，如 Parquet 所做的那样。
• 编码方案的简洁性：列式格式的编码方案保持简单至关重要，以确保具有竞争力的解码性能。未来的格式设计者应注意解码过程中从多个编解码算法中进行选择的性能成本。
• 减少块压缩和重量级编码的使用：在现代硬件上，查询处理的瓶颈正在从存储 I/O 转移到计算 CPU。除非在特定情况下证明有好处，否则未来格式应限制使用块压缩和其他重量级编码。
• 元数据布局的集中化和随机访问优化：未来格式中的元数据布局应集中化，并且对随机访问友好，以更好地支持 ML 训练中常见的宽（特征）表。基本 I/O 块的大小应针对高延迟云存储进行优化。
• 索引和过滤结构的增强：随着存储成本的降低，未来格式可以存储更复杂的索引和过滤结构，以加快查询处理速度。
• 嵌套数据模型与内存格式的亲和性：嵌套数据模型的设计应与现代内存格式具有亲和性，以减少转换开销。
• 支持机器学习工作负载：常见机器学习工作负载的特性要求未来格式有效地支持宽表投影和低选择性选择。 这需要更好的元数据组织和更有效的索引。此外，未来格式应为大型二进制对象分配单独的区域，并采用专门为浮点数设计的压缩技术。
• GPU 解码效率：未来的格式应考虑使用 GPU 的解码效率。 这不仅需要在文件级别有足够的并行数据块，还需要编码算法可以并行化，以充分利用 GPU 线程块内的计算。

这些经验教训表明，未来的列式存储格式需要更加注重解码性能、元数据管理、索引和过滤机制，以及对现代硬件和机器学习工作负载的支持。