【RocksDB 内核机制】LevelDB 基线：单线程 Leveled 与 DBImpl 骨架

RocksDB 架构演进 一章会把 diff 列成表：多线程 flush、Column Family、RateLimiter 等。若不清楚 LevelDB 1.23 原来长什么样，这些「新增」容易读成孤立特性。LevelDB 是 Google 2011 年开源的嵌入式 LSM 引擎，代码量小、结构清晰，RocksDB 在文件布局与 API 命名上大量继承它。

本文是系列第 2 篇，锚定 LevelDB 1.23（google/leveldb tag 1.23），从 DBImpl 入手讲清：

1. 进程内有哪些长期存活的对象（MemTable、VersionSet、TableCache）？
2. DBImpl::Write 如何把多个线程的写入合并成一次 WAL 追加？
3. DBImpl::Get 如何在 MemTable → immutable MemTable → SST 层级中查找？
4. SST 文件与 MANIFEST 在磁盘上承担什么语义？

先修：lsm-tree 第 1–4 篇 已用 C 实现等价组件；本篇改读 官方 C++ 源码，路径与 toy engine 一一对应。

本文是「RocksDB 内核机制」系列第 2 篇（共 18 篇）。→ 系列目录

篇目	核心内容
第 1 篇 · LSM 生态全景	存储三角与系列地图
第 2 篇 · LevelDB 基线	单线程 compaction、Write/Get 骨架
第 3 篇 · RocksDB 架构演进	相对 LevelDB 的 diff
第 4 篇 · WAL 与 WriteBatch	WAL record 与 group commit 细节

版本锚定：LevelDB 1.23；对照 RocksDB 9.x（下篇）。

环境说明：LevelDB 源码引用 GitHub google/leveldb tag 1.23；本机 WSL2 未在本篇粘贴 leveldb_bench 输出。机制来自 doc/impl.md 与 db/db_impl.cc。

一、LevelDB 1.23 架构总览

LevelDB 对外暴露 leveldb::DB 接口：Put、Get、Delete、Write(WriteBatch*)、NewIterator。内部唯一实现类是 DBImpl（db/db_impl.h）。官方实现说明 doc/impl.md 把持久化状态概括为：

• 当前 MemTable（mem_）与可选的 immutable MemTable（imm_）；
• 多层 SST 文件（Level 0 … Level N），由 VersionSet 管理；
• WAL 日志（*.log）与 MANIFEST（版本变更日志）。

flowchart TB
  subgraph mem["Memory"]
    MEM["mem_ active MemTable"]
    IMM["imm_ immutable MemTable"]
  end
  subgraph disk["Disk"]
    WAL["WAL *.log"]
    L0["Level 0 SST overlap"]
    L1["Level 1 SST"]
    LN["Level N SST"]
    MAN["MANIFEST"]
  end
  WRITE["DBImpl::Write"] --> WAL
  WRITE --> MEM
  MEM -->|"mem full"| IMM
  IMM -->|"CompactMemTable"| L0
  BG["BackgroundCompaction<br/>single thread"] --> L0
  BG --> L1
  BG --> LN
  MAN -->|"LogAndApply"| L0

与 lsm-tree 全景 一致：前台写 只碰 WAL + MemTable；flush 与 level compaction 在后台完成。LevelDB 的关键约束是：同一时刻最多一个后台 compaction 任务（background_compaction_scheduled_ 标志 + env_->Schedule）。

二、DBImpl 核心成员

DBImpl 在 db/db_impl.cc 中持有 LSM 的全部可变状态。下表列出读 Write/Get 路径时必须认识的字段（名称来自 LevelDB 1.23 源码）：

无 Column Family：整个 DB 只有一棵 LSM 树、一套 comparator。RocksDB 的 ColumnFamilyData 在此不存在——这是下篇 diff 的第一行。

单 immutable MemTable：imm_ 最多一个；RocksDB 改为 MemTableList 队列，允许多个 immutable memtable 等待 flush（适配多线程 flush）。

三、Write 路径：DBImpl::Write 与 group commit

多线程并发 Put 时，LevelDB 不让每个线程各自写 WAL，而是 写队列 + batch 合并（group commit）。DBImpl::Write（db/db_impl.cc）逻辑骨架如下：

Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) {
  Writer w(&mutex_);
  w.batch = updates;
  w.sync = options.sync;
  w.done = false;

  MutexLock l(&mutex_);
  writers_.push_back(&w);
  while (!w.done && &w != writers_.front()) {
    w.cv.Wait();
  }
  if (w.done) {
    return w.status;
  }

  Status status = MakeRoomForWrite(updates == nullptr);
  uint64_t last_sequence = versions_->LastSequence();
  Writer* last_writer = &w;
  if (status.ok() && updates != nullptr) {
    WriteBatch* write_batch = BuildBatchGroup(&last_writer);
    WriteBatchInternal::SetSequence(write_batch, last_sequence + 1);
    last_sequence += WriteBatchInternal::Count(write_batch);

    {
      mutex_.Unlock();
      status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));
      if (status.ok() && options.sync) {
        status = logfile_->Sync();
      }
      if (status.ok()) {
        status = WriteBatchInternal::InsertInto(write_batch, mem_);
      }
      mutex_.Lock();
    }
    versions_->SetLastSequence(last_sequence);
  }
  // ... 唤醒队列中后续 Writer ...
  return status;
}

（摘自 LevelDB 1.23 db/db_impl.cc，删减了错误处理与 wake-up 循环。）

关键步骤

1. 入队：每个写线程包装为 Writer，在 writers_ 上等待轮到自己成为队首。
2. MakeRoomForWrite：若 mem_ 过大，将其转为 imm_ 并调度 flush；若 L0 文件过多，阻塞前台写（write stall 雏形）。
3. BuildBatchGroup：队首线程把多个等待中的 WriteBatch 合并，上限约 1MB（小 batch 限制增长，避免拖慢延迟敏感写）。
4. WAL 再 MemTable：在 释放 mutex_ 之后 写 WAL 并 InsertInto(mem_)——队首 Writer 独占日志文件，避免并发写 log。
5. 分配 sequence：每条 KV 在 MemTable 内按 (user_key, sequence, type) 排序；sequence 单调递增，供 MVCC 式可见性（非 SQL 事务，但支持 Snapshot）。

WriteOptions::sync == true 时，logfile_->Sync() 保证 WAL 落盘后才返回——与 PostgreSQL commit 刷 WAL 同族语义，细节留第 4 篇展开。

MakeRoomForWrite 与 stall

MakeRoomForWrite（同文件）在以下情况循环等待或切换 MemTable：

• imm_ != nullptr：上一次 flush 尚未完成，新 MemTable 不能无限创建；
• L0 文件数 >= kL0_SlowdownWritesTrigger：先 sleep 微秒级，给 compaction 让路；
• L0 文件数 >= kL0_StopWritesTrigger：完全停止接受写，直到后台 compact 降 L0。

RocksDB 把这套逻辑扩展为更细粒度的 WriteController 与多种 compaction 风格下的 stall 状态机（第 11 篇）。

四、后台线程：flush 与 compaction 共用一个 worker

LevelDB 通过 Env::Schedule 投递 唯一 后台任务 DBImpl::BGWork → BackgroundCall → BackgroundCompaction：

void DBImpl::BackgroundCompaction() {
  mutex_.AssertHeld();

  if (imm_ != nullptr) {
    CompactMemTable();  // flush imm_ → L0 SST
    return;
  }
  Compaction* c = versions_->PickCompaction();  // leveled picker
  // ... DoCompactionWork 或 TrivialMove ...
}

优先级规则：先 flush imm_，再 level compaction。因此 immutable MemTable 堆积会直接推迟 L0→L1 归并——与生产 RocksDB 中 flush 线程池分离不同（下篇）。

MaybeScheduleCompaction 在 MemTable 切换、Get 采样命中、ManualCompaction 等路径被调用；若已有 background_compaction_scheduled_，则不再重复调度。整个 DB 同一时刻 最多一个 DoCompactionWork 在执行。

Leveled 策略要点（与 lsm-tree compaction 篇 一致）：

• L0：MemTable flush 产物，文件之间 key range 可重叠；
• L1+：同一 level 内 SST key range 两两不重叠；
• 相邻 level 容量比约 10:1（MaxBytesForLevel），compaction 自 L0 向深层推进。

五、Get 路径：MemTable → imm → Version

DBImpl::Get（db/db_impl.cc）展示标准 LSM 点查顺序：

Status DBImpl::Get(const ReadOptions& options, const Slice& key,
                   std::string* value) {
  MutexLock l(&mutex_);
  SequenceNumber snapshot = options.snapshot != nullptr
      ? static_cast<const SnapshotImpl*>(options.snapshot)->sequence_number()
      : versions_->LastSequence();

  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != nullptr) imm->Ref();
  current->Ref();

  {
    mutex_.Unlock();
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // hit active memtable
    } else if (imm != nullptr && imm->Get(lkey, value, &s)) {
      // hit immutable memtable
    } else {
      s = current->Get(options, lkey, value, &stats);
    }
    mutex_.Lock();
  }
  // Unref mem, imm, current
  return s;
}

（摘自 LevelDB 1.23，删减 Ref/Unref 与 stats 更新。）

读取要点

1. Snapshot sequence：未设 snapshot 时使用 LastSequence()，即读「已提交」最新版本；设 snapshot 则只可见 \(\leq\) snapshot sequence 的版本。
2. LookupKey：编码 user_key + sequence，MemTable 内按 InternalKey 降序排列，同 user_key 多版本取第一个 \(\leq\) snapshot 的记录。
3. Version::Get：自 L0 向 Ln 查找；L0 需检查所有可能重叠文件，Ln 用二分定位单个 SST；每层可用 Bloom Filter 跳过（lsm-tree 第 3 篇）。
4. 锁粒度：点查在读 SST 时 释放 DB mutex，避免阻塞写队列；仅 Ref/Unref 保护 MemTable/Version 生命周期。

读放大 \(RA\) 在最坏情况下与层数成正比；Bloom Filter 将多数「key 不存在」探测降为 \(O(1)\) 次内存判断。

六、SSTable 与 MANIFEST 最小语义

LevelDB 的 SST 称 Table（table/format.h），由 TableBuilder 顺序写入、TableCache mmap 读取。文件布局（Footer 定长）：

文件命名：*.sst 或六位数字（TableFileName）；写入后不可变，compaction 产出新文件、旧文件进入 obsolete 列表待删除。

MANIFEST 与 VersionEdit

内存中 Version 描述某一时刻各 Level 的 FileMetaData 集合。变更不直接改内存结构后刷盘，而是：

1. 将增量描述写入 VersionEdit（增删文件、Comparator 变更、log number 等）；
2. 追加到 MANIFEST 文件（CURRENT 指向最新 MANIFEST）；
3. LogAndApply 成功后切换 current 指针。

崩溃恢复时：先 replay WAL 重建 MemTable，再读 MANIFEST 重建 Version，最后删除不在 Version 中的 orphan SST。RocksDB 保留这一骨架，并增加 column family、WAL 目录、MinLogNumberToKeep 等字段（第 6 篇）。

doc/impl.md 用一句话概括：MANIFEST 是 LSM 拓扑的 redo log；WAL 是 MemTable 内容的 redo log——两者分工不同，不可互相替代。

七、LevelDB 的设计边界（为何被 fork）

LevelDB 1.23 刻意保持小巧，下列限制直接催生 RocksDB：

这些不是「缺陷」，而是 Scope 选择。教学与嵌入式轻量场景 LevelDB 仍然合适；TiKV/Flink 路径则普遍绑定 RocksDB 9.x。

八、与 lsm-tree DIY 的对照表

对照阅读时，建议打开 LevelDB doc/impl.md 作索引，再跳 db_impl.cc 的 Write/Get/BackgroundCompaction 三个函数——本系列后续 RocksDB 篇目会标注 同名函数在 RocksDB 中的新文件（如 db_impl_write.cc）。

九、小结

LevelDB 1.23 给出了 LSM 生产实现的 最小闭环：Write 队列 group commit、WAL + MemTable、单线程 flush/compaction、Version + MANIFEST 管理不可变 SST。DBImpl::Write 与 DBImpl::Get 两条路径涵盖了写优化引擎 80% 的结构性行为；compaction 细节与 leveled 不变式在 lsm-tree 第 4 篇 已从算法层讲过，本篇补齐 官方源码锚点。

下一篇在此基础上对照 RocksDB 9.x：多 WriteThread、并行 FlushJob/CompactionJob、Column Family、RateLimiter 与 Statistics 如何把 LevelDB 骨架扩展为 Flink/TiKV 可用的生产引擎。

参考资料

1. Google LevelDB, Implementation notes（doc/impl.md，release 1.23）。
2. Google LevelDB 源码, db/db_impl.cc — DBImpl::Write、MakeRoomForWrite、DBImpl::Get、BackgroundCompaction（tag 1.23）。
3. Google LevelDB 源码, db/version_set.cc — VersionEdit、LogAndApply。
4. Google LevelDB 源码, table/format.h — SST Footer 与 block handle。
5. lsm-tree 系列 — WAL、MemTable、SST、Compaction 算法对照。
6. RocksDB Wiki, RocksDB vs LevelDB（下篇 diff 的官方对照）。
7. 本系列第 1 篇、第 3 篇。

返回 系列目录 ｜ 上一篇：LSM 生态全景 ｜ 下一篇：RocksDB 架构演进