【RocksDB 内核机制】MemTable 与 Flush：SkipList 到 L0 SST

第 4 篇 钉住了 WAL + WriteBatch 如何把写持久化并原子进内存。MemTable 是 LSM 写路径的 吸收层：随机写先落内存结构，攒够 write_buffer_size 后 冻结（immutable），由后台 FlushJob 顺序扫描输出 L0 SST。

lsm-tree 第 2 篇 用 C 实现了跳表 MemTable 与 WAL 恢复；本文对照 RocksDB 9.x 生产实现：默认 SkipList MemTableRep、MemTableList 多 immutable 队列、FlushJob 与 BuildTable 的协作。Flush 触发的 write stall 留 第 11 篇；SST 内部 Block 布局留 第 6 篇。

版本锚定：RocksDB 9.x（memtable/skiplist.h、db/flush_job.*、db/memtable_list.*）。实验：reproduce/run_db_bench.sh exp05（write_buffer_size=65536 强制频繁 flush）。

一、MemTable 在 LSM 写路径中的位置

flowchart TB
  W["WriteImpl: InsertInto"] --> AM["Active MemTable<br/>(mutable)"]
  AM -->|"size ≥ write_buffer_size"| SW["SwitchMemtable"]
  SW --> IM["MemTableList<br/>immutable 队列"]
  IM --> FJ["FlushJob (bg thread)"]
  FJ --> SST["L0 *.sst"]
  SST --> VS["VersionSet::LogAndApply"]
  W --> WAL["WAL .log"]

与 WAL 的关系：WAL 保证 进程崩溃 时 MemTable 未 flush 部分可重放；MemTable flush 成功后，对应 WAL 段可在 min_log_number_to_keep 规则下回收（与 MANIFEST 中 log number 联动，见第 6 篇）。

二、SkipList MemTableRep

2.1 为何用跳表

RocksDB 默认 Options::memtable_factory = SkipListFactory()。底层模板 memtable/skiplist.h 继承 LevelDB 设计：

• 写：外部同步（write thread 或 DB mutex）；插入 \(O(\log n)\)；
• 读：无内部锁；依赖 节点链接后 immutable 的不变式；
• 参数：max_height = 12，branching_factor = 4（构造函数默认）。

db/memtable.h 注释概括 CF 侧模型：

For each CF, rocksdb maintains an active memtable that accept writes, and zero or more sealed memtables (immutable). MemTableList maintains a list of ReadOnlyMemTable objects.

2.2 InternalKey 与 Arena

MemTable 存的不是用户 key，而是 InternalKey（db/dbformat.h）：user_key + sequence + value_type。同一 user key 的多版本按 sequence 降序 排列，供 Get / Iterator 找最新可见版本（第 7 篇）。

内存分配走 Arena / ConcurrentArena（allow_concurrent_memtable_write 时），减少小块 malloc；ImmutableMemTableOptions::arena_block_size 等由 MutableCFOptions 注入。

2.3 可选 MemTableRep

通过 MemTableRepFactory 可换 HashSkipList、VectorRep（bulk load）、Ribbon 等。默认 SkipList 在 通用随机写 与 范围扫描 之间平衡最好；Flink state 等点查为主场景有时调 prefix_extractor + Hash 结构（第 16 篇）。

2.4 与 lsm-tree DIY 对照

三、MemTableList：mutable 与 immutable 队列

3.1 两层结构

db/memtable_list.h 定义：

• MemTableListVersion：不可变快照，持 std::vector<ReadOnlyMemTable*>，从新到旧 搜索（Get / AddIterators）；
• MemTableList：维护当前 Version 指针、refcount；切换时 COW 新版本。

读路径通过 SuperVersion 持有 MemTableListVersion* 指针，避免 flush 期间长时间持锁（Install 时原子切换）。

3.2 容量与 max_write_buffer_number

MutableCFOptions 相关项：

双缓冲直觉：active 写满 → 变 immutable 并新建 active；后台 flush 最旧 immutable 时不阻塞新写（除非 stall）。

3.3 Get 与 Iterator 如何叠层

MemTableListVersion::Get（注释）：从 最新 MemTable 向旧搜索，返回 第一个 匹配 key 的版本，并通过 *seq 带回 sequence。

Iterator 路径 AddIterators 为 每个 immutable + active 构造 MemTableIterator，再与 SST 层 MergeIterator 合并（第 8 篇）。

3.4 Memtable history（可选）

max_write_buffer_number_to_maintain / max_write_buffer_size_to_maintain 可在 flush 后 保留已 flush MemTable 只读副本 于 history，供 Transaction 冲突检测等；与 GetFromHistory 配合。默认 OLTP 负载可忽略。

四、SwitchMemtable：从 mutable 到 immutable

Switch 由 DBImpl::SwitchMemtable（db/db_impl/db_impl_write.cc 等）在 write 路径或 flush 压力下调度，典型步骤：

1. 将当前 active 标记为 immutable（MemTable::MarkImmutable + 不再接受 insert）；
2. 分配新 active MemTable（新 ID / arena）；
3. MemTableList::Add 把 immutable 挂入列表；
4. 若 WAL 需要切换，新建 log 文件（log::Writer 新 log_number）；
5. imm()->FlushRequested() → EnqueuePendingFlush → MaybeScheduleFlushOrCompaction。

Atomic flush（atomic_flush=true）：多 CF 同时 Switch 并共享 flush 边界，保证 CF 间 checkpoint 一致——Flink 多 CF state 场景会关心（第 13、16 篇）。

五、FlushJob：PickMemTable 到 L0

5.1 生命周期

db/flush_job.h FlushJob 核心 API：

构造参数包含：ColumnFamilyData*、VersionSet*、snapshot 列表（决定 flush 时保留的最老 sequence）、FlushReason、output_compression 等。

5.2 WriteLevel0Table

FlushJob::Run 在 mempurge 等分支之后调用 WriteLevel0Table()（db/flush_job.cc）：

1. 合并 mems_（一个或多个 immutable MemTable）上的 按 InternalKey 排序 迭代器；
2. 调用 BuildTable（db/builder.cc）+ BlockBasedTableBuilder 输出 .sst；
3. 填充 FileMetaData（file number、smallest/largest key、sequence 范围、checksum）；
4. 通过 VersionEdit::AddFile 准备 MANIFEST 增量。

Flush 不 直接删 MemTable：Install 成功后 MemTableList::Remove 并 Unref；失败则 rollback 或保留待重试。

5.3 FlushReason 与调度

FlushReason 枚举包括：kWriteBufferFull、kWriteBufferManager、kManualCompaction、kExternalFileIngestion 等。DBImpl::BackgroundFlush 从 flush_queue_ 取 FlushRequest，线程池 Env::Priority::HIGH 通常优先于 compaction（可配置）。

WriteBufferManager（全局内存 cap）可在 未达单 CF write_buffer_size 时提前 flush，避免进程 RSS 失控——与 stream-processing 第 12 篇 的 state 内存调参相关。

5.4 MemPurge（实验特性）

FlushJob 含 MemPurge 路径：对 overwrite 重的负载 过滤 immutable 中已失效 KV 到新 MemTable，减少写放大；失败则回退普通 flush。生产默认仍以 全量 sort-merge 写 SST 为主路径。

六、Install 与 WAL 回收衔接

Flush Install 阶段（VersionSet::LogAndApply）把 新 L0 文件 写入 MANIFEST，并更新 Version 层级视图。成功后：

• 只被已 flush MemTable 覆盖的 WAL 段可标记删除；
• GetLiveFiles / checkpoint 以 MANIFEST + SST 为准。

读路径此时可见 MemTable（尚未 flush 的新写）+ 新 L0 + 旧 Ln 叠加；SuperVersion 切换保证 原子视图（第 7 篇）。

七、实验：exp05 强制 flush 观察 SST

reproduce/run_db_bench.sh Exp 05：

cd post/db/rocksdb/reproduce
export DB_BENCH="$PWD/rocksdb/db_bench"   # 或 _build/db_bench
# 脚本片段：
db_bench --benchmarks=fillrandom --num=50000 --write_buffer_size=65536 \
  --db="${DB_FLUSH}"
ls "${DB_FLUSH}"/*.sst | wc -l

设计意图：write_buffer_size=65536（64 KiB）远小于 5 万条 ×（key + 100B value），触发 多次 SwitchMemtable + flush，DB 目录下出现 多个 .sst。

观察点：

1. SST 个数随写入递增（exact 数字取决于 key/value 大小与 block size，不在此伪造）。
2. LOG 中 (Started/Finished) flush 事件与 event:flush_finished JSON（若 run_properties.sh 抓取）。
3. 对比 默认 64 MiB write_buffer_size：SST 个数显著减少——说明 flush 频率由 MemTable 容量驱动。

多线程 fillrandom 可叠加观察 max_write_buffer_number 触发的 stall（需更低阈值，见第 11 篇 exp11）。

与 WAL 目录对照：同一 DB 在 flush 后执行 ls *.log 与 ls *.sst——WAL 文件数与 max_total_wal_size / wal_ttl_seconds 回收策略相关；SST 文件数直接反映 MemTable flush 次数。二者比值是排查「写放大在 WAL 还是 L0」的第一眼线索。

八、并发 MemTable 写入

当 DBOptions::allow_concurrent_memtable_write=true 且 MemTableRep 支持时，WriteImpl leader 在 WAL 之后可把 follower 设为 STATE_PARALLEL_MEMTABLE_WRITER，多线程并行 MemTable::Insert。

约束（db/db_impl/db_impl_write.cc 注释）：

• MemTableRep 必须声明支持并发写；
• batch 含 Merge 时退化为串行；
• inplace_update_support 与并发写不兼容（启动时 CheckConcurrentWritesSupported 检查）。

并行写后通过 MemTablePostProcessInfo 批量更新 num_entries / data_size 统计，避免热路径 atomic 风暴。对 高线程 db_bench，开并发 MemTable 写可显著降 write_memtable_time——但 CPU 与 cache 争用上升，需实测。

九、Flush 调度与 PickMemTable

DBImpl::BackgroundFlush 循环从 flush_queue_ 取任务。FlushJob::PickMemTable（持 db_mutex）逻辑要点：

1. 从 ColumnFamilyData::imm()（即 MemTableList）取 最旧 且 memtable_id ≤ max_memtable_id 的 immutable；
2. 若 min_write_buffer_number_to_merge > 1，尝试 合并相邻 immutable 一次 flush，减少 L0 文件数；
3. 记录 existing_snapshots：flush 输出的 SST 必须保留 snapshot 仍需要的旧 sequence（通过 SnapshotChecker / earliest_write_conflict_snapshot）；
4. PickMemTable 之后必须 Run() 或 Cancel()，否则泄漏 memtable 引用。

FlushJob::Run 成功且 write_manifest=true 时，Install 调用 VersionSet::LogAndApply；失败则 Rollback immutable 回列表或触发 BGError。

十、FileMetaData 与 L0 特殊性

Flush 产出 FileMetaData（db/version_edit.h 相关结构）字段包括：

L0 文件 key range 可重叠（ unlike L1+ 层间不变式）。故 L0 读放大高，需 L0→L1 compaction 合并（第 10 篇）。频繁小 flush（exp05）会 堆 L0 文件，是故意演示 trade-off，而非推荐配置。

十一、调参直觉（非 cookbook）

详细参数矩阵见 storage/32-rocksdb-practice；本系列只解释 内核为何读这些旋钮。

db_bench 对照实验：在 exp05 基础上把 write_buffer_size 改为默认 67108864（64 MiB）再跑 5 万条，对比 SST 个数与 flush 次数——同一 num 下 SST 个数应 显著减少，说明 flush 频率主要由 MemTable 容量驱动而非绝对写入条数。

11.1 Range tombstone 与 flush

DeleteRange 在 MemTable 中存 range deletion meta，flush 时写入 SST 的 range tombstone block（或 meta 索引），读路径由 RangeDelAggregator 合并 MemTable 与 SST 层 tombstone（第 8 篇）。大 range delete 会 放大 MemTable 元数据，可能触发 提前 flush——排查 delete-range 性能时不只看 compaction，也要看 MemTable 占用。

11.2 imm() 与 SuperVersion

ColumnFamilyData::imm() 返回 MemTableList*，与 SuperVersion 中的 memtable_list 指针配合：Install flush 时 新建 SuperVersion，读线程持旧 SuperVersion ref 仍看到 flush 前 MemTable，写线程在新 SuperVersion 上继续。理解 immutable 队列长度 必须同时看 imm()->NumNotFlushed() 与 stall 条件——仅看 RSS 不够。

Flush 线程优先级默认 Env::Priority::HIGH（相对 LOW compaction），意图是 尽快释放 immutable 占用的 write_buffer_size，避免写 stall。若磁盘为 HDD，过高 flush 并发可能与 compaction 争抢 seek，需结合 max_background_flushes 与 max_background_jobs 联调（第 12 篇）。

与 stream-processing 的衔接：Flink RocksDB state backend 的增量 checkpoint 依赖 flush 产出的 SST 文件列表；MemTable 越大，checkpoint 间 未 flush 数据越多，恢复 replay WAL 越长——embed 场景常在 更小 write_buffer 与 更频繁 flush 之间取舍，而非无脑放大 MemTable。

十二、小结

MemTable 层完成三件事：

1. SkipList（默认） 提供有序、并发友好的内存表；
2. MemTableList 管理 active + 多个 immutable，读路径按时间从新到旧叠层；
3. FlushJob 在后台把 immutable 顺序刷为 L0 SST，经 VersionEdit 进入 MANIFEST。

写路径链条至此：WriteBatch → WAL → MemTable → SST → MANIFEST 全部连通。下一篇拆解 SST 文件格式 与 MANIFEST / VersionSet 的磁盘语义。

参考资料

1. RocksDB 9.x 源码：memtable/skiplist.h（跳表不变式与并发读）。
2. RocksDB 9.x 源码：db/memtable.h、db/memtable.cc（MemTable / ReadOnlyMemTable）。
3. RocksDB 9.x 源码：db/memtable_list.h、db/memtable_list.cc（immutable 队列与 Get）。
4. RocksDB 9.x 源码：db/flush_job.h、db/flush_job.cc（PickMemTable、WriteLevel0Table）。
5. RocksDB 9.x 源码：db/builder.cc（BuildTable）。
6. RocksDB 9.x 源码：db/db_impl/db_impl_write.cc（SwitchMemtable、EnqueuePendingFlush）。
7. lsm-tree 第 2 篇：WAL + MemTable（DIY 跳表与 WAL 恢复）。
8. 本系列 index；实验 reproduce/run_db_bench.sh exp05。

返回 系列目录 ｜ 上一篇：WAL 与 WriteBatch ｜ 下一篇：SST 格式与 MANIFEST