【RocksDB 内核机制】Get 与 Snapshot：SuperVersion 与 sequence number

第 6 篇 把 SST 磁盘布局与 VersionSet/MANIFEST 钉住了；读者已经知道 LSM 树每一层有哪些 SST 文件。生产里更常问的是：一次 Get(key) 究竟按什么顺序查 MemTable、Immutable MemTable 和 L0–Ln？ReadOptions::snapshot 如何截断可见版本？flush/compaction 进行中，读线程会不会看到半套状态？

本文是系列 第 7 篇，沿 DBImpl::GetImpl（RocksDB 9.x，db/db_impl/db_impl.cc）与 SnapshotImpl（db/snapshot_impl.h）把读路径钉住。与 lsm-tree DIY 第 2 篇 的 toy Get 不同，RocksDB 用 SuperVersion 把 mem/imm/version 绑成一致快照，用 sequence number 做版本裁剪。

版本锚定：RocksDB 9.x（reproduce/rocksdb/，ROCKSDB_MAJOR = 9）。本文不粘贴未实测的 db_bench 延迟数字。

一、点查在 LSM 上的层级模型

LSM 写路径把更新追加到 MemTable，flush 后落入 L0，再经 compaction 沉到 L1+。读路径必须在 所有仍可能持有该 user key 最新版本 的结构上查找，并按 版本从新到旧 取第一个对当前读者可见的记录。

flowchart TB
  API["DB::Get / GetImpl"] --> SV["GetAndRefSuperVersion"]
  SV --> MEM["mem->Get"]
  MEM -->|miss| IMM["imm->Get"]
  IMM -->|miss| VER["Version::Get"]
  VER --> FP["FilePicker 逐文件"]
  FP --> TC["TableCache::Get"]
  TC --> SST["BlockBasedTable::Get"]

MemTable 命中 时直接返回，不再碰磁盘；MemTable 未命中 才进入 Version::Get，由 FilePicker 按 storage_info_.level_files_brief_ 与 file_indexer_ 决定候选 SST，再经 TableCache::Get 打开单个文件做点查（见 db/version_set.cc Version::Get）。

与 B-Tree 引擎「树高固定、页内 MVCC 链」不同，LSM 的读放大来自 层数 × 文件数；第 9 篇讲 Block Cache / Bloom 如何裁剪无效 I/O。

二、Internal Key 与 sequence number

RocksDB 磁盘与 MemTable 存的不是 user key，而是 Internal Key：user_key + 8 字节 trailer，trailer 打包 sequence number（高 56 bit） 与 ValueType（低 8 bit）（db/dbformat.h）。

// db/dbformat.h（节选）
enum ValueType : unsigned char {
  kTypeDeletion = 0x0,
  kTypeValue = 0x1,
  kTypeMerge = 0x2,
  // ...
  kTypeSingleDeletion = 0x7,
  kTypeRangeDeletion = 0xF,  // meta block
};

inline uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
  assert(seq <= kMaxSequenceNumber);
  return (seq << 8) | t;
}

排序规则：InternalKeyComparator 先比 user key（含 user-defined timestamp 时按 comparator 规则），user key 相同时 sequence 大的排在前——因此同一 user key 的多版本在 SST / MemTable 中 降序 排列，点查时 先遇到最新写入。

每次 Write 为 batch 内每条记录分配递增 sequence（VersionSet::AllocateSequence 路径）；删除写 kTypeDeletion / kTypeSingleDeletion，不是原地抹掉旧值。Compaction 在 无 Snapshot 引用 且 tombstone 不再被更旧版本需要时，才物理删除（第 10 篇展开）。

LookupKey（db/lookup_key.h）在 GetImpl 入口构造：把 user key 与 snapshot 对应的 sequence 编码成 MemTable 键和 InternalIterator _seek 键，保证各层用同一可见上界：

// db/lookup_key.h（接口）
LookupKey(const Slice& _user_key, SequenceNumber sequence,
          const Slice* ts = nullptr);
Slice memtable_key() const;
Slice internal_key() const;

三、GetImpl：从 SuperVersion 到 Version::Get

DBImpl::GetImpl 是 DB::Get / MultiGet / 事务读的核心实现（db/db_impl/db_impl.cc）。主干步骤：

1. GetAndRefSuperVersion(cfd) — 取得当前 CF 的 SuperVersion 并增加引用计数。
2. 确定 snapshot sequence — 见下一节。
3. LookupKey lkey(key, snapshot, read_options.timestamp)。
4. sv->mem->Get → sv->imm->Get — 命中则 done = true。
5. sv->current->Get(...) — 在 Version 上走 FilePicker + TableCache::Get。
6. ReturnAndCleanupSuperVersion — 释放 SuperVersion 引用。

// db/db_impl/db_impl.cc（节选，顺序与语义一致）
SuperVersion* sv = GetAndRefSuperVersion(cfd);

SequenceNumber snapshot;
if (read_options.snapshot != nullptr) {
  snapshot = static_cast<const SnapshotImpl*>(read_options.snapshot)->number_;
} else {
  snapshot = GetLastPublishedSequence();
  // WriteUnprepared 等 callback 可能抬高 max_visible_seq
}

LookupKey lkey(key, snapshot, read_options.timestamp);

if (sv->mem->Get(lkey, ...)) {
  done = true;
} else if (sv->imm->Get(lkey, ...)) {
  done = true;
}

if (!done) {
  sv->current->Get(read_options, lkey, ...);
}
ReturnAndCleanupSuperVersion(cfd, sv);

Version::Get 内循环（db/version_set.cc）：

FilePicker fp(user_key, ikey, &storage_info_.level_files_brief_, ...);
FdWithKeyRange* f = fp.GetNextFile();
while (f != nullptr) {
  if (*max_covering_tombstone_seq > 0) break;  // range tombstone 已覆盖
  *status = table_cache_->Get(read_options, *internal_comparator(),
                               *f->file_metadata, ikey, &get_context, ...);
  switch (get_context.State()) {
    case GetContext::kFound: /* 返回 */ break;
    case GetContext::kDeleted: /* key 存在但已删 */ break;
    case GetContext::kNotFound: f = fp.GetNextFile(); break;
    // ...
  }
}

GetContext::SaveValue（table/get_context.cc）在 Internal Key 匹配 user key 后，用 CheckCallback(parsed_key.sequence) 判断 该版本是否 ≤ snapshot；不满足则 continue 找更旧版本。遇到 kTypeDeletion 且可见则置 kDeleted，对调用方表现为 NotFound。

四、SuperVersion：读一致性的锚点

SuperVersion（db/column_family.h）把一次读需要的 四层指针 绑在一起：

struct SuperVersion {
  ColumnFamilyData* cfd;
  ReadOnlyMemTable* mem;           // 当前可变 MemTable
  MemTableListVersion* imm;        // immutable MemTable 列表快照
  Version* current;                // 当前 LSM Version（SST 集合）
  MutableCFOptions mutable_cf_options;
  uint64_t version_number;
  // ...
  std::atomic<uint32_t> refs;
};

何时新建 SuperVersion：MemTable 写满切换、flush 完成、compaction 安装新 Version、部分 CF 选项变更等——写线程在持 mutex_ 下 InstallSuperVersion，旧 SuperVersion 引用计数归零后异步 Cleanup。

读线程如何拿 SuperVersion：GetAndRefSuperVersion → cfd->GetThreadLocalSuperVersion(this)（db_impl.cc）。线程本地缓存 SuperVersion 指针，避免每次 Get 抢 DB mutex；失效时从 ColumnFamilyData::super_version_ 重新 ref。

这保证 Get 全程看到的 mem / imm / current 来自同一安装点，不会在 MemTable 查完、SST 查一半时混入另一轮 flush 的新文件。代价是 flush/compaction 可能 延迟释放 仍被 SuperVersion 引用的 MemTable 和 SST（第 11 篇 write stall 与此相关）。

sequenceDiagram
  participant R as Read thread
  participant SV as SuperVersion
  participant W as Write / Flush thread
  R->>SV: Ref (GetAndRefSuperVersion)
  R->>SV: mem / imm / Version::Get
  W->>SV: InstallSuperVersion (new)
  Note over SV: old SV refs>0, 暂不 Cleanup
  R->>SV: Unref (ReturnAndCleanupSuperVersion)
  Note over SV: refs==0 → Cleanup mem/imm/version

五、Snapshot 语义与生命周期

公开 API（include/rocksdb/db.h）：

• GetSnapshot() → GetSnapshotImpl(false)，记录 当前 GetLastPublishedSequence()。
• ReleaseSnapshot(const Snapshot*) — 从双向链表移除，并可能触发 oldest snapshot 更新与 compaction 调度。

SnapshotImpl（db/snapshot_impl.h）：

class SnapshotImpl : public Snapshot {
 public:
  SequenceNumber number_;  // const after creation
  SequenceNumber min_uncommitted_ = kMinUnCommittedSeq;  // WritePrepared 用
  SequenceNumber GetSequenceNumber() const override { return number_; }
  // ...
};

SnapshotList 用 环形双向链表 维护所有活跃 snapshot；compaction 通过 GetSnapshotContext 收集 最老 snapshot sequence，决定哪些 tombstone / 旧版本 不能物理删除。

关键顺序（GetImpl 注释）：必须先 GetAndRefSuperVersion 再取 snapshot sequence（无显式 snapshot 时）。若顺序颠倒，中间发生的 flush 可能 compact 掉 本应对新读可见 的数据，或让 snapshot 读看到不一致结果。

ManagedSnapshot（db/snapshot_impl.cc）RAII 包装 GetSnapshot / ReleaseSnapshot，适合 C++ 嵌入代码。

与 PostgreSQL MVCC 的一句对照：PostgreSQL 用 事务 xmin/xmax + CLOG 在堆页上判断元组对快照是否可见；RocksDB 用 全局递增 sequence 编码在 Internal Key 尾部，读路径在合并序上 跳过 sequence > snapshot 的版本，不维护 per-key 版本链与 undo。

六、特殊路径与边界

Merge 与 Blob

• kTypeMerge：GetImpl 可能返回 MergeInProgress，由 MergeOperator 合并操作数（GetContext::SaveValue 中 kMerge 分支）。
• BlobDB / kTypeBlobIndex：Version::Get 内 BlobFetcher 根据 index 拉取大 value（集成 Blob 路径；本系列不展开 BlobDB 运维）。

Range Tombstone

MemTable / SST 除点 tombstone 外，还有 range deletion meta block。max_covering_tombstone_seq 非零时，Version::Get 提前终止 文件扫描——该 key 已被范围删除覆盖，无需再读更旧文件。

read_tier

ReadOptions::read_tier == kPersistedTier 且存在未持久化数据时，GetImpl 跳过 MemTable（skip_memtable），只读已 flush SST——用于特殊一致性检查，非常规业务读。

Column Family

本文以单 CF 描述；多 CF 时每个 ColumnFamilyHandle 独立 SuperVersion 与 LSM 树，WAL 仍共享（第 13 篇）。

七、调试与统计

RocksDB Statistics 中与 Get 相关的 tick（GetImpl / Version::Get 内 RecordTick）：

DB::GetProperty("rocksdb.num-files-at-levelN") 等需持锁或通过 SuperVersion 读 Version（GetIntPropertyOutOfMutex 路径）。排查「点查慢」时：先看 L0 文件数 与 memtable miss 比例，再查 Block Cache（第 9 篇）。

八、小结

• GetImpl 路径：SuperVersion → mem → imm → Version::Get → TableCache；Internal Key 按 user key ↑、sequence ↓ 排序。
• sequence number 是 LSM 内的 全局版本号；LookupKey 与 GetContext::CheckCallback 共同实现 snapshot 裁剪。
• SuperVersion 保证一次读绑定的 mem/imm/version 一致；引用计数延迟资源回收。
• GetSnapshot / ReleaseSnapshot 维护最老可见 sequence，驱动 compaction 能否丢弃旧版本。
• PostgreSQL MVCC 是页级元组可见性；RocksDB 是 单键多版本合并序 + sequence 上界，语义相近但数据结构完全不同。

上一篇：SST 格式与 MANIFEST

下一篇：Iterator 与 MergeIterator

返回 系列目录

参考资料

1. RocksDB 9.x 源码：db/db_impl/db_impl.cc（GetImpl、GetAndRefSuperVersion、GetSnapshotImpl、ReleaseSnapshot）；db/snapshot_impl.h；db/column_family.h（SuperVersion）；db/dbformat.h；db/lookup_key.h；db/version_set.cc（Version::Get）；table/get_context.cc（A 级）。
2. RocksDB Wiki, Basic Operations / Snapshots（A 级 API 语义）。
3. 第 6 篇 SST 与 MANIFEST；lsm-tree WAL+MemTable（DIY 对照）。
4. PostgreSQL 内核 MVCC（PG 可见性一句对照，B 级阅读路径）。