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 个值总字节 | 说明 |
|---|---|---|---|
| 原始 long | 8 | 64 | 与值域无关 |
| 位打包 3 位 | 0.375 | 3 | 只花值域需要的位 |
位打包的收益上限由位宽决定:值域 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 个相同值 | 1 | 8 | 4000 | 500× |
| 1000 个两两交替 | 1000 | 8000 | 4000 | 0.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 × 8B | 8,000 |
| 索引 | 1,000,000 × 10 位 / 8 | 1,250,000 |
| 合计 | — | 1,258,000 |
| 原始 | 1,000,000 × 8B | 8,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 | 全为 1 | 1 | 125 | 32× |
| 递增但步长波动 | 小范围 | 若干位 | 随之上升 | 下降 |
| 随机无序 | 大范围 | 接近原宽 | 接近原始 | 几乎无收益 |
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/s | CPU 解压能力 |
| 解压耗时 | 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 字节 |
| 低基数枚举 | 建字典 | 索引位打包 | Zstd | 100 万行 1.258MB |
| 单调时间戳 | 求差值 | Delta + 位打包 | Zstd | 1000 值 125 字节 |
| 高基数随机串 | 无 | Plain | Zstd | 1GB 压到 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
在 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 处理剩余字节冗余 → 最后按数据形态组合,而不是迷信单一编码。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。