LevelDB 源码阅读：MemTable 刷盘与 SSTable 格式

MemTable 那篇停在了 LSM 写路径的终点：一个 Put/Delete 变成了 arena 打包、带版本号、按跳表有序的记录。本篇讲这记录堆积之后发生的事——活跃 memtable 写满、LevelDB 必须把它落盘成 SSTable（Sorted String Table），以及它在磁盘上究竟长什么样。

这是你已经读过的「内存三件套」与后续磁盘结构之间的桥梁：

→ LevelDB 源码阅读：Arena 区域分配器 → LevelDB 源码阅读：SkipList 索引 → LevelDB 源码阅读：MemTable

LSM 主线继续推进：MemTable → WAL (log) → SSTable (table/block) → Compaction (version_set)。本篇覆盖 MemTable → SSTable 这一步，以及 SSTable 本身的形态。

1. 为什么 memtable 是「不可变」的——双缓冲交接

memtable 并非天生不可变。正在被写入的那张是可变的（mem_）；正在被刷盘的那张被冻结成 imm_（immutable）。冻结发生在 MakeRoomForWrite（db/db_impl.cc:1396-1399）：

imm_ = mem_;                                       // 把活跃表「冻结」
has_imm_.store(true, std::memory_order_release);
mem_ = new MemTable(internal_comparator_);          // 立刻开一张新表接新写入
mem_->Ref();

核心动机是让读写互不阻塞：

1. 刷盘是慢操作，若直接在 mem_ 上刷，写路径会被卡住整整一次刷盘。
2. 改用「切换」：mem_ 原子交接给 imm_（只读快照），立刻 new 一张干净 mem_ 给前台继续写。切换只是指针赋值，几乎零成本。
3. 此后前台写进新 mem_（不再和刷盘抢锁）；后台慢慢把只读的 imm_ 扫出来写 SSTable。
4. 因 imm_ 刷盘期间绝不被修改，后台读它无需和前台抢锁——这正是它叫 immutable 的原因。
5. CompactMemTable 刷完，imm_ = nullptr，一轮交接结束；mem_ 再满则再来一轮。

类比：把当前这叠纸「冻结」交给打印机去印，同时你在另一叠新纸上继续写，两件事并行不耽误。

2. 一个并发细节：background_compaction_scheduled_ 不是 atomic

db/db_impl.h 里两个相邻的标志看起来像，类型却不同：

std::atomic<bool> shutting_down_ GUARDED_BY(mutex_);   // 约 175 行
bool background_compaction_scheduled_ GUARDED_BY(mutex_); // 约 196 行

background_compaction_scheduled_ 是 mutex_ 下的普通 bool，它的每一次读写都已在持锁状态下进行：

• MaybeScheduleCompaction() 标注了 EXCLUSIVE_LOCKS_REQUIRED(mutex_)，开头 mutex_.AssertHeld()，函数内读+写该标志。
• BackgroundCall() 全程持锁，末尾设置 background_compaction_scheduled_ = false;。
• ~DBImpl / TEST_CompactMemTable 只在先取锁后才 while (background_compaction_scheduled_) Wait();。

既然互斥锁已经把并发访问串行化（且 unlock/lock 自带 release/acquire 语义），再做成 atomic 既不会更安全，反而增加开销与噪音。

反观 shutting_down_ 之所以是 atomic，是因为它刻意与 mutex 解耦——它是后台长循环里反复轮询的「立即停」信号（如 DoCompactionWork 中 while (input->Valid() && !shutting_down_.load(...))），若每次都抢锁太重。通用法则：能用 GUARDED_BY(mutex_) 管住的普通变量就用普通变量；只有「需在持锁之外也能安全读写」的共享状态才升级成 atomic。

3. 后台 compaction 入口：BackgroundCompaction()（db_impl.cc:708-787）

由 BackgroundCall() 在持锁状态下调用。做两类事：

if (imm_ != nullptr) {
  CompactMemTable();   // 最高优先级：先刷冻结的 memtable
  return;
}

imm_ 存在就优先把它落盘（否则前台写会卡在等 immutable 清空），做完直接返回。否则挑选要 compact 的对象：

• 手动：用户 CompactRange() / 测试接口触发的 versions_->CompactRange(...)。
• 自动：versions_->PickCompaction() 挑 write-amplification 最差的层。

两者都返回 Compaction* c，三种结局：

• c == nullptr：没东西要压。
• Trivial Move（真）：单文件且下一层无 key 重叠——LogAndApply 一个 RemoveFile+AddFile 写进 MANIFEST，「挪」到下一层，几乎零 I/O。
• 真正合并：DoCompactionWork 归并多个输入、丢弃被覆盖/墓碑 key、写出新 SSTable，再 CleanupCompaction / ReleaseInputs / RemoveObsoleteFiles。

注意 LogAndApply / DoCompactionWork 内部会临时释放 mutex_，让前台不被长时间卡住，返回时再持锁，与 caller 的 MutexLock 衔接。

env_->Schedule(BGWork)
  → BGWork → BackgroundCall()          // 持锁；background_compaction_scheduled_ = true
      → BackgroundCompaction()          // 本段
          ├─ imm_ 有 → CompactMemTable()  刷盘
          └─ 否则 PickCompaction / CompactRange
                ├─ TrivialMove → LogAndApply（挪文件）
                └─ 否则 DoCompactionWork（归并重写）
      → MaybeScheduleCompaction()       // 还要压就再排
      → background_compaction_scheduled_ = false

4. CompactMemTable()：冻结 memtable → SSTable（db_impl.cc:549-580）

由后台线程持锁调用，作用是把 imm_ 刷成磁盘上的 L0（或更深）SSTable：

1. assert(imm_ != nullptr)；取当前版本 base = versions_->current() 并 Ref()。
2. WriteLevel0Table(imm_, &edit, base)——核心，把 imm_ 写成 SSTable，并填好 edit（记录新增了哪个文件）。
3. 刷盘中途若 shutting_down_ 触发，记错（库要没了）。
4. 成功后提交元数据：edit.SetLogNumber(logfile_number_)（旧 WAL 从此可丢弃），versions_->LogAndApply(&edit, &mutex_) 写进 MANIFEST 并切换到新 Version（内部临时放锁）。
5. 提交成功：imm_->Unref() → imm_ = nullptr → has_imm_.store(false)（前台轮询用的 atomic）→ RemoveObsoleteFiles()。失败则 RecordBackgroundError。

5. WriteLevel0Table + BuildTable：memtable → SSTable（db_impl.cc:505-547, builder.cc:17-72）

5.1 WriteLevel0Table 流程

• ① 申请文件号：meta.number = versions_->NewFileNumber()（SSTable 文件名即此号）。
• ② pending_outputs_ 占坑：登记「正在生成中」的文件号，防并发 RemoveObsoleteFiles 误删未写完的文件；进插出删。
• ③ 有序迭代器：mem->NewIterator() 返回跳表迭代器。因跳表按 InternalKeyComparator 有序，吐出的 (key, value) 严格递增。
• ④⑤ 放锁刷盘（最重要）：mutex_.Unlock() → BuildTable(...)（真写磁盘）→ mutex_.Lock()。这正是 imm_ 要冻结的原因——刷盘与前台写入并发。
• 选层：默认 level 0；若 meta.file_size>0 且 base!=nullptr，PickLevelForMemTableOutput 可能下沉到 L1/L2；最后 edit->AddFile(level, ...) 交给 LogAndApply 提交。

5.2 BuildTable：怎么 dump（builder.cc:17-72）

• iter->SeekToFirst() 从最小 key 开始。
• 建物理文件 TableFileName(dbname, meta->number)，new TableBuilder。
• meta->smallest.DecodeFrom(iter->key())（首 key）；循环 builder->Add(key, value) 顺序写入；meta->largest.DecodeFrom(key)（末 key）。
• builder->Finish() 收尾写出 index/footer；file->Sync() + file->Close() 落盘；通过 table_cache 打开验证。
• meta->smallest/largest 是文件首尾 internal_key，后续选层和读路径「该查哪些文件」都靠这两个边界。

一句话：顺序扫 memtable → TableBuilder 按块写出 SSTable → 记录首尾 key 与大小。memtable 已有序，无需再排序。

5.3 PickLevelForMemTableOutput：新文件落哪层（version_set.cc:470-495）

memtable 刷盘不总进 L0，无冲突时尽量下沉以减少 L0 拥堵与未来 compaction 量：

• 若新文件与 L0 重叠（L0 文件间 key 范围允许重叠）→ 只能放 L0，返回 0。
• 否则从 L0 往下试探（level < config::kMaxMemCompactLevel，默认 2）：
  • level+1 重叠 → 停在当前层；
  • 检查 level+2（「爷爷层」）重叠总字节，超过 MaxGrandParentOverlapBytes → 停（防未来读放大爆炸）；
  • 否则 level++。
• 返回最终 level（通常 0/1/2）。

WriteLevel0Table(imm_, edit, base)
 ├ 申请文件号、pending_outputs_ 占坑
 ├ 拿 memtable 有序迭代器
 ├ Unlock → BuildTable：顺序扫 → TableBuilder 写 SSTable（记 smallest/largest、Sync） → Lock
 ├ PickLevelForMemTableOutput：L0 不重叠就尽量下沉 L1/L2
 └ edit->AddFile(level, ...) → 交给 LogAndApply 提交 MANIFEST

6. SSTable 磁盘格式（TableBuilder / BlockBuilder）

6.1 文件整体布局（footer 在最后）

┌─────────────────────────────────────────────┐
│  data block 0  (block_data + type + crc)     │  ← 真正的 kv 数据
│  data block 1  (block_data + type + crc)     │
│  ...                                          │
│  filter block   (布隆过滤器数据，可选)        │
│  metaindex block (指向 filter block 的位置)   │
│  index block    (每块「最短分隔键 + 位置」)    │  ← 定位 data block
│  footer         (metaindex_handle, index_handle, magic) │ ← 固定大小，读时先读它
└─────────────────────────────────────────────┘

读时先读固定大小 footer 拿两个 handle，再沿索引逐层定位到具体 data block。

6.2 Data Block 内部：前缀压缩（block_builder.cc）

单个 entry 格式：

shared_bytes   : varint32   // 与上一个 key 共享的前缀长度
unshared_bytes : varint32   // 本 key 独有部分长度
value_length   : varint32
key_delta      : char[unshared_bytes]   // 只存「不共享」的后缀
value          : char[value_length]

BlockBuilder::Add 和上一个 key 比公共前缀 shared，只存后缀 key[shared..]；value 整段存。shared 永远与紧邻上一个 key比，解码须顺序扫拼接。

举例（restart_interval 设大，5 个有序 key）：

序	(shared, non_shared)	落盘 key 部分	还原
①	(0, 9)	"the apple"	首 key，直接
②	(8, 5)	"ication"	"the apple" 前 8 + "ication" = "the application"
③	(8, 1)	"y"	"the application" 前 8 + "y" = "the apply"
④	(4, 6)	"banana"	"the apply" 前 4 + "banana" = "the banana"
⑤	(7, 2)	"nd"	"the banana" 前 7 + "nd" = "the band"

原 50 字节 key → 压缩后 23 字节（省一半多，value 不动）。

Restart point：每 block_restart_interval（默认 16）个 key 强制重置（shared=0 整段存），并把偏移记进 restarts_[]。作用：

• 块被切成段，每段最多 16 key；
• 查找先在 restarts_[] 上二分定位段，再从段起点顺序拼（最多 16 次）；
• Finish() 把 restarts_[] 与数量追加到块尾部。

6.3 切块与索引：延迟写 + 最短分隔键（table_builder.cc）

Add 每来一个 kv 塞进 data_block，满 block_size（默认 ~4KB）就 Flush。Flush 落盘后触发索引延迟技巧（注释 ~50-59 行）：

if (r->pending_index_entry) {
  r->options.comparator->FindShortestSeparator(&r->last_key, key); // 算最短分隔键
  r->pending_handle.EncodeTo(&handle_encoding);
  r->index_block.Add(r->last_key, Slice(handle_encoding));          // (分隔键, 上块 handle)
  r->pending_index_entry = false;
}

• 写第 N 块时不立刻写索引项；等看到第 N+1 块第一个 key，才用 FindShortestSeparator 算「≥ 第 N 块所有 key、< 第 N+1 块所有 key」的最短分隔键当索引键。
• 这样索引键比真实 key 更短，索引更小，二分仍正确。
• pending_handle 是刚落盘块的 BlockHandle（offset+size）。

6.4 每块压缩与 trailer（WriteBlock / WriteRawBlock）

落盘前可选 Snappy/Zstd 压缩，仅压缩收益 >12.5% 才用（否则原样）。每个 block 物理格式：

[block_data][type:1B][crc:4B]

trailer[0]=type；CRC 覆盖数据+type（crc32c::Mask），读时校验防损坏。BlockHandle 记 offset（文件内位置）+ size（仅 block_data，不含 trailer），varint 编码，是内部定位任意 block 的通用句柄。

6.5 Finish()：filter / metaindex / index / footer（213-268）

• Flush() 落最后一块。
• filter block：Add 时把每个 key 加进布隆过滤器；读时先查，若「肯定不存在」免找 data block。
• metaindex block：小索引，记录 "filter.<策略名> -> filter_block 位置"。
• index block：把最后一块的 pending 索引项用 FindShortSuccessor 收尾后写出。
• footer：固定长度（含魔数），读 SSTable 的入口，存 metaindex_handle 与 index_handle。

读路径（下一篇）：阅读 LevelDB：读路径 会讲 Get 如何从顶向下走完这些结构——snapshot 可见性、放锁前 Ref() 这套动作、Version::Get 在 L0/L1+ 的遍历，以及 TableCache 这座桥。

6.6 FindShortestSeparator 怎么算最短分隔键

默认实现：找 start 与 limit 第一个不同字节，把 start 该字节 +1 并截断到该位，得 sep 满足 start < sep < limit。

注释例子：第 N 块末键 start="the quick brown fox"，第 N+1 块首键 limit="the who"：

• 第 4 位不同 'q'(0x71) vs 'w'(0x77)；'q'+1='r'，截断到第 5 位 → "the r"。
• 验证："the r" > "the quick brown fox"（第 4 位 'r'>'q'）✓；"the r" < "the who"（第 4 位 'r'<'w'）✓。
• 第 N 块索引项写成 ("the r", handle_N)，"the r" 比真实 key 短得多。

查找正确性：分隔键 sep_N 满足 last_N < sep_N < first_{N+1}。二分找「第一个 ≥ 目标」的索引键：

• 目标在第 N 块内 ⇔ first_N ≤ 目标 ≤ last_N；因 sep_N ≥ last_N ≥ 目标 且 sep_{N-1} < first_N ≤ 目标，第一个 ≥ 目标 的正是 sep_N → 去块 N ✓。
• 例：查 "the queen"（< "the quick brown fox"，在块 N）→ "the r" > "the queen" → 去块 N ✓。
• 例：查 "the rabbit"（落在两块空隙，谁都不存）→ "the r" 是其前缀故 < "the rabbit" 被跳过，去块 N+1，块内最小 "the who" > "the rabbit" → 查无 ✓。

好处：索引块常驻内存/频繁读，越短越好；大量 key 共享长前缀时（同 user_key 不同版本、同业务前缀）索引体积显著缩小。

7. 与「内存三件套」的关联

• BuildTable 顺序扫描的那个有序迭代器，正是 MemTable 里的跳表——所以无需再排序，数据本就按 InternalKeyComparator 有序。
• 被冻结的 imm_，正是第 1 节那个双缓冲、只读快照——它由 Arena/SkipList「节点绝不单独释放」的设计才得以成立。
• 每个 internal_key 里打包的版本号/seq（见 MemTable 篇），正是后续 compaction 能丢弃被覆盖值与墓碑的依据。

8. 速记表

主题	要点
immutable memtable	双缓冲切换：imm_=mem_; new mem_；冻结后只读，后台刷盘与前台写并发、无需抢锁
background_compaction_scheduled_	永远持锁访问 → 普通 bool + GUARDED_BY；shutting_down_ 需跨线程轮询 → atomic
BackgroundCompaction	持锁；先 flush imm_，否则 PickCompaction/TrivialMove/真正归并
CompactMemTable	imm_ dump 成 SSTable → LogAndApply 提交 MANIFEST（旧 WAL 可弃）→ 清 imm_、has_imm_=false
WriteLevel0Table	放锁刷盘（并发关键）；pending_outputs_ 防误删；智能选层 L0/L1/L2
BuildTable	顺序扫有序 memtable → TableBuilder 写 SSTable，记录 smallest/largest
前缀压缩	每 key 只存与上一 key 不同的后缀；每 16 key 一个 restart point（完整 key + 二分）
索引延迟写	第 N 块索引项等第 N+1 块首 key，用最短分隔键，索引更短且二分正确
每块 trailer	[data][type:1B][crc:4B]；CRC 覆盖 data + type
SSTable 布局	data blocks + filter + metaindex + index + footer（固定，读入口）