返回文章列表

用 Rust 从零实现列式存储:编码比压缩算法更重要

599 字·5 分钟阅读
Rust从零造轮子存储

"列式存储快",这句话的原因常被简单归结为"列压缩比高"。但压缩只解释了一半。

更本质的原因是:分析型查询通常只碰少部分列。 行存读一行要带出全部 50 列,列存只读需要的那 3 列——IO 量直接少了一个数量级。

而让列存真正强大的第二层,是编码:列内的数据高度同质(全是同一类型的值),所以有大量可以利用的规律。


先看清行存的问题

假设一张订单表,一行是:

pub struct Order {
    pub id: u64,
    pub user_id: u64,
    pub amount: i64,
    pub status: u8,
    pub created_at: i64,
    pub region: [u8; 8],
    // ... 还有 40 个字段
}

行存的存储方式:

[id1][user1][amount1][status1][ts1][region1][...] 
[id2][user2][amount2][status2][ts2][region2][...]
[id3][user3][amount3][status3][ts3][region3][...]

查询 SELECT sum(amount) WHERE region = 'x' 时:

  • 只关心 amount 和 region 两列
  • 但每个磁盘块里混着全部字段
  • 扫 1GB 数据,实际用到的可能只有 60MB

更糟的是 CPU 缓存: 每个 cache line(64 字节)里只有几个字节是需要的。

列存的布局:

id:       [1][2][3][4]...[n]
user_id:  [u1][u2][u3]...[un]
amount:   [a1][a2][a3]...[an]
status:   [s1][s2][s3]...[sn]

同样的查询只需要读 amount 和 region 两段连续内存。 IO 量按列的比例下降。

编码才是重点

把同一列的值连续存放之后,会发现它们有很强的规律:

status 列:  [1,1,1,1,1,1,2,2,2,2,1,1,1,1]      -> 大量重复
region 列:  ["cn-beijing","cn-beijing",...]     -> 字典编码
id 列:      [1001,1002,1003,1004,...]           -> 等差!增量编码
amount 列:  [100,200,300,400,...]               -> 同上
timestamp:  [1700000000,1700000001,...]         -> 大数但增量小

四种规律对应四种编码,这才是列存能压到 10:1 以上的原因——而通用压缩算法(gzip、zstd)在这些场景下反而效果一般,因为它们看到的是"字节流",不是"数值规律"。

列存的核心竞争力是"按列的语义做编码",不是"用更强的压缩算法"。 这也是为什么 Parquet 的 zstd 压缩率通常不如它自带的字典 + RLE 组合。

编码一:字典编码(Dictionary)

适合基数低(不同值少)的列,比如状态、地区、类别。

pub struct DictionaryEncoder {
    /// 值 -> 编码后的整数
    dict: std::collections::HashMap<Vec<u8>, u32>,
    /// 反向表,解码时用
    values: Vec<Vec<u8>>,
    /// 编码后的整数序列
    codes: Vec<u32>,
}
impl DictionaryEncoder {
    pub fn new() -> Self {
        Self {
            dict: std::collections::HashMap::new(),
            values: Vec::new(),
            codes: Vec::new(),
        }
    }
 
    pub fn encode(&mut self, value: &[u8]) -> u32 {
        if let Some(&code) = self.dict.get(value) {
            self.codes.push(code);
            return code;
        }
 
        let code = self.values.len() as u32;
        self.dict.insert(value.to_vec(), code);
        self.values.push(value.to_vec());
        self.codes.push(code);
        code
    }
 
    pub fn decode(&self, code: u32) -> Option<&[u8]> {
        self.values.get(code as usize).map(|v| v.as_slice())
    }
 
    /// 压缩率:原始字节数 / 编码后字节数
    pub fn compression_ratio(&self) -> f64 {
        let raw: usize = self.codes.iter().map(|_| 8).sum(); // 假设原始是 8 字节
        let encoded = self.codes.len() * self.code_width();
        raw as f64 / encoded.max(1) as f64
    }
 
    /// 编码需要多少位:基数 <= 256 用 1 字节,<= 65536 用 2 字节
    fn code_width(&self) -> usize {
        match self.values.len() {
            0..=256 => 1,
            257..=65536 => 2,
            _ => 4,
        }
    }
}

两个关键优化:

1. 码宽按基数选。 只有 5 个不同的 status 值,每个码只需要 3 个 bit——而不是 4 字节。

2. 字典本身也要编码。 字典往往是字符串,可以用前缀共享(类似 Trie 的序列化)来压缩。

字典编码还有一个隐藏的好处:直接支持 GROUP BY 和等值比较。

WHERE status = 'paid'
-> 先在字典里查 'paid' 的码是 2
-> 然后只需要比较整数 2,而不是字符串比较

字符串比较是全内存扫描里最慢的操作之一(要逐字节比)。转成整数比较之后,能快好几倍。

这也是为什么字典编码几乎所有列存格式都实现了。 它同时带来"压缩"和"查询加速"两个收益。

编码二:RLE(游程编码)

适合相邻值大量重复的列。比如排好序的时间戳、状态位。

#[derive(Debug, Clone, PartialEq)]
pub struct Run<T> {
    pub value: T,
    pub count: u32,
}
 
pub fn rle_encode(values: &[u32]) -> Vec<Run<u32>> {
    let mut runs = Vec::new();
    if values.is_empty() {
        return runs;
    }
 
    let mut current = values[0];
    let mut count = 1u32;
 
    for &v in &values[1..] {
        if v == current && count < u32::MAX {
            count += 1;
        } else {
            runs.push(Run { value: current, count });
            current = v;
            count = 1;
        }
    }
    runs.push(Run { value: current, count });
    runs
}
 
pub fn rle_decode(runs: &[Run<u32>]) -> Vec<u32> {
    let mut out = Vec::with_capacity(runs.iter().map(|r| r.count as usize).sum());
    for run in runs {
        out.extend(std::iter::repeat(run.value).take(run.count as usize));
    }
    out
}

RLE 的关键在于"用 (值, 次数) 代替重复的值"。

不用 RLE: [1,1,1,1,1,1,1,1,1,1]  = 40 字节(u32)
用 RLE:   [(1, 10)]              = 8 字节

5 倍的压缩,而且解码是纯顺序的,非常快。

RLE 的天然搭档:位图(Bitmap)

布尔列(is_deleted、has_shipped)用位图最合适——1 个 bit 存一个值:

pub struct Bitmap {
    bits: Vec<u64>,
    len: usize,
}
 
impl Bitmap {
    pub fn new(len: usize) -> Self {
        Self {
            bits: vec![0u64; len.div_ceil(64)],
            len,
        }
    }
 
    pub fn set(&mut self, i: usize) {
        self.bits[i / 64] |= 1u64 << (i % 64);
    }
 
    pub fn get(&self, i: usize) -> bool {
        (self.bits[i / 64] >> (i % 64)) & 1 == 1
    }
 
    /// 位图之间做 AND / OR,一次 64 位
    pub fn and(&self, other: &Bitmap) -> Bitmap {
        let bits = self.bits.iter().zip(&other.bits).map(|(a, b)| a & b).collect();
        Bitmap { bits, len: self.len }
    }
 
    pub fn count_ones(&self) -> usize {
        self.bits.iter().map(|b| b.count_ones() as usize).sum()
    }
}

位图不只是压缩手段,它还是"执行"的手段。

WHERE a > 10 AND b < 5 可以先用两个比较生成两个位图,然后一次 64 位的 AND 得到结果——这是向量化执行的基础(下一篇的主题)。

而且 RLE 和位图天然互补:位图只在"稀疏"时才值得(否则 1 bit/值 已经是最小单位),RLE 在"成段重复"时更优。很多格式会根据数据特征自动选。

编码三:增量编码(Delta)

适合单调递增或接近等差的列。典型是自增主键、时间戳。

pub fn delta_encode(values: &[i64]) -> Vec<i64> {
    if values.is_empty() {
        return Vec::new();
    }
 
    let mut out = Vec::with_capacity(values.len());
    out.push(values[0]); // 第一个存原值
 
    for i in 1..values.len() {
        out.push(values[i] - values[i - 1]);
    }
    out
}
 
pub fn delta_decode(deltas: &[i64]) -> Vec<i64> {
    let mut out = Vec::with_capacity(deltas.len());
    let mut acc = 0i64;
 
    for &d in deltas {
        acc += d;
        out.push(acc);
    }
    out
}

为什么有效? 看时间戳:

原值:   [1700000000, 1700000001, 1700000002, 1700000003]
增量:   [1700000000, 1, 1, 1]

大数变成了小数。 而小数意味着——可以用更少的字节存。

增量 + 变长整数 + 位打包

增量之后通常还有一个"大多数增量很小、偶尔很大"的分布。所以:

第一步:增量编码。 大数变小。

第二步:位打包(bit packing)。 如果所有值都小于 2^7,每个只用 7 bit:

pub fn bit_pack(values: &[u64], bit_width: u32) -> Vec<u8> {
    let mut out = Vec::new();
    let mut buffer = 0u64;
    let mut bits_in_buffer = 0u32;
 
    for &v in values {
        buffer |= (v & ((1u64 << bit_width) - 1)) << bits_in_buffer;
        bits_in_buffer += bit_width;
 
        while bits_in_buffer >= 8 {
            out.push((buffer & 0xFF) as u8);
            buffer >>= 8;
            bits_in_buffer -= 8;
        }
    }
 
    // 收尾
    if bits_in_buffer > 0 {
        out.push((buffer & 0xFF) as u8);
    }
    out
}
 
pub fn bit_unpack(data: &[u8], bit_width: u32, count: usize) -> Vec<u64> {
    let mut out = Vec::with_capacity(count);
    let mut buffer = 0u64;
    let mut bits_in_buffer = 0u32;
    let mut byte_idx = 0;
 
    for _ in 0..count {
        while bits_in_buffer < bit_width {
            let byte = data.get(byte_idx).copied().unwrap_or(0) as u64;
            buffer |= byte << bits_in_buffer;
            bits_in_buffer += 8;
            byte_idx += 1;
        }
 
        out.push(buffer & ((1u64 << bit_width) - 1));
        buffer >>= bit_width;
        bits_in_buffer -= bit_width;
    }
    out
}

位打包的压缩比非常实在:如果增量都是个位数(0-15),bit_width = 4,也就是每个值 4 bit——比 u64 省 16 倍。

这就是 Parquet 里 "delta binary packed" 编码的效果,它对时间戳列的压缩率通常能达到 20:1 以上。

注意位打包的边界处理。 上面用"累积到 8 位就吐一个字节"的写法,避免了跨字节边界的复杂处理。这是位操作里最容易出错的地方,一定要写单元测试。

编码四:FOR(Frame of Reference)

有时一列的值都在一个很小的范围内,但不是从 0 开始:

[1000000, 1000001, 1000002, 1000003]

增量编码会把第一个值 1000000 原样存下来——这是个"大数尾巴"。

FOR 的做法是"先减去最小值,再位打包":

pub struct ForEncoded {
    pub min: u64,
    pub bit_width: u32,
    pub packed: Vec<u8>,
    pub count: usize,
}
 
pub fn for_encode(values: &[u64]) -> Option<ForEncoded> {
    if values.is_empty() {
        return None;
    }
 
    let min = *values.iter().min()?;
    let max = *values.iter().max()?;
 
    // 偏移后的最大值决定位宽
    let range = max - min;
    let bit_width = 64 - range.leading_zeros();
 
    let offsets: Vec<u64> = values.iter().map(|v| v - min).collect();
 
    Some(ForEncoded {
        min,
        bit_width,
        packed: bit_pack(&offsets, bit_width),
        count: values.len(),
    })
}

FOR + 位打包,效果往往比增量还稳:它不会因为"第一个值特别大"而浪费。

实际格式里通常是组合使用:先做增量,再对增量做 FOR(因为增量分布也有个最小正值),再位打包。这就是 Parquet 的 "DELTA_BINARY_PACKED" 的实际结构。

编码选择:怎么自动决定

一个可用的实现应该根据数据特征自动选编码:

pub fn choose_encoding(values: &[i64]) -> Encoding {
    if values.is_empty() {
        return Encoding::Plain;
    }
 
    // 1. 先看去重后的基数
    let distinct: std::collections::HashSet<_> = values.iter().collect();
    if distinct.len() < values.len() / 4 && distinct.len() < 1024 {
        return Encoding::Dictionary;   // 基数低,字典编码
    }
 
    // 2. 看是否有很多连续重复
    let repeats = values.windows(2).filter(|w| w[0] == w[1]).count();
    if repeats > values.len() / 2 {
        return Encoding::Rle;          // 大量相邻重复
    }
 
    // 3. 看是否单调(或者近似单调)
    let monotonic = values.windows(2).all(|w| w[0] <= w[1]);
    if monotonic {
        // 看增量是否小
        let max_delta = values
            .windows(2)
            .map(|w| (w[1] - w[0]) as u64)
            .max()
            .unwrap_or(0);
 
        if max_delta < 1 << 16 {
            return Encoding::DeltaBinaryPacked;   // 单调且增量小
        }
    }
 
    // 4. 看值域是否集中
    let min = *values.iter().min().unwrap();
    let max = *values.iter().max().unwrap();
    let range = (max - min) as u64;
 
    // 相对值域很小 -> FOR
    if (range as f64) < (max.abs() as f64) * 0.5 {
        return Encoding::For;
    }
 
    Encoding::Plain
}

注意这里的顺序:从"压缩收益最大"的条件开始判断。 字典 > RLE > 增量 > FOR > 原样。

真实实现(Parquet)还会做一件事:按块(page)而不是按整列选编码。 一个 100 万行的列会被切成 64KB 左右的页,每页独立选编码——因为数据的特征在局部可能不同(比如时间戳列的前半段是密集的,后半段是稀疏的)。

查询下推:让统计信息帮你跳过大块数据

编码之外,列存还有一个杀手特性:每个数据块都带统计信息(min/max),可以跳过整个块。

pub struct ColumnChunkStats {
    pub min: i64,
    pub max: i64,
    pub null_count: u64,
    pub row_count: u64,
}
 
impl ColumnChunkStats {
    /// 判断这个块是否可能包含满足条件的行
    pub fn might_match(&self, range: &(i64, i64)) -> bool {
        // 区间不相交 -> 整块跳过
        !(self.max < range.0 || self.min > range.1)
    }
}

这就是 zone map / 谓词下推(predicate pushdown)。

效果非常直接:WHERE created_at > '2026-01-01' 时,如果数据按时间排序存储,前面 80% 的块可以直接跳过,一次 IO 都不做。

pub fn scan_with_filter(chunks: &[ColumnChunk], predicate: &(i64, i64), col: usize) -> Vec<i64> {
    let mut results = Vec::new();
 
    for chunk in chunks {
        // 1. 先用统计信息跳过
        if !chunk.stats[col].might_match(predicate) {
            continue;
        }
 
        // 2. 真正解码并过滤
        let values = chunk.decode_column(col);
        for v in values {
            if v >= predicate.0 && v <= predicate.1 {
                results.push(v);
            }
        }
    }
 
    results
}

统计信息跳过是"免费的过滤"——它不需要解码,只需要读几十字节的元信息,就能排除整个数据块。

排序对分析型数据库的性能影响巨大,根本原因就在这里:有序的数据让 min/max 区间不重叠,谓词下推才能跳过大量块。

结论

列式存储的能力来自两层:

第一层是布局:同列连续存放,只读需要的列。 第二层是编码:字典(基数低)、RLE(成段重复)、增量 + 位打包(单调小增量)、FOR(值域集中),按块自动选择。

再加上一层"元数据加速":

每个块的 min/max 统计,让"不匹配的块"完全不用解码。

理解了这三层,再看 Parquet 的 encoding、page_size、row_group_size、statistics 这些配置,你会清楚每个旋钮在控制什么。而且会明白为什么"把数据按常用的过滤字段排序"能带来数量级的性能提升——它让 zone map 真正起作用。

下一篇我们去看"解码之后怎么算"——向量化执行引擎。