Bitcask 论文详解

1. 论文背景

Bitcask 最初由 Riak 团队在 2010 年提出，作为 Riak 分布式数据库的底层存储引擎之一。论文非常短（只有 6 页），但提出了一个极其精巧的设计。

论文开头提出了对一个 KV 存储引擎的期望：

1. 读写低延迟
2. 高吞吐量，尤其是随机写入场景
3. 能处理远超内存容量的数据集
4. 崩溃恢复友好，快速恢复且不丢数据
5. 简单的备份和恢复策略
6. 相对简单、易于理解的代码结构

Bitcask 的设计目标就是同时满足以上所有要求。让我们来看看它是怎么做到的。

2. 核心数据模型

Bitcask 的核心思路可以用一句话概括：

这个设计带来了两个关键优势：

• 写入：永远是顺序追加（append-only），不需要随机写磁盘，写入速度接近磁盘顺序写的理论极限。
• 读取：先查内存索引拿到磁盘位置，然后一次精确的磁盘随机读，最多一次 IO。

磁盘上的数据文件

Bitcask 实例就是一个目录，目录中包含多个数据文件（data file）。在任意时刻，只有一个"活跃文件"（active file）接受写入，其余的都是"旧文件"（older file），只读不写。

当活跃文件的大小达到阈值时，它会被关闭变成旧文件，同时创建一个新的活跃文件。

日志记录格式

每条数据写入磁盘时，都编码成一条 LogRecord（日志记录），格式如下：

• CRC32：校验和，用于检测数据是否损坏
• Type：记录类型（正常写入 / 删除标记 / 事务结束标记）
• Key Size / Value Size：Key 和 Value 的长度
• Key / Value：实际的键值数据

3. 内存索引（KeyDir）

论文中把内存索引称为 KeyDir。它是一个哈希表，存储每个 Key 对应的数据在磁盘上的位置信息：

KeyDir: Key → { file_id, offset, size }

• file_id：数据所在的文件编号
• offset：数据在该文件中的起始偏移量
• size：数据记录的总长度

有了 KeyDir，读取流程非常简洁：

1. 根据 Key 在 KeyDir 中查找，得到 (file_id, offset, size)
2. 打开对应的数据文件，在 offset 处读取 size 字节
3. 解码得到 Value，返回

4. 读写流程

写入流程（Put）

1. 将 Key-Value 编码成 LogRecord
2. 追加写入当前活跃文件
3. 更新内存索引（KeyDir），将 Key 映射到新的磁盘位置

注意：如果是覆盖写（Key 已存在），旧数据不会被删除，只是内存索引指向了新位置。旧数据变成"垃圾"，等待 Merge 清理。

读取流程（Get）

1. 在内存索引中查找 Key，获取 (file_id, offset)
2. 根据 file_id 定位到对应的数据文件
3. 在 offset 处读取数据，解码出 Value

删除流程（Delete）

1. 写入一条类型为"删除"的 LogRecord（tombstone）
2. 从内存索引中移除该 Key

5. Merge 合并过程

由于 Bitcask 是追加写入的，覆盖写和删除都不会真正移除旧数据，磁盘上会积累大量"垃圾"数据。Merge（合并）就是用来回收这些空间的。

Merge 的流程：

1. 遍历所有旧数据文件中的每条记录
2. 对每条记录，检查内存索引 —— 如果该 Key 的最新位置指向当前记录，说明它是有效数据
3. 将有效数据写入新的数据文件
4. 同时生成一个 Hint File（索引提示文件），记录每个 Key 在新文件中的位置
5. Merge 完成后，删除旧的数据文件

6. 启动恢复

当 Bitcask 实例启动（或崩溃后重启）时，需要重建内存索引。流程如下：

1. 扫描数据目录，找到所有数据文件，按文件编号排序
2. 如果存在 Hint File，优先从 Hint File 中加载索引（速度快）
3. 对于没有 Hint File 覆盖的数据文件，逐条读取 LogRecord，根据记录内容重建索引
4. 最后一个文件设为活跃文件，继续接受写入

7. Bitcask 的优势与局限

8. 与课程实现的对应关系

了解了论文的设计，我们来看看后续各章与论文概念的对应关系：