学术研究报告：btrblocks——数据湖中高效的列式压缩方案

本文由四位研究者合作完成：Maximilian Kuschewski（德国慕尼黑工业大学）、David Sauerwein与Adnan Alhomssi（德国埃尔朗根-纽伦堡大学）、Viktor Leis（慕尼黑工业大学）。该研究于2023年6月发表在ACM的期刊*Proceedings of the ACM on Management of Data*（第1卷第2期，文章118号），标题为《btrblocks: Efficient Columnar Compression for Data Lakes》。

学术背景

随着云计算的普及，数据湖（Data Lake）成为企业存储和分析海量数据的主流架构。数据湖通常基于S3等云存储服务构建，依赖Apache Parquet等开放列式存储格式。然而，现有格式在远程访问和高吞吐网络环境下存在解压效率低的问题，导致扫描操作受CPU性能限制，增加查询时间和成本。为此，研究团队提出btrblocks——一种专为数据湖设计的开源列式存储格式，通过轻量级编码方案实现快速解压和高压缩比，属于数据库与数据压缩领域的原创性研究。

研究流程与方法

研究分为五个核心环节：

1. 编码方案设计
   btrblocks整合了7种现有编码和1种新设计的伪十进制编码（Pseudodecimal Encoding），覆盖整数、浮点数和字符串类型。编码方案包括：

   • Run-Length Encoding (RLE)：压缩连续重复值。
     
   • 字典编码：用短代码替换高频字符串。
     
   • 频率编码：针对偏态分布数据，仅存储高频值及其位置。
     
   • SIMD优化的FOR+Bit-packing：基于帧偏移（Frame of Reference, FOR）的整数压缩。
     
   • Roaring Bitmap：高效存储NULL值。
     
   • FSST（Fast Static Symbol Table）：字符串子串替换技术。
     
   • 伪十进制编码：将浮点数转换为（有效数字，指数）的元组，便于后续压缩（见第4部分详述）。
     

2. 级联压缩框架
   通过递归选择最优编码组合（如先RLE再字典编码），最多支持3级级联。团队设计了基于采样的选择算法：从数据块（默认64,000条）中随机抽取10段64条数据（占1%），统计最小值、最大值、唯一值数量等指标，排除不适用方案后，评估各编码在样本上的压缩比，最终选择最优级联路径。该算法仅消耗1.2%的压缩时间，准确率达77%。

3. 伪十进制编码实现
   针对浮点数的IEEE 754格式缺陷（如0.99存储为0.9899…），该编码将双精度数转换为（有效数字×10^指数）的十进制表示（如3.25→(+325, 2)）。通过预计算10的负幂次表，结合SIMD指令加速解压。若转换失败（如-0.0或NaN），则保留原始值作为“补丁”。

4. 解压优化
   所有编码方案均针对现代CPU优化：

   • 向量化RLE：使用AVX2指令并行复制8个整数或4个双精度数。
     
   • 字典加速：通过AVX2批量查询字典项，字符串字典仅存储指针而非副本。
     
   • FSST API改进：减少单字符串解压的冗余指令。
     

5. 实验验证
   使用真实数据集Public BI Benchmark（包含46个Tableau工作簿的异构数据，共119.5GB）和TPC-H合成数据，对比Parquet（含Snappy/Zstd压缩）、ORC等格式。测试环境为AWS c5n.18xlarge实例（100Gbps网络），测量压缩率、解压吞吐量和端到端云成本。

主要结果

1. 压缩率

   • btrblocks在Public BI上的平均压缩比为5.28×，优于Parquet+Zstd（6.05×）和专用系统如SQL Server（5.1×）。
     
   • 伪十进制编码在价格类浮点数据中表现突出（如某政府数据集压缩比达75×），但对高精度坐标数据效果有限（如经纬度仅1.0×）。
     

2. 解压性能

   • 内存解压吞吐量达174.6 GB/s（Parquet为56.1 GB/s），网络扫描成本降低1.8倍。
     
   • 向量化使解压速度提升17%，但即使禁用SIMD，btrblocks仍比Parquet快2.3倍。
     

3. 云成本
   在S3扫描测试中，btrblocks的有效网络吞吐（Tc）达86 Gbps（接近理论极限91 Gbps），而Parquet因解压瓶颈仅能利用52.6 Gbps。加载完整数据集时，btrblocks的成本仅为Parquet的38%。

结论与价值

btrblocks通过轻量级编码组合和级联决策算法，解决了数据湖中解压效率与压缩率的矛盾。其科学价值在于：
1. 提出首个面向数据湖的端到端压缩设计，涵盖多数据类型与级联策略。
2. 开发的伪十进制编码填补了浮点数压缩的研究空白。
3. 开源实现（GitHub仓库）为业界提供了可替代Parquet的高性能方案。

应用层面，该技术可降低云数据分析的存储与计算成本（如Snowflake、Redshift等系统），促进开放数据湖生态的普及。

研究亮点

1. 数据驱动设计：基于Public BI的真实数据分布优化编码方案选择。
   
2. 级联压缩泛化框架：支持任意编码的多级递归组合，突破传统两阶段限制。
   
3. 硬件感知优化：全面利用AVX2指令集，实现接近理论极限的解压吞吐。
   

此外，研究揭示了Parquet等格式的局限性：其元数据布局（如列偏移存储在文件尾部）导致单列读取需多次网络请求，而btrblocks通过分离元数据与数据块解决了这一问题。这一发现为未来格式设计提供了重要参考。