合并操作实现

合并操作实现

这个页面描述了RocksDB合并特性的内部实现细节。它的目标是专业的RocksDB工程师和/或其他Facebook工程师谁有兴趣了解如何合并工作。

| 如果您是RocksDB的用户，并且只想知道如何在生产中使用Merge，请转到客户机界面页面。否则，假定您已经阅读了该页。

Context 上下文

这里是一个高层次的概述，代码更改，我们需要实现合并:

我们创建了一个抽象基类MergeOperator，用户需要从中继承。
我们更新了Get()、iteration和compact()调用路径，以便在必要时调用合并操作符的FullMerge()和PartialMerge()函数。
需要做的主要更改是实现合并操作数的”叠加”，我们将在下面描述。
我们引入了一些其他的接口更改(例如:更新Options类和DB类以支持合并操作符)
我们创建了一个更简单的AssociativeMergeOperator，使用户在一个非常常见的用例下生活得更轻松。注意，这可能效率更低。

对于读者来说，如果上面的任何语句在高层没有意义，那么您可能应该首先阅读Client Interface页面。( https://github.com/facebook/rocksdb/wiki/Merge-Operator ) 否则，我们将直接深入到下面的细节，并讨论一些设计决策和选择实现的基本原理。

Interface 接口

快速重复界面(假设读者对界面已经比较熟悉):

// The Merge Operator
//
// Essentially, a MergeOperator specifies the SEMANTICS of a merge, which only
// client knows. It could be numeric addition, list append, string
// concatenation, edit data structure, ... , anything.
// The library, on the other hand, is concerned with the exercise of this
// interface, at the right time (during get, iteration, compaction...)
class MergeOperator {
 public:
  virtual ~MergeOperator() {}
  // Gives the client a way to express the read -> modify -> write semantics
  // key:         (IN) The key that's associated with this merge operation.
  // existing:    (IN) null indicates that the key does not exist before this op
  // operand_list:(IN) the sequence of merge operations to apply, front() first.
  // new_value:  (OUT) Client is responsible for filling the merge result here
  // logger:      (IN) Client could use this to log errors during merge.
  //
  // Return true on success, false on failure/corruption/etc.
  virtual bool FullMerge(const Slice& key,
                         const Slice* existing_value,
                         const std::deque<std::string>& operand_list,
                         std::string* new_value,
                         Logger* logger) const = 0;
  // This function performs merge(left_op, right_op)
  // when both the operands are themselves merge operation types.
  // Save the result in *new_value and return true. If it is impossible
  // or infeasible to combine the two operations, return false instead.
  virtual bool PartialMerge(const Slice& key,
                            const Slice& left_operand,
                            const Slice& right_operand,
                            std::string* new_value,
                            Logger* logger) const = 0;
  // The name of the MergeOperator. Used to check for MergeOperator
  // mismatches (i.e., a DB created with one MergeOperator is
  // accessed using a different MergeOperator)
  virtual const char* Name() const = 0;
};

RocksDB数据模型

在详细介绍merge的工作原理之前，让我们先来了解一下RocksDB的数据模型。

简而言之，RocksDB是一个版本化的键值存储。对数据库的每次更改都是全局有序的，并分配一个单调递增的序列号。对于每个键，RocksDB保存操作历史。我们将每个操作表示为OPi。经历n次更改的键(K)在逻辑上看起来是这样的(物理上，更改可能在活动memtable、不可变memtable或级别文件中)。

K:   OP1   OP2   OP3   ...   OPn

一个操作有三个属性:它的类型——要么是Delete要么是Put(现在我们也有了Merge)，它的序号和值(Delete可以作为没有值的简并情况处理)。序列号将会增加，但对于单个键来说不是连续的，因为它们是由所有键全局共享的。

当客户端发出db->Put或db->Delete时，库实际上会将该操作附加到历史记录中。不检查现有值，可能是出于性能考虑(如果键不预先存在，那么Delete将保持静默，这也就不足为奇了……)

db->Get呢?它返回键相对于时间点(由序列号指定)的状态。键的状态可以是不存在的，也可以是不透明的字符串值。它以不存在开始。每个操作都将密钥移动到一个新状态。从这个意义上说，每个键都是一个状态机，操作作为转换。

从状态机的角度来看，Merge实际上是一个泛型转换，它查看当前状态(现有值，或不存在该值)，将其与操作数(与合并操作关联的值)组合在一起，然后生成一个新值(状态)。 Put是归并的简并情况，它不关注当前状态，仅根据操作数生成新状态。 Delete更进一步——它甚至没有操作数，并且总是将键恢复到原来的状态——不存在。

Get

在主体中，Get返回键在特定时间的状态。

K:   OP1    OP2   OP3   ....   OPk  .... OPn
                            ^
                            |
                         Get.seq

假设OPk是最近可见的操作:

k = max(i) {seq(OPi) <= Get.seq}

然后，如果OPk是Put或Delete, Get应该简单地返回指定的值(如果Put)或NotFound状态(如果Delete)。它可以忽略以前的值。

使用新的合并操作，我们实际上需要向后看。我们能走多远?直到Put或Delete(超过此值的历史记录都不是必需的)。

K:   OP1    OP2   OP3   ....    OPk  .... OPn
            Put  Merge  Merge  Merge
                                 ^
                                 |
                              Get.seq
             -------------------->

对于上面的例子，Get应该返回如下内容:

Merge(...Merge(Merge(operand(OP2), operand(OP3)), operand(OP4)..., operand(OPk))))

在内部，RocksDB从新的到旧的遍历关键历史。RocksDB的内部数据结构支持一个很好的“二进制搜索”样式的查找函数。因此，如果提供一个序列号，它实际上可以返回:k = max(i) {seq(OPi) <= Get。seq}相对有效。然后，从OPk开始，它将按照前面提到的那样从new到old遍历历史，直到找到Put/Delete。

为了实际执行合并，rocksdb使用了两个指定的合并操作符方法:FullMerge()和PartialMerge()。客户端接口页提供了关于这些函数在高层含义的良好概述。但是，为了完整起见，应该知道PartialMerge()是一个可选函数，用于将两个合并操作(操作数)合并到一个操作数中。例如，将OP(k-1)与OPk结合起来生成一些OP’，这也是一种合并操作类型。当PartialMerge()不能组合两个操作数时，它返回false，向rocksdb发送信号来处理操作数本身。这是怎么做到的?在内部，rocksdb提供了一个类似于内存堆栈的数据结构(实际上我们使用STL Deque)来堆栈操作数，保持它们的相对顺序，直到找到Put/Delete，在这种情况下，FullMerge()用于将操作数列表应用到基值上。

Get()的算法如下:

Get(key):
  Let stack = [ ];       // in reality, this should be a "deque", but stack is simpler to conceptualize for this pseudocode
  for each entry OPi from newest to oldest:
    if OPi.type is "merge_operand":
      push OPi to stack
        while (stack has at least 2 elements and (stack.top() and stack.second_from_top() can be partial-merged)
          OP_left = stack.pop()
          OP_right = stack.pop()
          result_OP = client_merge_operator.PartialMerge(OP_left, OP_right)
          push result_OP to stack
    else if OPi.type is "put":
      return client_merge_operator.FullMerge(v, stack);
    else if v.type is "delete":
      return client_merge_operator.FullMerge(nullptr, stack);
  // We've reached the end (OP0) and we have no Put/Delete, just interpret it as empty (like Delete would)
  return client_merge_operator.FullMerge(nullptr, stack);

因此，RocksDB将”堆叠”这些操作，直到它到达Put或Delete(或键历史记录的开始)，然后调用用户定义的FullMerge()操作，并使用作为参数传入的操作序列/堆栈。因此，在上面的例子中，它将从OPk开始，然后转到OPk-1，…等。当RocksDB遇到OP2时，它的堆栈看起来像[OP3, OP4，…(OP3是堆栈的前端/顶部)。然后它将调用用户定义的合并操作符::FullMerge(key, existing_value = OP2, operands = [OP3, OP4，…OPk])。这应该将结果返回给用户。

Compaction 压缩

接下来是有趣的部分，rocksdb最关键的后台过程。压缩是在不影响任何外部可见状态的情况下缩短键的历史的过程。什么是外部可见状态?快照基本上是由序列号表示的快照。让我们来看一个例子:

K:   OP1     OP2     OP3     OP4     OP5  ... OPn
              ^               ^                ^
              |               |                |
           snapshot1       snapshot2       snapshot3

对于每个快照，我们可以将支持操作定义为快照可见的最新操作(OP2是snapshot1的支持操作，OP4是snapshot2的支持操作……)。

显然，在不影响外部可观察状态的情况下，我们不能删除任何支持操作。其他操作呢?在引入合并操作之前，我们可以告别所有不支持的操作。在上面的例子中，完全压缩会将K的历史减少到OP2 OP4和OPn。原因很简单:Put和Delete是快捷方式，它们隐藏了以前的操作。

使用merge，过程有点不同。即使某些合并操作数不支持任何快照，我们也不能简单地删除它，因为稍后的合并操作可能会依赖于它的正确性。而且，实际上，这意味着我们甚至不能删除过去的Put或Delete操作，因为以后可能会有依赖于它们的merge操作数。

那么我们该怎么做呢?我们从最新的操作数开始，”堆积”(和/或部分合并)合并操作数。我们会在下列任何一种情况下停止堆叠及处理堆叠(以先发生的情况为准):

1.遇到Put/Delete—我们调用FullMerge(value或nullptr, stack)
2.遇到键历史结束—我们调用FullMerge(nullptr, stack)
3.遇到支持操作(快照)—请参见下面
4.遇到文件结束-请参见下面

前两种情况或多或少类似于Get()。如果看到Put，调用FullMerge(Put的值，堆栈)。如果你看到一个删除，同样的。

然而，压缩引入了两种新的情况。首先，如果遇到快照，我们必须停止合并过程。当发生这种情况时，我们只需写出未合并的操作数，清除堆栈，并继续压缩(从支持操作开始)。类似地，如果我们已经完成了压缩(“文件结束”)，我们不能简单地应用FullMerge(nullptr, stack)，因为我们可能没有看到键历史的开始;在某些文件中可能有一些条目恰好没有包含在压缩中。因此，在本例中，我们还必须简单地写出未合并的操作数，并清除堆栈。在这两种情况下，所有合并操作数都变成”支持操作”，并且不能删除。

这里部分合并的作用是促进压缩。由于很有可能达到支持的操作或文件末尾，所以很有可能大多数合并操作数在很长一段时间内不会被压缩。因此，支持部分合并的合并操作符使压缩变得更容易，因为剩余的操作数不会被堆叠，而是在写入新文件之前被合并为单个合并操作数。

Example

当我们提出规则时，让我们看一个具体的例子。假设计数器K从0开始，经过一系列加法运算，被重置为2，然后再经过一些加法运算。现在一个完整的压缩已经完成(一些外部可见的快照已经就位)——会发生什么?

(注意:在这个例子中，我们假设了结合律，但是没有部分归并的概念也是一样的)

K:    0    +1    +2    +3    +4     +5      2     +1     +2
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
We show it step by step, as we scan from the newest operation to the oldest operation
K:    0    +1    +2    +3    +4     +5      2    (+1     +2)
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
A Merge operation consumes a previous Merge Operation and produces a new Merge operation (or a stack)
      (+1  +2) => PartialMerge(1,2) => +3
K:    0    +1    +2    +3    +4     +5      2            +3
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
K:    0    +1    +2    +3    +4     +5     (2            +3)
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
A Merge operation consumes a previous Put operation and produces a new Put operation
      (2   +3) =>  FullMerge(2, 3) => 5
K:    0    +1    +2    +3    +4     +5                    5
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
A newly produced Put operation is still a Put, thus hides any non-Supporting operations
      (+5   5) => 5
K:    0    +1    +2   (+3    +4)                          5
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
(+3  +4) => PartialMerge(3,4) => +7
K:    0    +1    +2          +7                           5
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
A Merge operation cannot consume a previous Supporting operation.
       (+2   +7) can not be combined
K:    0   (+1    +2)         +7                           5
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
(+1  +2) => PartialMerge(1,2) => +3
K:    0          +3          +7                           5
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
K:   (0          +3)         +7                           5
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3
(0   +3) => FullMerge(0,3) => 3
K:               3           +7                           5
                 ^           ^                            ^
                 |           |                            |
              snapshot1   snapshot2                   snapshot3

总结一下:在压缩过程中，如果支持的操作是Merge，那么它将组合以前的操作(通过部分Merge或堆叠)，直到

达到了另一个支持操作(换句话说，我们越过了快照边界)
到达Put或Delete操作时，我们将合并操作转换为Put。
键历史记录结束，在这里我们将合并操作转换为Put
到达压缩结束文件时，我们将其视为跨越快照边界

注意，我们假设合并操作在上面的示例中定义了PartialMerge()。对于没有PartialMerge()的操作，操作数将在堆栈上组合，直到遇到其中一种情况

此压缩模型存在问题

如果没有找到Put/Delete，例如，如果Put/Delete恰好在另一个没有进行压缩的文件中，那么压缩将逐个写出键，就像没有压缩一样。主要的问题是我们做了不必要的工作，把他们推到台前。

类似地，如果有一个键应用了许多合并操作，那么如果没有PartialMerge，那么所有这些操作都必须存储在内存中。最后，这可能导致内存溢出或类似的情况。

可能的未来解决方案: 为了避免维护堆栈/deque的内存开销，最好遍历该列表两次，一次向前查找Put/Delete，一次反向查找。这可能需要大量的磁盘IO，但这只是一个建议。最后，我们决定不这样做，因为对于大多数(如果不是所有)工作负载，内存中的处理应该足以处理单个键。在未来，围绕这一点还有辩论和基准测试的空间。

压缩算法

算法上，压缩现在的工作如下:

Compaction(snaps, files):
  // <snaps> is the set of snapshots (i.e.: a list of sequence numbers)
  // <files> is the set of files undergoing compaction
  Let input = a file composed of the union of all files
  Let output = a file to store the resulting entries
  Let stack = [];       // in reality, this should be a "deque", but stack is simpler to conceptualize in this pseudo-code
  for each v from newest to oldest in input:
    clear_stack = false
    if v.sequence_number is in snaps:
      clear_stack = true
    else if stack not empty && v.key != stack.top.key:
      clear_stack = true
    if clear_stack:
      write out all operands on stack to output (in the same order as encountered)
      clear(stack)
    if v.type is "merge_operand":
      push v to stack
        while (stack has at least 2 elements and (stack.top and stack.second_from_top can be partial-merged)):
          v1 = stack.pop();
          v2 = stack.pop();
          result_v = client_merge_operator.PartialMerge(v1,v2)
          push result_v to stack
    if v.type is "put":
      write client_merge_operator.FullMerge(v, stack) to output
      clear stack
    if v.type is "delete":
      write client_merge_operator.FullMerge(nullptr, stack) to output
      clear stack
  If stack not empty:
    if end-of-key-history for key on stack:
      write client_merge_operator.FullMerge(nullptr, stack) to output
      clear(stack)
    else
      write out all operands on stack to output
      clear(stack)
  return output

在压缩中选择高层文件

注意，所有合并操作数的相对顺序应该始终保持不变。由于所有迭代器都“逐层”搜索数据库，所以我们永远不希望旧的合并操作数处于比新合并操作数更早的级别。因此，我们还必须更新压缩，以便当它选择要压缩的文件时，它扩展其上层文件，使其也包含所有“早期”合并操作数。为什么会改变呢?因为，当任何条目被压缩时，它总是会移动到较低的级别。因此，如果给定键的合并操作数分布在同一级别的多个文件上，但其中只有一些文件经过压缩，那么这种情况就会发生，即较新的合并操作数被下推到较晚的级别。

从技术上讲，这是经典rocksdb中的一个bug! 具体地说，这个问题一直存在，但是对于大多数(如果不是所有)没有合并操作符的应用程序，可以假设每个级别(除了级别0)都有一个密钥版本，因为压缩总是压缩重复的put，以便只包含最新的put值。所以交换顺序的概念是无关紧要的，除了在0级(压缩总是包含所有重叠的文件)。所以这个是固定的。

一些问题: 对于恶意输入，这可能导致在压缩过程中总是必须包含许多文件，而系统实际上只想选择一个文件。这可能会减慢速度，但是基准测试表明这并不是一个真正的问题。

笔记效率

快速讨论合并和部分合并的效率。

拥有一堆操作数可以更有效。例如，在string-append示例中(假设没有部分合并)，为用户提供一组堆叠在一起的字符串操作数来追加，允许用户摊销构造最终字符串的成本。举个例子,如果我给我需要追加的1000个小的字符串列表,可以使用这些字符串计算字符串的最终尺寸,储备/分配空间这个结果,然后进行所有的数据复制到新分配的内存数组中。相反，如果我总是被迫部分合并，那么系统将不得不执行1000次重新分配，每个字符串操作数执行一次，每个操作数的大小都比较大，并且总共需要分配的字节数可能非常大。在大多数用例中，这可能不是问题;在我们的基准测试中，我们发现它只在一个很大程度上使用热键的内存数据库中起作用，但这对于“不断增长的数据”是需要考虑的。无论如何，我们为用户提供了一个选择。

从这一点可以得出的关键点是，在某些情况下，拥有一堆操作数(而不是一个操作数)可以渐进地提高操作的总体效率。例如，在上面的字符串追加操作中，合并操作理论上可以使字符串追加操作平摊O(N)时间操作(其中N是所有操作后最终字符串的大小)，而没有堆栈，我们可以进行O(N²)时间操作。

更多信息，请联系rocksdb团队。或者查看RocksDB wiki页面。