存储算法 #11：Delta 编码

Delta 编码将有序递增序列转为差值序列存储，结合 Varint 可将时间戳等单调 ID 压缩 50%~80%；ClickHouse、Parquet、Gorilla 时序数据库均内置此方案。

相关文章：Varint 与 ZigZag 编码 · LZ4 与 Snappy 与 Zstd

目录

问题背景

有序递增序列（时间戳、单调递增 ID、日志序号）直接存储时，每个元素都是一个大数值，例如 Unix 时间戳约 1.6×10⁹，需要 4~8 字节。

关键观察：相邻元素的差值通常远小于原值。

• 每秒采集一次的时间戳，差值恒为 1000（ms），甚至为 1
• 自增 ID 差值往往为 1~10
• 差值用 Varint 编码可压缩到 1~2 字节

收益公式（粗估）：

原始大小 = n × 8 字节（64-bit 整数）
压缩后   = 8 字节（首值） + (n-1) × avg_delta_varint_bytes

当 avg_delta < 128 时，差值 Varint 仅需 1 字节，整体压缩率约 87.5%。

基础 Delta 编码

2.1 核心数据结构

DeltaEncoded {
    first_value  : int64   // 原始序列第一个元素，完整存储
    deltas[]     : int64[] // 后续元素与前一元素的差值，可为负数
}

2.2 编码伪代码

encode_delta(arr: int64[]) -> DeltaEncoded:
    n = arr.length
    if n == 0: return {}

    output.first_value = arr[0]
    output.deltas = new int64[n - 1]

    prev = arr[0]
    for i = 1 to n - 1:
        delta = arr[i] - prev      // 差值，可为负
        output.deltas[i - 1] = delta
        prev = arr[i]              // 滑动窗口：上一个原始值

    return output

2.3 解码伪代码

decode_delta(encoded: DeltaEncoded) -> int64[]:
    n = encoded.deltas.length + 1
    result = new int64[n]

    result[0] = encoded.first_value
    for i = 1 to n - 1:
        result[i] = result[i - 1] + encoded.deltas[i - 1]
        // 累加还原：当前值 = 前一值 + 差值

    return result

2.4 正确性保证

encode 后再 decode 必须还原原始序列：

∀ i ≥ 1: result[i] = result[i-1] + (arr[i] - arr[i-1])
        = arr[i-1] + arr[i] - arr[i-1]
        = arr[i]   ✓

Delta-of-Delta（二阶差分）

3.1 适用场景

当差值序列本身也是近似等差的（例如每秒采集一次，时间戳差值总是约 1000ms），可以对差值再求差，使大多数值趋近于 0。

Gorilla 时序数据库（Facebook，2015）的 timestamp 压缩就采用此方案。

3.2 数据结构

DeltaOfDeltaEncoded {
    first_value  : int64   // 原始序列首值
    first_delta  : int64   // 第一个差值（d1 = arr[1] - arr[0]）
    dod[]        : int64[] // 差值的差值：dod[i] = delta[i] - delta[i-1]
}

3.3 编码伪代码

encode_dod(arr: int64[]) -> DeltaOfDeltaEncoded:
    n = arr.length
    if n <= 1: return {first_value=arr[0]}

    out.first_value = arr[0]
    out.first_delta = arr[1] - arr[0]        // 第一个差值完整存储
    out.dod = new int64[n - 2]

    prev_delta = out.first_delta
    for i = 2 to n - 1:
        curr_delta = arr[i] - arr[i - 1]     // 当前差值
        dod = curr_delta - prev_delta         // 差值的差值
        out.dod[i - 2] = dod
        prev_delta = curr_delta              // 滑动：更新上一差值

    return out

3.4 解码伪代码

decode_dod(encoded: DeltaOfDeltaEncoded) -> int64[]:
    n = encoded.dod.length + 2
    result = new int64[n]
    result[0] = encoded.first_value
    result[1] = result[0] + encoded.first_delta

    prev_delta = encoded.first_delta
    for i = 2 to n - 1:
        curr_delta = prev_delta + encoded.dod[i - 2]  // 还原差值
        result[i]  = result[i - 1] + curr_delta        // 还原原值
        prev_delta = curr_delta

    return result

3.5 Gorilla 的位级优化

Gorilla 对 DoD 值用变长位存储：

规则等差序列（DoD=0）每个时间戳仅需 1 bit。

FOR（Frame of Reference）编码

4.1 思路

在一个数据块（block，如 128 个元素）内，选一个基准值 base（通常为最小值），存储：

base + [val[0]-base, val[1]-base, ..., val[n-1]-base]

所有差值均非负，且范围缩小，可用固定位宽 bit-packing 打包。

4.2 数据结构

FORBlock {
    base       : int64   // 块内最小值（基准）
    bit_width  : uint8   // 差值所需最小位宽，range = max_delta.bit_length()
    packed[]   : byte[]  // 所有差值按 bit_width 位宽连续打包
}

4.3 编码伪代码

encode_for(arr: int64[], block_size: int = 128) -> FORBlock[]:
    blocks = []
    for chunk in split(arr, block_size):
        base = min(chunk)
        deltas = [v - base for v in chunk]
        max_delta = max(deltas)
        bit_width = ceil(log2(max_delta + 1))   // 至少 1 bit

        packed = bit_pack(deltas, bit_width)     // 将每个差值压进 bit_width 位
        blocks.append({base, bit_width, packed})

    return blocks

4.4 解码伪代码

decode_for(blocks: FORBlock[]) -> int64[]:
    result = []
    for block in blocks:
        deltas = bit_unpack(block.packed, block.bit_width)
        for delta in deltas:
            result.append(block.base + delta)   // 还原 = base + 差值
    return result

4.5 位宽影响

执行追踪

以时间戳序列为例（单位：秒）：

原始序列: [1620000000, 1620000001, 1620000003, 1620000006]

5.1 基础 Delta 编码追踪

步骤 1: first_value = 1620000000
步骤 2: i=1, delta = 1620000001 - 1620000000 = 1,   prev = 1620000001
步骤 3: i=2, delta = 1620000003 - 1620000001 = 2,   prev = 1620000003
步骤 4: i=3, delta = 1620000006 - 1620000003 = 3,   prev = 1620000006

DeltaEncoded = {first_value: 1620000000, deltas: [1, 2, 3]}

存储大小对比（结合 Varint）：

5.2 Delta-of-Delta 追踪

差值序列:      [1, 2, 3]
first_delta =  1
dod[0] = 2 - 1 = 1
dod[1] = 3 - 2 = 1

DoD编码 = {first_value: 1620000000, first_delta: 1, dod: [1, 1]}

若差值恒为 1（等差序列），则 DoD 全为 0，每个后续时间戳仅需 1 bit。

5.3 FOR 编码追踪

arr   = [1620000000, 1620000001, 1620000003, 1620000006]
base  = min = 1620000000
deltas = [0, 1, 3, 6]
max_delta = 6 → bit_width = ceil(log2(7)) = 3

packed = 000 001 011 110  (12 bits = 1.5 bytes)
FORBlock = {base: 1620000000, bit_width: 3, packed: 0x01_6x...}
总大小 = 8(base) + 1(bit_width) + 2(packed) ≈ 11 B

工程实现

6.1 ClickHouse Delta Codec

ClickHouse 的列式存储对整型列支持 Delta codec，通常与 LZ4 组合：

CREATE TABLE metrics (
    ts       DateTime   CODEC(Delta, LZ4),
    value    Float64    CODEC(Delta, LZ4),
    user_id  UInt64     CODEC(Delta, LZ4)
) ENGINE = MergeTree ORDER BY ts;

工作机制：

1. Delta 阶段：列内相邻行求差，得到差值列
2. LZ4 阶段：对差值列做通用压缩（小数值重复多，LZ4 效果更好）

适用列类型：时间列、单调 ID 列、传感器采样值；
不适用：随机 UUID、无规律字符串。

6.2 Parquet Delta Encoding

Parquet 定义了两种 Delta encoding：

DELTA_BINARY_PACKED（整型）：

• 按 mini-block（128 个值）分组
• 每个 mini-block 存储 base delta + bit-packing 差值
• 对应 FOR 编码的列存实现

Block结构:
  [block_size: varint][mini_block_count: varint]
  per mini_block:
    [min_delta: zigzag_varint][bit_widths: byte[8]][packed_deltas: ...]

DELTA_BYTE_ARRAY（字节数组/字符串）：

• 存储相邻字符串的公共前缀长度 + 后缀
• 适合有序字符串列（如有序 URL、有序用户名）

编码结构:
  [prefix_lengths: DELTA_BINARY_PACKED]
  [suffixes: DELTA_LENGTH_BYTE_ARRAY]

异常与边界场景

场景 1：非单调序列（差值为负）

情况：arr = [100, 50, 80]，差值 = [-50, 30]

处理方式：

• 基础 Delta：直接存负数，需配合 ZigZag 编码（将负数映射为正数再 Varint）
• FOR：base 取最小值，差值仍为非负，但 bit_width 可能因范围大而增加
• 若序列完全无序，差值方差极大，压缩率退化甚至膨胀

ZigZag 映射：zigzag(n) = (n << 1) XOR (n >> 63)，确保 -1→1, 1→2, -2→3，小绝对值始终短编码

场景 2：差值方差过大（压缩率退化）

情况：arr = [1, 1000000, 2, 999999]，差值 = [999999, -999998, 999997]

处理方式：

• Delta 编码的差值与原值一样大，无压缩收益
• ClickHouse/Parquet 会退化为原始存储（不强制使用 Delta）
• 实践中应先分析数据分布，仅对单调/近单调列启用 Delta

场景 3：解码时累加溢出（int64 边界）

情况：首值接近 Int64.MAX_VALUE，差值为正，累加后溢出

处理方式：

• 使用无符号 64-bit 整数（uint64）时，溢出为模运算，可还原（对应编码时也用无符号减法）
• 使用有符号 64-bit 时，编码端需检测：arr[i] - arr[i-1] 若溢出则报错或换用更宽类型
• ClickHouse 的 Delta codec 对 UInt64 列使用无符号模运算，天然正确

场景 4：单元素或空序列

encode_delta([])        → {first_value: 无, deltas: []}
encode_delta([42])      → {first_value: 42, deltas: []}
decode_delta({42, []})  → [42]

空序列返回空结果，单元素只存首值，逻辑最简，需在边界判断中覆盖。

场景 5：FOR 块内全相同值

情况：chunk = [100, 100, 100, 100]，deltas = [0, 0, 0, 0]

处理方式：

• max_delta = 0，bit_width 应设为 1（避免 log2(0) 错误）
• packed 全 0，1 bit × 4 = 0.5 字节（接近理论最优）
• 解码时所有值均为 base = 100，正确还原

参考资料

1. Gorilla 论文：Pelkonen et al. "Gorilla: A Fast, Scalable, In-Memory Time Series Database." VLDB 2015. PDF
2. Parquet 格式规范：Apache Parquet Encoding Definitions. 官方文档
3. ClickHouse Codecs：ClickHouse Column Compression Codecs. 官方文档
4. Daniel Lemire 博客："SIMD Compression and the Intersection of Sorted Integers." SIAM Journal on Scientific Computing, 2016.
5. Lemire & Boytsov："Decoding billions of integers per second through vectorization." Software: Practice and Experience, 2015.
6. 《数据密集型应用系统设计》（DDIA）第 3 章：存储与检索，列式存储压缩一节。