《大规模分布式计算深入解析》3.2 编码与压缩:字典、RLE、Bit-packing、Zstd

用位打包、RLE、字典和 Delta 载荷做教学预算,再对照 Parquet 真实编码的头部和开销。

3.2 编码与压缩:字典、RLE、Bit-packing、Zstd

3.1 把数据切成了 page,但 page 里放什么、怎么放,才决定最终占多少字节。同一列整数,直接按 8 字节一个写,和按实际位宽打包,体积能差一个数量级;同一列字符串,按原样存和先建字典,也完全不同。

这一节按「数据形态 → 编码 → 字节账 → 适用条件」的顺序,逐一拆开 Bit-packing、RLE、字典、Delta 与 Zstd。核心判断是:编码的收益来自数据里的某种规律,规律不存在时,再复杂的编码也只会增加 CPU 开销。

先区分载荷模型与格式字节

下文的 3 B 位负载、8 B 定长 run、125 B 定长 delta 都是手算模型,未计页头、层级和格式头。Parquet 的 RLE/bit-packed hybrid 包含变长 run header,把 bit-packed run 按八个值分组,RLE 值按当前 bit width 写入所需字节。DELTA_BINARY_PACKED 有块长、mini-block 数、值数、第一值、块级最小差值和 mini-block 位宽等数据。字典值和索引也分属相应页及编码。测量真实文件时分别列出未压缩载荷、格式开销和最终压缩后的页或列块长度。 Parquet 编码规范

Bit-packing:只花值域需要的位

整数的存储宽度由类型决定,但实际值域往往小得多。一个 long 占 8 字节,可如果这列值只在 0..7 之间,3 个位就够表示。Bit-packing 把连续的值按固定位宽首尾相接,不做字节对齐。

lab 的用例 23 是 8 个值、位宽 3:

位宽 = 3(可表示 0..7)
总位数 = 8 个值 × 3 位 = 24 位
总字节 = 24 / 8 = 3 字节
原始表示 = 8 个值 × 8 字节 = 64 字节
压缩比 = 64 / 3 ≈ 21.3,即约 21 倍
表示每值字节8 个值总字节说明
原始 long864与值域无关
位打包 3 位0.3753只花值域需要的位

位打包的收益上限由位宽决定:值域 0..7 只要 3 位,理论压缩比就是 64/3;值域扩大到 0..255 需要 8 位,压缩比降到 8 倍;值域再到 0..65535 需要 16 位,只剩 4 倍。所以位打包最适合「小整数 + 窄值域」,比如枚举、状态码、年龄、数量。

位打包本身不关心值是否重复,它只关心最大值需要多少位。若一列里绝大多数是小值、偶尔出现一个极大值,位宽会被那一个极大值抬高,整体收益骤降。这时要么把异常值单独处理,要么先做 Delta 或其他变换。

RLE:连续重复折成一个 run

Run-Length Encoding 把连续相同的值折成「值 + 重复次数」。lab 的用例 24 是 1000 个相同的 int:

1 个 run = value 4B + count 4B = 8 字节
原始 int 数组 = 1000 × 4B = 4000 字节
压缩比 = 4000 / 8 = 500 倍
数据形态run 数编码字节原始字节压缩比
1000 个相同值184000500×
1000 个两两交替1000800040000.5×(反而变大)

RLE 的收益完全取决于 run 的长度。run 越长,摊到每个值的成本越低;若数据频繁交替,每个值都成一个 run,模型中的 8 字节 run比原来的 4 字节值还贵,压缩比小于 1。这就是为什么 RLE 只该用在「确实有连续重复」的列上,而不是无条件套用。

RLE 在 Parquet 里还有两个特殊用途:编码定义层级与重复层级,以及编码布尔列。这两类数据天然是大量连续相同值,RLE 几乎总是最优。Parquet 实际使用的是 RLE/bit-packing 混合编码:连续重复用 run 表示,非重复段用位打包成组存放,兼顾两种形态。

字典编码:低基数列的主路径

字典编码先收集一列里的不同值,建成字典,再用索引替换原值。它把「存值」变成「存索引」,值越大、重复越多,收益越明显。

lab 的用例 25 是 100 万行、1000 个不同值、索引 10 位:

字典项 = 1000 个 × 8B = 8000 字节
索引位图 = 1,000,000 行 × 10 位 / 8 = 1,250,000 字节
总字节 = 8000 + 1,250,000 = 1,258,000 字节 ≈ 1.258MB
原始 long 数组 = 1,000,000 × 8B = 8,000,000 字节 = 8MB
压缩比 = 8,000,000 / 1,258,000 ≈ 6.36 倍
组成计算字节
字典1000 × 8B8,000
索引1,000,000 × 10 位 / 81,250,000
合计—1,258,000
原始1,000,000 × 8B8,000,000

字典的收益由「基数 / 行数」决定。基数 1000、行数 100 万时,每个值平均重复 1000 次,索引成本被摊薄;若基数接近行数(每行都不同),字典项本身就要 8MB,再加索引,反而比原数组更大。所以字典编码有明确边界:低基数才用,高基数应回退到普通编码。

Parquet 的实现里,字典不是无限的。字典页有大小上限,超过阈值就回退到 PLAIN 或 Delta 编码,并把已写的数据页改成非字典格式。回退是逐 column chunk 发生的,所以同一列在不同 row group 里可能用不同编码,读取器必须按 chunk 元数据分别处理。

字典索引的位宽也不是固定的:1000 个不同值需要 10 位(2^10 = 1024),100 个不同值只要 7 位。位宽由基数决定,基数越小,索引越省。这就是「先字典、再位打包索引」的组合:字典消除值本身的宽度,位打包消除索引的浪费。

Delta:有序数值只存差值

对单调递增的时间戳、自增 ID、有序价格,相邻值的差往往很小。Delta 编码先存第一个值,之后只存差值;差值再用位打包压缩。

lab 的用例 26 是 1000 个递增时间戳,delta 全为 1:

差值位宽 = 1 位(差值恒为 1)
总位数 = 1000 × 1 = 1000 位
总字节 = 1000 / 8 = 125 字节
原始 int 数组 = 1000 × 4B = 4000 字节
压缩比 = 4000 / 125 = 32 倍
数据形态差值分布位宽1000 值字节压缩比
严格递增、步长 1全为 1112532×
递增但步长波动小范围若干位随之上升下降
随机无序大范围接近原宽接近原始几乎无收益

Delta 的收益来自「有序」。数据按时间或 ID 排序后,差值集中在很小的范围,位宽骤降;一旦顺序被打乱,差值变成大随机数,Delta 不仅不省,还要额外存基准值。排序本身就是一种编码预处理,这也是写入前按常用过滤列排序能提升压缩率的原因。

Delta 对浮点数要小心:浮点差值仍有精度问题,通常先转成整数(如毫秒时间戳、定点小数)再做 Delta。对字符串,Delta 变体存的是前缀长度与后缀,适合有序的 URL、路径等。

Zstd:压缩比与解压吞吐的账

编码之后,page 还要做一层块压缩。Zstd 的取舍很直接:压缩级别越高,体积越小,但压缩耗时越长;解压速度相对稳定,通常远快于压缩。

lab 的用例 27 给出 1GB 原始数据、4 倍压缩的账:

压缩后容量 = 1GB / 4 = 0.25GB
解压吞吐 = 2GB/s
解压耗时 = 0.25GB / 2GB/s = 0.125 秒
指标数值含义
原始容量1GB压缩前
压缩比4×编码 + 压缩后的总体效果
压缩后容量0.25GB实际读盘字节
解压吞吐2GB/sCPU 解压能力
解压耗时0.125 秒每读 1GB 原始数据的 CPU 成本

这 0.125 秒不是免费的。压缩比越高,读盘越少,但解压占用的 CPU 越多;当查询是 IO 受限时,高压缩比划算;当查询是 CPU 受限时,解压可能成为新瓶颈。选压缩级别,本质是在「IO 时间」与「CPU 时间」之间找平衡。

Zstd 相对 Snappy 的优势是同等压缩比下体积更小,代价是压缩稍慢;相对 Gzip 的优势是解压快得多。列式格式通常默认 Snappy 或 Zstd:前者追求写入与读取的平衡,后者追求更小的存储与更低的 IO。压缩算法本身不改变语义,只改变字节数与 CPU 开销。

编码组合:实际文件里不是单选

真实文件里,一列往往经历「变换 + 编码 + 压缩」三步,而不是只用一种编码:

数据形态第一步变换第二步编码第三步压缩本例账本
小整数、窄值域无Bit-packing可选8 值 3 字节
连续重复无RLE可选1000 值 8 字节
低基数枚举建字典索引位打包Zstd100 万行 1.258MB
单调时间戳求差值Delta + 位打包Zstd1000 值 125 字节
高基数随机串无PlainZstd1GB 压到 0.25GB

本例先编码再压缩。先字典再位打包,索引才紧凑;先 Delta 再位打包,差值才窄;先编码再压缩,压缩器才有规律可利用。反过来,先压缩再编码,编码器面对的是高熵字节流,几乎找不到可压缩的结构。

编码最适合最不适合主要风险
Bit-packing小整数、窄值域值域跨度大一个极值抬高整体位宽
RLE长 run、布尔、层级频繁交替run 头开销大于收益
字典低基数、字符串枚举基数接近行数字典膨胀后回退
Delta有序数值随机无序乱序后差值变大
Zstd字节级冗余已高度编码的数据解压 CPU 成本

没有「最强编码」,只有「匹配数据形态的编码」。同一张表里,不同列该用不同编码;同一列在不同 row group 里,也可能因为数据分布变化而回退。理解这一点,才不会把「换了编码却更慢」当成引擎 bug。

三个常见误解

误解一:压缩比越高越好,直接选最高压缩级别。 真相:高压缩比省 IO 但增 CPU,解压 1GB 原始数据对应的 0.25GB 压缩块要 0.125 秒;CPU 受限时,高压缩级别反而拖慢查询。

误解二:字典编码对所有字符串列都有效。 真相:字典收益取决于基数与行数之比;基数接近行数时,字典项加索引会比原数据更大,必须回退。

误解三:RLE 总能压缩重复数据。 真相:RLE 按 run 收费,频繁交替的数据每个值都成一个 run,8 字节 run 头会让体积不降反升。

一句话总结本节

编码的收益来自数据规律:8 个 3 位值位打包后只有 3 字节(原始 64 字节,约 21 倍),1000 个相同值 RLE 后只有 8 字节(原始 4000 字节,500 倍),100 万行 1000 个不同值字典编码后 1.258MB(原始 8MB,约 6.36 倍),1000 个步长 1 的时间戳 Delta 后 125 字节(原始 4000 字节,32 倍);1GB 数据 4 倍压缩到 0.25GB 后,按 2GB/s 解压需 0.125 秒。选编码先看值域、重复与顺序,再看压缩比与 CPU 的平衡。

本节 lab

下载卷五 Java 8 实验 · 实验运行与版本说明

在 bd-engine-lab 中验证编码字节账:

  • 源码:src/format/Format.java 与 src/format/FormatSuite.java。
  • 运行:cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。
  • 断言:用例 23 验证「8 个值、位宽 3,位打包为 24 位即 3 字节」;用例 24 验证「1000 个相同值压成 1 个 run 共 8 字节,原始 4000 字节,压缩 500 倍」;用例 25 验证「100 万行、1000 个不同值、索引 10 位,字典编码总计 1,258,000 字节」;用例 26 验证「1000 个步长 1 的时间戳 Delta 后为 125 字节」;用例 27 验证「1GB 原始数据 4 倍压缩到 0.25GB,按 2GB/s 解压耗时 0.125 秒」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:先分辨编码与压缩的分工 → 用位打包消除整数宽度浪费 → 用 RLE 消除连续重复 → 用字典消除低基数值本身 → 用 Delta 消除有序数值的绝对量 → 用 Zstd 处理剩余字节冗余 → 最后按数据形态组合,而不是迷信单一编码。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图