【RocksDB 内核机制】Iterator 与 MergeIterator：范围扫描与 tombstone

第 7 篇 讲清了 GetImpl 如何在 SuperVersion 上做点查；范围查询（NewIterator、前缀扫描、Compaction 输入归并）走的是 另一套栈：底层是多个 InternalIterator，中间用 MergeIterator 按 Internal Key 序归并，最外层 DBIter 把 同一 user key 的多版本 折叠成用户可见的一条记录，并处理 tombstone 可见性。

本文是系列 第 8 篇，源码锚点：RocksDB 9.x 的 DBImpl::NewInternalIterator（db/db_impl/db_impl.cc）、MergingIterator（table/merging_iterator.cc）、DBIter::IsVisible（db/db_iter.cc）。多路归并的 最小堆直觉 与 lsm-tree DIY Compaction 篇 同源——那篇实现了 toy MergeIterator；本篇对照生产路径与 读侧 tombstone 语义。

版本锚定：RocksDB 9.x（reproduce/rocksdb/）。不粘贴未实测的 scan QPS。

一、为什么 Iterator 比 Get 多一层

点查可以在第一个命中文件停止；范围扫描必须把 mem + imm + 各层 SST 的键流 合并 成全局 Internal Key 序，再由 DBIter 去重 / 删隐。

flowchart TB
  USER["DB::NewIterator"] --> DBI["DBIter (ArenaWrappedDBIter)"]
  DBI --> MI["MergingIterator"]
  MI --> M["MemTable Iterator"]
  MI --> I["Imm MemTable Iters"]
  MI --> L0["L0 Table Iters (×N)"]
  MI --> L1["LevelIterator L1"]
  MI --> LN["LevelIterator L2..Ln"]
  L0 --> TC["TableCache::NewIterator"]
  L1 --> TC
  LN --> TC

二、InternalIterator 抽象

InternalIterator（table/internal_iterator.h）是 SST、MemTable、MergeIterator 的统一接口：Seek / SeekForPrev / Next / Prev / key / value / status。键值为 Internal Key（含 sequence 与 type）。

典型实现：

TableCache::NewIterator（db/table_cache.cc）打开 SST：FindTable 把 TableReader 放入 Table Cache，再 table_reader->NewIterator(...)。Iterator 销毁时通过 RegisterReleaseAsCleanup 释放 cache handle。

三、NewInternalIterator：子迭代器如何组装

DBImpl::NewInternalIterator（db/db_impl/db_impl.cc）在已 ref 的 SuperVersion 上构建整棵树：

MergeIteratorBuilder merge_iter_builder(
    &cfd->internal_comparator(), arena,
    !read_options.total_order_seek && prefix_extractor != nullptr,
    read_options.iterate_upper_bound);

// 1. 可变 MemTable
auto mem_iter = super_version->mem->NewIterator(...);
merge_iter_builder.AddPointAndTombstoneIterator(mem_iter, mem_tombstone_iter);

// 2. Immutable MemTable 列表
super_version->imm->AddIterators(..., &merge_iter_builder, ...);

// 3. L0–Ln（非 kMemtableTier）
super_version->current->AddIterators(read_options, file_options_,
                                     &merge_iter_builder, ...);

internal_iter = merge_iter_builder.Finish(...);
internal_iter->RegisterCleanup(CleanupSuperVersionHandle, ...);

顺序：mem → imm（新→旧）→ L0 各文件 → L1 LevelIterator → … → Ln。MergeIteratorBuilder::Finish 调用 MergingIterator::Finish，若有 range tombstone iter 则初始化堆项（merging_iterator.cc 文件头注释）。

Version::AddIteratorsForLevel（db/version_set.cc）：

• L0：文件 key 范围 可重叠，每个 SST 一个 TableCache::NewIterator，全部加入 MergeIterator。
• L1+：同层文件 不重叠，构造单个 LevelIterator，在层内按文件 index 移动，lazy 打开下一个 SST。

这与 lsm-tree Compaction 篇 的 L0/L1+ 不变式一致；该文用最小堆归并多个 SST 输入，堆元素来源不同，比较器与 tie-break 规则相同（Internal Key 序）。

四、MergeIterator：堆归并与 range tombstone

MergingIterator 类注释（table/merging_iterator.cc）说明核心机制：

• 用 min-heap / max-heap 合并 point iterator 的当前 key。
• Range tombstone 把 [start_key, end_key) 的起止键也作为堆项；维护 active_ 集合 跟踪哪些层有活跃范围删除。
• 堆顶 point key 若被 更底层或同层 range tombstone 覆盖，则 跳过（FindNextVisibleKey）。

不变式（节选，forward 扫描）：

1. minHeap_.top() 为 ITERATOR 类型。
2. 堆顶 key 不被任何 range tombstone 覆盖。

NewMergingIterator 在 n == 1 时 直接返回 子 iter，避免堆开销；n >= 2 才分配 MergingIterator（可放在 Arena 上）。

InternalIterator* NewMergingIterator(const InternalKeyComparator* cmp,
                                     InternalIterator** list, int n,
                                     Arena* arena, bool prefix_seek_mode) {
  if (n == 0) return NewEmptyInternalIterator<Slice>(arena);
  if (n == 1) return list[0];
  // n >= 2: new MergingIterator(cmp, list, n, ...)
}

Compaction 侧：FlushJob 也用 NewMergingIterator 合并多个 MemTable（db/flush_job.cc），与读路径共享同一归并组件——读是 在线多路归并， compaction 是 离线多路归并，堆逻辑同构（对读 lsm-tree compaction 堆 的图示）。

prefix_seek_mode

当 CF 配置了 prefix_extractor 且未设 total_order_seek 时，MergeIterator 在 prefix 边界 上优化 Seek（prefix_seek_mode_）。全表扫描或需要严格全序时应设 ReadOptions::total_order_seek = true。

五、DBIter：user key 折叠与可见性

DB::NewIterator 最终返回 ArenaWrappedDBIter，内部包装 DBIter（db/db_iter.cc），持有：

• 底层 MergingIterator 产出的 Internal Key 流；
• sequence_：与 GetImpl 相同，来自 snapshot 或 GetLastPublishedSequence；
• optional ReadCallback（事务 / WriteUnprepared）。

IsVisible

bool DBIter::IsVisible(SequenceNumber sequence, const Slice& ts,
                       bool* more_recent) {
  bool visible_by_seq = (read_callback_ == nullptr)
                            ? sequence <= sequence_
                            : read_callback_->IsVisible(sequence);
  bool visible_by_ts = /* timestamp_ub_ / timestamp_lb_ 检查 */;
  if (more_recent) *more_recent = !visible_by_seq;
  return visible_by_seq && visible_by_ts;
}

Next / Seek 循环从 MergeIterator 取 Internal Key，跳过不可见版本，直到：

• 找到可见的 value / merge → 暴露给用户的 key() / value()；
• 或可见 tombstone → 该 user key 对客户端不可见（等价于不存在），继续扫描下一 user key；
• 或被 range tombstone 覆盖 → 同样跳过。

因此 范围扫描不会返回已删除 key（除非 ReadOptions::fill_cache 等副作用；语义上 Valid()==false 或已越过）。与 Get 的 GetContext::kDeleted 一致。

同一 user key 多版本

Internal Key 序下，同一 user key 按 sequence 降序 排列。DBIter 只向用户展示 第一个可见版本；若可见的是 tombstone，user key 不出现在迭代结果中。更旧版本 不再读取（已在新版本决策中忽略）。

六、Tombstone 可见性细则

点删除（Point Tombstone）

MemTable / SST 内仍存 tombstone 记录；对 snapshot ≤ tombstone.sequence 的读可见，读 更新 snapshot 则 key 消失。

Range Tombstone

Range deletion 存在 meta block（kTypeRangeDeletion），MemTable 也有 range del skiplist。MergeIterator 与 GetImpl 共用 覆盖 sequence 逻辑：max_covering_tombstone_seq 大于点查/迭代 key 的 sequence 时，key 视为删除。

ReadOptions::ignore_range_deletions = true 时跳过 range tombstone iter 构建（危险，仅特殊工具路径）。

Compaction 与 scan 的交互

长范围扫描可能触发大量 SST 的 Index/Data Block 读；tombstone 密集时 DBIter 需 连续 Next 跳过 大量内部键（db/db_iter.cc 注释 long-running operation due to tombstones）。Compaction 不及时会导致 scan 放大 与 空间膨胀（第 10–11 篇）。

七、ReadOptions 对扫描的影响

Flink / TiKV 嵌入场景的大前缀 scan 需关注 prefix_extractor 与 auto_prefix_mode 是否与 key 编码一致（第 16 篇）。

八、与 Get 路径的对照

                    Get                          Iterator
                      |                              |
            LookupKey + snapshot           DBIter.sequence_
                      |                              |
              mem -> imm -> Version          MergeIterator (mem+imm+L0..Ln)
                      |                              |
              FilePicker 单文件链            全层键流归并
                      |                              |
              GetContext::SaveValue          DBIter::IsVisible + tombstone 折叠
                      |                              |
              单 key 返回                        Valid / key / value 循环

两者共享 SuperVersion、sequence 可见性 与 TableCache；Iterator 额外付 堆维护 与 DBIter 去重 成本。L0 文件多时，MergeIterator 子源数量 ≈ imm_count + L0_files + (Ln 层数)，是 scan 延迟的重要因子。

九、小结

• InternalIterator 统一 MemTable / SST / 归并层接口；键为 Internal Key。
• NewInternalIterator 按 mem → imm → L0（多 iter）→ L1+（LevelIterator）组装，MergeIterator 最小堆归并——与 lsm-tree compaction 归并堆 同构。
• DBIter 负责 snapshot 裁剪与 tombstone 不暴露；可见删除使用户迭代器看不到该 user key。
• Range tombstone 由 MergeIterator active_ 与 GetContext / DBIter 共同处理。
• 排查 scan 慢：看 L0 文件数、tombstone 密度、是否误用 total_order_seek、Block Cache 命中（第 9 篇）。

上一篇：Get 与 Snapshot

下一篇：Block Cache 与 Bloom

返回 系列目录

参考资料

1. RocksDB 9.x 源码：db/db_impl/db_impl.cc（NewInternalIterator）；db/version_set.cc（Version::AddIteratorsForLevel、LevelIterator）；table/merging_iterator.cc；db/db_iter.cc（IsVisible）；db/table_cache.cc（A 级）。
2. RocksDB Wiki, Iterator / Read-only and Secondary Instances（A 级）。
3. lsm-tree Compaction 与 MergeIterator（DIY 堆归并对照）。
4. 第 7 篇 Get/Snapshot；第 6 篇 SST。