内存索引与日志结构存储

Bitcask:所有写都是追加

前三课攒齐了零件:三条 IO 通路、带 crc 的记录格式、WAL 和恢复。这一课把它们组装成完整引擎。 组装方案选 Bitcask 模型 —— Riak 用了十几年的经典设计,结构简单到一页纸讲完, 却和 Weka 元数据层「日志结构 + 内存索引」的思路同源,是它的迷你原型。

核心决定只有一个:数据文件就是日志,所有写都是追加。上一课 WAL 和数据是两份, Bitcask 干脆合并 —— 追加的记录本身就是数据的最终归宿,不再有第二次落盘:

• 写路径:put/delete 编码成记录,追加到当前活跃数据文件,group commit fsync,完事
• 内存索引:HashMap,key → 这条记录在哪个文件、什么偏移、多长
• 读路径:查索引,一次定点读,验 crc,返回 —— 任何 key 最多一次盘 IO
• 文件写到上限(比如 256 MiB)就关闭封存,换新文件继续;旧文件从此只读

use std::collections::HashMap;

/// 索引项:值住在哪
#[derive(Clone, Copy)]
pub struct ValueLoc {
    pub file_id: u32,
    pub offset: u64,
    pub len: u32,
}

pub struct KvEngine {
    index: HashMap<Vec<u8>, ValueLoc>,
    active: DataFile,            // 唯一可追加的文件
    sealed: Vec<DataFile>,       // 已封存,只读
    dir: std::path::PathBuf,
}

delete 怎么办?追加一条墓碑记录(tombstone):内容就是「这个 key 死了」。 索引里删掉,盘上的旧值先不管 —— 日志结构里没有原地删除,只有「新的盖旧的」。

为什么这个模型对 SSD 特别友好?想想 L2 预告过的 FTL:SSD 内部本来就不能原地改写, 所有「覆盖写」都被固件翻译成「写新页、旧页标废、后台擦除」。日志结构等于把 IO 模式 调成了 SSD 固件最喜欢的样子 —— 纯顺序写,写放大最小,也没有随机写把 FTL 的 GC 逼疯。 你运维时看到过 SSD「越用越慢、稳态性能腰斩」的曲线,随机小写就是主犯。

启动重建与 hint 文件

内存索引断电即失,启动时要从数据文件重建:按 file_id 从旧到新,逐文件顺序扫描, 每条合法记录更新一次索引 —— 后扫到的自然覆盖先扫到的,墓碑则删索引项。 活跃文件的尾部可能有 torn write,用上一课的截断逻辑处理;封存文件扫出坏记录则完全不同 —— 它们早就 fsync 过,坏了就是真损坏,要报错而不是静默截断。同一个 crc 失败, 在不同上下文里含义天差地别,这是引擎必须分清的事。

重建的代价是全量读一遍数据。100 GiB 数据、2 GB/s 的顺序读,启动要 50 秒 —— 对比你运维数据库时「crash recovery 进行中,业务干等」的煎熬,这个账必须优化。 Bitcask 的答案是 hint 文件:封存一个数据文件时,顺手把它的索引摘要 (key、file_id、offset、len,不含 value)写成旁边的 hint 文件。启动时优先读 hint, 体积通常是数据文件的百分之一以下,重建速度快两个数量级。hint 丢了、坏了怎么办? 无所谓 —— 它是纯缓存,验 crc 不过就扔掉,退回扫数据文件重建。 可以随时丢弃重建的东西,损坏就不是事故,这个原则能省掉一大堆一致性设计。

空间放大与 GC 触发时机

追加写的账单后置:同一个 key 写 10 次,盘上躺着 10 份,9 份是死的;delete 更讽刺 —— 盘上反而多了一条墓碑。死数据占的空间与活数据之比叫空间放大, 日志结构存储的宿命,RocksDB、Weka 乃至 SSD 固件内部,全都逃不掉,只能靠 GC 定期收尸。

GC 的动作:挑死数据比例高的封存文件,把其中还活着的记录拷进新文件,旧文件整个删掉。 「活着」的判定很便宜 —— 拿记录的 key 查内存索引,索引指向的位置就是这条记录,才算活。

什么时候触发?给每个封存文件记两个数:总记录数和死记录数(索引被覆盖/删除时顺手加一), 死亡率超过阈值(比如 40%)就入队。两条运维直觉要带进来:

• 限速。GC 是纯内部 IO,和前台写抢同一块盘。不限速的 GC 就是你恨过的 「RAID 重建把业务打死」现场重演 —— 给 GC 加个简单的令牌桶,比如上限 100 MiB/s。
• 别追求零死数据。死亡率 40% 才回收,意味着稳态下浪费约三分之一空间 —— 这是故意的。 阈值调到 10%,GC 就要频繁搬运大量还活着的数据,写放大换空间放大,通常更亏。 容量便宜,盘的写寿命和前台延迟贵。

GC 的原子性:崩在中间怎么办

GC 是「拷贝、切换、删除」三步,崩溃可能落在任何两步之间。设计好坏的分水岭就在这:

/// GC 一个封存文件。崩在任何一行,引擎都不丢数据 —— 逐行推演过。
fn gc_one_file(&mut self, victim_id: u32) -> Result<(), StoreError> {
    let mut out = DataFile::create(self.dir.join(format!("gc-{victim_id}.tmp")))?;
    let mut moved: Vec<(Vec<u8>, ValueLoc)> = Vec::new();

    for rec in self.scan_file(victim_id)? {
        // 只搬还活着的:索引仍指向 victim 里这个位置
        let alive = self
            .index
            .get(&rec.key)
            .is_some_and(|loc| loc.file_id == victim_id && loc.offset == rec.offset);
        if alive {
            let new_loc = out.append(&rec)?;
            moved.push((rec.key, new_loc));
        }
    }
    out.sync()?;                                  // ① 新文件先落稳
    let final_path = self.dir.join(format!("data-{}.seal", out.id()));
    std::fs::rename(out.path(), &final_path)?;    // ② rename 原子转正
    fsync_dir(&self.dir)?;                        // ③ 目录项持久化
    for (key, loc) in moved {
        self.index.insert(key, loc);              // ④ 内存索引切换
    }
    std::fs::remove_file(self.file_path(victim_id))?; // ⑤ 最后才删旧文件
    Ok(())
}

逐段推演崩溃点 —— 这个练习你以后每写一段落盘代码都要做一遍:

• 崩在 ① 之前或 ①② 之间:留下个 .tmp 垃圾文件,启动时按扩展名清掉,数据无损
• 崩在 ②③④ 之间:新旧两份数据并存。冗余无害 —— 重建索引时同一 key 出现两份, 取哪份内容都一样;下轮 GC 会把旧的收走
• 崩在 ⑤ 之前:同上,还是双份并存
• 顺序不能换:先删旧文件再 fsync 新文件,崩在中间就是真丢数据。 「先立新、再拆旧」,和你做存储迁移时的割接纪律一字不差

接口冻结:后面五个阶段都靠它

引擎完工,最后一件事不是写代码,是签字画押。从 L2 开始,压测工具、分布式层、 文件系统层全部构建在这层 API 之上 —— 接口再改,返工是乘法级的。冻结的内容:

/// forge-store 对外的全部承诺。L2 起视为冻结,改动需走设计评审。
pub trait BlobStore {
    /// 返回 Ok 即持久:此后任何崩溃,get 都能读回这个值
    fn put(&mut self, key: &[u8], value: &[u8]) -> Result<(), StoreError>;
    /// Ok(None) 表示 key 不存在;数据损坏必须返回 Err,绝不返回脏数据
    fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>, StoreError>;
    /// 返回 Ok 即持久:此后任何崩溃,get 都返回 Ok(None)
    fn delete(&mut self, key: &[u8]) -> Result<(), StoreError>;
}

注意冻结的重点不是三个函数签名,是注释里那三句语义承诺 —— put 返回即持久、 损坏必报错、delete 返回即永别。L3 的副本协议、L5 的模拟测试,验的全是这三句话。 接口是签名加语义,只对签名编程的下场你运维时见过:文档说幂等实际不幂等的 API,坑哭一片。

在 forge-store crate 里实现 KvEngine,把已有的 wal 记录格式、crc 校验、bitmap 经验组装成 Bitcask 风格引擎:

1. 数据文件即日志:put/delete 编码为带 len/seq/crc 头的记录追加写入,group commit fsync;活跃文件超过 256 MiB 即封存换新,文件名 data-{file_id}.seal,活跃文件 data-{file_id}.active;
2. 内存索引 HashMap,值为 ValueLoc(file_id, offset, len);delete 写墓碑记录并从索引移除;
3. 封存文件时生成 hint 文件(key 与 ValueLoc 的列表,带整体 crc);启动重建:优先读 hint,hint 缺失或 crc 失败则扫数据文件;活跃文件尾部损坏按 WAL 规则截断,封存文件损坏必须报错;
4. GC:按文件死亡率超过 40% 触发,严格按「fsync 新文件、rename 转正、fsync 目录、更新索引、删旧文件」顺序;启动时清理遗留 .tmp 文件;
5. KvEngine 实现 trait BlobStore;生产路径零 unwrap;
6. 测试:万条随机 put/delete 后关闭重开,全量对拍;删除 hint 后重启结果不变;GC 后数据完整且盘占用下降;用一个可注入"在第 N 步后 panic"的钩子,分别模拟崩在 GC 五个步骤之间,重启后全量对拍。

跑 cargo test -p forge-store 和 cargo clippy,贴结果。

小结

• Bitcask = 数据文件即日志 + 内存 HashMap 索引:写永远顺序追加,读最多一次定点 IO,SSD 最喜欢的模式
• 启动重建靠扫文件,hint 文件把它加速两个数量级;hint 是可丢弃的缓存,坏了重建,不算事故
• 空间放大是追加写的宿命:死亡率阈值触发 GC,限速防打死前台,别追求零浪费
• GC 原子性五步曲:fsync 新 → rename → fsync 目录 → 切索引 → 删旧;先立新再拆旧
• 接口冻结冻的是语义承诺:put 返回即持久、损坏必报错 —— 后面五个阶段全押在这三句话上
• 引擎齐活,下一课上刑场:kill -9 一万次,见真章