返回文章列表

用 Rust 从零实现 Bitcask:为什么它的写入能比 B+ 树快十倍

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

上一篇写 LSM-Tree 时,我们用了三层结构才把读放大压下去。Bitcask 用一层就做到了——因为它干脆不排序。

Bitcask 是 Riak 的默认存储引擎,设计思路简单到有点可疑:

写入:追加到文件末尾,同时在内存里记下 "key -> 偏移"
读取:查内存索引拿到偏移,一次 seek 读出来
删除:写一条墓碑记录
更新:写一条新记录,覆盖内存索引里的偏移

没有排序,没有合并,没有后台任务。 一个完整可用的 Bitcask,核心代码不到 300 行。


磁盘格式

数据文件是纯追加的,每条记录长这样:

+--------+--------+---------+--------+---------+--------+-------+
| crc32  | ts     | key_len | value_len | key   | value  |  ...  |
| 4B     | 8B     | 4B      | 4B     | var    | var    |       |
+--------+--------+---------+--------+---------+--------+-------+
pub struct Record {
    pub timestamp: u64,
    pub key: Vec<u8>,
    pub value: Option<Vec<u8>>, // None 表示墓碑
}
 
impl Record {
    fn encode(&self) -> Vec<u8> {
        let key_len = self.key.len() as u32;
        let value_len = self.value.as_ref().map(|v| v.len()).unwrap_or(0) as u32;
        let tombstone = self.value.is_none();
 
        let mut buf = Vec::with_capacity(4 + 8 + 4 + 4 + 1 + self.key.len() + value_len as usize);
 
        buf.extend_from_slice(&0u32.to_le_bytes()); // crc 占位,最后回填
        buf.extend_from_slice(&self.timestamp.to_le_bytes());
        buf.extend_from_slice(&key_len.to_le_bytes());
        buf.extend_from_slice(&value_len.to_le_bytes());
        buf.push(tombstone as u8);
        buf.extend_from_slice(&self.key);
        if let Some(v) = &self.value {
            buf.extend_from_slice(v);
        }
 
        let crc = crc32(&buf[4..]);
        buf[0..4].copy_from_slice(&crc.to_le_bytes());
        buf
    }
}

墓碑用 value_len = 0 + 一个标志位表示,而不是真删。 因为一旦写入就是不可变的——这是 Bitcask 所有简单性的来源。

内存索引:key -> (文件, 偏移)

内存里只维护最小信息:

#[derive(Debug, Clone, Copy)]
pub struct KeyDirEntry {
    pub file_id: u32,
    pub offset: u64,
    pub size: u32,      // 整条记录的长度,用来一次读完
    pub timestamp: u64,
}
pub struct KeyDir {
    map: std::collections::HashMap<Vec<u8>, KeyDirEntry>,
}

注意这里存的是"记录位置",不是值本身。 值始终在磁盘上,靠一次 seek + read 取出来。这就把内存占用压到了 key 长度 × 数量 的量级。

这也是 Bitcask 的一句名言:"所有 key 必须能装进内存。" 这是它唯一的硬约束,也是它最大的限制。

写入路径:一次 append 加一次 map 更新

use std::fs::{File, OpenOptions};
use std::io::{Seek, SeekFrom, Write};
 
pub struct Bitcask {
    dir: std::path::PathBuf,
    active_id: u32,
    active: File,
    active_size: u64,
    /// 单个数据文件最大多少字节
    max_file_size: u64,
    keydir: KeyDir,
}
 
impl Bitcask {
    pub fn put(&mut self, key: Vec<u8>, value: Vec<u8>) -> std::io::Result<()> {
        self.write_record(Record {
            timestamp: now_millis(),
            key,
            value: Some(value),
        })
    }
 
    pub fn delete(&mut self, key: Vec<u8>) -> std::io::Result<()> {
        self.write_record(Record {
            timestamp: now_millis(),
            key,
            value: None, // 墓碑
        })
    }
 
    fn write_record(&mut self, record: Record) -> std::io::Result<()> {
        let is_tombstone = record.value.is_none();
        let key = record.key.clone();
        let encoded = record.encode();
 
        self.active.write_all(&encoded)?;
        // 想要"写入即持久"就打开它,代价见上一篇 WAL
        // self.active.sync_data()?;
 
        let offset = self.active_size;
        self.active_size += encoded.len() as u64;
 
        if is_tombstone {
            self.keydir.map.remove(&key);
        } else {
            self.keydir.map.insert(
                key,
                KeyDirEntry {
                    file_id: self.active_id,
                    offset,
                    size: encoded.len() as u32,
                    timestamp: record.timestamp,
                },
            );
        }
 
        if self.active_size >= self.max_file_size {
            self.roll_file()?;
        }
        Ok(())
    }
}

这一段就是 Bitcask 的全部写入逻辑。 对比一下 B+ 树:找叶子、可能分裂、写回多个页、维护父节点指针;对比 LSM:写 WAL、写 MemTable、判断 flush、可能触发 compaction。

Bitcask 只做了一件事:追加,然后改一个 map 的值。 这就是它写入吞吐高的原因。

Bitcask 的写入是"一次顺序写 + 一次内存哈希表更新",没有任何随机 IO,也没有任何后台任务参与。

读取路径:一次 seek

    pub fn get(&self, key: &[u8]) -> std::io::Result<Option<Vec<u8>>> {
        let Some(entry) = self.keydir.map.get(key) else {
            return Ok(None);
        };
 
        let mut file = self.open_data_file(entry.file_id)?;
        file.seek(SeekFrom::Start(entry.offset))?;
 
        let mut buf = vec![0u8; entry.size as usize];
        file.read_exact(&mut buf)?;
 
        let record = Record::decode(&buf)?;
        Ok(record.value) // 墓碑在 keydir 里已经被移除了,这里不会拿到 None
    }

一次随机读,就一次。 因为索引直接告诉了你位置。

对比 LSM:要查 MemTable、多个 immutable、L0 全部、L1 一个、L2 一个……Bitcask 的读放大是 1,LSM 的读放大是层数。

文件轮转

单个文件不能无限大(否则恢复时读不动,删除时也回收不了空间)。写满就换新文件:

    fn roll_file(&mut self) -> std::io::Result<()> {
        self.active.sync_all()?;
        self.active_id += 1;
        let path = self.dir.join(format!("{}.data", self.active_id));
        self.active = OpenOptions::new()
            .create(true)
            .write(true)
            .append(true)
            .open(path)?;
        self.active_size = 0;
        Ok(())
    }

文件命名用递增 ID,这样恢复时按 ID 排序就是写入顺序——后面的记录一定比前面的新。

恢复:扫描所有文件,后写的覆盖先写的

崩溃后重启,keydir 是空的,必须重建。做法是按文件 ID 从小到大扫描:

    pub fn open(dir: impl AsRef<std::path::Path>, max_file_size: u64) -> std::io::Result<Self> {
        let dir = dir.as_ref().to_path_buf();
        let mut ids = discover_file_ids(&dir)?;
        ids.sort_unstable();
 
        let mut keydir = KeyDir::default();
 
        for id in &ids {
            Self::scan_file(&dir, *id, &mut keydir)?;
        }
 
        // 最后一个文件继续追加
        let active_id = *ids.last().unwrap_or(&0);
        let path = dir.join(format!("{active_id}.data"));
        let active = OpenOptions::new().create(true).write(true).append(true).open(&path)?;
        let active_size = active.metadata()?.len();
 
        Ok(Self { dir, active_id, active, active_size, max_file_size, keydir })
    }
 
    fn scan_file(
        dir: &std::path::Path,
        id: u32,
        keydir: &mut KeyDir,
    ) -> std::io::Result<()> {
        let mut file = File::open(dir.join(format!("{id}.data")))?;
        let mut offset = 0u64;
        let file_len = file.metadata()?.len();
 
        loop {
            if offset >= file_len {
                break;
            }
 
            match Record::read_at(&mut file, offset) {
                Ok(Some((record, size, _))) => {
                    if record.value.is_some() {
                        keydir.map.insert(
                            record.key,
                            KeyDirEntry {
                                file_id: id,
                                offset,
                                size: size as u32,
                                timestamp: record.timestamp,
                            },
                        );
                    } else {
                        keydir.map.remove(&record.key);
                    }
                    offset += size as u64;
                }
                // CRC 校验失败或文件被截断:停在这里,后面都是残骸
                Ok(None) | Err(_) => {
                    eprintln!("文件 {id} 在偏移 {offset} 处截断");
                    break;
                }
            }
        }
        Ok(())
    }

两个关键点:

  1. 扫描顺序决定了正确性。 后扫的文件覆盖先扫的条目,所以必须按 ID 升序(也就是写入时间升序)。
  2. 遇到损坏就停,但只停这一个文件。 后面的文件仍然要扫——因为损坏只可能出现在"正在写的那个文件"的尾部。

Bitcask 的恢复是"重放式"的:它不修改数据文件,只是重建内存索引。 这让恢复逻辑异常简单,也永远不会破坏已有数据。

Merge:回收空间

追加写有个必然结果:同一个 key 被更新 N 次,磁盘上就有 N 份。 删除也不会释放空间。

解法是后台的 merge(压缩) 进程:

1. 选一个"非活跃"的数据文件(不会再有新写入)
2. 遍历它,只保留每个 key 的"最新版本"(如果最新版本在别的文件里,就整条丢掉)
3. 把保留下来的记录写入一个新的、紧凑的文件
4. 原子地删除旧文件,更新 keydir 里的 file_id
    pub fn merge_file(&mut self, id: u32) -> std::io::Result<()> {
        let mut old = File::open(self.dir.join(format!("{id}.data")))?;
        let mut offset = 0u64;
        let file_len = old.metadata()?.len();
 
        let new_id = self.next_file_id();
        let mut new_file = File::create(self.dir.join(format!("{new_id}.data")))?;
        let mut new_offset = 0u64;
 
        while offset < file_len {
            let Ok(Some((record, size, _))) = Record::read_at(&mut old, offset) else {
                break;
            };
            offset += size as u64;
 
            // 只在"这条记录就是该 key 的最新版本"时才保留
            let Some(entry) = self.keydir.map.get(&record.key) else {
                continue; // 已被删除
            };
            if entry.file_id != id || entry.offset != offset - size as u64 {
                continue; // 最新版本在别处,这条是旧的
            }
 
            let encoded = record.encode();
            new_file.write_all(&encoded)?;
 
            // 更新索引指向新文件
            self.keydir.map.insert(
                record.key.clone(),
                KeyDirEntry {
                    file_id: new_id,
                    offset: new_offset,
                    size: encoded.len() as u32,
                    timestamp: record.timestamp,
                },
            );
            new_offset += encoded.len() as u64;
        }
 
        new_file.sync_all()?;
        std::fs::remove_file(self.dir.join(format!("{id}.data")))?;
        Ok(())
    }

判断"是不是最新版本"要同时比 file_id 和 offset。 只比 file_id 不够——同一个文件里同一个 key 可能写过两次。

这段实现里有个容易忽略的顺序问题:必须先 sync_all 新文件,再删旧文件。 反过来的话,中间崩溃就会丢数据——旧文件已删,新文件还没落盘。

Hint file:加速恢复

如果数据文件很大,恢复时要扫描全部内容。但恢复只需要 key → 位置 的映射,不需要 value。

Hint file 就是为此存在的:merge 时,把要保留的记录的元信息单独写一个 .hint 文件:

+---------+--------+--------+--------+
| key_len | value_len | offset | ts  |
| 4B      | 4B     | 8B     | 8B  |
+---------+--------+--------+--------+
| key ...                           |

恢复时直接读 hint 文件,不需要碰数据文件的内容,也不用做 CRC 校验(数据文件本身会校验)。

    fn scan_hint_file(dir: &std::path::Path, id: u32, keydir: &mut KeyDir) -> std::io::Result<()> {
        let mut file = File::open(dir.join(format!("{id}.hint")))?;
        // 逐条读元信息,直接插进 keydir
        // 速度比扫数据文件快一个数量级
        Ok(())
    }

这是 Bitcask 一个很实在的优化:恢复时间从"与数据量成正比"降到"与 key 数量成正比"。一个有 1 亿个 key、每个 value 1KB 的库,扫数据要读 100GB,扫 hint 只要读几 GB。

Bitcask 的边界

它简单快手,但有几个明确的限制,写之前必须知道:

1. 所有 key 必须装进内存。 这是硬约束。1 亿个 key、每个 32 字节,就至少 3.2GB 内存。超过这个量级就得换引擎。

2. 范围查询是灾难。 keydir 是 HashMap,无序。要 scan key1..key2,只能遍历全部 key 再排序——O(n log n)。

改进办法是换成有序索引(BTreeMap),代价是写入变慢、内存开销更大。这时它其实已经变成了 LSM 的一个变体。

3. 读放大是 1,但每次读都是随机 IO。 单次读取比 LSM 好,但如果 value 很大,随机读的成本会拖累吞吐。

4. 需要 merge 才能回收空间。 merge 会和读写争抢 IO,需要限速。

维度 Bitcask
写入 极快(纯追加)
点查 快(一次随机读)
范围查询 差(索引无序)
内存占用 高(全部 key)
空间回收 需 merge

它适合什么

Bitcask 的定位非常清晰:key 数量可控、点查为主、写入密集、value 可能较大。

Riak 把它作为默认引擎正是因为这些:Riak 是 KV 存储,key 是有限数量的对象 ID,value 是可能很大的文档,访问模式是点查。

反面例子是分析型数据库——那边要扫大量数据还要范围查询,Bitcask 完全不合适。

存储引擎没有优劣,只有匹配。Bitcask 把"简单"这件事做到了极致,代价是把"有序"这件事彻底放弃了。

结论

Bitcask 的核心就三句话:

写入是追加,删除是墓碑;内存只存 key → 偏移;恢复时按文件顺序重放,merge 时保留最新版本。

它的价值不只是"能当 KV 用",而是展示了存储引擎设计里的一条重要路径:如果一个场景不需要有序性,那么放弃排序能换来的简单和性能,是惊人的。 下一篇我们会看到另一条路径——既要有序,又要近似——那就要请出 HNSW 了。