用 Rust 从零实现 Bitcask:为什么它的写入能比 B+ 树快十倍
上一篇写 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(())
}两个关键点:
- 扫描顺序决定了正确性。 后扫的文件覆盖先扫的条目,所以必须按 ID 升序(也就是写入时间升序)。
- 遇到损坏就停,但只停这一个文件。 后面的文件仍然要扫——因为损坏只可能出现在"正在写的那个文件"的尾部。
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 了。