rocksdb-deleterange-wiki - JonahGao's Notes

- https://github.com/facebook/rocksdb/wiki/DeleteRange-Implementation#tombstone-fragments # Tombstone Fragments - 问题：原始的 range tombstones 相互重叠无法二分搜索 - 例如 `[c, d)@4`, `[g, h)@7` 和 `[a, z)@10`，查找 `e@1` - 无论按 start key 还是 end key 排序后二分搜索都无法找到 `[a, z)@10` - 如果使用 linear search，开销又会很大 - 解决：将 tombstone 切分为 seq 相同的多个连续区间即 fragment，让 framgments 之间无重叠 - 例如 `[a, d)@4`可等价拆分为 `[a, b)@4` 和 `[b, d)@4`。 - 上述的例子中可拆分为： - `[a, c)@10`，`[c, d)@4`， `[c, d)@10`，`[d, g)@10`，`[g, h)@10`，`[g, h)@7`， `[h, z)@10` - 算法： db/range_tombstone_fragmenter.cc. --- # WritePath ## Memtable - 写入到一个专用的 memtable，格式为 `start : end` - 写入时不进行 fragment，而是在读的时候进行 fragment。 ## SST Files - 存储到专门的 tombstones meta-block 中。 - 与 memtable 不同，写入的是 fragmented 之后的。 - 第一个创建 table reader 时，会对 fragment 进行缓存。 --- # Read Path ## Point Lookups - 先检查 `FragmentedRangeTombstoneIterator::MaxCoveringTombstoneSeqnum()` - 如果找到了 tombstone，则不需要搜索 lower levels，因为他们的 merge operands / point values 都被删除了 - 只需要处理在 tombstone 之后写入的数据 ## Range Scans - 以 forward scan 为例，需要维护三个数据结构： - **active heap**：按 end key 排序，fragmented tombstone iterators（**每 table 一个**）的小顶堆 - **active seqnum**：按 seq 排序，fragmented tombstone iterators 的有序集合 - **inactive heap**：按 start key 排序的 tombstone小顶堆 - active heap - 其中的迭代器都指向了覆盖了最近 lookup ikey 的 tombstone fragments。 - actvie seqnum： - 包含了 active heap 中的迭代器，虽然只使用它们的序列号 - inactive heap： > contains iterators pointing at tombstone fragments that start after the most recent lookup key - 其中的迭代器指向了最近 lookup ikey 之后的 tombstone fragments - 一个迭代器不能同时出现在 active 和 inactive set 中。 ```mermaid block-beta columns 1 MemTable["Memtable \n[a, b)@40\n[a, b)@35\n ."] block: L0 1.sst["1.sst \n[a, c)@15\n[d, f)@20\n ."] 2.sst["2.sst \n[b, e)@5\n[e, x)@10\n ."] end ``` - 示例图：一个 memtable，两个 **L0** 文件。 - 例如 DBIter 中的 merging iterator 指向 ikey `a@4`： - active iteratorss 将会包含： - `1.sst`的 tombstone iterator 指向了 `[a, c)@15` - memtable tombstone iterator 指向了 `[a, b)@40` - inactive iterators： - `2.sst` 的 tombstone iterator 指向 `[b, e)@5` - active seqnum set：`{15, 40}` - 从以上结构可以得知，最大的 covering tombstone 拥有 seqnum 40，大于 4，因此 `a@4` 被删除了，我们需要检查另外一个 key。 - 接下来我们检查 `b@50` - active heap： - `1.sst` tombstone iterator 指向 `[a, c)@15` - `2.sst` 指向 `[b, e)@5` - inactive heap 为空 - active seqnum set: `{5, 15}` - 因此最大的 covering tombstone 拥有 seqnum 15，`b@50`没有被覆盖 - 详细实现：[db/range_del_aggregator.cc](https://github.com/facebook/rocksdb/blob/main/db/range_del_aggregator.cc) --- # Compaction - 在 flush 和 compactions，range tombstones 需要支持两个主要的操作： 1. 识别位于 snapshot stripe 中可以被删除的 point keys - snapshot stripe：两个相邻的快照的 seqnum 范围 2. 往 output file 中写入 range tombstones - 对于 1 ，使用跟 range scans 相同的数据结构，但是每个 snapshot stripe 一个。 - 迭代时跳过不在 snapshot stripe seq range 中的 tomebstones - 对于 2，创建一个 merging iterator，包含了在 output file 范围内的所有 fragmented tombstone iterator，创建 table builder 的 iterator 时传入它。 ## File Boundaries - 如果只有 point keys 数据，确定 SST file 的边界非常直观，只需要找到文件中最小和最大的 user key 即可。 - 但对于 range tombstones，就会变得复杂，一种简单策略是允许 tombstone 的 start 和 end key 扮演文件边界： - start key 的 seqno 为 tombstone 的 seqno - end key 的 seqno 为 `kMaxSequenceNumber`（同 user key 中第一个 ikey） - 对于 L0 文件没有问题，但是其它对于层次需要保证各个文件范围不重叠。 - 如果 tombstone 范围很大，覆盖很多 keys，会导致创建非常大的 SST 文件。 - 为了解决这个问题，我们限制一个文件的最大 user key 不大于下一个文件的最小 user key - 如果一个 range tombstone 跨越两个文件，文件最大 key 的 seq 和 type 会被设置为 `kMaxSequenceNumber` 和 `kTypeRangeDeletion` - 即假装 tombstone 不会超过下一个文件的起始 - edge case：某个 user key 跨越了两个相同的文件，即一个文件的最大 ukey 是下一个文件的最小 ukey - 在这种情况下，即使有 tombstone 覆盖了这个间隙，也不会改变文件的边界。 ## Range Tombstone Truncation - 在过去，如果一个 compaction input file 包含了一个 range tombstone，我们会将包含相同 tombstone 的其它文件也加入到 compaction。 - 问题：对于范围特别大的 tombstone，会导致非常大的 compaction。 - 解决：clean cut 停止在最大 key 具有 range tombstone footer 的文件 - footer: (kMaxSequenceNumber, kTypeRangeDeletion) - 但这与 RocksDB 的另一个优化有冲突：将 bottommost level 所有 key seqs 设置为0，如果这些 key 在该 level 只有一个版本。考虑以下例子： - DB 有三个 levels（Lmax 为 2），没有快照。 - L1 有一个 range tombstone `[a, f)@10` - L1 有两个文件： - `1.sst`范围 `[a@5, c@3]` - `2.sst`范围 `[e@20, g@7]` - 如果 `2.sst` compacted 到 L2，它的内部 key `e@20` seqnum 会被设置为 0 - 用户创建迭代器并扫描到 `e@0` 时， `1.sst`中的 tombstone `[a, f)@10`被认定为 active，并且覆盖了 `e` ，导致 e 被错误认定为删除了。 - 为了防止这种情况，我们需要找到一种方法来防止 `1.sst` 中的 tombstone 覆盖 `2.sst` 中的 keys。更普遍地说，需要防止 range tombstones 覆盖他们所需文件的范围之外的 keys。 - 方案分为两个部分： - internal key range tombstone boundaries - atomic compaction units ## Iternal Key Range Tombstone Boundaries - 直观的想法：按照文件的 user key boundaries 截断 range tombstone - 问题：range tombstones 的 end key 是 exclusive 的，所以即使他们应该覆盖文件中的最大 key，截断后就不行了。 - 一个不直观的想法是使用 internal keys 作为 range tombstone boundaries。 - [ ] 对于前面 largest key 跨越两个 SST 文件的场景，tomebstone boundary 的 seqnum 为 largest key 的减一。 - 详细解释见 `TruncatedRangeDelIterator` 的注释 ## Atomic Compaction Units - 即使我们在内存中使用 internal keys 作为 range tombstone boundaries，在磁盘上我们仍然需要使用 user keys，因为这是原始格式所要求的。 - 这意味着在 compaction 时，需要将 internal key-truncated tombstone 转换为 user key-truncated tombstone。这就意味着之前的问题会重现。 - 从广义上讲，解决此问题的方法是在 compaction 截断 tombstone 时，使其超过文件的最大键。 - 一种简单的想法是使用 input level 的 compaction boundaries，但是由于我们可以在 tombstone 结束之前停止 compaction，我们可能会遇到如下情况： 1. DB 有三个 levels，无快照。tombstone `[a, g)@10`分割在两个 L1 文件之间： - `1.sst`范围 `[a@4, c@6]` - `2.sst`范围 `[e@12, k@7]` 2. compact `2.sst` 到 L2，key `e@12`输出到 `3.sst`并且 seqnum 被设置为 0 3. 另一个 compaction 将 `1.sst` compact 到 L2，范围为 `[a, f)`，这也引入了 `3.sst`. range tombstone 被截断为 `[a, f)@10`，可以覆盖 `e@0`，导致被错误地认定被 tombstone 覆盖。 - 问题的根源在于一个重复存在于多个文件的 tombstone，可以出现在边界重叠的不同 compactions 中。 - 为了解决这个，我们必须为涉及这些文件的所有 compactions 选择不相交的边界，我们称之为atomic compaction unit boundries。