# InternalIterator
- InternalIterator 面向 ikey entries：key 带 seq 和 type。
- `InternalIterator` 实例化自 `InternalIteratorBase` 类
- `InternalIteratorBase<Slice>`
- InternalIterator 的实现类：
- MemTableIterator：迭代 memtable
- LevelIterator：迭代某层的 SSTs
- MergingIterator：合并多个迭代器
- CompactionMergingIterator
- TruncatedRangeDelMergingIter
- FragmentedRangeTombstoneIterator
- ClippingIterator
## InternalIteratorBase 方法
- 绝大多数为纯虚函数。
### SetRangeDelReadSeqno()
- 入参：`SequenceNumber read_seqno`
- 让迭代器只处理 seq 小于等于 `read_seqno` 的 range tombstones。
- 对于 tombstone iterators 它们只会返回序列号小于等于 `read_seqno` 的 tombstones
### Valid()
- 返回当前迭代器是否有效
- 有效的定义：迭代器指向一个 KV 对，且 status 是 ok 的
### SeekToFirst()
- 指向输入的第一个 key。
### SeekToLast()
- 指向输入的最后一个 key。
### Seek(target)
- 入参：`const Slice &target`
- 指向等于或超过 target 的第一个 key。
- 所有的 `Seek*`类方法执行前都会清楚之前的 error status。
### SeekForPrev(target)
- 入参：`const Slice &target`
- 指向等于 target 或在 target 之前的第一个 key。
### Next()
- 移动到下一个 entry。如果到末尾了，Valid() 返回 false。
### Prev()
- 移动到之前的 entry。
### key()
- 获取当前 entry 的 key。
- 返回 Slice，在下次对迭代器修改之前==有效==。
### NextAndGetResult(result)
- 调用 Next(), 并获取当前结果。
- 参数：`IterateResult *result`（返回值）
- 返回值：返回是否 Valid()
- IterateResult
- **`key`** : `Slice`
- **`bound_check_result`**：`IterBoundCheck`
- **`value_prepared`**：`bool`，如果为 false，则需要先调用 `PrepareValue()` 再调用 `value()`
### user_key()
- 返回当前 user key。需要先检查 Valid()。
### value()
- 获取当前 value。返回 Slice，在下次对迭代器修改之前==有效==。
- 需要先检查 Valid()，有时候也需要先调用 `PrepareValue()`
### status()
- 返回 err status。没错就返回 Status::OK
### PrepareValue()
- 有些类型的迭代器，Seek()/ Next() 等操作可能只加载了 key 而没有加载 value。
- 目的：避免读取可能不需要的 value。
- 这些迭代器创建时会指定 `allow_unprepared_value_` 为 true。
- 该函数用于加载 value，在 `value()` 之前调用。
- 例外：`IterateResult::value_prepared` 为 true。
- 如果发送错误，返回 false。
### MayBeOutOfLowerBound()
- 这个迭代器可能会返回比 `ReadOptions::iterate_lower_bound` 更小的 keys。
### UpperBoundCheckResult()
- 如果迭代器已经根据`iterate_upper_bound` 检查了当前 key ，返回检查结果。
### SetPinnedItersMgr(mgr)
- 给迭代器设置 PinnedIteratorsManager，大多数迭代器不需要，默认实现为空操作。
### IsKeyPinned()
- 如果返回 true，则意味着 `key()` 返回的 Slice 会一直有效，只要
- 没有调用 `PinnedIteratorsManager::ReleasePinnedData` 且
- 迭代器没有删除。
- IsKeyPinned() 保证始终返回 true， 如果
- 迭代器创建时指定了 `pin_data` 为 true
- `BlockBasedTableOptions::use_delta_encoding` 为 false
### IsValuePinned()
- 如果返回 true，则意味着 `value()` 返回的 Slice 会一直有效，只要
- 没有调用 `PinnedIteratorsManager::ReleasePinnedData` 且
- 迭代器没有删除。
### Get/SetReadaheadState(info)
- 参数：`ReadaheadFileInfo *`
- 当迭代器移向同一 level 另一个文件时，复用之前文件的 readahead state 来设置新文件的。
- 避免 `readahead_size` 从初始值开始（8KB）
- PR: [Reuse internal auto readhead_size at each Level](https://github.com/facebook/rocksdb/pull/9056)
### IsDeleteRangeSentinelKey()
- 默认实现返回 false。LevelIterator 中使用，表示当前迭代位置是否是文件边界 sentinel key。
### SeekForPrevImpl(target)
- 非虚函数，用于实现 SeekForPrev()
- 流程：
- 调用 `Seek(target)`
- 循环调用 Prev() 直到当前key 小于等于 target
----
# MemTableIteraor
- 用于迭代一个 MemTable 的 Internal Iterator。
## 核心成员
- **`iter_`**：`MemTableRep::Iterator *`，指向底层实现类如跳表的迭代器
- **`bloom_`**：`DynamicBloom`，memtable 的前缀 bloom filter
- **`prefix_extractor_`**：`SliceTransform *`
- **`valid_`**：`bool`，实现 Valid() 方法
- **`status_`**：`Status`，实现 status() 方法
- **`arena_mode_`**：`bool`，是否使用了外部传入的 Arena
- 如果为 true，释放 `iter_` 时只析构不调用 Delete
- **`value_pinned_`**：`bool`，默认为 true，除非开启了`inplace_update_support` 选项。
## 构造函数
- 入参：
- **`mem`**：`MemTable`，目标 memtable
- **`arena`**：`Arena *`，外部提供内存分配器，可为空
- **`use_range_del_table`**：`bool`，扫描 delete range table 还是普通数据 table
- 初始化 `iter_`，三种分支创建不同类型的迭代器：
- range delete 迭代器
- 当参数 `use_range_del_table` 为 true，则从 `mem.range_del_table_` 上创建迭代器
- prefix scan
- 当 `prefix_extractor_` 不为空且 `total_order_seek` 和 `auto_prefix_mode` 为 false 时，调用 `mem.table_->GetDynamicPrefixIterator()`
- 对于跳表实现，等用于 `GetIterator()`
- 同时初始化 `bloom_` 为 `mem.bloom_filter`
- 一般数据迭代器
- 即调用 `mem.table_->GetIterator()` 创建
## Seek(k)
1. 如果有 prefix bloom filter，则检查 filter 中 目标 key 是否存在
- 不存在则设置 `valid_` 为 false 并返回（迭代器结束了）
- 这相当于只能扫描到跟目标 key 前缀相同的数据（即 [prefix seek](https://github.com/facebook/rocksdb/wiki/Prefix-Seek)）
2. 调用 `iter_->Seek(k)`，设置 `valid_` 为 `iter_->Valid()`
## SeekForPrev(k)
1. 同样先检查 prefix bloom filter（如果有），filter 每命中则置 `valid_` 为 false 返回
2. 调用 `iter_->Seek(k)`
3. 如果非 Valid() 且 status ok 的话，调用 `SeekToLast()`
- 即 memtable 的所有数据都小于 k，此时 prev 还是可能存在的，移动到最后一条数据即可。
4. 重复调用 `Prev()`直到指向 k 或者 k 之前
## SeekToFirst / SeekToLast / Next / Prev
- 调用 `iter_` 的对应方法
## key() / value()
- 底层 `iter_`只会返回 key，只有 `iter_->key()` 方法。
- key 的结构：
| key_len(varint32) | ikey data | value_len(varint32) | value data |
| ----------------- | --------- | ------------------- | ---------- |
- key() 和 value() 方法都调用 `iter_->key()`，然后从中抽取 key 或 value 部分。
## IsKeyPinned()
- 始终为 true。
## 总结
- 实现上基本是直接调用底层 Memtable 实现类（如跳表）的迭代器
- 但需要处理 prefix seek 逻辑
- prefix seek 先检查 bf，bf 没有就置为 invalid
- 也需要解码 key / value
- 底层类 value() 为空，KV 都在 key() 返回值中。
----
# LevelIterator
- 用于迭代某一层 SSTs 的 Internal Iterator。
## 核心成员
- **`table_cache_`**：`TableCache *`，用于创建某个 SST 的迭代器。
- **`flevel_`**：`LevelFilesBrief *`，目标 level 的文件列表。
- **`level_`**：`int`，目标 level
- **`file_index_`**：`size_t`，当前迭代到哪个文件了
- **`file_iter_`**：[[iterator#^52ba69|IteratorWrapper]]，当前文件的迭代器
- 一般为 wrapped 之后的 BlockBasedTableIterator
- 只能迭代出 point keys
- **`range_del_agg_`**：`RangeDelAggregator *`，构造时传入，可能为空
- **`range_tombstone_iter_`**：`unique_ptr<TruncatedRangeDelIterator> *`
- [PR: Skip swaths of range tombstone covered keys in merging iterator](https://github.com/facebook/rocksdb/pull/10449)
- 当前 SST 的 tombstone iterator
- 当移动到一个新的 SST 时，会更新为新 SST 的 tombstone iterator
- 指向 MergingIterator 中 `range_tombstone_iters_`的对应元素，相当于 `unique_ptr` 的空间分配在那里，对其赋值就能更新 MergingIterator 中的对应元素。
- 指针关联的操作在 `MergeIteratorBuilder::Finish()` 中
```mermaid
flowchart TB
subgraph LevelIterator
iter["unique_ptr * range_tombstone_iter_"]
end
subgraph MergingIterator
direction TB
subgraph ts["Tombstone Iter Vector"]
direction LR
t0["unique_ptr"]
t1["unique_ptr"]
t2["unique_ptr"]
end
end
iter --> t1
```
- **`current_value_`**：`FileDescriptor`
- [ ] 未使用
- **`prefix_extractor_`**：`shared_ptr<SliceTransform> &`，来自 cf option
- **`prefix_exhausted_`**：`bool`，用于 prefix seek
- 下一个文件的起始key 跟 Seek 的目标 key 前缀不同，表示前缀整体迭代完成，不需要继续
- **`to_return_sentinel_`**：`bool`
- 当迭代当前 SST 内所有 point keys EOF 后，下次 Next/Prev 返回文件的边界 key
- 该 key 可能是由 delete range 扩展的，这种情况它会超过了（大于或小于）文件内的所有 point keys
- 为 true 表示存在这样的key，且当前迭代位置为 sentinel key
- 前提：仅当`range_tombstone_iter_` 不为空时才返回 sentinel key
- **`sentinel_`**: `Slice`，返回的文件边界 key
- 当调用 `to_return_sentinel_` 为 true，`key()` 函数会返回该 key。
- **`read_seq_`**：`SequenceNumber`，读取时可见的最大 seqno
- 来自 `ReadOptions.snapshot`，没有则为 kMaxSequenceNumber
- 用于限制 SST tombstone iterator 对外可见的 upper bound
<br>
- **`compaction_boundaries`**：`vector<AtomicCompactionUnitBoundary>`
> To be propagated to RangeDelAggregator in order to safely truncate range tombstones.
- [PR: Truncate range tombstones by leveraging InternalKeys](https://github.com/facebook/rocksdb/pull/4432)
- compaction 使用，当创建 compaction input iterators 时，由构造函数中传入
- 表示当前 level 每个 SST 的 AtomicCompactionUnitBoundary，当创建 SST iterator 时，会将 boundary 作为 SST TruncatedRangeDelIterator 的截断边界（而不使用 SST 的范围）
- 见 `TableCache::NewIterator()`
## TrySetDeleteRangeSentinel(boundary_key)
- 前提：
- 当前 SST 迭代到末尾 EOF 了。
- 即 `!file_iter_.Valid()` 且 status 是 ok 的。
- 操作：
- 设置 `to_return_sentinel_` 为 true，同时设置 `sentinel_` 为 `boundary_key`
- `boundary_key`来自文件的 smallest 或 largest key，可能不是文件中的某个 point key 而是 tombstone 扩展而来的。
## ClearSentinel()
- 设置 `to_return_sentinel_` 为 false
## NewFileIterator()
- 将 `file_iter_` 指向 `file_index_` 位置的文件。
- 主要是调用 `table_cache_->NewIterator()`初始化 `file_iter`
- 同时也会更新 `range_tombstone_iter_`
## SkipEmptyFileForward()
- 检查当前文件是否已经迭代完成，结束的话就切换到下一个文件。
- 迭代完成的条件（需同时满足）：
1. `to_return_sentinel_`为 false
- true 表示有 sentinel 需要迭代，没有结束
2. `file_iter_`的 status 为 ok 、 Valid() 为 false
3. `file_iter_->UpperBoundCheckResult()` 不为 `kOutOfBound`
- 下一个文件的 key 更大，没必要切换了。不切换的结果就是 LevelIterator 的 `Valid()`会返回 false，迭代中止
- 无法切换到下一个文件：
- 满足任一条件：
- 当前文件是本层最后一个
- 迭代位置超过 ReadOption `iterate_upper_bound` （下一个文件的 key 更大了）
- `prefix_exhausted_` 为 true
- 表示本层次都迭代结束了，执行`file_iter_->Set(nullptr)`，并返回。
- Set 为 nullptr 效果就是设置 `file_iter_`的 `valid_` 为 false
- 见 `IteratorWrapperBase::Set()` 函数
- 可以切换到下一个文件时，执行：
- `file_iter_`切换到下一个文件
- 重置迭代器到起始位置：
- 对 `file_iter_` 进行 `SeekToFirst()`，并调用 `TrySetDeleteRangeSentinel`
- 对 tombstone iter 调用 `SeekToFirst()`
## Seek(target)
1. 先检测目标 key 是否在当前文件(`file_index_`)的范围内，不在则需要 reseek file
- reseek：二分搜索当前 level，切换到新文件，并更新 `file_index_` 和 `file_iter_`
2. 调用 `file_iter_->Seek(target)`，seek 当前文件迭代器
3. prefix seek 状态下，如果下一个文件的前缀与 target 不同，则设置 `prefix_exhausted_`，表示前缀已经迭代完成， `SkipEmptyFileForward`不需要尝试下一个文件
- PR：[LevelIterator to avoid gap after prefix bloom filters out a file #5861](https://github.com/facebook/rocksdb/pull/5861)
4. 基于 largest key 尝试设置 DeleteRangeSentinel（Seek 后可能出于 point keys 末尾）
5. 调用 `SkipEmptyFileForward()`尝试切换到下一个文件（有可能当前文件没有 seek 到有效数据）
- SkipEmptyFileForward 中针对下一个文件直接 `SeekToFirst()`就行，因为新文件肯定大于等于 target，也会尝试设置 DeleteRangeSentinel
- `SeekToFirst()`和 sentinel 两者其中一个必然是有效的。
## Next()
- 如果 `to_return_sentinel_` 为 true，则清除（当前位置为 sentinel，Next消耗了它）
- 否则调用 `file_iter_.Next()`，并基于 largest key 调用 `TrySetDeleteRangeSentinel()`
- 调用 `SkipEmptyFileForward()`查看是否有必要切换到下一个文件
## SkipEmptyFileBackward()
- 类似 SkipEmptyFileForward，当前 `file_iter_`非 Valid()时，切换到前一个文件。
- TrySetDeleteRangeSentinel 时使用文件的 smallest key。
- 用于 `Prev()`, `SeekToPrev()`, `SeekToLast()`
## SeekToLast()
- 设置 `file_iter_` 为当前 level 最后一个文件，并调用 `file_iter_->SeekToLast()`
- 并基于 smallest key 调用 TrySetDeleteRangeSentinel（需要 `range_tombstone_iter_` 不为空）
- 调用 `SkipEmptyFileBackward()`，如果 `file_iter_` 为空则切换为前一个文件
- [x] ❓ 什么情况下文件会为空？
- 文件内只有 range tombstones，没有 point keys
- 且 `range_tombstone_iter_`为空，即不读取 sentinels
- SST largest key 对应的 sentinel 不算作 Last
- 与 Prev 的逻辑一致，backfoward 的 sentinel 只考虑 smallest key
## Prev()
- 类似 Next()，当前文件迭代完成后，切换为上一个文件。
## 总结
- 迭代某一个有序 level 的 SST files。
- 特殊：可选地，能迭代出文件边界 key，用于上层使用者感知文件切换。
- 仅当 `range_tombstone_iter_`指针不为空时，由上层按需指定
- 该 key 可能不存在于 point keys 中而是来自 delete range
- forward 方向的 sentinel 只考虑文件的 largest key，backward 方向则只考虑 smallest key
- [x] 切换文件 NewFileIterator 时，如何更新 tombstone iter 的
- NewFileIterator() 中跟`file_iter`一起更新
----
# IteratorWrapper
^52ba69
- 封装了一个 InternalIterator，提供跟 iterator 类似的接口，为底层 iterator 缓存了 valid() 和 key() 的结果。
- `IteratorWrapper` 是 `IteratorWrapperBase<Slice>` 的别名。
## 核心成员
- **`iter_`**：`InternalIteratorBase<TValue> *`，底层 iter，TValue 默认为 Slice。
- **`result_`**：`IterateResult`，缓存的当前 key 等数据，具体包括：
- **`key`**：`Slice`
- **`bound_check_result`**：`IterBoundCheck`，默认 kUnknown
- **`value_prepared`**：`bool`，默认 true，如果为 false 表示调用 value() 前需要先调用 PrepareValue()
- **`valid_`**：`bool`，缓存的当前 valid 状态
## Update()
- 从底层 iter 同步数据到缓存
- 更新 `valid_` 为 `iter_->Valid()`
- 如果 `valid_` 为 true，更新 `result_`
- key 为 `iter_->key()`
- `bound_check_result`为 kUnknown
- `value_prepared` 为 false
## Seek/SeekToFirst/SeekToLast/Prev
- 调用底层 `iter_` 对应方法，然后调用 Update 更新 key 等缓存。
## Next()
- 调用底层 `iter_->NextAndGetReuslt`，结果存储到 `result_`中
## PrepareValue()
- 如果 `result_.value_prepared` 为 true，则表示已经 prepare 过了，直接返回。
- 否则调用 `iter_->PrepareValue()`，更新 `result_`
## Set(iter)
- 设置底层 iter，并返回 `iter_` 旧值。
- 如果入参为 nullptr, 设置 `valid_` 为 false；否则调用 Update() 同步缓存。
## DeleteIter(is_arena_mode)
- 删除迭代器，如果 `is_arena_mode` 为 false 直接 delete，为 true 只调用析构函数。
------
# MergingIterator
- internal iterator，合并多个来自不同 level 迭代器，并应用 range tombstones。
- L0 有重叠，每个文件算一个 level。
## Doc Comment
- MergingIterator 使用了一个 min/max heap 来合并多个 point iterators 的数据。也可以添加 range tombstones, 被 tombstones 覆盖的的 keys 将会被跳过。
### 处理 range tombstones
- 将 tombstone 的 start 和 end 两个 key 跟普通 point keys 一起放入 `minHeap_`或 `maxHeap_`。
- 每个 range tombstone 仅在它的内部 key 范围 `[start_key, end_key)` 内是 active 的。`active_` set 用于跟踪有 active range tombstone 的 levesl。
- 以 forward scan 为例：
- Level j 会位于 `active_` 中当它当前的 range tombstone 满足
- tombstone 的 start key 已经从 `minHeap_`中弹出，且 end key 还在 `minHeap_`中
- 如果`minHeap_`堆顶是来自 Level L 的一个 point key，通过检查 `active_` 中是否有小于等于 L 的 level 存在比如 `l` 就可以判断该 point key 是否被 tombstone 覆盖。
- 当 `l == L` 时，还需要进一步检查 tombstone 的 seqno。
### Invariants
- 在 forward scan期间，MergingIterator 会维持以下的 invariants：
- 在调用每个 InternalIterator API 后，如 `Seek*()`，`Next()` 和 `FindNextVisibleKey()`，如果 `minHeap_`非空，则：
1. `minHeap_.top().type == ITERATOR`
2. `minHeap_.top()->key()` 没有被任何 range tombstone 所覆盖
- 在每次调用 SeekImpl() 后：
3. 对于所有 level `i` 和 `j <= i`，`range_tombstone_iters[j].prev.end_key() < children_[i].iter.key()`，也就是说 `range_tombstone_iters_[j]`当前是 level `j`中第一个 end key 大于等于 `children_[i].iter.key()` 的 tombstone。
4. 对于所有 level `i` 和 `j <= i`，如果 `j` 在 `active_`中，那么 `range_tombstone_iters[j]->start_key < children_[i].iter.key()`
- 当 `range_tombstone_iters[j]` 非 Valid() 时，我们考虑它的 prev 为最后一个 range tombstone
- 当涉及到 tombstone 的 start / end key 时，假设它的 value 为 `HeapItem::tombstone_pik`。 value 的 `op_type` 为 kMaxValid，这使得 tombstone keys 具有和 point keys 不一样的 value。
## HeapItem
- min/max heap 中的元素类型。每个 HeapItem 可以是一个 point iter 或者 range tombstone iter，取决于 `HeapItem::type`.
- 成员：
- **`iter`**: `IteratorWrapper`，point iterator
- **`level`**：`int`，iter 来自哪个 level，level 越小表示数据越新
- 因为 L0 的存在，这个是==虚拟== level，每个 L0 算一个 level，同一个 level 内数据有序
- **`tombstone_pik`**：`ParsedInternalKey`，tombstone 的 start 或 end key
- **`type`**：`Type`，三个枚举值
- `ITERATOR`
- `DELETE_RANGE_START`
- `DELETE_RANGE_END`
## 核心成员
- **`direction_`**：`Direction`，迭代方向：forward or reverse
- **`children_`**：`vector<HeapItem>`，所有需要 merge 的 child point iterators。
- *Invariant*：
- `children_[i]`在 `minHep_`中当且仅当 `children_[i].iter.Valid()`
- [ ] 最多一个 `children_[i]` 在 `minHeap_`中
- **`pinned_heap_item_`**：`vector<HeapItem>`
- 负责存储 range tombstone start 和 end keys 的 HeapItem
- heap 中的元素可能会指向它
- `pinned_heap_item_[i]`对应 `range_tombstone_iters_[i]`
- 即存储每个 level 当前的 tombstone，与 level 一一对应。
- *Invariant*:
- 分别设 `pinned_heap_item_[i]` 和 `range_tombstone_iters_[i]` 为 item 和 iter
- 当 `iter->Valid()` 时
- 如果 `item.type == DELETE_RANGE_START`，则 item 的 `tombstone_pik` 为 `iter->start_key()`
- 如果 `item.type == DELETE_RANGE_END`，则 item 的 `tombstone_pik` 为 `iter->end()`
- **`range_tombstone_iters_`**：`vector<unique_ptr<TruncatedRangeDelIterator>>`
- `range_tombstone_iters_[i]` 对应 `children_[i]`的 tombstone iter
- NULL 则表示该 child 没有 tombstones
- 如果为空，表示 merging 时不需要处理 range tombstones.
- *Invariant*：
- `pinned_heap_item[i]` 在 `minHeap_` 中当且仅当 `range_tombstone_iters_[i]->Valid()`
- [ ] 最多只有一个 `pinned_heap_item_[i]` 在 `minHeap_` 中
- **`active_`**：`set<size_t>`，哪些 levels 的 range tombstones 是 active 的。
- levels 从新到旧排序。
- *Invariant*：
- `i` 存在于 `active_` 中当前仅当 `range_tombstone_iters_[i]->Valid()` 以及`pinned_heap_item_[i].type == DELETE_RANGE_END`
- **`current_`**：`IteratorWrapper *`
- 当前迭代位置，当前堆顶的 child point iterator，用于返回当前 key() / value()
- 来自 `CurrentForward()/CurrentReverse()`.
- **`minHeap_`**：`BinaryHeap<HeapItem*, MinHeapItemComparator>`
- 按 每个 item 的 iter 当前 key 的顺序， 最小的 item 在堆顶，用于 forward iteration。
- 元素为 HeapItem 的==指针==，指向`children_`或 `pinned_heap_item_`中的元素。
- **`maxHeap_`**：`BinaryHeap<HeapItem*, MaxHeapItemComparator>`
- 按 HeapItem key 顺序的大顶堆，key 最大的在堆顶，用于 reverse iteration
- **`iterate_upper_bound_`**：`const Slice *`，来自 ReadOtions
- 只用于限制 range tombstones。point iterator 已在内部自己应用了该限制。
## Finish()
- MergingIteratorBuilder 结束后调用，此时所有的 iteartors 都已经添加完成。
- 该函数主要是 `range_tombstone_iters_` 来初始化 `pinned_heap_item_`。
- 过程：
- `pinned_heap_item_`跟 `range_tombstone_iters_` 大小一样
- 每个 `pinned_heap_item_` 元素的值初始化为：
- level 从 0 开始依次递增
- `tombstone_pik.type` 为 kTypeMaxValid
> [!note]- 使用 kTypeMaxValid 的原因
> tombstone 的 end key 是 exclusive 的。考虑 point internal key 跟 tombstone 的 start/end key 相同，使用 kTypeMaxValid 能保证 **start < end < point internal key**（kTypeMaxValid 最大，相同 ukey 和 seq 下顺序在最前面）。
>
> 实际上只有 TruncatedRangeDelIterator 中 truncated 后的 tombstone 需要这个，untruncated 的 tombstone key 会使用 kMaxSequenceNumber 和 kTypeRangeDeletion，已经能跟 point keys 区分开来。*见 TruncatedRangeDelIterator::start_key()/end_key()*
## AddToMinHeapOrCheckStatus(item)
- 将 child point iter 插入到 `minHeap_`
- 前提 iter 是 Valid 的，非 Valid 的话则检查其 status
## InsertRangeTombstoneToMinHeap()
- 参数：
- **`level`**：`size_t`
- **`start_key`**：`bool`，默认 true，表示插入 tombstone 的 start key，false 表示 end key
- **`replace_top`**：`bool`，默认 false，是否替换堆顶元素
- 将 `range_tombstone_iters[level]` 当前迭代位置的 tombstone 更新到`pinned_heap_item_[level]`，并插入到 min heap 中
- 如果插入的是 end key，则更新 `active_`
- **特例**：如果 tombstone 当前超过 `iterate_upper_bound_`（整体超过，即 tombstone start key 大于等于它），则不插入到 min heap，如果 `replace_top`为 true 则只进行 pop 操作。
## PopDeleteRangeStart()
- 如果 `minHeap_`的堆顶为 tombstone 的 start，则弹出，并插入 tombstone end 到 `minHeap_`中。该 tombstone 开始变成 active，需要更新 `active_`。
## SkipNextDeleted()
- 如果当前 key （min heap 堆顶）不应该返回给用户，就返回 true，这可能是因为以下三种情况：
- 当前 key 被某个 tombstone 覆盖
- 当前 key 是文件边界 sentinel key
- 当前 key 是 tombstone 的 end key
- 可能会根据需要 advance 堆顶 iter，并相应维护 heap 顺序和更新 `active_`。
- 调用前提：
- `minHeap_`非空，迭代方向为 kForward
- `minHeap` 堆顶不是 tombstone start
### DELETE_RANGE_END
- 即当前堆顶为 tombstone end key。此时当前 tombstone end key 是所有 iterators 中最小的，后续迭代的 keys 都会大于它，因此该 tombstone 已经使用完成，失效了，需要==清理==。
- 处理流程：
1. 从 `active_`中删除该 tombstone。
2. 删除堆顶即该 tombstone end
3. 移动该 tombstone 所属的 iter 到下一个 tombstone 位置（调用 Next ）
4. 如果 tombstone iter 是 Valid 的话（即新 tombstone 有效），将其 start key 加入到 `minHeap_`中
5. 函数返回值： true
- 总结：删除当前 tombstone，插入同 level 下一个 tombstone。
### Sentinel Key
- 即当前堆顶为 point iter，但指向 sentinel key。
- 表示此时需要==切换==到同 level 的下一个文件，需要进行一些特殊处理。
- 如果 sentinel key 是一个 delete range tombstone，则对应的 tombstone 一定之前以后遇到过了。
- 因为放入 heap 中使用的 key type 更大，排序在前面
- 因此 `active_.count(current->level)` 必然为 0.
- 处理流程：
1. 弹出 `minHeap_` 堆顶元素（即该指向 sentinel key 的 child point iter)
2. heap 中还有当前文件残留未结束的 tombstone end key，进行清理
- 场景：文件最大 point key 和 tombstone end key 拥有相同的 user key，且该 user key 跨越两个文件。例如两个key分别为 `foo@100` 和 `foo@99`，tombstone end key 经过 truncated 后的 seqno 为前一个 key 的减一。
- 见 `TruncatedRangeDelIterator::TruncatedRangeDelIterator()`函数中对 largest key 的截断处理。
- 这也意味着这样的 tombstone end key 最多只有一个。
3. 调用 `child_iter->Next()`，将 LevelIterator 移动到一个新的文件；
4. 将新文件的 point iter 重新插入到 `minHeap_` 中
5. 将新文件 tombstone iter 的 首个 tombstone 插入到 heap 中（调用 `InsertRangeTombstoneToMinHeap()`）
- 总结：
- 处理文件切换相关逻辑：清理旧文件的 point iter & tombstone, 插入新文件的 point iter & tombstone。
- 该 case 下函数值为 true。
### Check active
- 即当前堆顶为 point iter，且指向非 sentinel；需要检查其当前 key 是否被 active tombstones 覆盖。
```mermaid
---
title: Check Cover
---
flowchart
classDef default font-size:10pt;
Start@{ shape: circle, label: "Start" } --> IsEmpty{active_ 是否为空}
IsEmpty -- 不为空 --> CompareLevel
CompareLevel{"cmp(active_begin,
current_level\)"}
IsEmpty -- 为空 --> ReturnFalse1
ReturnFalse1@{ shape: dbl-circ, label: "返回 false" }
CompareLevel -- 小于 --> LT[tombstone所属level 更新
当前 key 肯定被覆盖]
LT --> Seek[调用SeekImpl跳到
active tombstone end
即跳过该tombstone范围]
Seek --> ReturnTrue1@{ shape: dbl-circ, label: "返回 true" }
CompareLevel -- 等于 --> EQ[tombstone与当前
key的level 相同]
EQ --> CompareSeq{"cmp(key_seq,
tomb_seq)"}
CompareSeq -- 小于 --> LTKey[tombstone seq 更新,
key被覆盖]
NotCovered --> ReturnFalse3@{ shape: dbl-circ, label: "返回 false" }
LTKey --> Next[Next 当前 point iter，
弹出并重新插入 heap 中]
Next --> ReturnTrue2@{ shape: dbl-circ, label: "返回 true" }
CompareSeq -- 不小于 --> NotCovered[key seq 更新，
未被覆盖]
CompareLevel -- 大于 --> GT[active levels更旧
key 没有被覆盖]
GT --> ReturnFalse4@{ shape: dbl-circ, label: "返回 false" }
```
- `active_begin` 为 `active_.begin()`，活跃的最小/最新 tombstone level
- SeekImpl 仅移动大于等于 current level 的 levels。
- 即 tombstone active level 所能影响到的（比 active level 旧的）
## FindNextVisibleKey()
- 重复调用 `PopDeleteRangeStart()` 和 `SkipNextDeleted()` 直到堆顶为一个有效的 point key iter。
- 即堆顶 iter 指向一个 point key，且该 key 未被 tombstone 所覆盖。
- 或者 heap 为空没有更多的 keys。
## SeekImpl()
- 参数：
- **`target`**: `const Slice &`
- **`starting_level`**：`size_t`，默认值为 0
- *`range_tombstone_reseek`*：`bool`，默认为 false。
- target 是否来自 tombstone end key，表示来自 cascading seek，仅用于 perf 统计。
- 功能：
- 将所有 `levels >= starting_level`的 components 移动到 target 处或之后；
- components：point iters 和 tombstone iters
- 小于 `starting_level` 的（更新的）不动
- **调用场景**：SkipNextDeleted() 中发现了位于 level `i` 的 active tombstone，则需要将大于等于 `i` 的 iters 移动到 tombstone 之后（即跳过被其覆盖的部分），小于等于 `i`的更加新，不会被覆盖，因此无需移动
- 流程：
1. 清理两个 heap，`active_` 不动；
2. 添加小于 `starting_level` 的 child point iters；
- 直接重新放回 `minHeap_`中，不需要 advance iter
3. 添加小于 `starting_level`的 tombstones；
- 即将 `pinned_heap_item_[level]`放入 heap 中
- 优化：如果 level 位于 `active_`中，表示之前已经成功放入过堆中（未超过 `upper_bound`），则不需要越界检查，直接 push
4. 从 `active_`删除大于等于 `starting_level`的，因为下面要进行 reseek；
5. 处理大于等于 `starting_level`的 iters
- 将 point iter 和 tombstone iter 都 Seek 到 target，并插入到 heap 中
- 如果 seek 后的 tombstone start key 大于 target，则插入其 start key，否则插入其 end key（这种情况表示 tombstone 与 target 重叠，视为 active）。
- 优化：[cascading seek](https://github.com/facebook/rocksdb/pull/10449)，不断更新 target，跳过已经被更新 level tombstone 覆盖的范围。
> [!info] cascading seek
> - 如果 target 与某 level 的 当前 tombstone 重叠，则更旧的层次需要同时跳过 target 和 tombstone end key，因为对于更旧的 level，小于 target 的部分无效，被当前 tombstone 覆盖的也无效，此时更新下次 seek target 为 tombstone end key，直接跳到 tombstone end key 之后。
<svg xmlns:xl="http://www.w3.org/1999/xlink" xmlns="http://www.w3.org/2000/svg" version="1.1" xmlns:dc="http://purl.org/dc/elements/1.1/" viewBox="1381.1937 -61.94451 391.0175 74.95892" width="391.0175" height="74.95892">
<defs>
<marker orient="auto" overflow="visible" markerUnits="strokeWidth" id="DimensionArrow_Marker" stroke-linejoin="miter" stroke-miterlimit="10" viewBox="-1 -9 15 18" markerWidth="15" markerHeight="18" color="black">
<g>
<path d="M 0 0 L 12.000001 0 M 12.000001 7.500001 L 12.000001 -7.500001 M 0 3.0000002 L 10.500001 0 L 0 -3.0000002" fill="none" stroke="currentColor" stroke-width="1"/>
</g>
</marker>
<marker orient="auto" overflow="visible" markerUnits="strokeWidth" id="DimensionArrow_Marker_2" stroke-linejoin="miter" stroke-miterlimit="10" viewBox="-14 -9 15 18" markerWidth="15" markerHeight="18" color="black">
<g>
<path d="M 0 0 L -12.000001 0 M -12.000001 -7.500001 L -12.000001 7.500001 M 0 -3.0000002 L -10.500001 0 L 0 3.0000002" fill="none" stroke="currentColor" stroke-width="1"/>
</g>
</marker>
</defs>
<metadata> Produced by OmniGraffle 7.24.2\n2025-03-26 03:17:37 +0000</metadata>
<g id="Canvas_1" stroke-opacity="1" fill="none" fill-opacity="1" stroke-dasharray="none" stroke="none">
<title>Canvas 1</title>
<g id="Canvas_1_Layer_1">
<title>Layer 1</title>
<g id="Graphic_5">
<text transform="translate(1386.1937 -28.881592)" fill="black">
<tspan font-family="Helvetica Neue" font-size="16" fill="black" x="5684342e-20" y="15" xml:space="preserve">tombstone</tspan>
<tspan font-family="Helvetica Neue" font-size="16" fill="black" x="22.536" y="33.448" xml:space="preserve">start</tspan>
</text>
</g>
<g id="Graphic_6">
<text transform="translate(1690.1392 -28.881592)" fill="black">
<tspan font-family="Helvetica Neue" font-size="16" fill="black" x="5684342e-20" y="15" xml:space="preserve">tombstone</tspan>
<tspan font-family="Helvetica Neue" font-size="16" fill="black" x="25.048" y="33.448" xml:space="preserve">end</tspan>
</text>
</g>
<g id="Graphic_7">
<text transform="translate(1552.317 -28.881592)" fill="black">
<tspan font-family="Helvetica Neue" font-size="16" fill="black" x="3.92" y="15" xml:space="preserve">seek</tspan>
<tspan font-family="Helvetica Neue" font-size="16" fill="black" x="6679102e-19" y="33.448" xml:space="preserve">target</tspan>
</text>
</g>
<g id="Line_10">
<line x1="1435.0544" y1="-43.526283" x2="1720.5" y2="-43.50106" marker-end="url(#DimensionArrow_Marker)" marker-start="url(#DimensionArrow_Marker_2)" stroke="black" stroke-linecap="round" stroke-linejoin="round" stroke-width="1"/>
</g>
<g id="Graphic_12">
<path d="M 1576.4522 -45.224517 C 1577.7458 -43.503865 1577.6376 -41.080547 1576.1081 -39.551047 C 1574.4289 -37.871807 1571.6723 -37.905855 1569.951 -39.627113 C 1568.3832 -41.194877 1568.2152 -43.621617 1569.4666 -45.310817 L 1569.4521 -45.310996 L 1572.6333 -50.24677 C 1572.7267 -50.391677 1572.9218 -50.430507 1573.069 -50.3335 C 1573.1061 -50.309075 1573.1379 -50.27731 1573.1623 -50.24023 L 1576.4665 -45.22435 Z" fill="white"/>
<path d="M 1576.4522 -45.224517 C 1577.7458 -43.503865 1577.6376 -41.080547 1576.1081 -39.551047 C 1574.4289 -37.871807 1571.6723 -37.905855 1569.951 -39.627113 C 1568.3832 -41.194877 1568.2152 -43.621617 1569.4666 -45.310817 L 1569.4521 -45.310996 L 1572.6333 -50.24677 C 1572.7267 -50.391677 1572.9218 -50.430507 1573.069 -50.3335 C 1573.1061 -50.309075 1573.1379 -50.27731 1573.1623 -50.24023 L 1576.4665 -45.22435 Z" stroke="#84cd5c" stroke-linecap="round" stroke-linejoin="round" stroke-width="2"/>
</g>
<g id="Graphic_16">
<title>Clear</title>
<path d="M 1671.5355 -58.23076 L 1666.8234 -61.94451 L 1648.142 -47.221204 L 1629.4606 -61.94451 L 1624.7484 -58.23076 L 1643.4298 -43.507454 L 1624.7484 -28.784147 L 1629.4606 -25.070397 L 1648.142 -39.793704 L 1666.8234 -25.070397 L 1671.5355 -28.784147 L 1652.8541 -43.507454 Z" fill="#ccc"/>
</g>
</g>
</g>
</svg>
## CurrentForward()
- 返回当前`minHeap_`堆顶的 point iter。空的话返回 nullptr.
- 前提：堆顶元素（如果非空）为 ITERATOR（非 tombstone)。
## Seek()
1. 调用 SeekImpl(), `starting_level`为0，所有 levels 都需要 reseek。
2. 调用 FindNextVisibleKey(), 确保堆顶为有效 point iter。
3. 更新 `current_` 为 CurrentForward()，即堆顶 point iter。
## Next()
1. 调用 `current_->Next()`，并将 `current_`弹出再重新插入到 `minHeap_` 中；
2. 调用 FindNextVisibleKey(), 确保堆顶为有效 point iter；
3. 更新 `current_` 为 CurrentForward()
## 总结
- 使用 `minHeap` 维持堆顶为 children 中最小的 iter，实现合并逻辑；
- tombstone 处理：
1. 先把 tombstone start key 放入 minHeap 中，当其变为堆顶时，表示 tombstone 开始激活，pop start key 后再将 tombstone end key 放入 minHeap 中。
2. tombstone 激活后，迭代 point keys 时需要检查是否被 tombstone 覆盖；
3. 当 tombstone end key 变为堆顶时，表示该 tombstone 已经失效，后续的 point keys 都会超过它，将其 pop 出堆并从 active 中删除。
---
# Iterator iterface
- 迭代的 item 面向 user key（即不带 seq 和 type）
- 关键方法：
- Valid, status()
- SeekToFirst，SeekToLast，Seek，SeekForPrev
- Next，Prev
- key(), value()
---
# DBIter
- 继承自 Iterator。
- 负责将 InternalIterator 产生的 internal keys 转换为 user keys。
- 处理 key 多版本、deletion markers 、merge 等逻辑。
```mermaid
flowchart LR
InternalIter@{ shape: win-pane, label: "InternalIterator" }
DBIter
User@{ shape: lean-l, label: "User" }
InternalIter -- internal keys --> DBIter
DBIter -- user keys --> User
```
## 核心成员
- **`iter_`**：`IteratorWrapper`，input InternalIteator
- **`version_`**：`Version *`，迭代器创建时当前 Version，构造时传入
- **`sequence_`**：`SequenceNumber`，最大可见 seq。
- 来自 `ReadOptions.snapshot` 或者当前 Version 的 LastSequence()
- **`max_skippable_internal_keys_`**: `uint64_t`
- 来自 ReadOptions，跳过太多 keys 时返回 Incomplete，默认为0表示不启用。
- **`saved_key_`**：`IterKey`
- 存储当前迭代位置的 user key，即 key() 函数会返回 `saved_key_.GetUserKey()`
- 但在 Seek/Next 等函数的调用过程中，可能会指向 delete marker 等
- **`value_`**：`Slice`，存储当前迭代位置的 value，用于 value() 函数返回。
## ParseKey()
- 解析 `iter_.key()` 到 `ikey_` 中，失败则设置 ==`valid_` ==为 false，同时填充 `status_`；
- 返回值：bool，是否成功
## FindNextUserEntryInternal()
- 从当前 `saved_key_`位置开始，查找下一个有效的 user entry（可供迭代器返回的）
- 参数：
- **`skipping_save_key`**：`bool`，是否跳过 `saved_key_` 中保存的 user key
- 典型场景：`saved_key_` 保存了当前迭代位置的 user key，DBIter Next() 时就需要跳过它，找下一个不同的 user key。
- **`prefix`**：`const Slice *`，不为 NULL 表示 prefix scan
- 循环迭代底层 `iter_`，跳过无效的 internal keys
- 如 seq 不可见、delete marker
- `skipping_save_key` 逻辑，跳到下一个 user key
```mermaid
stateDiagram-v2
[*] --> ReadIkey
ReadIkey: 读取 iter_->key() 到 ikey_
ReadIkey --> IsVisible
IsVisible: 当前 ikey_ 是否对 sequence_ 可见
state VisibleState <<choice>>
IsVisible --> VisibleState
VisibleState --> SkipSaved1: 可见
VisibleState --> UpdateUserKey: 不可见
SkipSaved1: 是否需要跳过 saved_key_（skipping_saved_key 为 true 且 ikey_.user_key 小于等于 save_key_ 的 user key）
state SkipState <<choice>>
SkipSaved1 --> SkipState
SkipState --> DoSkip: 是
DoSkip: 跳过当前 internal entry，num_skipped++
SkipState --> CheckType: 否
CheckType: 检查 ikey_.type
state TypeState <<choice>>
CheckType --> TypeState
TypeState --> DeleteType: kTypeDeletion | kTypeSingleDeletion
DeleteType: 跳过当前 user key（将 ikey_.user_key 存入 saved_key，并设置 skipping_saved_key）
TypeState --> ValueType: kValue
ValueType: 找到有效 user entry，存入 saved_key_ 和 value_，结束
ValueType --> [*]
UpdateUserKey: 跳过该 internal entry，选择性更新 saved_key_
state join_state <<join>>
UpdateUserKey --> join_state
DeleteType --> join_state
DoSkip --> join_state
join_state --> AdvanceIter
State AdvanceIter {
CheckReseek: 是否需要 reseek
state ReseekState <<choice>>
CheckReseek --> ReseekState
ReseekState --> DoReseek: 需要
ReseekState --> NextIter: 不需要
NextIter: iter->Next()
DoReseek: iter.Seek(reseek_key)
state join_state2 <<join>>
NextIter --> join_state2
DoReseek --> join_state2
join_state2 --> CheckValid
CheckValid: 检查 iter_->Valid()
}
AdvanceIter --> ReadIkey: 下一轮循环
```
- `num_skipped`：衡量相同的 user key 下，跳过了多少个它的 intenal entries，超出 cf 配置则进行 **reseek**（相对于顺序性扫描并跳过，reseek 可能更高效）。
- `reseek_key`（internal key）的确定：
- 如果 `skipping_saved_key` 为 true，设为 `(saved_key_.user_key, 0, kTypeDeletion)`
- 即同 user key 最后一个 seq 和 type（最小值）
- 否则，设为 `(saved_key_.user_key, sequence_, kValueTypeForSeek)`
- 即同 user key 第一个可见的 internal key
- 每次循环都会进行 TooManyInternalKeysSkipped() 检查：如果循环总次数超过 `ReadOptions.max_skippable_internal_keys`， DBIter 以 Incomplete 状态失败。
## SeekToFirst()
1. 调用 `iter_->SeekToFirst()`
2. 设置 `save_key_` 为 `iter_->key()`
3. 调用 FindNextUserEntry(), 不跳过 `saved_key_`
## SetSavedKeyToSeekTarget(target)
- 将 target user key 设置到 `saved_key_` 中（设置为 internal key 格式）
- user key： `max(iterate_lower_bound_, target)`
- 确保不小于 `iterate_lower_bound_`
- seq： `sequence_`，即创建 iter 时指定的
- type： `kValueTypeForSeek`
## Seek(target)
1. 调用 SetSavedKeyToSeekTarget 将 target 存入 `saved_key_`
2. Seek 底层 iter：`iter_->Seek(saved_key_)`
3. FindNextUserEntry(), 不跳过 `saved_key_`
## Next()
1. Advance 底层 iter：`iter->Next()`
2. FindNextUserEntry(), 跳过 `saved_key_`（需要找下一个跟当前不同的 user key）
## 总结
- 消费 internal enties，返回 user entries
- 处理同 key 多版本、seq 可见性、delete marker 等逻辑
- 同一个 user key 只返回一个最新可见的版本
- reseek 优化
---
# ArenaWrappedDBIter
- 将 DBIter，MergingIterator 及其引用的其他内部 Iterator 都分配在一起，对缓存更友好。
-------
# DBImpl
## NewIterator()
- 创建整个 DB 的 user iterator。
- 流程：
1. 获取并引用 sv
2. 确定读最大可见 seq，来自快照或者 LastSequence)
3. 调用 DBImpl::NewInternalIterator() 创建 DB 级别的 internal iter（MergingIterator）
- 创建 MergingIterator，依次添加以下 child internal iters
- memtable
- immutable memtables
- L0 每个文件创建一个 TableReader iter
- 其余每层创建一个 LevelIterator
- MergingIterator 绑定 sv，实现迭代器析构后 Unref sv（CleanupSuperVersionHandle）
4. 基于 internal iter 创建 DBIter
- 使用 ArenaWrappedDBIter 优化，让 DBIter、所有 internal iters 都分配在同一段连续空间。
----
# TODO
- [ ] readahead_size / prefetch 实现
- [ ] PinnedIteratorsManager
- [x] 迭代器如果防止 memtable 不会被释放
- 引用 sv，memtable 是在其所属的 sv 无引用后才释放。
- [ ] MergingIterator backward 方向的实现
- [ ] DBIter 对 kTypeMerge 处理
- [ ] DBIter backward 方向迭代
## Prefix scan
- [ ] total_order_seek 和 auto_prefix_mode 实现
- [ ] `auto_prefix_mode`
- [ ] [PR: Add ReadOptions.auto_prefix_mode #6314](https://github.com/facebook/rocksdb/pull/6314)
## 实验
- 测试 prefix seek 行为
- [ ] 生成一个只有 tomstones 的 SST