返回文章列表

用 Rust 从零实现 LSM-Tree:MemTable、SSTable 和 Compaction

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

为什么 RocksDB、LevelDB、Cassandra、TiKV 都用 LSM-Tree,而不是 B+ 树?

答案是一句话:把随机写变成顺序写。

B+ 树每次插入都要找到叶子节点再改,位置随机。机械盘上这意味着寻道,SSD 上意味着写放大和擦除单元。LSM-Tree 的写全是"追加到文件末尾"——顺序、快、对 SSD 友好。

代价是读要查多层,还要后台不停合并。这篇把这三个部件都写出来。


整体结构

        写入
         │
         v
   ┌───────────┐
   │  WAL      │  先写日志(上一篇)
   └─────┬─────┘
         v
   ┌───────────┐
   │ MemTable  │  内存里的有序表(BTreeMap / 跳表)
   └─────┬─────┘
         │ 写满后冻结
         v
   ┌───────────┐
   │ Immutable │  正在 flush 的只读表
   └─────┬─────┘
         │ flush 到磁盘
         v
   ┌───────────┐
   │  L0 SST   │  可能有重叠
   └─────┬─────┘
         │ compaction
         v
   ┌───────────┐
   │  L1..Ln   │  层内有序不重叠,层间容量递增
   └───────────┘

读的时候从新到旧依次查:MemTable → Immutable → L0 → L1 → ... → Ln。找到第一个就返回,因为越新的数据越"真"。

部件一:MemTable

MemTable 就是一个内存里的有序表。用 BTreeMap 完全够用,用跳表更好(因为可以并发),这里先用 BTreeMap:

use std::collections::BTreeMap;
 
pub type Key = Vec<u8>;
 
#[derive(Clone, Debug, PartialEq)]
pub enum Value {
    Put(Vec<u8>),
    Delete,          // 墓碑
}
 
#[derive(Default)]
pub struct MemTable {
    map: BTreeMap<Key, Value>,
    /// 当前占用的近似字节数,用来判断何时 flush
    size: usize,
}

关键设计:删除用墓碑(tombstone)而不是真删。

impl MemTable {
    pub fn put(&mut self, key: Key, value: Vec<u8>) {
        self.size += key.len() + value.len();
        self.map.insert(key, Value::Put(value));
    }
 
    pub fn delete(&mut self, key: Key) {
        self.size += key.len();
        // 不移除,写入墓碑
        self.map.insert(key, Value::Delete);
    }
 
    pub fn get(&self, key: &[u8]) -> Option<&Value> {
        self.map.get(key)
    }
}

为什么是墓碑?因为 LSM-Tree 是多层的。同一个 key 可能在 L0 老 SSTable 里存在,在 MemTable 里被删了。如果 MemTable 直接移除,读的时候会落到下层,读到已经被删的旧值。

墓碑的作用是"遮蔽"下层的旧数据,直到 compaction 把它和旧数据一起丢掉。

在 LSM 里,"删除"是一种写入,而不是一种移除。

写满就冻结:

impl MemTable {
    pub fn should_flush(&self, limit: usize) -> bool {
        self.size >= limit
    }
 
    /// 转成有序的键值对列表,准备 flush
    pub fn into_sorted(self) -> Vec<(Key, Value)> {
        self.map.into_iter().collect()
    }
}

部件二:SSTable

SSTable(Sorted String Table)是磁盘上的有序不可变文件。它最简单的形态就是把所有键值对按序追加写入:

+------------------+
| key1 | val1      |
| key2 | val2      |
| key3 | val3      |
| ...              |
+------------------+

但这样的文件查找要全扫。所以加一个稀疏索引:

数据区(按 key 有序):
  [apple=1][banana=2][cherry=3][date=4][elder=5][fig=6]...
 
稀疏索引(每 N 条记一条):
  apple  -> offset 0
  cherry -> offset 100
  elder  -> offset 200

查找 date 时,先二分索引定位到 [cherry, elder) 区间,只需扫描这一小段。

pub struct SsTableWriter {
    file: std::fs::File,
    index: Vec<(Key, u64)>,   // 稀疏索引
    offset: u64,
    count: usize,
    index_interval: usize,    // 每多少条记一个索引项
}
 
impl SsTableWriter {
    pub fn new(path: &std::path::Path, index_interval: usize) -> std::io::Result<Self> {
        let file = std::fs::File::create(path)?;
        Ok(Self {
            file,
            index: Vec::new(),
            offset: 0,
            count: 0,
            index_interval,
        })
    }
 
    pub fn append(&mut self, key: &[u8], value: &Value) -> std::io::Result<()> {
        // 每 index_interval 条记一个索引
        if self.count % self.index_interval == 0 {
            self.index.push((key.to_vec(), self.offset));
        }
 
        let mut buf = Vec::with_capacity(16 + key.len());
        buf.extend_from_slice(&(key.len() as u32).to_le_bytes());
        buf.extend_from_slice(key);
 
        match value {
            Value::Put(v) => {
                buf.push(1);
                buf.extend_from_slice(&(v.len() as u32).to_le_bytes());
                buf.extend_from_slice(v);
            }
            Value::Delete => {
                buf.push(0); // 墓碑标记
            }
        }
 
        use std::io::Write;
        self.file.write_all(&buf)?;
        self.offset += buf.len() as u64;
        self.count += 1;
        Ok(())
    }
}

写完数据,再把索引和元信息追加到文件末尾(也可能是单独的文件):

    pub fn finish(mut self) -> std::io::Result<()> {
        let index_start = self.offset;
 
        // 写索引区
        let mut buf = Vec::new();
        for (key, offset) in &self.index {
            buf.extend_from_slice(&(key.len() as u32).to_le_bytes());
            buf.extend_from_slice(key);
            buf.extend_from_slice(&offset.to_le_bytes());
        }
 
        // 末尾放"索引起始位置 + 索引项数",读取时先读它
        let footer_start = self.offset + buf.len() as u64;
        buf.extend_from_slice(&index_start.to_le_bytes());
        buf.extend_from_slice(&(self.index.len() as u64).to_le_bytes());
        buf.extend_from_slice(&footer_start.to_le_bytes());
 
        use std::io::Write;
        self.file.write_all(&buf)?;
        self.file.sync_all()?;   // 落盘!见上一篇
        Ok(())
    }
}

Footer 放在文件末尾是 LSM 的惯例:这样写入时不需要预留头部空间,可以纯追加。

用布隆过滤器加速"key 不存在"的判断

即使有稀疏索引,判断"key 不在这个 SSTable 里"仍要读一段数据。而 LSM 的读路径要查很多层——每一层都读一次磁盘,代价很高。

解法是为每个 SSTable 配一个布隆过滤器(前面写过的轮子):

pub struct SsTableReader {
    index: Vec<(Key, u64)>,
    bloom: BloomFilter,
    data: std::fs::File,
    min_key: Key,
    max_key: Key,
}
 
impl SsTableReader {
    pub fn may_contain(&self, key: &[u8]) -> bool {
        // 布隆说"不存在"就跳过,省一次磁盘 IO
        self.bloom.contains(key)
    }
 
    pub fn get(&self, key: &[u8]) -> Option<Value> {
        // 1. 先看 key 是否落在 [min_key, max_key] 之外
        if key < self.min_key.as_slice() || key > self.max_key.as_slice() {
            return None;
        }
        // 2. 布隆过滤器快速排除
        if !self.may_contain(key) {
            return None;
        }
        // 3. 二分索引定位,扫描小段
        let start = self.lookup_index(key);
        self.scan_from(start, key)
    }
}

布隆过滤器在这里的价值极高:它把"读这个 SSTable 但 key 不存在"从一次磁盘 IO 变成一次内存位查询。LSM 的读放大,一半靠布隆过滤器压下去。

读路径:从新到旧

pub struct LsmTree {
    memtable: MemTable,
    immutables: Vec<MemTable>,       // 正在 flush 的
    levels: Vec<Vec<SsTableReader>>, // L0, L1, ...
    wal: Wal,
}
 
impl LsmTree {
    pub fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
        // 1. MemTable
        if let Some(v) = self.memtable.get(key) {
            return unwrap_value(v);
        }
 
        // 2. 冻结的 MemTable(从新到旧)
        for mem in self.immutables.iter().rev() {
            if let Some(v) = mem.get(key) {
                return unwrap_value(v);
            }
        }
 
        // 3. 各层 SSTable
        for level in &self.levels {
            for sst in level.iter().rev() {   // 层内从新到旧
                if let Some(v) = sst.get(key) {
                    return unwrap_value(v);
                }
            }
        }
        None
    }
}
 
fn unwrap_value(v: &Value) -> Option<Vec<u8>> {
    match v {
        Value::Put(data) => Some(data.clone()),
        Value::Delete => None, // 墓碑 = 不存在
    }
}

注意 unwrap_value:墓碑返回 None,但这个 None 是"确定不存在",不能再往下查。 这就是为什么读路径必须"找到第一个就返回",而不是"找到非墓碑才返回"。

读放大:LSM 的原罪

上面这个 get 的最坏情况要读 N 层 × 每层若干 SSTable。这就是读放大(read amplification)。

优化手段:

手段 作用
布隆过滤器 跳过"肯定没有"的 SSTable
层内有序(L1+ 不重叠) 每层只需二分查 1 个文件
块缓存 热点数据块常驻内存
key range 元信息 快速排除 key 不在范围的 SSTable

L0 特殊:它的 SSTable 之间可能重叠(因为是直接从 MemTable flush 的,新老表有交集),所以 L0 要全部检查。

部件三:Compaction

Compaction 是 LSM 的心脏,做两件事:

  1. 合并:把多个 SSTable 合成一个,去掉被覆盖的旧值和墓碑
  2. 分层:保持每层容量和覆盖范围合理

最简单的策略是分层合并(Leveled Compaction,LevelDB 风格):

  • L0 满了(比如 4 个文件)→ 全部合并进 L1
  • L1 超过大小上限 → 挑一个文件晋升到 L2,同时合并 L2 中被覆盖的范围
  • 依此类推
pub fn compact_l0(&mut self) -> std::io::Result<()> {
    if self.levels[0].len() < L0_COMPACTION_TRIGGER {
        return Ok(());
    }
 
    // 1. 收集所有要合并的表(L0 全部 + L1 中范围重叠的)
    let to_merge: Vec<&SsTableReader> = self.levels[0].iter().collect();
 
    // 2. 归并排序地读,同 key 保留最新
    let mut merged: Vec<(Key, Value)> = Vec::new();
    let mut iterators: Vec<_> = to_merge.iter().map(|t| t.iter()).collect();
 
    while let Some((key, value)) = next_smallest(&mut iterators) {
        // 同 key 取最新的(越靠前的表越新)
        if merged.last().map(|(k, _)| k.as_slice()) != Some(key.as_slice()) {
            merged.push((key, value));
        }
    }
 
    // 3. 丢掉墓碑(如果下层没有同名 key 就可以安全丢)
    merged.retain(|(key, value)| {
        !matches!(value, Value::Delete) || self.key_exists_below(key, 1)
    });
 
    // 4. 写出新的 L1 表
    write_sstable(&self.new_l1_path(), &merged)?;
    Ok(())
}

墓碑什么时候能真删? 只有当 compaction 能看到"所有层"时。如果下层还有同名旧值,墓碑必须保留(否则删掉的 key 会复活)。

这就是著名的 "墓碑复活"(zombie resurrection) 问题:compaction 只合并了 L0 和 L1,就把墓碑丢了,而 L2 里还有旧值——结果删掉的 key 又出现了。

墓碑的删除条件是"比它更旧的所有层里都没有这个 key",而不是"我合并的这一批里没有"。 只做部分层合并时,墓碑必须保留。

写放大:compaction 的代价

LSM 的写放大有两个来源:

  1. 一层内数据被反复合并:从 L0 到 L5,一条数据平均要被重写 5-10 次
  2. compaction 触发频繁:配置不当会导致"合并风暴",磁盘 IO 打满

写放大 vs 读放大是一对矛盾:

策略 写放大 读放大 代表
Leveled 高(10-20x) 低 LevelDB, RocksDB 默认
Tiered / Size-Tiered 低 高 Cassandra
FIFO 最低 — 日志类数据

RocksDB 提供了 Universal Compaction(Tiered 风格),就是在写放大敏感的场景下用的。TiKV 也做了混合策略:小数据量用 leveled,大数据量切 tiered。

一个容易忽略的点:WAL 和 MemTable 的一致性

回到写入路径。正确的顺序是:

pub fn put(&mut self, key: Key, value: Vec<u8>) -> std::io::Result<()> {
    // 1. 先写 WAL
    self.wal.append(&Record::Put {
        key: key.clone(),
        value: value.clone(),
    })?;
 
    // 2. 按策略 fsync
    self.wal.sync()?;
 
    // 3. 再写 MemTable
    self.memtable.put(key, value);
 
    // 4. 检查是否需要 flush
    if self.memtable.should_flush(self.flush_threshold) {
        self.freeze_and_flush()?;
    }
    Ok(())
}

WAL 必须先于 MemTable。如果反过来,MemTable 写成功但 WAL 失败,进程崩溃后这条数据就丢了,但调用方以为写成功了。

flush 完成之后,对应的 WAL 段就可以删了:

fn freeze_and_flush(&mut self) -> std::io::Result<()> {
    let mem = std::mem::take(&mut self.memtable);
 
    // 写到 SSTable(先 sync 文件)
    let path = self.new_sst_path();
    let mut writer = SsTableWriter::new(&path, 16)?;
    for (key, value) in mem.into_sorted() {
        writer.append(&key, &value)?;
    }
    writer.finish()?;
 
    // 原子地加入层级:先写临时文件再 rename
    self.levels[0].insert(0, SsTableReader::open(&path)?);
 
    // 到现在,这个 MemTable 的数据已经在盘上了,WAL 可以截断
    self.wal.checkpoint(self.current_lsn)?;
    Ok(())
}
 
fn new_sst_path(&self) -> std::path::PathBuf {
    self.dir.join(format!("L0-{}.sst", self.next_sst_id))
}

注意 SsTableWriter::finish() 里的 sync_all():SSTable 必须真正落盘,才能认为"这个 MemTable 的数据安全了",进而截断 WAL。顺序反了就会丢数据。

还有一个原子性问题:新 SSTable 怎么"原子地"对读者可见?

做法是写临时文件再 rename:

let tmp = format!("{}.tmp", path.display());
// ... 写入 tmp ...
std::fs::rename(&tmp, &path)?;   // rename 在同一文件系统内是原子的
std::fs::File::open(&path)?.sync_all()?;  // 目录也要 fsync 才保证 rename 持久

目录的 fsync 是很多人漏掉的一步。 文件内容 fsync 了,但"文件存在"这个目录项可能还在缓存里,掉电后文件就消失了。

参数怎么调

LSM 的性能对参数非常敏感,几个核心项:

pub struct Options {
    /// MemTable 多大时 flush
    pub memtable_size: usize,        // 64MB 起步
    /// L0 多少个文件触发合并
    pub l0_compaction_trigger: usize, // 4
    /// L0 多少个文件开始限速
    pub l0_slowdown_writes: usize,    // 8
    /// L0 多少个文件停止写入
    pub l0_stop_writes: usize,        // 12
    /// 每层大小倍数
    pub level_multiplier: usize,      // 10
    /// 写入限速(字节/秒)
    pub write_rate_limit: u64,
}

l0_stop_writes 是防雪崩的兜底:如果 compaction 完全跟不上写入,L0 文件堆积到阈值就停止接受写入——宁可让上游变慢,也不能让内存和读放大失控。

LSM 的写路径必须能"反压"。 一个只会吞写入、不会拒绝的 LSM,最终会因为 L0 堆积而读性能崩溃。

结论

LSM-Tree 的三层结构各司其职:

MemTable 承接写入(内存有序);SSTable 承载持久化(磁盘有序 + 稀疏索引 + 布隆);Compaction 缝合两者(归并去重 + 分层 + 回收空间)。

它的核心权衡也很清楚:用写放大换写吞吐,用布隆过滤器和分层压读放大,用墓碑处理删除,用限速和停止写入防雪崩。

理解了这一套,你再看 RocksDB 的 200 个配置项,就不会觉得它们是玄学了——每一个旋钮,都对应这个权衡表上的一个点。