从零实现基于磁盘的LSM-Tree存储引擎：WAL、SSTable、布隆过滤器与Compaction策略深度实战

引言：为什么需要 LSM-Tree？

在现代分布式数据库和存储引擎中，LSM-Tree（Log-Structured Merge-Tree）是最核心的数据结构之一。从 Google 的 Bigtable 到 Apache HBase、Cassandra，从 LevelDB 到 RocksDB，LSM-Tree 凭借其出色的写入性能和空间利用率，成为写密集型工作负载的首选方案。

本文将从零开始实现一个基于磁盘的 LSM-Tree 存储引擎，涵盖 WAL 预写日志、MemTable 跳表、SSTable 文件格式、布隆过滤器、压缩策略、MVCC 并发控制、范围查询迭代器，以及性能优化技巧。

1. 整体架构概览

pub struct LsmEngine {
    // 活跃的内存表（可写）
    memtable: Arc<RwLock<MemTable>>,
    // 只读内存表队列（正在flush中）
    immutable_memtables: Arc<RwLock<Vec<Arc<MemTable>>>>,
    // 磁盘SSTable层级
    levels: Arc<RwLock<Vec<LevelMeta>>>,
    // WAL预写日志
    wal: Arc<Mutex<WalWriter>>,
    // 布隆过滤器缓存
    bloom_filters: Arc<RwLock<HashMap<u32, BloomFilter>>>,
    // 配置参数
    config: EngineConfig,
    // WAL目录路径
    wal_dir: PathBuf,
    // SST目录路径
    sst_dir: PathBuf,
}

写入路径：先写 WAL → 再写 MemTable → WAL 截断。读取路径：MemTable → Immutable MemTable → L0 SST → L1 SST → ... → Ln SST。

2. WAL 预写日志（Write-Ahead Log）

WAL 是保证持久性的关键。每次写入必须先在 WAL 中顺序追加，即使系统崩溃也能通过重放 WAL 恢复数据。

pub struct WalWriter {
    file: BufWriter<File>,
    path: PathBuf,
    size_threshold: u64,
    files: Vec<WalFileMeta>,
}

impl WalWriter {
    pub async fn append(&mut self, key: &[u8], value: Option<&[u8]>) -> Result<()> {
        let record = WalRecord {
            key_len: key.len() as u32,
            value_len: value.map(|v| v.len() as u32).unwrap_or(0),
            key: key.to_vec(),
            value: value.map(|v| v.to_vec()),
            checksum: Self::crc32(key, value),
            is_delete: value.is_none(),
        };
        self.encode_record(&record)?;
        
        // MemTable 超过阈值时需要截断WAL
        if self.current_size > self.size_threshold {
            self.rotate()?;
        }
        Ok(())
    }
    
    fn crc32(key: &[u8], value: Option<&[u8]>) -> u32 {
        let mut hasher = Crc32Hasher::new();
        hasher.update(key);
        if let Some(v) = value {
            hasher.update(v);
        }
        hasher.finalize()
    }
}

WAL 文件按序号递增（wal_001.log、wal_002.log），当 MemTable 被 flush 为 SST 后，对应的 WAL 文件可以安全删除。这种设计确保：每个 WAL 文件只对应尚未持久化到 SST 的数据，恢复时只需重放当前活跃的 WAL 文件即可。

3. MemTable：跳表实现

MemTable 是内存中的有序数据结构，我们选择跳表（SkipList）而非 B+树或红黑树，原因有三：无锁并发友好、实现简单、范围查询效率高。

const MAX_LEVEL: usize = 12;
const P: f64 = 0.5;

pub struct SkipNode {
    key: Vec<u8>,
    value: Option<Vec<u8>>,  // None = 墓碑标记
    timestamp: u64,
    next: Vec<Option<<SkilListNode>>>, // 各层前向指针
}

pub struct MemTable {
    head: SkilListNode,
    level: AtomicUsize,
    size_bytes: AtomicU64,
    max_size: u64,
}

impl MemTable {
    pub fn insert(&self, key: Vec<u8>, value: Option<Vec<u8>>) {
        let mut update: Vec<MutSkilListNode> = vec![self.head.clone(); MAX_LEVEL];
        let mut current = self.head.clone();
        
        // 从最高层开始查找插入位置
        for i in (0..self.level.load(Ordering::Relaxed)).rev() {
            while let Some(ref next) = current.next[i] {
                if next.key < key {
                    current = next.clone();
                } else {
                    break;
                }
            }
            update[i] = current.clone();
        }
        
        // 随机高度
        let new_level = Self::random_level();
        let new_node = SkipNode::new(key, value, new_level);
        
        // 逐层插入
        for i in 0..new_level {
            new_node.next[i] = update[i].next[i].take();
            update[i].next[i] = Some(new_node.clone());
        }
        self.size_bytes.fetch_add(new_node.size() as u64, Ordering::Relaxed);
    }
}

MemTable 大小超过阈值（默认 64MB）时变为 Immutable MemTable，由后台线程异步 flush 到磁盘成为 SSTable。

4. SSTable 文件格式

SSTable（Sorted String Table）是 LSM-Tree 在磁盘上的基本存储单元。我们的文件格式设计如下：

┌──────────────────────────────────────────────────────┐
│                    SSTable File Layout                │
├──────────────────────────────────────────────────────┤
│  Data Block 1     │ ... │ Data Block N             │
├──────────────────────────────────────────────────────┤
│  Index Block (Block Offsets + Keys)                  │
├──────────────────────────────────────────────────────┤
│  Bloom Filter Block (m bits, k hash functions)       │
├──────────────────────────────────────────────────────┤
│  Metadata: {min_key, max_key, count, level,         │
│            filter_offset, index_offset, checksum}     │
└──────────────────────────────────────────────────────┘

pub struct SstBuilder {
    data_blocks: Vec<DataBlock>,
    index_block: IndexBlock,
    bloom: BloomFilter,
    block_size: usize,
}

impl SstBuilder {
    pub fn add_entry(&mut self, key: &[u8], value: &[u8], seq: u64) {
        self.bloom.add_key(key);
        
        // 刷新当前 Block
        if self.current_block_size >= self.block_size {
            self.flush_data_block();
        }
        
        let internal_key = InternalKey::new(key, seq);
        self.current_block.add_entry(internal_key.encode(), value);
    }
    
    pub fn finalize(mut self) -> Result<SstFile> {
        self.flush_data_block();
        let bloom_data = self.bloom.encode();
        let index_data = self.index_block.encode();
        
        let footer = Footer {
            bloom_offset: data_len,
            index_offset: data_len + bloom_data.len() as u64,
            entry_count: self.total_entries,
            min_key: self.min_key.clone(),
            max_key: self.max_key.clone(),
        };
        
        Ok(SstFile { data: all_bytes, footer })
    }
}

5. 布隆过滤器（Bloom Filter）

布隆过滤器是 SSTable 读取优化的核心组件。它可以用极小的内存判断某个 key "一定不存在"于某个 SST 中，避免大量无效的磁盘 IO。

pub struct BloomFilter {
    bits: BitVec,
    num_hashes: usize,
    num_bits: usize,
}

impl BloomFilter {
    pub fn new(num_items: usize, false_positive_rate: f64) -> Self {
        let num_bits = Self::optimal_bits(num_items, false_positive_rate);
        let num_hashes = Self::optimal_hashes(num_bits, num_items);
        BloomFilter {
            bits: bitvec![0; num_bits],
            num_hashes,
            num_bits,
        }
    }
    
    // 双哈希模拟 k 个哈希函数: g(x) = h1(x) + i * h2(x)
    pub fn add_key(&mut self, key: &[u8]) {
        let (h1, h2) = Self::hash_pair(key);
        for i in 0..self.num_hashes {
            let pos = ((h1.wrapping_add((i as u64).wrapping_mul(h2)))
                % self.num_bits as u64) as usize;
            self.bits.set(pos, true);
        }
    }
    
    pub fn may_contain(&self, key: &[u8]) -> bool {
        let (h1, h2) = Self::hash_pair(key);
        for i in 0..self.num_hashes {
            let pos = ((h1.wrapping_add((i as u64).wrapping_mul(h2)))
                % self.num_bits as u64) as usize;
            if !self.bits[pos] { return false; }
        }
        true
    }
}

在实际实现中，我们使用 10 bits/item 的标准配置，此时假阳性率约 1%，k=7，每个 SSTable 附带约 10N bits 的布隆过滤器，一个 256MB 的 SST 仅需约 3MB 的内存即可缓存其过滤器。

6. Compaction 压缩策略

Compaction 是 LSM-Tree 的核心后台操作，负责将过时数据回收、合并小文件、减少读取放大。我们实现两种经典策略：

pub trait CompactionStrategy: Send + Sync {
    fn pick_compaction(&self, levels: &[LevelMeta]) -> Option<CompactionTask>
}

// 策略1: Leveled Compaction（RocksDB默认）
// 目标: 每层只保留1个重叠SST(除L0)
pub struct LeveledStrategy {
    max_level_size: Vec<u64>,
    size_ratio: u64,  // 相邻层大小比, 通常=10
}

impl CompactionStrategy for LeveledStrategy {
    fn pick_compaction(&self, levels: &[LevelMeta]) -> Option<CompactionTask> {
        // 从Li层选一个有重叠的SST
        for i in 1..levels.len() {
            if levels[i].size > self.max_level_size[i] {
                let picked_sst = &levels[i].ssts[0];
                let overlapped = levels[i+1].find_overlap(picked_sst);
                return Some(CompactionTask::new(i, picked_sst.clone(), overlapped));
            }
        }
        None
    }
}

// 策略2: Tiering Compaction（Cassandra风格）
// 目标: 每层保留多个不重叠SST, 层数到一定数量再合并
pub struct TieringStrategy {
    fanout: usize,  // 每层最大SST数, 通常=4
}

pub struct Compactor {
    engine: Arc<LsmEngine>,
    strategy: Box<dyn CompactionStrategy>,
}

impl Compactor {
    pub async fn compact(&self, task: CompactionTask) -> Result<()> {
        // 1. 读取所有输入SST的数据
        let mut merged = MergeIterator::new();
        for sst in &task.inputs {
            let reader = SstReader::open(sst.path())?;
            merged.push(reader.scan()?);
        }
        
        // 2. Write new SSTs
        let mut builder = SstBuilder::self();
        while let Some((key, value, seq)) = merged.next() {
            // 跳过过时的旧版本
            if self.should_skip(&key, seq) { continue; }
            // 跳过已删除的墓碑(在最后一层且无下层引用时)
            if value.is_none() & task.is_last_level { continue; }
            builder.add_entry(&key, value.as_ref().map(|v| v.as_slice()), seq);
        }
        
        // 3. 原子替换: 先写新文件, 再更新元数据, 最后删旧文件
        let new_ssts = builder.finalize_batch()?;
        self.atomic_replace(task.level, &task.inputs, &new_ssts)?;
        Ok(())
    }
}

7. MVCC 多版本并发控制

通过全局递增的 sequence number 实现快照读（Snapshot Read），确保读操作不会被正在进行的写入阻塞：

impl LsmEngine {
    pub async fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
        let seq = self.last_seq.load(Ordering::Acquire);
        self.get_with_seq(key, seq)
    }
    
    pub async fn get_with_seq(&self, key: &[u8], seq: u64) -> Result<Option<Vec<u8>>> {
        // 1. 查 MemTable (最新数据)
        if let Some(v) = self.memtable.read().await.search_lt(key, seq) {
            return Ok(v); // v=None 表示当前 seq 下已被删除
        }
        
        // 2. 查 Immutable MemTables (从最新到最老)
        let imm_tables = self.immutable_memtables.read().await;
        for imm in imm_tables.iter().rev() {
            if let Some(v) = imm.search_lt(key, seq) {
                return Ok(v);
            }
        }
        drop(imm_tables);
        
        // 3. 逐层查 SSTable (L0 → Ln)
        let levels = self.levels.read().await;
        for (level_idx, level) in levels.iter().enumerate() {
            for sst in level.ssts.iter().rev() {
                // 快速过滤: 使用序列号元数据
                if !sst.may_contain_key(key, seq) { continue; }
                // 布隆过滤器预过滤
                if level_idx > 0 && !self.bloom_check(sst.id, key) { continue; }
                if let Some(v) = self.sst_get(sst, key, seq)? {
                    return Ok(Some(v));
                }
            }
        }
        Ok(None)
    }
}

8. 范围查询迭代器

pub struct LsmIterator {
    mem_iters: Vec<Box<dyn Iterator>,   // MemTable迭代器链
    imm_iters: Vec<Box<dyn Iterator>,   // Immutable迭代器链  
    sst_iters: Vec<SstIterator>,       // SST迭代器（各层一个）
    merge_heap: BinaryHeap<MergeElem>, // 多路合并堆
    snapshot_seq: u64,
}

impl Iterator for LsmIterator {
    type Item = (Vec<u8>, Vec<u8>);
    
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let elem = self.merge_heap.pop()?;
            
            // 跳过重复key(取seq最大的), 跳过snapshot_seq之后的版本
            if let Some(ref prev) = self.last_key {
                if elem.key == *prev { continue; } // 同一key的较旧版本
            }
            if elem.seq > self.snapshot_seq { continue; }
            
            // 填充 merge 堆
            if let Some(next) = self.advance_source(elem.source_id) {
                self.merge_heap.push(next);
            }
            
            if elem.value.is_none() {
                self.last_key = Some(elem.key); // 删除墓碑也跳过
                continue;
            }
            
            self.last_key = Some(elem.key.clone());
            return Some((elem.key, elem.value.unwrap()));
        }
    }
}

9. 性能优化：7个关键技巧

1) Block Cache（块缓存）：将 SST 的数据块缓存在内存中，LRU 淘汰策略，可配置 256MB-2GB。读密集场景下命中率可达 80%+。

2) Write Buffer Manager：限制 WAL + 所有 Immutable MemTable 的总大小，超过阈值时阻塞写入（backpressure），防止 OOM。

3) Prefetch（预读优化）：范围查询时提前 async 预取下一个 SST 的数据块。

4) Prefix Bloom Filter：对 key 前缀构建布隆过滤器，极大加速 prefix_scan 性能。

5) Compression（数据压缩）：每层使用不同压缩算法——L0 用 LZ4（速度优先），深层用 ZSTD（压缩率优先）。

6) Direct I/O：绕过 OS Page Cache，使用 O_DIRECT 自己做缓存管理，避免 double-buffering。

7) 并行 Compaction：不同层之间可以并行 compact，利用 SSD 的多队列并发能力提升压缩吞吐。

10. 性能基准测试

在我们的 Rust 实现上，使用 64 字节 key + 4KB value 的配置，在 NVMe SSD 上的测试结果：

11. 故障恢复流程

impl LsmEngine {
    pub async fn recover(wal_dir: &Path, sst_dir: &Path) -> Result<Self> {
        // 1. 扫描所有 WAL 文件（按序号排序）
        let mut wal_files = std::fs::read_dir(wal_dir)?
            .filter_map(|e| e.ok())
            .map(|e| e.path())
            .filter(|p| p.extension() == Some("log".as_ref()))
            .collect<Vec<_>>();
        wal_files.sort();
        
        // 2. 重放 WAL 重建 MemTable
        let memtable = MemTable::new(DEFAULT_MEMTABLE_SIZE);
        for wal_path in &wal_files {
            let reader = WalReader::open(wal_path)?;
            for record in reader.records() {
                let record = record?;
                if record.is_delete {
                    memtable.insert(record.key, None);
                } else {
                    memtable.insert(record.key, record.value.unwrap());
                }
            }
        }
        
        // 3. 加载所有 SST 元数据
        let levels = Self::load_sst_metadata(sst_dir).await?;
        
        // 4. 重建布隆过滤器
        let bloom_filters = Self::rebuild_bloom_filters(&levels)?;
        
        Ok(Self { memtable, levels, wal_files, bloom_filters, .. })
    }
}

12. 与 Rust生态集成

// 与 tokio 深度集成的异步 API
impl LsmEngine {
    pub async fn batch_write(&self, batch: WriteBatch) -> Result<()> {
        // 批量写入优化: 合并 WAL 写入为单次 fsync
        {
            let mut wal = self.wal.lock().await;
            for entry in &batch.entries {
                wal.append(&entry.key, entry.value.as_deref())?;
            }
            wal.sync().await?; // 单次 fsync
        }
        for entry in &batch.entries {
            self.memtable.write().await.insert(entry.key.clone(), entry.value.clone());
        }
        Ok(())
    }
    
    pub async fn snapshot(&self) -> Snapshot {
        let seq = self.last_seq.load(Ordering::Acquire);
        Snapshot { engine: self.clone(), seq }
    }
}

// 与 Arrow/Parquet 集成的列式导出
impl LsmEngine {
    pub async fn export_to_parquet(&self, path: &Path) -> Result<()> {
        let schema = Arc::new(RecordBatch::new_empty(self.schema.clone()));
        let writer = ParquetFileWriter::try_new(path, schema, None)?;
        let mut scan = self.scan(Range::full()).await?;
        while let Some(batch) = scan.next_batch(8192).await? {
            writer.write(&batch)?;
        }
        writer.finish()?;
        Ok(())
    }
}

总结

LSM-Tree 的设计哲学是"将随机写转换为顺序写"，通过后台 Compaction 将数据逐步整理到更高效的结构中。这种设计天然适配现代存储硬件（SSD/NVMe）的特性：

• 顺序写友好：WAL 和 SST 的顺序写入充分利用 SSD 的写入带宽
• 读取放大可控：通过布隆过滤器、Block Cache、分层策略，将读取 I/O 控制在可接受范围
• 空间利用率可控：定期 Compaction 清除旧数据，空间放大系数通常在 1.1-1.3 之间
• 工程可控性：所有参数（块大小、压缩比、缓存大小）均可根据业务场景精细调优

从 LevelDB 到 RocksDB、Pebble、SlateDB，LSM-Tree 的设计不断进化，但其核心思想始终不变：内存接受随机写，磁盘只做顺序写，后台合并保效率。理解 LSM-Tree，就理解了现代存储引擎的半壁江山。