存储算法 #08：Bitcask

Bitcask 通过追加写日志 + 全量内存索引（KeyDir）实现读 O(1)、写 O(1) 的高性能 KV 存储，是 Riak 默认存储引擎，也被 Erlang 系系统广泛采用。

相关文章：WAL（Write-Ahead Log） · Redo 与 Undo Log

目录

核心思想

问题背景：传统 B-Tree 存储引擎在高并发写入时面临随机 I/O 瓶颈：每次更新需要找到数据页并原地修改，机械磁盘的随机写性能极低（约 100-200 IOPS）。

朴素方案：原地更新（B-Tree 方式）
  写 key=A, value=hello
    → 在磁盘中找到 A 所在的数据页（随机读）
    → 修改该页（随机写）
  机械磁盘随机写：约 100 IOPS → 高并发写入时严重瓶颈

Bitcask 方案：追加写 + 内存索引
  所有写入（包括更新、删除）追加到 Active Data File 末尾（顺序写，最优模式）
  内存中维护 KeyDir（HashMap），记录每个 key 最新版本在磁盘的精确位置
  读取时：KeyDir 查到位置 → 1 次随机读 → 返回 value

核心设计原则：
  1. Active Data File 只追加，绝不原地修改（Append-Only）
  2. 同一时刻只有一个 Active File 接受写入（单线程写，无竞争）
  3. 所有 key 的最新位置必须全部在内存 KeyDir 中（硬约束）
  4. 旧版本数据通过 Compaction 周期性清理

数据文件格式

每条磁盘记录（Record）的精确字节布局：

Record {
    crc        uint32    // 4 字节：CRC32 校验（覆盖 timestamp+key_size+value_size+key+value）
    timestamp  uint32    // 4 字节：Unix 时间戳（秒级），用于 TTL 和版本判断
    key_size   uint16    // 2 字节：key 的字节长度（最大 65535 字节）
    value_size uint32    // 4 字节：value 的字节长度（最大 4GB，实际受内存限制）
    key        bytes     // key_size 字节：key 内容
    value      bytes     // value_size 字节：value 内容
}

header 固定长度 = 4 + 4 + 2 + 4 = 14 字节
每条记录总长度 = 14 + key_size + value_size

特殊 tombstone 记录（表示删除）：
    value = TOMBSTONE_MAGIC（固定魔数，如 0xDEADBEEF 或特殊字节序列）
    value_size = TOMBSTONE_SIZE（固定值，如 4）
    含义：key 已被删除，Compaction 时跳过该 key

文件管理规则：

Active Data File：当前接受写入的文件，file_id 为最大值
Immutable Data File：已关闭的旧文件，只读不写
  - 当 Active File 超过阈值（如 1GB）→ 关闭为 Immutable File
  - 创建新 Active File（file_id 递增）
文件命名：{file_id}.data（如 0001.data、0002.data）
file_id 规则：单调递增整数，保证 file_id 越大越新

KeyDir 结构

KeyDir 是驻留内存的全量索引，核心数据结构：

KeyDir = HashMap<key: bytes, entry: KeyDirEntry>

KeyDirEntry {
    file_id    uint32    // 数据所在文件的 ID
    value_sz   uint32    // value 的字节长度（用于 pread，避免多读）
    value_pos  uint64    // value 在文件中的字节偏移量（文件起点=0）
    timestamp  uint32    // 写入时间戳（用于 TTL 过期判断）
}

内存占用估算：
    每个 entry 固定约 20 字节（4+4+8+4 字节）
    key 本身按实际长度存储
    1000 万个 key，平均 key=20 字节 → 约 400MB 内存
    → key 数量越多，内存占用越高，这是 Bitcask 的核心约束

关键不变量（Invariant）：
    KeyDir[k].value_pos 始终指向磁盘上 k 的最新版本
    如果 k 已被删除，KeyDir 中不存在 k 的条目

get 操作

时间复杂度：O(1) 内存查找 + 1 次随机 I/O

函数 get(key):
    // 步骤1：查内存索引（O(1) 哈希查找）
    entry = KeyDir.get(key)
    if entry == nil:
        return NOT_FOUND           // key 不存在或已被删除

    // 步骤2：检查 TTL（可选，如果支持过期）
    if entry.timestamp + TTL < now():
        KeyDir.remove(key)         // 惰性删除过期 key
        return NOT_FOUND

    // 步骤3：打开对应数据文件（通常已缓存 fd）
    fd = fileCache.open(entry.file_id)   // 从 fd 缓存获取，避免重复 open()

    // 步骤4：精确定位读取（1 次随机 I/O）
    raw = pread(fd, offset=entry.value_pos, length=entry.value_sz)
    //   pread 是 POSIX 接口：在指定偏移读取，不改变文件位置指针
    //   只读 value 部分，不读 header

    // 步骤5：校验（可选，从偏移往前 14 字节读 header 验证 CRC）
    // 简化版本跳过校验，生产实现通常读整条记录验证 CRC

    return raw                     // 返回原始 value 字节

put 操作

时间复杂度：O(1) 追加写 + O(1) 哈希更新

函数 put(key, value):
    // 步骤1：构造记录
    ts = now_unix_seconds()
    record = Record {
        crc        = crc32(ts ++ key_size ++ value_size ++ key ++ value),
        timestamp  = ts,
        key_size   = len(key),
        value_size = len(value),
        key        = key,
        value      = value,
    }

    // 步骤2：检查 Active File 容量，必要时轮转
    if activeFile.size + recordSize > MAX_FILE_SIZE:
        activeFile.close()                  // 关闭当前 Active File（变为 Immutable）
        activeFile = openNewFile(nextFileId())   // 创建新 Active File

    // 步骤3：追加写入 Active File（顺序写，O(1)）
    write_pos = activeFile.currentOffset   // 记录写入前的偏移量
    activeFile.append(record)              // 追加到文件末尾
    //   value 在文件中的偏移 = write_pos + 14 + key_size
    value_pos = write_pos + HEADER_SIZE + len(key)

    // 步骤4：更新内存 KeyDir（O(1) 哈希写入）
    KeyDir[key] = KeyDirEntry {
        file_id   = activeFile.id,
        value_sz  = len(value),
        value_pos = value_pos,
        timestamp = ts,
    }
    // 旧版本的磁盘记录仍然存在，等待 Compaction 清理
    // 旧的 KeyDir 条目被覆盖，旧磁盘位置成为"孤儿数据"

    return OK

delete 操作

函数 delete(key):
    // 步骤1：检查 key 是否存在
    if KeyDir.get(key) == nil:
        return NOT_FOUND           // 已经不存在，幂等操作

    // 步骤2：写入 tombstone 记录（追加，不修改旧数据）
    ts = now_unix_seconds()
    tombstone = Record {
        crc        = crc32(ts ++ key_size ++ TOMBSTONE_SIZE ++ key ++ TOMBSTONE_MAGIC),
        timestamp  = ts,
        key_size   = len(key),
        value_size = TOMBSTONE_SIZE,     // 固定魔数大小
        key        = key,
        value      = TOMBSTONE_MAGIC,    // 特殊删除标记
    }
    activeFile.append(tombstone)

    // 步骤3：从 KeyDir 移除（立即生效，后续 get 返回 NOT_FOUND）
    KeyDir.remove(key)

    return OK

注意：
  tombstone 记录只是在磁盘上留下"已删除"的标记
  Compaction 时扫描到 tombstone → 跳过该 key，不写入新文件
  tombstone 本身在 Compaction 后也会被删除（不写入新 Compact File）

Compaction 合并

目的：清理旧版本和 tombstone，回收磁盘空间，同时生成 Hint File 加速下次启动。

函数 Compaction(immutableFiles):
    // 前提：只对 Immutable Data File 做 Compaction，Active File 不参与
    // 原因：Active File 仍在写入，不能被替换

    latestValues = HashMap<key, Record>()  // 临时存储每个 key 的最新记录

    // 步骤1：扫描所有 Immutable File，收集每个 key 的最新版本
    for each file in sort(immutableFiles, by=file_id, order=ASC):
        // file_id 越大越新，后扫描的记录覆盖先扫描的
        for each record in file.readAllRecords():
            if not validCRC(record):
                skip                       // 跳过损坏记录
            if record.value == TOMBSTONE_MAGIC:
                latestValues.remove(record.key)   // 删除标记，移除
            else:
                latestValues[record.key] = record // 覆盖旧版本

    // 步骤2：生成新的 Compact File + Hint File
    compactFile = openNewFile("compact.data")
    hintFile    = openNewFile("compact.hint")

    for each (key, record) in latestValues:
        // 写入 Compact File（与普通数据文件格式相同）
        write_pos = compactFile.currentOffset
        compactFile.append(record)
        value_pos = write_pos + HEADER_SIZE + len(key)

        // 写入 Hint File（只含 key 和位置信息，不含 value，体积小）
        hint = HintRecord {
            timestamp  = record.timestamp,
            key_size   = len(key),
            value_sz   = record.value_size,
            value_pos  = value_pos,        // 在 Compact File 中的偏移
            key        = key,
        }
        hintFile.append(hint)

    compactFile.close()
    hintFile.close()

    // 步骤3：原子替换旧文件（保证安全性）
    atomicRename(compactFile → "new.data")
    atomicRename(hintFile    → "new.hint")
    deleteOldFiles(immutableFiles)         // 删除被合并的旧文件

    // 步骤4：更新 KeyDir（用 Compact File 中的新位置覆盖）
    for each hint in hintFile.readAll():
        KeyDir[hint.key] = KeyDirEntry {
            file_id   = compactFile.id,
            value_sz  = hint.value_sz,
            value_pos = hint.value_pos,
            timestamp = hint.timestamp,
        }

启动恢复

函数 Startup():
    // 步骤1：扫描数据目录，找到所有 .data 和 .hint 文件
    dataFiles = listFiles("*.data").sortBy(file_id)
    hintFiles = listFiles("*.hint")

    KeyDir = HashMap()  // 重建空的 KeyDir

    // 步骤2：优先从 Hint File 重建（快速路径）
    //   Hint File 只含 key + 位置，不含 value，文件体积远小于 data file
    for each hintFile in hintFiles.sortBy(file_id):
        for each hint in hintFile.readAll():
            KeyDir[hint.key] = KeyDirEntry {
                file_id   = correspondingDataFile(hintFile).id,
                value_sz  = hint.value_sz,
                value_pos = hint.value_pos,
                timestamp = hint.timestamp,
            }

    // 步骤3：对没有对应 Hint File 的数据文件，全扫重建
    //   通常是 Active File（最新的，尚未 Compaction）
    for each dataFile in dataFiles where no hintFile exists:
        offset = 0
        while offset < dataFile.size:
            header = pread(dataFile, offset, HEADER_SIZE)  // 读 14 字节 header
            if not validCRC(readFullRecord(offset)):
                break                                       // CRC 错误，停止（文件末尾可能不完整）

            record = readFullRecord(dataFile, offset)
            value_pos = offset + HEADER_SIZE + record.key_size

            if record.value == TOMBSTONE_MAGIC:
                KeyDir.remove(record.key)
            else:
                // 只有当这条记录比 KeyDir 中已有的更新时才覆盖
                existing = KeyDir.get(record.key)
                if existing == nil or record.timestamp >= existing.timestamp:
                    KeyDir[record.key] = KeyDirEntry {
                        file_id   = dataFile.id,
                        value_sz  = record.value_size,
                        value_pos = value_pos,
                        timestamp = record.timestamp,
                    }
            offset += HEADER_SIZE + record.key_size + record.value_size

    // 步骤4：确定 Active File（file_id 最大的 .data 文件）
    activeFile = openForAppend(max(dataFiles, by=file_id))
    return OK

对比：
    有 Hint File：只读 key + 位置（约等于 KeyDir 序列化），速度极快
    无 Hint File：需全扫所有数据文件（包括 value），速度慢，与数据量成正比
    → Compaction 生成 Hint File 是提升启动速度的关键优化

执行追踪

场景：依次执行 put A、put B、put A（更新）、delete B，然后触发 Compaction。

初始状态：
  ActiveFile = 0001.data（offset=0）
  KeyDir = {}

=== 操作1：put("A", "hello") ===
写入 0001.data offset=0:
  [ crc=0xAA | ts=1000 | key_sz=1 | val_sz=5 | "A" | "hello" ]
  record 总长度 = 14 + 1 + 5 = 20 字节

KeyDir 更新：
  A → {file_id=1, val_sz=5, val_pos=14+1=15, ts=1000}
  （val_pos = 0 + 14 + 1 = 15，即 value 字节在文件中的偏移）

ActiveFile 当前 offset = 20

=== 操作2：put("B", "world") ===
写入 0001.data offset=20:
  [ crc=0xBB | ts=1001 | key_sz=1 | val_sz=5 | "B" | "world" ]
  record 总长度 = 20 字节

KeyDir 更新：
  A → {file_id=1, val_sz=5, val_pos=15, ts=1000}    ← 不变
  B → {file_id=1, val_sz=5, val_pos=20+14+1=35, ts=1001}

ActiveFile 当前 offset = 40

=== 操作3：put("A", "hi") 更新 A ===
写入 0001.data offset=40:
  [ crc=0xCC | ts=1002 | key_sz=1 | val_sz=2 | "A" | "hi" ]
  record 总长度 = 14 + 1 + 2 = 17 字节

KeyDir 更新（覆盖旧条目）：
  A → {file_id=1, val_sz=2, val_pos=40+14+1=55, ts=1002}   ← 指向新位置
  B → {file_id=1, val_sz=5, val_pos=35, ts=1001}

磁盘 0001.data 状态（offset=0..57）：
  [0 ] A=hello（旧版本，KeyDir 已不指向此处，变为孤儿）
  [20] B=world
  [40] A=hi（最新版本，KeyDir 指向此处）

ActiveFile 当前 offset = 57

=== 操作4：delete("B") ===
写入 0001.data offset=57：
  [ crc=0xDD | ts=1003 | key_sz=1 | val_sz=4(TOMBSTONE) | "B" | TOMBSTONE_MAGIC ]
  record 总长度 = 14 + 1 + 4 = 19 字节

KeyDir 更新：
  A → {file_id=1, val_sz=2, val_pos=55, ts=1002}
  B → 已从 KeyDir 移除

ActiveFile 当前 offset = 76

磁盘 0001.data（0..76）：
  [0 ] A=hello（孤儿，旧版本）
  [20] B=world（孤儿，tombstone 标记已删除）
  [40] A=hi（有效）
  [57] B=TOMBSTONE（已删除标记）

=== Compaction（对 0001.data 执行） ===
扫描 0001.data，收集最新版本：
  遇到 A=hello(ts=1000)   → latestValues[A] = {hello, ts=1000}
  遇到 B=world(ts=1001)   → latestValues[B] = {world, ts=1001}
  遇到 A=hi(ts=1002)      → latestValues[A] = {hi, ts=1002}     ← 覆盖旧版本
  遇到 B=TOMBSTONE(ts=1003) → latestValues.remove(B)             ← 删除 B

最终 latestValues = { A → "hi" }

生成 0002.data（Compact File）：
  [0 ] A=hi（只保留最新版本，共 17 字节）

生成 0002.hint（Hint File）：
  [0 ] { ts=1002, key_sz=1, val_sz=2, val_pos=15, key="A" }

原子删除 0001.data，保留 0002.data + 0002.hint

KeyDir 更新：
  A → {file_id=2, val_sz=2, val_pos=15, ts=1002}

磁盘空间：76 字节 → 17 字节（减少 78%）

异常场景

1. Active File 写入中途崩溃

场景：put("A","hello") 执行到一半，仅写入 header 部分，value 未写完，系统崩溃。

磁盘状态：
  [...] [ crc=0xAA | ts=1000 | key_sz=1 | val_sz=5 | "A" | "he" ]（不完整）

恢复时处理：
  读取 header → 发现需要读取 key_size=1, value_size=5 共 6 字节内容
  实际读到只有 2 字节（"he"）→ 文件到达末尾，记录不完整
  → 停止扫描（不完整记录不加入 KeyDir）
  → Active File 的写入位置回退到最后一条完整记录末尾
  → 不完整记录被截断/忽略，事务自动失败（客户端未收到成功响应）

CRC 验证：即使读到完整字节数，也可能因为中途字节翻转导致 CRC 不匹配
  → 同样停止扫描，丢弃损坏记录

2. KeyDir 内存不足

场景：key 数量超过可用内存，无法将全部 key 加载到 KeyDir。

Bitcask 的硬约束：KeyDir 必须全量在内存，这不是可选项。
  如果 KeyDir 放不进内存：
    get(key) 无法在内存中找到位置 → 无法完成 1 次 I/O → 核心设计失效

处理方式（Bitcask 本身不解决此问题）：
  如果 key 数量过大，应切换到 LSM Tree（如 RocksDB）
    → LSM 用 Bloom Filter + Block Index 代替全量内存索引
    → 以牺牲部分读性能（多层 SSTable 查找）换取更低内存占用

适用场景限制：
  Bitcask 适合 key 数量有限、value 体积较大的场景（如：设备 ID → 状态数据）
  不适合 key 数量无限增长的场景（如：用户 URL 点击记录）

3. Compaction 中途崩溃

场景：Compaction 生成 Compact File 到一半，系统崩溃。

崩溃时状态：
  0001.data（旧文件）：完整，仍然存在
  0002.data（新文件）：不完整，只写了一部分

安全性保证（原子替换）：
  Compaction 使用两阶段策略：
    1. 写入新文件（0002.data.tmp）
    2. 全部写完后，原子 rename：0002.data.tmp → 0002.data
    3. 只有 rename 成功后，才删除旧文件 0001.data

  如果在步骤1或2崩溃：
    0002.data.tmp 不完整 → 以 .tmp 后缀存在，启动时忽略
    0001.data 完整存在 → 正常扫描重建 KeyDir
    → 数据零损失，只是没有清理旧文件（浪费一些磁盘空间，下次 Compaction 补做）

  如果在步骤3崩溃（删除旧文件中断）：
    0001.data 和 0002.data 同时存在
    启动时两个文件都扫描，file_id=2 > file_id=1，同一 key 以 file_id 较大者为准
    → KeyDir 最终指向 0002.data 中的最新版本
    → 再次触发 Compaction 删除 0001.data（去重清理）

4. 同一 key 大量更新导致旧数据膨胀

场景：key="counter" 被更新了 100 万次，磁盘上存在 100 万条历史记录（KeyDir 只有 1 条）。

问题：磁盘空间严重浪费，I/O 读写放大。

Compaction 解决：
  扫描所有历史记录，只保留 ts 最大的那条
  其余 999999 条记录在 Compact File 中消失
  磁盘空间恢复正常

但 Compaction 之前的写放大（Write Amplification）：
  每次 put 都写一条完整记录（含 header）
  如果 value 很小（如 4 字节计数器），header(14B) > value(4B)
  → header 开销占主导，空间利用率低
  → 解决方案：将小 value 聚合后批量写入，或使用固定长度 value 格式

Compaction 触发策略：
  - 阈值触发：旧数据占比 > 50%（通过数据文件总大小 vs 有效数据估算）
  - 时间触发：每隔固定时间（如 1 小时）执行一次
  - 手动触发：运维命令

与 LSM Tree 对比

选 Bitcask 的场景：
  - key 数量可控（百万级以内，能放入内存）
  - value 较大（硬件遥测、日志条目、会话状态）
  - 读性能极致要求（不能接受多次 I/O）
  - 写入模式：一次写入，少量读取

选 LSM Tree 的场景：
  - key 数量庞大（数十亿级，内存放不下）
  - 需要范围扫描（按 key 前缀查询）
  - 写入吞吐优先，可接受偶尔多次 I/O
  - 通用数据库场景（OLTP、时序数据）

参考资料

• Sheehy, J. & Smith, D. (2010). Bitcask: A Log-Structured Hash Table for Fast Key/Value Data. Basho Technologies. (原始论文 PDF)
• Riak 官方文档：Bitcask Storage Backend
• 《Designing Data-Intensive Applications》Martin Kleppmann，Chapter 3：Storage and Retrieval
• 《Database Internals》Alex Petrov，Chapter 6：B-Tree Variants & Log-Structured Storage