RocksDB 范围删除Range Deletion处理机制深入解析从 Tombstone 碎片化到点查与迭代器集成【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb范围删除DeleteRange()是 RocksDB 中以较低成本批量删除一段连续键空间的核心能力其背后的 tombstones 处理贯穿了 LSM 树的点查Point Lookup、迭代Iterator与压缩Compaction三大路径。本文以 docs/components/read_flow/08_range_deletions.md 为主线结合 db/range_del_aggregator.h、db/range_del_aggregator.cc、db/range_tombstone_fragmenter.h、table/get_context.cc 等源码完整讲解 tombstone 的分裂存储、文件边界截断、点查的序列号比较优化以及迭代器侧的堆式活跃追踪算法读完你可以掌握 RocksDB 内部如何保证被范围删除覆盖的键在任何读取路径下都不可见这一核心语义。概览两种读路径两种集成策略DeleteRange(start, end)写入的是覆盖[start, end)键区间的 tombstone每个 tombstone 带有写入时的序列号。为了让这些 tombstone 真正生效RocksDB 必须在两条读路径上分别处理点查Point Lookup采用轻量的max_covering_tombstone_seq序列号比较不做完整聚合迭代器Iterator采用完整的RangeDelAggregator基于堆BinaryHeap实时追踪活跃 tombstone集合。两条路径共享同一个底层设施tombstone 碎片化Fragmentation与文件边界截断File Boundary Truncation。下面先看这两层基础设施再分别进入点查与迭代器路径。RangeDelAggregator 架构抽象基类与两种实现RangeDelAggregator定义见 db/range_del_aggregator.h是范围删除聚合的抽象接口核心虚方法包括AddTombstones()注入来自某个 SST 文件或 memtable 的 tombstone 迭代器与ShouldDelete()判定某个内部键是否被 tombstone 覆盖。它有两个具体实现实现使用场景策略ReadRangeDelAggregator点查与迭代器读取单一 stripe覆盖序列号区间[0, snapshot_seqno]CompactionRangeDelAggregator压缩Compaction多个 stripe按 snapshot 边界切分序列号区间从源码看ReadRangeDelAggregator内部仅持有一个StripeRep其upper_bound由构造函数传入通常是读取时的 snapshot 序列号lower_bound固定为 0见 db/range_del_aggregator.h。而CompactionRangeDelAggregator持有std::mapSequenceNumber, StripeRep reps_在AddTombstones()中通过SplitBySnapshot()把每个 tombstone 迭代器按 snapshot 切分成多个子迭代器再按上界归入对应的 stripe见 db/range_del_aggregator.cc。其ShouldDelete()用reps_.lower_bound(parsed.sequence)先定位到包含该序列号的 stripe再做判定——这样压缩时每个 snapshot 区间内只关心该区间内可见的 tombstone从而能安全地把被覆盖的旧版本数据丢弃。每个StripeRep内嵌一对正/反向迭代器ForwardRangeDelIterator与ReverseRangeDelIterator见 db/range_del_aggregator.h分别服务RangeDelPositioningMode::kForwardTraversal正向扫描与kBackwardTraversal反向扫描并在切换方向时通过Invalidate()使另一方向的迭代器失效见 db/range_del_aggregator.cc。Tombstone 碎片化把重叠区间切成互不重叠的片段tombstone 只有被切分成互不重叠的片段才能支持高效的序列号查找。FragmentedRangeTombstoneList见 db/range_tombstone_fragmenter.h完成这一任务它读取未碎片化的 tombstone 迭代器通过FragmentTombstones()把所有 tombstone 的起止键作为切分点产出若干RangeTombstoneStack。每个 stack 共享同一对[start, end)用户键但内部保存了一组按序列号降序排列的tombstone 序列号用seq_start_idx/seq_end_idx索引到tombstone_seqs_向量中实现同一区间多版本 tombstone 的紧凑存储。以下面的输入为例输入存在重叠[a, e) seq10[c, g) seq15[f, z) seq5输出碎片化后互不重叠片段序列号集合[a, c)10[c, e)10, 15[e, f)15[f, g)15, 5[g, z)5碎片化带来的收益很直接片段之间零重叠每个点键至多命中一个片段查询可以二分定位片段内部序列号有序FragmentedRangeTombstoneIterator::SetMaxVisibleSeqAndTimestamp()用std::lower_bound在降序序列号数组中快速找到 upper_bound_的最大可见序列号见 db/range_tombstone_fragmenter.h存储紧凑共享起止键的多个 tombstone 只存一份 key 区间序列号放入连续数组。需要特别说明的是FragmentedRangeTombstoneIterator的构造路径比旧式RangeDelAggregator的 tombstone 折叠更高效——若输入迭代器本身有序碎片化是 O(n)而旧的折叠算法始终是 O(n log n)。这一点在 db/range_tombstone_fragmenter.h 的注释中有明确说明。此外每个 SST 的 range-del meta block 的碎片化结果会被缓存在FragmentedRangeTombstoneListCache见 db/range_tombstone_fragmenter.h中首个读者加锁初始化后续读者通过std::atomicbool initialized直接读取避免重复碎片化。文件边界截断tombstone 不得泄漏到相邻文件LSM 树中同一个用户键可能横跨多个 SST 文件若 tombstone 跨越文件边界就可能在边界处误删相邻文件中的键。TruncatedRangeDelIterator定义见 db/range_del_aggregator.h实现见 db/range_del_aggregator.cc解决此问题区间钳制tombstone 的范围被截断到源文件的[smallest, largest)内部键区间序列号调整一般情况下对largest.sequence - 1。原因在于同一个用户键可能恰好是前一文件的largest与后一文件的smallest递减 1 可确保截断后的结束键不会覆盖下一文件中同用户键的键。注释中说明这是为保证截断的结束键能覆盖本文件中最大的键见 db/range_del_aggregator.cc两个例外不调整当文件边界是被 range tombstone人为扩展的kTypeRangeDeletion且sequence kMaxSequenceNumber时无需调整当largest.sequence 0时由于同一 DB 中不可能存在同用户键同序列号的两个内部键可以确定本文件的largest不会出现在下一文件因此也无需调整。截断后Valid()还会再次校验当前 tombstone 与截断边界的相对位置见 db/range_del_aggregator.cc。核心不变量range tombstone 一律在文件边界处被截断杜绝删除跨文件泄漏。点查集成一次序列号比较代替完整聚合点查不需要构建完整的RangeDelAggregator而是走一条更轻的路径整个流程分三步Step 1计算最大覆盖序列号。在TableCache::Get()中对每个命中的 SST 文件通过该文件 tombstone 迭代器的MaxCoveringTombstoneSeqnum(user_key)计算出覆盖该用户键的 tombstone 的最大序列号若无可返回 0。该方法定义在 db/range_tombstone_fragmenter.h 附近。批量场景MultiGet则由TableCache::UpdateRangeTombstoneSeqnums()对每个 key 一次性计算并更新到GetContext见 db/table_cache.cc。Step 2跨文件追踪最大值。在所有被搜索的文件间维护一个全局的max_covering_tombstone_seq取各文件计算结果的最大值。这个值通过GetContext的构造参数传入见 db/version_set_sync_and_async.h。Step 3SaveValue 中做最终判定。在GetContext::SaveValue()中见 table/get_context.cc当找到候选点键后若max_covering_tombstone_seq ! nullptr且*max_covering_tombstone_seq parsed_key.sequence说明该点键的序列号低于覆盖它的 tombstone属于已被删除此时type被改写为kTypeRangeDeletion走删除处理分支。同时 table/get_context.cc 会把返回的seq_更新为max(*seq_, *max_covering_tombstone_seq)保证调用方拿到的是 tombstone 的序列号。这条路径用一次序列号比较替代了完整的RangeDelAggregator构建是点查性能的关键设计。提前终止优化。在Version::Get()实现在 db/version_set_sync_and_async.h中文件搜索循环的顶部调用下一个文件的TableCache::Get()之前会检查while (f ! nullptr) { if (*max_covering_tombstone_seq 0) { // 剩余文件里只可能包含被覆盖的键直接停止搜索 break; } ... *status CO_AWAIT(table_cache_-Get, ...); }其正确性依据是RocksDB 按 LSM 层次组织文件越靠下更深层的文件序列号越低既然当前已经存在一个覆盖该键且序列号更高的 tombstone那么任何更深层文件中同键的条目都必然被它覆盖继续搜索没有意义。memtable 侧同样应用该优化MemTable::Get在发现max_covering_tombstone_seq已覆盖目标键时也会相应短路处理见 db/memtable.cc 附近的序列号钳制逻辑。迭代器集成注册、过滤与级联 Seek迭代器需要把 tombstone 完整地并入MergingIterator的归并逻辑共三步Step 1注册Registration。每个子点迭代器与其对应的TruncatedRangeDelIterator通过MergeIteratorBuilder::AddPointAndTombstoneIterator()配对见 table/merging_iterator.cc。tombstone 迭代器作为哨兵条目与点键一起进入归并堆。Step 2过滤Filtering。MergingIterator::SkipNextDeleted()见 table/merging_iterator.cc在把候选点键暴露给DBIter之前先与当前活跃的 tombstone 集合比对。堆中有三类条目点键、文件边界哨兵键、range deletion 结束键。当堆顶是DELETE_RANGE_END时把对应层从活跃集合active_中移除并推进该 tombstone 迭代器当堆顶是文件边界哨兵键时清理旧文件的 tombstone 状态为进入新文件做准备。每次跳过被覆盖键都会累加internal_range_del_reseek_count性能计数见 table/merging_iterator.cc。Step 3级联 SeekCascading Seeks。若点键被覆盖迭代器会直接 seek 到该 tombstone 的结束键之后。但新的位置可能又被来自另一个层的 tombstone 覆盖于是触发新一轮 seek——这就是级联 seek。它保证了最终暴露给用户的键一定不被任何活跃 tombstone 覆盖。ShouldDelete 算法堆驱动的活跃集合维护ForwardRangeDelIterator::ShouldDelete()实现见 db/range_del_aggregator.cc是正向扫描时判定点键是否被覆盖的核心算法其数据结构与规则如下数据结构active_seqnums_按序列号降序排列的 multiset最高者在顶记录当前活跃 tombstone 的序列号active_iters_按结束键排序的BinaryHeap负责追踪哪些 tombstone 到当前位置已不再覆盖inactive_iters_按开始键排序的BinaryHeap负责追踪哪些 tombstone 从当前位置开始生效。算法步骤过期Expire弹出active_iters_中所有结束键 当前键的 tombstone将其从活跃集合移除并推进到下一个片段激活Activate弹出inactive_iters_中所有开始键 当前键的 tombstone加入活跃集合判定若active_seqnums_非空且其最大序列号 点键的序列号则该键被删除。复杂度每次查询均摊 O(log K)其中 K 为 range tombstone 数量。每个 tombstone 在一次正向扫描中至多被激活一次、过期一次因此总代价可控。反向扫描由ReverseRangeDelIterator::ShouldDelete()以对称方式实现见 db/range_del_aggregator.cc堆的排序方向相应取反。核心不变量一个点键被删除当且仅当存在一个序列号更高的 range tombstone 覆盖它。这一不变量在点查max_covering_tombstone_seq parsed_key.sequence与迭代器(*active_seqnums_.begin())-seq() parsed.sequence两条路径上以同一种序列号大小比较的形式落地。补充用户自定义时间戳与压缩侧的细节当前仓库的实现在两个维度上进一步扩展了上述机制用户自定义时间戳User-Defined Timestamp启用后tombstone 的 start/end 是携带时间戳的用户键FragmentedRangeTombstoneList会额外维护tombstone_timestamps_数组SetMaxVisibleSeqAndTimestamp()同时用序列号上界和时间戳上界ts_upper_bound_过滤可见性见 db/range_tombstone_fragmenter.h点查侧在时间戳场景下还会从 tombstone 回填时间戳见 table/get_context.cc。压缩侧CompactionCompactionRangeDelAggregator的NewIterator()通过内部类TruncatedRangeDelMergingIter见 db/range_del_aggregator.cc把各文件的截断 tombstone 按开始键归并成有序流再重新碎片化并持久化输出构造FragmentedRangeTombstoneList时传入for_compaction true与 snapshots从而丢弃任何 snapshot 都不可见的 tombstone 片段实现压缩对 tombstone 的淘汰。小结RocksDB 的范围删除处理可以概括为一条清晰的因果链DeleteRange()写入的 tombstone 先经FragmentedRangeTombstoneList碎片化为互不重叠、序列号有序的片段每个 SST 的 tombstone 经TruncatedRangeDelIterator在文件边界截断防止跨文件泄漏点查路径用MaxCoveringTombstoneSeqnum算出max_covering_tombstone_seq在GetContext::SaveValue()中一次比较完成删除判定并在Version::Get()中利用该值提前终止低层文件搜索迭代器路径通过RangeDelAggregator 堆驱动的ForwardRangeDelIterator::ShouldDelete()实时维护活跃 tombstone配合SkipNextDeleted()的过滤与级联 seek保证暴露给用户的每个键均不被覆盖压缩路径按 snapshot 分 stripe 判定并在输出时淘汰不可见的 tombstone 片段。相关测试可进一步参考 db/range_del_aggregator_test.cc 与 db/range_tombstone_fragmenter_test.cc它们覆盖了碎片化正确性、边界截断、正反向扫描等关键场景。理解这套机制是深入调试 RocksDB 读取路径、评估DeleteRange性能影响例如大量 tombstone 导致的点查与迭代成本的前提。【免费下载链接】rocksdbA library that provides an embeddable, persistent key-value store for fast storage.项目地址: https://gitcode.com/gh_mirrors/ro/rocksdb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考