阅读 LevelDB：读路径（从 Get 入口到落盘）

《刷盘与 SSTable》那篇停在”文件已落地”并留了个尾巴：“读路径下回分解”。这篇就是那段路径——当你调用 db->Get 时，请求离开前台线程、从内存里的 memtable 一路下钻到 SSTable 文件，甚至可能在回程顺手触发一次压缩。

这是你一直在读的 LSM 主线的下游半段：

→ 阅读 LevelDB：Arena 区域分配器 → 阅读 LevelDB：SkipList 跳表索引 → 阅读 LevelDB：MemTable 内存表 → 阅读 LevelDB：刷盘与 SSTable 格式

读路径是写路径的镜像。写路径把一次 Put 变成带版本号、按跳表有序的记录，再刷到磁盘；读路径要找出某个 key 的”可见版本”——它可能在活跃 memtable、冻结的 immutable memtable，或横跨各层的几十个 SSTable 文件里——并且整个过程不能阻塞后台压缩线程。

1. 总览：一次 Get 究竟干了什么

读路径入口是 DBImpl::Get。一次读取分四个阶段：

定可见性边界：算出 snapshot（本次读能看到的”时间点”）。
钉住对象：放锁前对 mem_ / imm_ / current 各 Ref() 一次，防止读期间被后台压缩删除。
放锁慢查：不持锁，依次查 memtable → immutable memtable → SSTable（Version::Get）；这个窗口里后台压缩线程可能并发运行。
读后反馈：若确实查了 SSTable，记录 seek_file 统计，可能触发”读放大驱动的压缩”。

涉及的核心文件：db/db_impl.cc、db/version_set.cc、db/version_set.h、db/table_cache.cc、db/table_cache.h、table/table.cc。

2. 第 1 步——定可见性边界：snapshot（MVCC）

db/db_impl.cc:1125-1131

SequenceNumber snapshot;
if (options.snapshot != nullptr) {
  snapshot =
      static_cast<const SnapshotImpl*>(options.snapshot)->sequence_number();
} else {
  snapshot = versions_->LastSequence();
}

两条事实驱动了整条读路径：

LevelDB 是**多版本（MVCC）**的：每条写入的记录都带一个全局递增的 SequenceNumber。
读不是”读最新那条”，而是”读 seq <= snapshot 的最新一条”。

两种情况：

调用方显式传了 options.snapshot → 用该快照的序列号（读时”时光倒流”，看不到之后写入）。
没传 → 用 versions_->LastSequence()，即”读最新已提交数据”。

这个 snapshot 紧接着用于构造查找键 LookupKey(key, snapshot)（见第 4 节），后续所有比较都只匹配 ≤ snapshot 的版本。作用：① 读已提交的一致数据；② 快照隔离；③ 已删除/被覆盖的旧版本自然不可见。

关联：GetSnapshot()（db_impl.cc:1187）返回 snapshots_.New(LastSequence())，你传进来的 options.snapshot 正是从这里来的。

3. 第 2 步——放锁前钉住对象：Ref()

db/db_impl.cc:1133-1138

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

Get 在 db/db_impl.cc:1145 会 mutex_.Unlock() 放锁去读（可能很慢，要读 SSTable 文件）。放锁期间后台压缩线程可能：

把 mem_ 冻结成新的 imm_（MakeRoomForWrite）；
把 imm_ 落盘后 delete（CompactMemTable 置 imm_=nullptr）；
切换 current 到新 Version（LogAndApply）。

若只裸拿指针、放锁期间后台把它 delete，Get 就会访问已释放内存而崩溃。Ref() 给对象内部原子引用计数 +1，保证读期间这些对象不会被真正析构；读完后（重新加锁）在 db/db_impl.cc:1162-1164 各 Unref() 一次，计数归零才释放。

这是 LevelDB 的典范模式：并发读 = 放锁做慢操作 + 用引用计数保护被访问对象的生命周期。Ref/Unref 本身原子，所以后台的 Unref 与这里安全协作。

4. 第 3 步——放锁读取 + seek 统计钩子

db/db_impl.cc:1143-1161

// Unlock while reading from files and memtables
{
  mutex_.Unlock();
  // First look in the memtable, then in the immutable memtable (if any).
  LookupKey lkey(key, snapshot);
  if (mem->Get(lkey, value, &s)) {
    // Done
  } else if (imm != nullptr && imm->Get(lkey, value, &s)) {
    // Done
  } else {
    s = current->Get(options, lkey, value, &stats);
    have_stat_update = true;
  }
  mutex_.Lock();
}

if (have_stat_update && current->UpdateStats(stats)) {
  MaybeScheduleCompaction();
}

LookupKey(key, snapshot) 把 user key 编码成含 8 字节序列号的内部查找键。
查找顺序：memtable → immutable memtable → SSTable（current->Get）。
have_stat_update = true 标志”本次读确实落到了 SSTable”。只有走 current->Get 才有意义（命中 memtable 时 stats 未初始化，不能喂给 UpdateStats）。

have_stat_update 的用途是触发 seek compaction（读放大驱动的压缩）：

当某个 SSTable 被频繁”读到但得跳过大量被覆盖/删除的旧版本”（seek 计数累积超阈值），UpdateStats 返回 true，调度一次后台压缩来降低读放大。
这是与”写放大触发压缩”并行的第二条压缩触发路径——只读访问也能驱动压缩。

5. 第 4 步——Version::Get：SSTable 层查找核心

db/version_set.cc:324-400

Status Version::Get(const ReadOptions& options, const LookupKey& k,
                    std::string* value, GetStats* stats) {
  stats->seek_file = nullptr;
  stats->seek_file_level = -1;
  // ...
  ForEachOverlapping(state.saver.user_key, state.ikey, &state, &State::Match);
  return state.found ? state.s : Status::NotFound(Slice());
}

这是 current->Get 的实现。当 memtable / immutable memtable 都没命中，就到这里，在”当前版本的全部 SSTable 文件”里找 seq <= snapshot 的最新可见版本。

5.1 State + Match：回调式遍历

ForEachOverlapping 枚举”所有可能含该 user_key 的文件”，每遇到一个文件回调 State::Match（version_set.cc:341-379）。Match 做三件事：

（1）记录”该被压缩”的候选文件（seek compaction 核心）

if (state->stats->seek_file == nullptr &&
    state->last_file_read != nullptr) {
  // We have had more than one seek for this read.  Charge the 1st file.
  state->stats->seek_file = state->last_file_read;
  state->stats->seek_file_level = state->last_file_read_level;
}
state->last_file_read = f;
state->last_file_read_level = level;

一次 Get 若因同一个 key 要查第二个及以后文件，说明第一个文件里”藏着空洞”（key 在第一个文件里是被覆盖/删除的旧版本，得继续往后找）。这种”多次 seek”是读放大信号。
把第一个文件记为 seek_file 候选——正是第 4 节 have_stat_update + UpdateStats 要消费的数据。

（2）真正去读这个 SSTable 文件

state->s = state->vset->table_cache_->Get(*state->options, f->number,
                                          f->file_size, state->ikey,
                                          &state->saver, SaveValue);

经 TableCache 取/开文件，命中后回调 SaveValue 写值。

（3）根据结果决定是否继续查下一个文件

switch (state->saver.state) {
  case kNotFound:  return true;   // 当前文件没这 key，继续找别的文件
  case kFound:     state->found = true; return false;  // 找到值，停下
  case kDeleted:   return false;  // 找到删除标记，停下（更旧的也不可见）
  case kCorrupt:   ... return false;  // 出错，停下
}

SaveValue（version_set.cc:262-275）：解析 internal key，确认 user_key 相等，按类型判定——kTypeValue→kFound 并拷贝 value，kTypeDeletion→kDeleted。
注意 kDeleted 也直接返回 false：删除标记意味着 key 在 snapshot 之前就被删了，更旧版本自然也不可见，不必再查。

5.2 为什么可能查多个文件

本质还是 MVCC：一个 user_key 的不同版本可能分散在不同文件/层，必须按”新优先”找到 seq <= snapshot 的最新一条。

6. ForEachOverlapping：L0 多查、L1+ 二分

db/version_set.cc:281-322

// L0：可能多个文件都含同一 key，必须按"新→旧"全查
for (uint32_t i = 0; i < files_[0].size(); i++) {
  FileMetaData* f = files_[0][i];
  if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
      ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
    tmp.push_back(f);
  }
}
if (!tmp.empty()) {
  std::sort(tmp.begin(), tmp.end(), NewestFirst);  // 按文件号新→旧
  // ...
}
// L1+：文件之间键范围不重叠，二分定位一个即可
for (int level = 1; level < config::kNumLevels; level++) {
  // ...
  uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
  // ...
}

L0：文件之间键范围允许重叠，同一 key 可能同时存在于多个 L0 文件 → 收集所有重叠文件，按 NewestFirst（文件号 a->number > b->number）排序后依次查，新的优先。
L1~L6：同一层文件键范围互不重叠（disjoint），一个 key 最多落在一个文件 → FindFile 二分定位那一个即可。

6.1 为什么 L0 这里不用 rbegin() 反向遍历

关键事实：files_[0] 在数组里不是按文件号排的，而是按 smallest key 排的。

FileSet 类型：typedef std::set<FileMetaData*, BySmallestKey> FileSet;（version_set.cc:586）。
填充顺序：Builder::SaveTo 按 added_files（按 BySmallestKey 排序的 set）遍历 push_back 到 v->files_[level]（version_set.cc:683）。

所以 files_[0] 内存顺序是 smallest user key 升序，不是 file number 升序。rbegin() 只是把”按 smallest key 升序”反转为”按 smallest key 降序”，跟”文件号新→旧”是两码事（同一个 user_key 重叠的多个 L0 文件，其数组位置和文件号大小没有对应关系）。因此必须显式 sort(tmp, NewestFirst) 按 number 排序，才能得到真正的”新→旧”。L0 文件数极少（通常 ≤ 十来个），sort 开销可忽略，正确性优先。

7. 对 FileMetaData 做了什么（L0 筛选细节）

db/version_set.cc:286-294

std::vector<FileMetaData*> tmp;
tmp.reserve(files_[0].size());
for (uint32_t i = 0; i < files_[0].size(); i++) {
  FileMetaData* f = files_[0][i];
  if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
      ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
    tmp.push_back(f);
  }
}

对 FileMetaData 做的是只读的”范围筛选 + 收指针”：

读边界键：取 f->smallest / f->largest（文件内 InternalKey 的最小/最大），再各取 .user_key()，剥掉序列号和类型后缀。
做区间判定：用用户比较器 ucmp 判断 user_key 是否落在 [smallest.user_key, largest.user_key] 闭区间内。
收集指针：命中就把 f（指针）push_back 进 tmp——零拷贝，原结构体一字未改。
tmp.reserve(files_[0].size())：预先按 L0 文件总数预留容量，避免循环内多次重新分配。

为什么用 user_key 而不是 internal_key：InternalKey 排序是”user_key 为主、sequence 为辅”，一个文件在 internal key 上的 [smallest, largest] 区间，其 user_key 跨度正好是 [smallest.user_key(), largest.user_key()]；只要目标 user_key 落在这个区间，文件内必含该 user_key 的某个版本。用 user_key 比较是安全正确的简化。

8. TableCache：VersionSet 与 Table 之间的桥梁

db/table_cache.h:22 / db/table_cache.cc

8.1 是什么

TableCache 是以 file_number → (RandomAccessFile* + Table*) 为条目的缓存。它把”逻辑文件号”映射成”已打开并常驻内存的 Table 读取器对象”，并做 LRU 管理（底层淘汰实现本次不展开）。

8.2 在架构里的位置

DBImpl::Get
  └─ Version::Get            // 逻辑层：遍历 files_[level]，找出"可能含该 key 的文件"
       └─ TableCache::Get    // 桥接层：file_number ──► 已打开的 Table 对象（LRU 缓存）
            └─ Table::InternalGet  // 物理层：解析单个 SSTable 文件格式、读 data block

VersionSet 只管”有哪些文件”：files_[level] 里每个 FileMetaData 只记录 number / file_size / smallest / largest 元信息，不持有打开的文件，也不存 index/filter 数据。
Table 只管”单个 SSTable 文件怎么读”：解析 footer、index、filter、data block。
TableCache 夹在中间：当 Version::Get 确定要查某文件（f->number + f->file_size），调 table_cache_->Get(...)（即第 5 节 version_set.cc:354 那行）。它负责”按号取对象”，拿到后委托 Table::InternalGet 干活。

8.3 核心实现：FindTable

db/table_cache.cc:41-76

Status TableCache::FindTable(uint64_t file_number, uint64_t file_size,
                             Cache::Handle** handle) {
  // ...
  *handle = cache_->Lookup(key);          // 1. 先查缓存
  if (*handle == nullptr) {
    // ... NewRandomAccessFile(fname, &file);   // 2. 未命中：开文件
    Table::Open(options_, file, file_size, &table);  // 3. 构造 Table 读取器
    *handle = cache_->Insert(key, tf, 1, &DeleteEntry);  // 4. 插入缓存
  }
  // ...
}

命中：直接返回已存在的 Table*，零文件 IO。
未命中：拼 SSTable 路径 → env_->NewRandomAccessFile 打开 → Table::Open 读 footer/index/filter 建好读取器 → 插入缓存。
错误结果不缓存（便于文件修复后自动恢复）。

TableCache::Get（table_cache.cc:100-112）：取 Table* 后转调 t->InternalGet(...)，用完 cache_->Release(handle)。

8.4 它承担的几个关键职责

避免重复打开文件的巨大开销：同一 SSTable 会被多次 Get / compaction / 迭代反复读。缓存 Table（已加载 index/filter block）后，后续命中直接复用。
统一生命周期 / fd 管理：TableAndFile 把 file 和 table 绑在一起，由缓存统一管理；LRU 淘汰时 DeleteEntry 把两者一起 delete（table_cache.cc:19-24）。
与 Version 生命周期解耦：compaction 切换版本后，旧 Version 的 files_ 变了，但文件句柄仍缓存在 TableCache 里、由引用计数控制，不会因版本切换立刻关文件。需要真正删文件时，调用 Evict(file_number)（table_cache.cc:114）把该号从缓存抹掉，防止读到已删除文件。

与前面引用计数的呼应：DBImpl::Get 对 mem/imm/current 用 Ref() 防放锁期间被压缩删掉；TableCache 用另一套底层缓存 handle 引用计数（Lookup 拿到即持有、Release 释放）。目的相同——保证”正在读”的对象不会被并发压缩释放。

9. 读路径是写路径的镜像

同一个设计的三条线索在这里重现：

snapshot / 序列号可见性正是 MemTable 篇里打包进每个 internal key 的 (s<<8)|type 标签。没有它，就没有 MVCC，也没有”最新可见版本”。
放锁前 Ref() 这套动作是《刷盘与 SSTable》那篇”双缓冲 immutable memtable”的读侧对应物。两者都是为了让慢操作（刷盘，或读盘）与前台流量并发，又不崩溃。
seek compaction 是写放大压缩触发器的”读放大孪生兄弟”。写路径在层太满时调度压缩，读路径则在 key 反复跨文件时调度。

而前一篇的整套 SSTable 格式正是”读之所以快”的原因：footer 锚定 index，index 的最短分隔键保证二分正确，bloom filter 跳过整个 data block，每块的 restart 数组把前缀解压的扫描限制在 16 步内。

10. 速记表

环节	位置	作用
定可见边界	`db_impl.cc:1125`	算 `snapshot`（MVCC）
钉住对象	`db_impl.cc:1136`	`Ref` 防止放锁期间被压缩删掉
放锁读	`db_impl.cc:1145`	查 mem / imm / SSTable
读统计钩子	`db_impl.cc:1154`	`have_stat_update` 标记查过 SSTable
触发读压缩	`db_impl.cc:1159`	`UpdateStats` → `MaybeScheduleCompaction`
SSTable 查找	`version_set.cc:324`	`Version::Get`：遍历候选文件找最新可见版本
L0 多查	`version_set.cc:288`	收集重叠文件，`sort(NewestFirst)` 按文件号新→旧
L1+ 二分	`version_set.cc:310`	`FindFile` 定位唯一文件
桥接缓存	`table_cache.cc:41`	`FindTable`：file_number → `Table*`，避免重复开文件