内存索引与日志结构存储

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(())
}

逐段推演崩溃点 —— 这个练习你以后每 review 一段落盘代码都要做一遍,而且只需要看得懂步骤顺序, 不需要看得懂语法:

• 崩在 ① 之前或 ①② 之间:留下个 .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,坑哭一片。

目标:把前三课的零件组装成一个完整的 Bitcask 风格 KV 引擎 —— 数据文件即日志、索引全在内存、有加速启动的索引摘要文件、有会限速的 GC。

行为规格:
1. 所有写都是追加:写入与删除都编码成一条带长度、序号、校验和的记录,追加到当前活跃数据文件;多个并发写攒批共用一次刷盘,返回成功即已落盘。删除追加的是墓碑记录,盘上不做原地删除;
2. 活跃文件写到 256 MiB 就封存换新。文件名要带序号,并且活跃与封存用不同后缀(如 .active 与 .seal),让我 ls 一眼就看出哪个正在写;
3. 内存索引记录每个 key 的值在哪个文件、什么偏移、多长;读路径查索引后最多一次定点读盘,验校验和后返回;key 不存在返回「没有」,要和出错区分开;
4. 封存一个文件时顺手写一个索引摘要文件:只含 key 与位置信息、不含 value,整体带一个校验和。启动重建时优先读它;缺失或校验和不对就扔掉、退回扫数据文件重建并顺手重写它 —— 它是纯缓存,坏了不算事故,绝不能因此拒绝启动,更不能让 key 凭空消失;
5. 启动扫描时,活跃文件尾部的损坏按上一课的规则截断(那是崩溃留下的正常现象),而封存文件里的损坏必须报错 —— 它早就刷过盘,坏了就是真损坏。同一个校验和失败,两种上下文两种处理,别混;
6. GC:给每个封存文件记总记录数与死记录数(索引被覆盖或删除时顺手加一),死亡率超过 40% 才回收,不要追求零浪费;判断一条记录是否还活着,就看索引是否仍然指向它所在的文件与偏移;
7. GC 的落盘顺序不许换:先把新文件的数据刷到盘上 → 同目录 rename 转正 → 刷父目录(rename 改的是目录项,目录也是文件)→ 切换内存索引 → 最后才删旧文件。启动时把遗留的临时文件按后缀清掉;
8. GC 是纯内部 IO,必须限速(比如上限 100 MiB/s),不许把前台写入的延迟打崩 —— 我见过 RAID 重建打死业务的现场;
9. 对外只暴露写、读、删三个操作,并且把语义承诺用注释写死:写返回即持久(此后任何崩溃都能读回这个值)、读到损坏必须报错绝不返回脏数据、删返回即永别;
10. 任何预期内的失败都要变成明确的错误返回给调用方,而不是让进程直接崩溃。

交付:实现 + 这几组测试:
- 一万条随机写/删之后关闭重开,逐 key 全量对拍;
- 删掉全部索引摘要文件后重启,结果必须一模一样;
- GC 之后数据完整,且磁盘占用下降;
- 一个能让进程「在 GC 第 N 步之后立刻死掉」的注入开关,在五个步骤之间各制造一次崩溃,重启后全量对拍都要通过。
这个注入开关是本次交付的重点:它必须真的让流程断在两步之间,而不是跑完整个 GC 再退出。(用什么库、模块怎么拆你定,最后告诉我为什么这么选。)

小结

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