写未准备-事务

写未准备-事务

本文档介绍了将memtable写入从准备阶段移动到未准备阶段的初始设计，此时批量写入仍然被写入。

WriteUnprepared很快就会宣布可以投入生产了。

目标

以下是本项目的目标:

减少内存占用，这也将支持处理非常大的事务。
避免由于一次向DB写入大量事务而导致写入停止。

概要

事务当前被缓冲在内存中，直到2PC的准备阶段。当事务较大时，缓冲数据也较大，并且立即将如此大的缓冲写入DB会对并发事务产生负面影响。此外，缓冲非常大的事务的整个数据可能会耗尽服务器的内存。内存占用的最大贡献是:

i)缓冲键/值，即 批处理写
ii)每键锁。在本设计中，我们将项目分为三个阶段，分别减少:
                                                 i)值
                                                 ii)键
                                                 ii)锁的内存使用

为了消除大事务中缓冲值的内存使用，在构建写批处理时，会将未准备好的数据逐步批处理成未准备的批量写入数据库。不过，为了简化回滚算法，键仍然被缓冲。当事务提交时，提交缓存将根据每个未准备的批量更新一个条目。主要的挑战是处理rollback 和 read-your-own-writes。

事务需要能够读取自己未提交的数据。以前，这是通过在查看数据库之前查看缓冲数据来完成的。我们通过跟踪写在磁盘上的未准备批的序列号来解决这个问题，并在读取数据的序列号与之匹配时增加ReadCallback返回true。这只适用于内存中设有缓冲批处理写的大型事务。

WritePrepared中的当前回滚算法只能在没有活动快照的情况下恢复后才能工作。然而，在WriteUnPrepared中，事务可以在实时快照存在时回滚。我们重新设计了回滚算法，

i)将被事务修改的键的先前值追加到事务中，因此本质上取消了写操作;
ii)提交回滚事务。将回滚事务处理为已提交的事务大大简化了实现，因此使用已提交事务处理实时快照的现有机制可以无缝应用。

WAL仍然会包含一个回滚标记，以便恢复过程能够在数据库崩溃时重新尝试回滚。要确定以前的值集，必须在事务对象中跟踪已修改键的列表。在没有缓冲写批的情况下，在项目的第一阶段，我们仍然缓冲修改后的key集。在第二阶段，当事务较大时，我们从WAL中检索key集。

RocksDB在TransactionLockMgr中跟踪锁定在事务中的键的列表。对于大型事务，锁定键列表将不适合存储在内存中。自动锁升级到范围锁可以用来近似一组点锁。当RocksDB检测到事务锁定了一定范围内的大量key时，它将自动将其升级为范围锁定。我们将在项目的第三阶段解决这个问题。更多细节见下面的”key锁定”一节。

本项目计划分三个阶段实施:

实现unprepared的批处理，但是key仍然在内存中缓存，以便回滚和锁定key。
使用WAL在回滚期间获取key集，而不是在内存中进行缓冲。
为大型事务实现范围锁定机制。

实现

WritePrepared概述

在现有的WritePrepared策略中，数据结构为:

PrepareHeap: 一堆正在进行的准备序列号
CommitCache: 准备提交seq的序列号之间的映射
maxevicted_seq: 从提交缓存中删除的最大序列号
OldCommitMap: 从提交缓存中删除的条目列表，如果它们对一些活动快照仍然不可见
DelayedPrepared: PrepareHeap中小于maxevicted_seq的已准备序列号列表

Put

需要批量处理数据库中的写操作，以避免遍历写队列的开销。为了避免与”批量写”混淆，这些将被称为”未准备批量”。通过批处理，我们还节省了必须在数据结构中生成和跟踪的未准备序列号的数量。一旦批处理达到一个可配置的阈值，它将被编写为WritePreparedTxn中的一个prepare操作，只不过将使用一个名为BeginUnprepareXID的新的WAL类型，而WritePreparedTxn策略使用的是BeginPersistedPrepareXID。同一批未准备key中的所有key将获得相同的序列号(除非存在重复key，否则会将该批划分为多个子批)

建议WAL格式: [BeginUnprepareXID]…[EndPrepare(XID)]

这意味着在最终准备之前，我们需要知道事务的XID(其中XID是事务生命周期中的一个名称uniq)(这对于MyRocks是正确的，因为我们在事务开始时生成事务的XID)

事务对象将需要跟踪已写入数据库的未准备批量的列表。为此，事务对象将包含一组nprep_seq编号，在编写未准备好的批处理时，将unprep_seq添加到该集合中。

在未准备的批处理写中，unprep_seq号也被添加到未准备的堆中(类似于WritePreparedTxn中的prepare堆)。

Prepare

在prepare中，我们将把当前写批中的剩余条目写到WAL中，但是使用BeginPersistedPrepareXID标记来表示事务现在已经准备好了。这是必需的，以便在崩溃时，我们可以返回给应用程序准备好的事务列表，以便应用程序可以执行正确的操作。未准备好的事务将在恢复时隐式回滚。

建议的WAL格式:[BeginUnprepareXID]…[EndPrepare(XID)] … [BeginUnprepareXID]…[EndPrepare(XID)] … [BeginPersistedPrepareXID]…[EndPrepare(XID)] … …[Commit(XID)]

在本例中，最后的prepare获取BeginPersistedPrepareXID，而不是BeginUnprepareXID，以表示事务已经真正准备好了。

注意,尽管DB文件(sst)向后和向前兼容WritePreparedTxn和WriteUnpreparedTxn之间,WriteUnpreparedTxn不是forward-compatible 与WritePreparedTxn: WritePreparedTxn将成功失败恢复表单上WriteUnpreparedTxn WAL文件生成,因为新标记的类型。但是，WriteUnpreparedTxn仍然完全向后兼容WritePreparedTxn，并且能够读取WritePreparedTxn WAL文件，因为它们看起来是一样的。

Commit

在commit时，需要更新提交映射和未准备堆。对于WriteUnprepared，提交可能有多个与之关联的prepare序列号。所有(unprep_seq, commit_seq)对必须添加到提交映射中，所有unprep_seq必须从unprepare_heap中删除。

如果在没有准备的情况下执行提交，并且事务之前没有编写未准备的批，那么当前未准备的批将直接被写出来，类似于WritePreparedTxn案例中的CommitWithoutPrepareInternal。如果事务已经编写了未准备的批，则添加一个隐式准备阶段。

Rollback

在WritePreparedTxn中，回滚实现仅限于在恢复之后立即回滚。它是这样实现的:

1.prep_seq = 将准备好的数据写入其中的seq
2.对于每个修改后的键，读取prep_seq - 1处的原始值
3.将原始值以新的序列号rollback_seq写回
4.将rollback_seq添加到提交映射
5.然后从PrepareHeap中删除prep_seq

如果pre_seq对活动快照可见，则此实现将无法工作。这是因为，如果max_evicted_seq超出了prep_seq，那么我们可以使用prep_seq < max_evicted_seq < snaphot_seq < rollback_seq。然后，snapshot_seq上的事务读取将假设prep_seq上的数据已经提交，因为prep_seq < max_evicted_seq，但是它没有记录在old_commit_map中。

WritePreparedTxn中的这个缺点是可以容忍的，因为MySQL只会在恢复时回滚准备好的事务，而不会有实时快照来观察这种不一致。然而，在WriteUnpreparedTxn中，这种情况不仅发生在恢复时，还发生在用户发起的未准备事务回滚时。

我们通过编写回滚标记，将回滚数据附加到中止的事务，然后在提交映射中提交事务，从而修复了这个问题。由于事务附加了回滚数据，虽然提交了，但它不会更改db的状态，因此可以有效地回滚。如果max_evicted_seq超出了prep_seq，因为被添加到CommitCache中，那么现有的过程 ie,向old_commit_map添加被驱逐的条目，将使用prep_seq < snapshot_seq < commit_seq处理活动快照。如果在回滚过程中崩溃，则在恢复时读取回滚标记并完成回滚过程。

如果数据库在回滚过程中崩溃，恢复将在WAL中看到一些部分编写的回滚数据。由于恢复过程最终将重新尝试回滚，因此只需使用包含相同先前值的新回滚批量覆盖这些部分数据。

对于非常大的事务，回滚批处理可以一次编写，也可以分为多个sub-patches。我们将在实现过程中进一步探讨这个选项。

WriteUnpreparedTxn中回滚的另一个问题是知道回滚哪些键。在此之前，由于整个准备批处理都缓冲在内存中，所以可以在写批处理上进行迭代，以找到需要回滚的修改过的键集。在项目的第一次迭代中，我们仍然将写键集保存在内存中。在下一个迭代中，如果键集的大小超过阈值，我们将从内存中清除键集，并在事务稍后中止时从WAL中检索它。每个事务都已经跟踪了一组未准备好的序列号，这些序列号可以用于寻找WAL中的正确位置。

Get

读取路径基本上与WritePreparedTxn相同。唯一的区别是事务能够读取自己的写。目前，GetFromBatchAndDB通过在从调用ReadCallback以确定可见性的DB中获取数据之前首先检查写批处理来处理这个问题。在没有写批处理的情况下，我们需要另一种机制来处理这个问题。

回想一下，每个事务都维护一个unprep_seq列表。在输入WritePreparedTxn中描述的主可见性逻辑之前，检查键是否有一个序列号存在于unprep_seq集合中。如果它存在，那么键就是可见的。这个逻辑发生在ReadCallback中，ReadCallback目前不接受一组序列号，但是可以扩展它，这样unprep_seq集就可以传递下去。

目前，Get和Seek在从DB读取数据时将直接查找快照指定的序列号，因此在应用可见性逻辑之前，可能会跳过同一事务编写的未提交数据。要解决这个问题，如果当前事务足够大，可以将其缓冲写批删除，而将其作为未准备的批写入数据库，则必须删除该优化。

Recovery

恢复的工作原理与WritePreparedTxn类似，只是对如何确定事务状态(未准备、已准备、已中止、已提交)做了一些更改。

在回收过程中，必须跟踪具有相同XID的未准备批次，直到观察到最终准备标记。如果恢复在没有EndPrepare的情况下完成，那么事务就没有准备好，并且隐式地完成了与应用程序回滚等价的操作。

如果恢复以EndPrepare结束，但是没有提交标记，那么事务就准备好了，并呈现给应用程序。

如果在EndPrepare之后找到了回滚标记，但是没有提交标记，那么事务将中止，恢复过程必须用它们的先前值覆盖中止的数据。

如果找到提交标记，则提交事务。

Delayed Prepared

大型事务的持续时间可能也会很长。如果一个事务在很长一段时间之后没有提交(100 kTPS工作负载1分钟)，那么它的序列号将被移动到delayedprepare，这是一个由锁保护的简单集合。如果发现当前实现是瓶颈，我们将把DelayedPrepared从一个集合更改为一个切分哈希表，类似于事务键锁定的方式。如果它在密钥锁定方面工作得足够好(这种情况发生得更频繁)，那么它在跟踪准备好的事务方面就应该工作得很好

Key Locking

目前，RocksDB通过TransactionLockMgr中的切分哈希表支持点锁。每次请求锁时，都会散列键并执行查找，以查看是否存在具有相同键的现有锁。如果是，则线程阻塞，否则，将授予锁并将其插入哈希表。这意味着所有锁定的键都将驻留在内存中，这对于大型事务来说可能存在问题。

为了缓解这个问题，当检测到一个事务在一个范围内锁定了多个键时，可以使用范围锁来近似于大量的点锁。在此，我们提出一个初步的方法来解决这个问题，以显示其可行性。当项目达到这个阶段时，我们将重新考虑其他设计方案，以及/或并行间隙锁定是否已经消除了这个问题。

为了支持范围锁，需要在N个逻辑分区中分区密钥空间，其中每个分区表示密钥空间中的连续范围。分区键表示每个分区，可以通过应用程序提供的回调从键本身计算。如果分区中锁定的键数超过阈值，则自动写锁; 在这种情况下，各个键被释放。

一个集合将用于保存所有分区的集合。一个分区将有以下 struct: struct Partition { map txn_locks; enum { UNLOCKED, LOCKED, LOCK_REQUEST } status = UNLOCKED; std::shared_ptr part_mutex; std::shared_ptr part_cv; int waiters = 0; };

当请求key锁时: 1.查找相应的分区结构。如果它不存在，那么创建并插入它。如果状态未锁定，则使用txn_locks[id]++递增，否则递增等待器并阻塞part_cv。递减等待器，并在线程被唤醒时重复此步骤。 2.请求点锁散列表上的点锁。

i) 如果授予了point lock，那么通过查看txn_locks[id]检查是否超过了阈值。
ii) 如果指针锁定超时，则使用txn_locks[id]--。

升级锁: 1.将分区状态设置为LOCKREQUEST、增量等待器和part_cv上的块，直到txn_locks只包含当前事务。减少等待器并在唤醒时重新检查txn_locks。 2.将状态设置为LOCKED。 3.从点锁散列表中删除该分区中的所有点锁。要删除的点锁可以通过tracked_keys确定。 4.更新trackedkeys以删除该分区中的所有点锁，并在trackedkeys中添加分区锁。

要解锁点锁: 1.从点锁散列表中删除点锁。 2.在相应的分区中递减txn_locks。 3.part_cv信号。如果服务员不是零。否则，删除分区。

解锁分区锁(没有用户API来触发这个，但是当事务结束时就会发生): 1.如果服务员不为零，则在part_cv上发出信号。否则，删除分区。

注意，任何时候从分区读取数据时，都必须持有它的互斥锁part_mutex。