DeleteRange 实现

本文档针对熟悉RocksDB代码基和约定的工程师

Tombstone Fragments 墓碑上的片段

DeleteRange API没有对它可以删除的范围提供任何限制(尽管如果start >= end，被删除的范围将被认为是空的)。 这意味着范围可以重叠并覆盖不同数量的键。用户创建的范围tombstone中缺少结构，因此不可能对范围tombstone进行二值搜索。 例如，假设一个DB包含范围tombstones [c, d)@4， [g, h)@7，和[a, z)@10，我们正在查找键e@1。如果我们分类的墓碑开始键,然后我们会选择(c, d),不包括e。 如果我们排序结束键的墓碑,然后我们会选择[g h),不包括e。然而,我们看到,z)封面e,所以在这两种情况下我们看错了墓碑。 如果我们将墓碑保留为这种形式，我们将不得不扫描所有的墓碑，以便找到一个潜在的覆盖墓碑。随着范围墓碑数量的增加，读取路径上的这种线性搜索开销变得非常昂贵。

但是，可以使用以下洞察力来转换这些tombstone: 一个范围tombstone等价于多个具有相同序列号的连续范围tombstone; 例如，[a, d)@4等价于[a, b)@4;[b, d) @4。使用这个事实，我们总是可以将一个范围tombstone列表”分段”为一组等价的、不重叠的tombstone。 前面的例子,我们可以转换(c, d) @4 (g, h) @7, [a, z) @10: [a、c) @10 (c, d) @10 (c, d) @4 (d、g) @10 (g, h) @10 [g h) @7 [h, @10 z)。

既然tombstone片段没有重叠，我们就可以安全地执行二进制搜索。回到e@1的例子，二分查找会找到[d, g)@10，它覆盖了e@1，从而给出正确的结果。

分裂算法

参阅 db/range_tombstone_fragmenter.cc (https://github.com/facebook/rocksdb/blob/master/db/range_tombstone_fragmenter.cc)

Write Path 写路径

Memtable

当调用DeleteRange时，kv被写到一个专用的memtable中，用于range tombstone。 格式是start: end(即，开始是key，结束是value)。范围墓碑不会直接在memtable中被分割，而是在每次发生读取时被分割。

有关范围tombstone如何刷新为SSTs的详细信息，请参阅压缩。(https://github.com/facebook/rocksdb/wiki/DeleteRange-Implementation#compaction)

SST 文件

就像在memtables中一样，SSTs中的range tombstone不是用点键内联存储的。 相反，它们存储在一个专用的元块中，用于range tombstone。但是，与memtables不同的是，在首次创建表阅读器时，范围墓碑会被分割并与表阅读器一起缓存。 每个SST文件包含该级别的所有范围墓碑，覆盖与文件的键范围重叠的用户键;这极大地简化了迭代器查找和点查找。

有关范围tombstones如何压缩到LSM树的详细信息，请参阅压缩。(https://github.com/facebook/rocksdb/wiki/DeleteRange-Implementation#compaction)

Read Path 读路径

由于写路径的简单性，读路径需要做更多的工作。

Point Lookups 点查询

当用户调用Get并沿着LSM树进行点查找时，要搜索的表中的范围tombstones将首先被分段(如果还没有分段的话)，并在检查文件内容之前进行二进制搜索。这是通过FragmentedRangeTombstoneIterator::MaxCoveringTombstoneSeqnum完成的(参见db/range_tombstone_fragmenter.cc);如果找到一块墓碑(即，返回值为非零)，然后我们知道没有必要搜索更低的级别，因为它们的合并操作数/点值已被删除。我们检查当前级别，查找可能在tombstone片段之后写入的任何键，处理合并操作数(如果有的话)，然后返回。这类似于查找点tombstone停止点查找的过程。

Range Scans 范围扫描

在点扫描期间读取范围删除的关键思想是创建一个类似于DBIter对点键使用的合并迭代器的结构，但是对于正在检查的表集中的范围墓碑。 这里有一个例子来说明这是如何工作的正向扫描(反向扫描是类似的):

考虑一个DB，其中memtable包含tombstone片段[a, b)@40， [a, b)@35，和2个L0文件1.sst 和 2.sst。 1.sst包含墓碑碎片[a, c)@15， [d, f)@20，和 2.sst包含墓碑碎片[b, e)@5， [e, x)@10。 除了memtable和SST文件中点键的合并迭代器，我们还跟踪了以下3种数据结构:

  1. 1.按结束键(活动堆)排序的碎片式tombstone迭代器的最小堆(每个表一个迭代器)
  2. 2.一组按序号排序的碎片式tombstone迭代器(活动seqnum集)
  3. 3.按开始键排序的最小墓碑堆(非活动堆)

活动堆包含指向覆盖最近(内部)查找键的tombstone片段的所有迭代器， 活动seqnum集合包含在活动堆中的迭代器(不过为了简单起见，我们只写出seqnums)，非活动堆包含指向最新查找键之后开始的tombstone片段的迭代器。 注意，迭代器不允许同时位于活动集和非活动集中。

假设DBIter中的内部合并迭代器指向内部键a@4。

活动迭代器将是 1.sst 的tombstone迭代器指向[a, c)@15和指向[a, b)@40的memtable的tombstone迭代器， 惟一不活动的迭代器是针对2.sst的tombstone迭代器指向[b, e] @5。活动seqnum集将包含{40,15}。 从这些数据结构中，我们知道最大的覆盖墓碑的seqnum为40，大于4;因此，删除了a@4，我们需要检查另一个键。

接下来，假设我们检查b@50。

作为响应，活动堆现在包含1.sst的迭代器。指向[a, c)@15 和 2.sst 指向[b, e)@5， 非活动堆不包含任何内容，而活动seqnum集包含{15,5}。

注意，memtable迭代器现在不在范围内，这些数据结构不会跟踪它。(即使memtable迭代器有另一个tombstone片段，但除了它的seqnum(较小)之外，该片段与前一个相同，因此跳过了它)。 因为最大的seqnum是15，所以不包括b@50。

有关实现细节，请参见db/range_del_aggregator.cc (https://github.com/facebook/rocksdb/blob/master/db/range_del_aggregator.cc)。

Compaction 压缩

在刷新和压缩期间，有两个主要操作需要tombstone支持:

  1. 1.识别可以删除的"snapshot stripe(快照条)"(两个相邻快照之间的seqnums范围)中的点键。
  2. 2.将范围墓碑写入输出文件。

对于(1)，我们使用与范围扫描描述的类似的数据结构，但是为每个快照条带创建一个。 此外，在迭代期间，我们跳过那些seqnums不在快照条带范围内的tombstones。

对于(2)，我们从输出文件范围内的所有碎片tombstone迭代器中创建一个合并迭代器， 通过将其传递给碎片处理程序创建一个新的迭代器，并将该迭代器中的每个tombstone片段写入表构建器。

有关实现细节，请参见db/range_del_aggregator.cc ( https://github.com/facebook/rocksdb/blob/master/db/range_del_aggregator.cc )。

文件边界

在只有点键的数据库中，确定SST文件边界非常简单:只需在文件中找到最小和最大的用户键。然而，有了range tombstones，故事就变得更加复杂了。 一个简单的策略是允许范围tombstone的开始和结束键充当文件边界(其中开始键的序列号将是tombstone的序列号，而结束键的序列号将是kMaxSequenceNumber)。 这对于L0文件很好，但是对于较低级别的文件，我们需要确保文件覆盖不相交的内部键范围。如果遇到覆盖许多键的范围特别大的tombstone，我们将被迫创建非常大的SST文件。 为了防止这种情况，我们将文件的最大(用户)密钥限制为不大于下一个文件的最小用户密钥;如果范围tombstone跨在两个文件之间，则将这个最大的键的序列号和类型设置为kMaxSequenceNumber和kTypeRangeDeletion。 实际上，我们假设tombstone不会在下一个文件的开头扩展到过去。

一个值得注意的边缘情况是，两个相邻的文件具有一个用户键，该用户键”跨接”两个文件;也就是说，一个文件的最大用户密钥是下一个文件的最小用户密钥。(这种情况并不常见，但如果快照阻止删除旧版本的密钥，则会发生这种情况) 在这种情况下，即使有范围tombstone覆盖了级别中的这个空白，我们也不会使用上面描述的范围tombstone约定来更改文件边界，因为这将使最大(内部)键比实际值更小。

Range Tombstone Truncation 墓碑截断范围

在过去，如果压缩输入文件包含范围tombstone，我们还会将包含相同范围tombstone的所有其他文件添加到压缩中。 但是，对于特别大的范围tombstone(通常由SQL中删除大表之类的操作创建)，这会创建出乎意料的大压缩。 为了使这些压缩更小，我们允许压缩”clean cut”停在一个文件上，该文件的最大键有一个”range tombstone footer”(kMaxSequenceNumber和kTypeRangeDeletion的序号和类型)。

不幸的是，这与另一个RocksDB优化冲突，如果每个键只有一个版本(在该级别)，则在最底层将所有键seqnums设置为0。 考虑下面的例子:

1.一个DB有三个级别(Lmax == L2)，没有快照，L1中有一个范围tombstone [a, f)@10，和 两个文件1.sst (point internal key range [a@5-c@3])和 L1中的2.sst(point internal key range [e@20-g@7])。 2.如果2.sst 被压缩到L2，它的内部键e@20的seqnum被设置为0。 3.用户创建一个迭代器，并到达e@0(以前是e@20)键。在1.sst中， 墓碑 [a, f)@10 被认为是活动的，由于它的seqnum大于0，它被认为覆盖了e;这是一个错误，因为key应该公开。 为了防止这种情况，我们需要找到一种方法来防止墓碑在1.sst覆盖在2.sst中的键值; 更一般地说，我们需要防止range tombstone能够覆盖文件范围之外的键。这个问题最终导致了一些非常复杂的边缘情况(参见db/db_range_del_test中的测试) ( https://github.com/facebook/rocksdb/blob/master/db/db_range_del_test.cc )。 因此，解决方案有两部分: 1.内部键范围tombstone边界 2.原子压缩单元

内部键范围墓碑边界

为了防止范围tombstone覆盖范围之外的键，一个简单的方法是在文件的用户键边界截断范围tombstone。 但是，range tombstone是end-key独占的，所以即使它们应该覆盖文件中最大的键，在该键处截断它们也会阻止它们这样做。 虽然前面讨论的文件边界扩展逻辑在很多情况下都避免了这个问题，但是当用户键跨在相邻的SST文件上时，两个文件中较小的那个文件中最大的键是一个实点键，因此不适合作为用户键截断点。

一个不太直观的想法是使用内部键作为墓碑边界。在这个扩展下，如果一个键包含在内部键范围中，并且它的seqnum小于tombstone的seqnum(而不是边界seqnums)，那么这个键将被覆盖。 为了提供预期的行为，未截断的tombstones的开始和结束键上都有kMaxSequenceNumber的seqnums。 在前面提到的最大键跨两个SST文件的边缘情况中，我们只使用seqnum比实际最大键小1的内部键作为tombstone边界。 (如果seqnum是0，或者它是一个人工扩展的边界(来自range tombstones)，那么我们忽略这一步: 请参阅db/range_del_aggregator中truncatedrangedelator上的注释，以作解释。) ( https://github.com/facebook/rocksdb/blob/master/db/range_del_aggregator.cc )

原子压缩单位

即使我们使用内存中的内部键作为范围tombstone边界，我们仍然必须在磁盘上使用用户键，因为这是原始格式所要求的。 这意味着在压缩期间，我们必须将一个内部键截断的tombstone转换为一个用户键截断的tombstone。 但是，如果只使用用户键，就会出现与前面描述的问题类似的风险，即实际上覆盖文件中最大键的tombstone会被截断，以不在压缩输出文件中覆盖它。

一般来说，这个问题的解决方案包括在压缩期间将tombstone截断到其文件中最大的键之后。一个简单的想法是在输入级使用压缩边界。 但是，由于我们可以在tombstone结束之前停止压缩(这些更改的主要动机)，我们可能会遇到如下情况:

1.DB有三个级别(Lmax == L2)，没有快照， 而tombstone [a, g)@10被分割到两个L1文件中: 1.sst (point key range [a@4-c@6]) 和 2.sst (point key range [e@12-k@7]) 2.向compact 2发出L1-L2压缩。2.sst下降到L2。键e@12保留在输出文件3中。并将其seqnum设置为0。 3.稍后将为compact 1发布另一个L1-L2压缩。1.sst下降到L2，键值范围[a-f]，也拉入3.sst。 范围tombstone被截断为[a, f)@10，因此e@0键(以前的e@12)被认为是由tombstone覆盖的，这是不正确的。

这个问题的根源在于，跨文件复制的tombstone可以放在具有重叠边界的不同压缩中。 要解决这个问题，我们必须为所有涉及这些文件的压缩选择不相交的边界，我们称之为原子压缩单元边界。 这些边界恰好跨越一个或多个具有重叠边界的文件(具有范围tombstone end键作为其最大键的文件不会被认为与下一个文件重叠)，并在压缩时计算。 使用原子压缩单元边界，我们允许将文件的结束键包含在截断范围tombstone的边界中，同时还防止这些边界包含来自以前压缩的键。

有关实现细节，请参见db/compact.cc (https://github.com/facebook/rocksdb/blob/master/db/compaction.cc)