写准备的事务

RocksDB支持乐观锁和悲观锁的并发控制。悲观事务使用锁在事务之间提供隔离。悲观事务中的默认写入策略是WriteCommitted， 这意味着只有在提交事务之后，才会将数据写入数据库，即memtable。此策略简化了实现，但是吞吐量、事务大小和支持的隔离级别的多样性方面有一些限制。 在下面，我们将详细解释这些内容，并介绍其他写策略，即writePrepared和writeUnpared。然后，我们深入到写准备事务的设计中。

WriteCommitted 优点 和 缺点

使用WriteCommitted写入策略，只有在事务提交之后，数据才会写入memtable。这大大简化了读取路径，因为可以假定其他事务读取的任何数据都是提交的。 然而，此写入策略意味着同时在内存中缓冲写入。这使得内存成为大型事务的瓶颈。2PC(两阶段提交) 中提交阶段的延迟也变得明显，因为大多数工作(即写入memtable)都是在提交阶段完成的。 当多个事务的提交以串行方式完成时，例如在MySQL的2PC实现中，长时间的提交延迟成为低吞吐量的主要因素。 此外，此写入策略不能提供更弱的隔离级别，例如未提交的读取，这可能为某些应用程序提供更高的吞吐量。

备选方案：WritePrepared和WriteUnpared

为了解决冗长的提交问题，我们应该在2PC的早期阶段进行memtable写入，以便提交阶段变得轻量级和快速。 2PC由写入阶段组成，在该阶段调用事务: （重新翻译） ::Put 在该阶段调用准备阶段，在该阶段调用 ::Prepare（如果以后请求提交事务，则在该阶段DB承诺提交事务），以及提交阶段，在该阶段调用 ::Commit 并且事务写入对所有读卡器都可见。

为了使提交阶段轻量级，可以在::Prepare 或 ::Put阶段执行memtable写入，从而分别生成WritePrepared 和 WriteUnprepared 写入策略。 缺点是，当另一个事物正在读取数据时，需要一种方法来区分哪些数据是提交的，如果是提交的，则需要一种方法来区分这些数据是否在事务启动之前提交，即在事务的读取快照中提交。 WritePrepared仍然存在缓冲数据的问题，这使得内存成为大型事务的瓶颈。但是，它为从writeCommitted转换为writeUnprepared写入策略提供了一个良好的里程碑。在这里， 我们解释了WritePrepared策略的设计。可以在此处找到使设计也支持writeUnprepared的更改。

WritePrepared 简而言之

这些是需要解决的主要设计问题: 1.我们如何用编写它们的事务来标识数据库中的键/值? 2.如何计算事务txn_w写入的键/值是否在读取事务txn_r的读取快照中？ 3.如何回滚由中止的事务写入的数据？

使用WritePrepared，事务仍然缓冲内存中的write batch对象中的写。调用2PC::Prepare 时，将内存中的批量写 写到WAL(写前日志)和memtable(每个列族一个memtable);我们重用RocksDB中已有的序列号概念， 用相同的序列号prepare_seq标记同一写入批处理中的所有键/值，该序列号也用作事务的标识符。 在提交时，它向WAL写入一个提交标记，其序列号commit_seq将用作事务的提交时间戳。在向读取器释放提交序列号之前，它在内存中的数据结构中存储了从prepare_seq到commit_seq的映射，我们称之为CommitCache。 当事务从DB读取值(标记为prepare_seq)时，它使用CommitCache来确定值的commit_seq是否在其读取快照中。要回滚已中止的事务。我们应用事务之前的状态，方法是执行另一个写操作来抵消已中止事务的写操作。

WritePrepared 设计

这里，我们展示了WritePrepared事务的设计细节。我们首先介绍了CommitCache的有效设计， 然后深入研究其他数据结构，因为我们看到它们对于确保CommitCache之上的正确性非常重要。

CommitCache 提交缓存

是否提交数据的问题主要是关于最近的事务。换句话说，如果有适当的回滚算法，我们可以假设数据库中的任何旧数据都是提交的， 并且也存在于读取事务的快照中，这通常是最近的快照。利用这种观察，对于大多数情况，维护最近提交项的缓存必须足够。 CommitCache是我们为此目的设计的一种高效的数据结构。

CommitCache是一个固定大小的内存中的commit项数组。要用提交项目更新缓存，我们首先用数组大小索引prepare_seq，然后重写数组中的相应项，即:CommitCache[prepare_seq % array_size] = . 每次插入都会导致前一个值被逐出，从而更新从CommitCache中逐出的最大序列号max_seq。在CommitCache中查找时，如果一个prepare_seq > max_evicted_seq 已收回但未在缓存中， 则认为它未提交。如果在缓存中另外找到该条目，则该条目将被提交，并由快照序列号为snap_seq的事务读取(如果commit_seq<=snap_seq)。如果prepare_seq < max_evicted_seq, 那么我们正在读取一个旧数据，除非证明另有说明，否则这很可能是承诺的，我们将在下面解释。

考虑到80K tps(每秒事务数)的写入量，提交缓存中有800个条目（在TransactionDBOptions::wpcommit_cache位中硬编码）, 并且每个事务的序列号增加了两个，将插入的条目从提交缓存中移出大约需要50秒。然而，在实践中，准备和提交之间的延迟只有一毫秒的一小部分，因此不太可能满足这个限制。 但是，为了正确起见，我们需要涵盖在maxseq提前执行其prepare_seq时未提交已准备事务的情况，否则读取事务将假定已提交。 为此，我们维护一个名为PrepareHeap的准备序列号堆：在::Prepare上插入一个prepare_seq，在::Commit上删除它. 当max_eviced_seq前进时，如果它大于堆中的最小prepare_seq，我们会弹出这些条目并将它们存储在一个名为delayed_prepared的集合中。 验证delayedprepared是否为空是一个有效的操作，需要在调用已提交的旧”准备就绪”之前完成该操作。 否则，读取事务还应该查看delayedprepared以查看是否在那里找到了它们读取的值”准备就绪”。 让我们强调这样的情况不会发生在合理的设置中，因此不会对性能产生负面影响。

尽管对于读写事务，它们应该在::Prepare阶段之后的几毫秒内提交，但是一些只读事务仍然可以挂起一些非常旧的快照。例如，当事务需要数据库的备份时，这种情况可能需要数小时才能完成。 这种只读事务不能假定旧数据在其读取快照中，因为它们的快照也可能非常旧。更准确的说，如果存在序列号为snapseq的实时快照，那么我们仍然需要保留一个收回的条目，其中prepare_seq<=snap_seq<commit_seq。 在这种情况下，我们将Prepare_Seq添加到old_commit_map中，这是从快照序列号到一组prepareseq的映射。 唯一需要支付查看此数据结构成本的事务是从非常旧的快照中读取的事务。此数据结构的大小预计非常小，只有少数事务在执行备份。)与读取快照重叠的并发事务的数量有限。当数据库通过定期获取快照列表通知快照发布时，旧的”提交”映射会被延迟地垃圾回收，这是推进max_evicted_seq的过程的一部分。

PreparedHeap 堆Prepared

顾名思义，PrepareHeap是一个堆准备序列号: 在 ::Prepare上插入prepare_seq。在 ::Commit上删除prepare_seq。堆结构允许有效地从堆中删除条目，实际删除会延迟，直到条目到达堆的顶部，即成为最小值。 要执行此操作，如果已移除的项尚未位于顶部，则会将其添加到另一个堆中。每次更改后，将比较两个堆的顶部，以查看主堆的顶部是否标记为要删除。

Rollback 回滚

要回滚一个中止的事务，对于每个写入的键/值，我们要写另一个键/值来取消先前的写入。由于在悲观事务中通过锁避免了写-写冲突， 因此可以保证每个键上只有一个挂起的写操作，这意味着我们只需要查看以前的值就可以计算出应该回滚到的状态。如果::Get的结果从一个快照与序号kMaxSequenceNumber是正常价值(被回滚数据将被忽略,因为他们不是comitted) 然后我们做一个 ::Put 键/值，如果它是一个不存在的值，我们插入一个::Delete条目。然后使用相同的commit_seq提交所有值(由中止的事务和回滚步骤编写)，并从PreparedHeap中删除中止的事务和回滚批的prepare_seq。

Atomic Commit 原子提交

在提交期间，提交标记被写入wal，并且提交条目也被添加到CommitCache。这两个任务需要原子化的完成，否则某个时刻的读取事务可能会错过对CommitCache的更新，但稍后会看到这一点。我们通过在发布提交条目的序列号之前更新CommitCache来实现这一点。 这样，如果读取快照可以看到提交序列号，则可以保证已更新了CommitCache。 这是通过一个PreReleaseCallback完成的，该回调添加到::WriteImpl 逻辑中。PreReleaseCallback还用于向PrepareHeap添加prepare_seq。 以便其顶部始终表示最小的未提交事务。（请参阅最小的未提交部分以了解如何使用它）。

当我们有两个写入队列 (two_write_queues=true)时，主写入队列可以同时写入wal和memtbale，第二个只能写wal，这将用于在WritePrepared事务中写入提交标记。 在这种情况下，主队列（它是PreReleaseCallback回调）始终用于准备实体，第二个队列（它是PreReleaseCallback回调）始终仅用于提交。（避免两个队列之间的争用情况） 除了PreparedHeap之外还维护顺序）通过避免并发插入CommitCache（以及每次从中逐出时调用的代码）来简化代码。

由于最后一个序列号可以通过任一队列前进，而另一个序列号不能通过保留的较低序列号前进，这可能会引发原子性问题。为了解决这个问题，我们引入了上次发布的序列号的概念，这将在拍摄快照时使用。 当我们有一个写入队列时，这与最后一个序列号相同;当我们有两个写入队列时，这是最后一个提交的条目(由第二个队列执行)。这种限制通过将非2PC事务拆分为两个步骤来惩罚它们) 通过主队列写入memtable）通过第二个队列提交和发布序列号。

IsInSnapshot 信息系统网络快照

IsInSnapshot(prepare_seq, snapshot_seq)实现了WritePrepared的核心算法，它将所有的teh数据结构放在一起，已确定带有prepare_seq标记的值是否在读取快照snapshot_seq中。

以下是IsInSnapshot算法的简化版本：

inline bool IsInSnapshot(uint64_t prep_seq, uint64_t snapshot_seq,
                         uint64_t min_uncommitted = 0,
                         bool *snap_released = nullptr) const {
  if (snapshot_seq < prep_seq) return false;
  if (prep_seq < min_uncommitted) return true;
  max_evicted_seq_ub = max_evicted_seq_.load();
  some_are_delayed = delayed_prepared_ not empty
  if (prep_seq in CommitCache) return CommitCache[prep_seq] <= snapshot_seq;
  if (max_evicted_seq_ub < prep_seq) return false; // still prepared
  if (some_are_delayed) {
     ...
  }
  if (max_evicted_seq_ub < snapshot_seq) return true; // old commit with no overlap with snapshot_seq
  // commit is old so is the snapshot, check if there was an overlap
  if (snaoshot_seq not in old_commit_map_) {
    *snap_released = true;
    return true;
  }
  bool overlapped = prepare_seq in old_commit_map_[snaoshot_seq];
  return !overlapped;
}

如果可以确定commit_seq<=snapshot_seq，则返回true，否则返回false

• snapshot_seq < prep_seq => commit_seq > snapshot_seq 因为 prep_seq <= commit_seq
• prep_seq < min_uncommitted => commit_seq <= snapshot_seq
• 在someare_delayed中检查delayed_prepared的空值，然后再进行CommitCache查找，这是一种优化，如果系统中没有延迟事务(这是常见的情况)，则跳过获取锁定。

如果不在CommitCache中，并且所有延迟准备的案例都不适用，那么这是一个从CommitCache中删除的旧提交。

• maxevicted_seq < snapshotseq => commit_seq < snapshot_seq since commit_seq <= max_evicted_seq
• 否则，oldcommit_map 包括所有这些旧快照以及与它们重叠的任何提交。

在下面的文章中，我们看到了IsInSnapshot的完整实现，它也涵盖了一些基本情况。IsInSnapshot(prepare_seq, snapshot_seq)实现了writeprepare的核心算法， 该算法将所有teh数据结构放在一起，以确定带有prepare_seq标记的值是否在读取快照snapshot_seq中。

inline bool IsInSnapshot(uint64_t prep_seq, uint64_t snapshot_seq,
                         uint64_t min_uncommitted = 0,
                         bool *snap_released = nullptr) const {
  if (snapshot_seq < prep_seq) return false;
  if (prep_seq < min_uncommitted) return true;
  do {
    max_evicted_seq_lb = max_evicted_seq_.load();
    some_are_delayed = delayed_prepared_ not empty
    if (prep_seq in CommitCache) return CommitCache[prep_seq] <= snapshot_seq;
    max_evicted_seq_ub = max_evicted_seq_.load();
    if (max_evicted_seq_lb != max_evicted_seq_ub) continue;
    if (max_evicted_seq_ub < prep_seq) return false; // still prepared
    if (some_are_delayed) {
      if (prep_seq in delayed_prepared_) {
        // might be committed but not added to commit cache yet
        if (prep_seq not in delayed_prepared_commits_) return false;
        return delayed_prepared_commits_[prep_seq] < snapshot_seq;
      } else {
        // 2nd probe due to non-atomic commit cache and delayed_prepared_
        if (prep_seq in CommitCache) return CommitCache[prep_seq] <= snapshot_seq;
        max_evicted_seq_ub = max_evicted_seq_.load();
      }
    }
  } while (UNLIKELY(max_evicted_seq_lb != max_evicted_seq_ub));
  if (max_evicted_seq_ub < snapshot_seq) return true; // old commit with no overlap with snapshot_seq
  // commit is old so is the snapshot, check if there was an overlap
  if (snaoshot_seq not in old_commit_map_) {
    *snap_released = true;
    return true;
  }
  bool overlapped = prepare_seq in old_commit_map_[snaoshot_seq];
  return !overlapped;
}

• 由于maxevicted_seq和CommitCache是分别更新的，while循环通过确保在CommitCache查找期间不更改maxevicted_seq来简化算法。

• 延迟准备的提交涉及四个非原子步骤: i) update CommitCache ii) add to delayedprepared_commits iii) publish sequence iv) remove from delayedprepared

  • 如果读取器只是遵循CommitCache查找 + delayedprepared查找顺序，那么它可能会在neither中发现一个延迟的prepare，并且没有检查它的commitseq。 因此，如果在delayed_prepared中没有找到序列，它仍然在CommitCache中执行第二次查找。相反的顺序确保如果有提交，它将看到提交。
  • 有一些奇怪的情况，延迟准备的提交可以在条目从delayedprepared列表中删除之前从提交缓存中删除。 delayedprepared_commits每次将延迟的准备从提交缓存中删除时都会更新它，这有助于避免错过此类提交。

Flush/Compaction 刷新/压缩

与读取事务类似，刷新/压缩线程使用IsInSnapshot API来确定哪些版本可以安全地垃圾收集而不影响实时快照。 不同之处在于，在压缩调用IsInSnapshot时，快照可能已经被释放了。 为了解决这个问题，如果IsInSnapshot使用snap_release参数进行扩展，这样如果它不能自信地给出true/false响应，它将向调用者发出信号，表明snapshot_seq不再有效。

Duplicate keys 重复键

WritePrepared将具有相同序列号的相同写批的所有数据写入。这是假设写批处理中没有重复键。 为了能够处理重复键，我们将写批处理划分为多个子批，每个子批在每个重复键之后执行。 如果memtable接收到具有相同序列号的键，则返回false。然后，mentable插入器推进序列号并再次尝试。

这种方法的限制是，写过程需要预先知道子批的数量，以便为每个写分配相应的序列号。 当使用事务API时，这可以通过WriteBatchWithIndex索引廉价地完成，因为它已经具有检测重复插入的机制。但是，当调用::CommitBatch将一个批直接写入数据库时，DB必须支付遍历写批并计算子批数量的开销。 如果有很多这样的写操作，这将导致不可忽略的开销。

检测重复键需要知道列族(cf)的比较器。如果cf被删除，我们首先需要确保WAL没有属于该cf的条目。 否则，如果DB崩溃后，恢复过程将看到该条目，但是没有比较器来判断它是否是副本。

Optimizations 优化

在这里，我们将介绍设计中对实现良好性能至关重要的附加细节。

Lock-free CommitCache 无锁 CommitCache

大多数从最近的数据读取都会导致对CommitCache的查找。因此，使CommitCache对读取有效是至关重要的。为了达到这个目的，使用固定数组已经是一个有意识的设计决策。 但是，我们需要进一步避免从这个数组读取数据时的同步开销。为此，我们将CommitCache设置为std::atomic数组，并将编码为可用的64位。数组的读写分别使用std:: memory_order_acquisition和std::memory_order_release完成。 在x86_64体系结构中，由于硬件缓存一致性协议的保证，这些操作被转换为简单的内存读写操作。我们对这个数据结构有其他的设计，并将在未来进行探索。

为了将编码为64位，我们使用这个算法: i) CommitCache中条目的索引已经隐含了prepare_seq的较高位; ii) prepare seq的较低位编码在64位条目的较高位中; commit_seq和prepare_seq之间的差异被编码到64位条目的较低位。

Less-frequent updates to max_evicted_seq 不太频繁地更新max_eviced_seq

一般情况下，maxevicted_seq在每次从CommitCache中删除时都会更新。 虽然更新max_evicted_seq并不一定很昂贵，但是随之而来的维护操作却很昂贵。 例如，它需要持有互斥锁来验证PreparedHeap中的顶部(尽管可以优化它，使其在不使用互斥锁的情况下完成)。 更重要的是，它涉及到保存用于从db中获取活动快照列表的db互斥对象，因为维护old_commit_map取决于活动快照列表，直到max_evicted_seq。 为了减少这种开销，在每次更新max_evicted_seq时，我们将它的值进一步增加到CommitCache大小的1%(如果它不超过上一个发布序列号)，以便在CommitCache数组包装之前进行100次维护，而不是在每次驱逐之前进行一次维护。

Lock-free Snapshot List 无锁快照列表

在上面的文章中，我们提到了在每个时间点都应该有几个只读事务执行备份。 因此，需要根据活动快照列表(在max_evicted_seq最后一次被高级化时拍摄)检查每次插入时预期的每个被驱逐条目。 由于这是经常做的，它需要有效地做，没有持有任何互斥。因此，我们设计了一个数据结构，使我们能够以无锁的方式执行此检查。 为此，我们将第一个S快照(在TransactionDBOptions::wp_snaoshot_cache_bits中硬编码为128)存储在std::atomic数组中，我们知道这对于x86_64架构上的读写非常有效。 单个写入器使用按升序排列的快照列表更新数组(从索引0开始)，并更新原子变量中的大小。

我们需要保证并发阅读器能够读取更新后仍然有效的所有快照。新列表和旧列表都进行了排序，新列表是前一个列表的子集加上一些新项目。 因此，如果一个快照同时在新列表和旧列表中重复出现，它将在新列表中以较低的索引出现。因此，如果我们只是按顺序插入新的快照，如果覆盖的项在新列表中仍然有效，那么它要么被写到数组中的相同位置，要么在被另一个项覆盖之前被写到索引较低的位置。 这保证从另一端读取数组的读取器最终会看到更新中重复出现的快照，无论是在写入器覆盖之前还是之后。

如果快照的数量超过数组大小，其余的更新将存储在一个由互斥锁保护的向量中。这只是为了确保在角情况下的正确性，而不是在正常运行中发生。

Smallest Uncommitted 最小未提交

我们跟踪最小的未提交数据并将其存储在快照中。当读取序列号小于最小未提交数据的数据时，我们将跳过对CommitCache的查找，以减少cpu缓存丢失。如果delayedprepared中最小的条目不是空的，则表示最小的未提交条目。 否则(几乎总是这样)，PreparedHeap顶部表示最小的未提交，这要感谢只通过主写队列按升序向其添加entires的规则。如果知道最小未提交序列已经大于memtables中的最小序列，那么最小未提交序列还将用于将ValidateSnapshot搜索限制为memtables。

rocksdb_commit_time_batch_for_recovery

如上所述，我们指定提交仅通过第二个队列完成。然而，当提交与CommitTimeWriteBatch同时进行时，它也将写入memtable, memtable本质上将把该批发送到主队列。 在本例中，我们执行两个单独的写操作来完成提交: 一个写CommitTimeWriteBatch通过主队列，另两个提交，以及准备好的批处理通过第二个队列提交。 为了避免这种开销，用户可以将rocksdb_commit_time_batch_for_recovery配置变量设置为true，该变量告诉RocksDB只在恢复期间需要这些数据。 通过只将CommitTimeWriteBatch写入WAL, RocksDB可以从中受益。它仍然将最后一个副本保存在内存中，以便在每次刷新之后将其写入SST文件。 当使用这个选项时，CommitTimeWriteBatch不能有重复的条目，因为我们不希望在每次提交请求时支付计算子批的成本。

Experimental Results 实验结果

下面是一些sysbench基准测试和linkbench(通过MyRocks完成)的改进摘要。

• benchmark………..tps………p95 latency….cpu/query
• insert……………….68%
• update-noindex…30%……38%
• update-index…….61%…….28%
• read-write…………6%……..3.5%
• read-only………..-1.2%…..-1.8%
• linkbench………….1.9%……+overall……..0.6%

下面是 内存中的Sysbench (https://gist.github.com/maysamyabandeh/bdb868091b2929a6d938615fdcf58424) 和 @mdcallag 的 SSD Sysbench (https://gist.github.com/maysamyabandeh/ff94f378ab48925025c34c47eff99306) 的详细结果。

Current Limitations 当前限制

读取工作负载的开销约为1%。这是因为需要做额外的工作来区分未提交的数据和提交的数据。

当前禁用合并操作数的回滚。这是为了解决MyRocks中在使用merge操作数之前没有锁定key的问题。

当前不支持Iterator::Refresh。没有根本的障碍，可以根据要求添加。

虽然WritePrepared策略生成的DB向后/向前兼容经典的writecom策略，但是WAL格式不是。因此，要更改WritePolicy，必须首先通过刷新数据库清空WAL。

如果启用了两个o_write_queues，非2pc事务将导致两次写入。如果大多数事务是非2pc的，那么应该禁用two_write_queues优化。

TransactionDB::Write会增加在写批处理中检测重复键的成本。

如果一个列族被丢弃，那么必须预先清理WAL，这样WAL中就不会有属于CF的条目。

当使用rocksdb_commit_time_batch_for_recovery时，传递给CommitTimeWriteBatch的数据不能有重复的键，并且只有在memtable刷新之后才可见。