用 Rust 从零实现 LSM-Tree:MemTable、SSTable 和 Compaction
为什么 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 的心脏,做两件事:
- 合并:把多个 SSTable 合成一个,去掉被覆盖的旧值和墓碑
- 分层:保持每层容量和覆盖范围合理
最简单的策略是分层合并(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 的写放大有两个来源:
- 一层内数据被反复合并:从 L0 到 L5,一条数据平均要被重写 5-10 次
- 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 个配置项,就不会觉得它们是玄学了——每一个旋钮,都对应这个权衡表上的一个点。