跳到主要内容

设计 KV 存储

问题​

如何用 Rust 设计一个键值存储引擎？

答案​

架构设计​

简化的 KV Store 实现​

use std::collections::BTreeMap;
use std::sync::{Arc, RwLock};
use std::fs::{File, OpenOptions};
use std::io::Write;

/// 基于 BTreeMap + WAL 的简易 KV 存储
pub struct KvStore {
    memtable: Arc<RwLock<BTreeMap<String, Option<String>>>>,
    wal: std::sync::Mutex<File>,
}

impl KvStore {
    pub fn open(path: &str) -> std::io::Result<Self> {
        let wal = OpenOptions::new()
            .create(true)
            .append(true)
            .open(format!("{}/wal.log", path))?;

        Ok(Self {
            memtable: Arc::new(RwLock::new(BTreeMap::new())),
            wal: std::sync::Mutex::new(wal),
        })
    }

    pub fn set(&self, key: String, value: String) -> std::io::Result<()> {
        // 1. 先写 WAL（保证持久性）
        {
            let mut wal = self.wal.lock().unwrap();
            writeln!(wal, "SET {} {}", key, value)?;
            wal.flush()?;
        }

        // 2. 再写 MemTable
        let mut table = self.memtable.write().unwrap();
        table.insert(key, Some(value));
        Ok(())
    }

    pub fn get(&self, key: &str) -> Option<String> {
        let table = self.memtable.read().unwrap();
        table.get(key).and_then(|v| v.clone())
    }

    pub fn delete(&self, key: &str) -> std::io::Result<()> {
        // 墓碑标记（写入 None）
        {
            let mut wal = self.wal.lock().unwrap();
            writeln!(wal, "DEL {}", key)?;
        }
        let mut table = self.memtable.write().unwrap();
        table.insert(key.to_string(), None);
        Ok(())
    }
}

存储引擎对比​

引擎数据结构写性能读性能适用场景
B-TreeB+ 树中等优秀读多写少
LSM-TreeMemTable + SSTable优秀中等写多读少
BitcaskHash Index + Log优秀优秀（内存索引）数据量 < 内存

Rust KV 存储生态​

库引擎特点
sledB-Tree (lock-free)纯 Rust，嵌入式
rocksdb (绑定)LSM-TreeFacebook 出品，生产级
redbB-Tree简单、安全、ACID

常见面试问题​

Q1: 为什么 LSM-Tree 写性能比 B-Tree 好？​

答案：

  • B-Tree：每次写可能触发页分裂，涉及随机 IO
  • LSM-Tree：写入先到内存的 MemTable（有序），满后顺序写到磁盘 SSTable

顺序写比随机写快 100 倍以上。代价是读取时可能需要查多层 SSTable（通过布隆过滤器优化）。

相关链接​