这份文档展示为了在批量写请求还在写入的时候，把写 memtable 这个操作从准备阶段移动到未准备阶段进行的最初设计。

WriteUnprepared很快就能成为可以在生产使用的功能了

目标¶

以下是这个项目的目标：

减少内存消耗，这使得处理非常大的事务变为可能。
避免由于一次性写入巨大的事务造成的写失速。

梗概¶

目前，事务会被缓存在内存，知道 2PC 的准备阶段。当事务非常巨大的时候，缓存的数据也会很大，并且一次性写入如此巨大的事务会对并行的事务造成负面影响。更进一步，缓存一个非常巨大的事务的所有数据会导致机器内存耗尽。对内存消耗最大的贡献者是 i) 缓存的键值对，比如说，批量写 ii) 每个 key 的锁。在这个设计，我们把工程拆分为三步，以减少内存。i) 值 ii) 键 iii) 他们对应的锁

为了排除在巨大事务中用于缓存值使用的内存，未准备的数据会被逐步写入未预备批处理，并且在写批处理还在构建的时候就被写入数据库。然而，为了简化回滚算法，key 还是被缓存起来了。当一个事务提交，每个未预备的批处理都会更新提交缓存中的一个项。这里主要的挑战是处理回滚，以及读取自己的写入。

事务需要可以读取他们自己的未提交事务。之前这是通过在搜索 DB 前，先查找缓存的数据来实现的。我们通过保持记录已经写入硬盘的未预备批量写的序列号，然后增加 ReadCallback，让其在独到的数据的序列号能匹配的时候返回 true，来解决这个问题。这只对巨大的事务生效，这些事务不需要让批量写请求缓存到内存。

目前，WritePrepared 的回滚算法只能在没有存活快照的恢复流程之后工作。在 WriteUnPrepared 中，即使现在有快照，事务也可以回滚。我们这样设计回滚算法 i) 追加被事务修改 key 的值，在事务修改前的值，这样肯定可以取消写入 ii) 提交回滚的事务。把一个回滚事务看做提交事务极大简化了实现，因为现有的提交时处理存活快照的机制能与之无缝结合。WAL 仍旧包括一个回滚标记，以保证在 DB 崩溃后，恢复过程能重新进行回滚。为了找到事务修改前的值，修改了的 key 的值必须被缓存在 Transaction 对象中。在没有缓存的批量写的情况下，在工程的第一阶段，我们仍需要缓存被修改的 key 的集合。在第二步，如果事务很大，我们从 WAL 中获取 key 集合。

RocksDB 使用 TransactionLockMgr 追踪一个事务被锁定的 key。对于巨大事务，被锁定的 key 的列表可能无法填入内存。自动锁定会上升至一个范围锁，用于近似一个集合的点锁。当 RocksDB 检测到一个事务正在锁定一个非常大的数量的在一个特定范围的 key 的时候，他会自动升级到区间锁。我们会在这个工程的第三阶段讨论这个。更多细节参考下面的“key 锁”

阶段¶

计划是我们分三个阶段执行这个项目：

实现未预备批量写，但是 key 仍旧缓存在内存中，用于回滚和 key 上锁
回滚的时候，使用 WAL 来获取 key 集合，而不是从内存缓冲区获得。
对巨大的事务，实现区间锁机制。

实现¶

WritePrepared 概览¶

在已经有的 WritePrepared 策略，数据结构包括：

PrepareHeap：一个正在处理中的准备序列号的堆
CommitCache：一个从准备序列号到提交序列号的映射
- max_evicted_seq_：从 CommitCache 淘汰的最大淘汰序列号
OldCommitMap：从 CommitCache 淘汰的项，如果他们在某些线上快照还能看到的话，进入这里。
DelayedPrepared：从 PrepareHeap 出来的小于 max_evicted_seq_ 的准备序列号。

Put¶

写入数据库需要使用批处理以避免因为写队列带来的额外消耗。为了避免与“批量写”冲突，他们会被成为“批量未预备 (unprepared batches)”。通过批处理，我们还会节省未预备序列号的号码，这个号码我们需要生成，并且在我们的数据结构中追踪。一旦一个批处理到达一个可配置的阈值，他会被标记，以确定是不是有一个预备操作在 WritePreparedTxn 中，只不过一个新的 WAL 类型，名为 BeginUnprepareXID，会被用于 BeginPersistedPrepareXID（在 WritePreparedTxn 策略中被使用）的反面。所有的在同一个未预备批处理中的 key 会获得同样的序列号（除非有一个冲突的 key，会把批处理拆分为多个子批处理）

提出的 WAL 格式： [BeginUnprepareXID] .... [EndPrepare(XID)]

这意味着，在最后准备之前，我们需要知道事务的 XID（XID 是一个事务生命周期中唯一的编码）。（这在 Myrocks 里面是这样的，因为我们在事务开始的时候生成 XID）

Transaction 对象会需要追踪已经写入到 db 的未预备事务的列表。为此，Transaction 对象会包含一系列 unprep_seq 数字，当一个未预备批处理被写入，unprep_seq 会被加入到这个集合。

在未预备批量写中，unprep_seq 数字同样会被加入到未预备堆（类似 WritePreparedTxn 的预备堆）

prepare¶

在 prepare 的时候，我们会把当前批量写中剩余的项写出到 WAL，但是使用 BeginPersistedPrepareXID 来表示这个事务已经准备好。这样，在崩溃的时候，我们可以给应用返回已经准备好的事务，这样应用可以进行正确的操作。未预备事务会在恢复的时候隐式地回滚。

提出的 WAL 格式： [BeginUnprepareXID]...[EndPrepare(XID)] ... [BeginUnprepareXID]...[EndPrepare(XID)] ... [BeginPersistedPrepareXID]...[EndPrepare(XID)] ... ...[Commit(XID)]

在这种情况下，最后的准备获得 BeginPersistedPrepareXID，而不是 BeginUnprepareXID，以表示事务真的准备好了。

注意，尽管 DB（sst 文件）在 WritePreparedTxn 和 WriteUnpreparedTxn 是向前向后兼容的，WriteUnpreparedTxn 的 WAL 对 WritePreparedTxn 不是想前兼容的：WritePreparedTxn 肯定会在回复一个通过 WriteUnpreparedTxn 生成的 WAL 的时候失败，因为有新的标记类型。然而，WriteUnpreparedTxn 仍旧向后兼容 WritePreparedTxn，并且可以读取 WritePreparedTxn 的 WAL，因为他们看起来是一样的。

Commit¶

提交的时候，提交映射和未预备堆需要被更新。对于 WriteUnprepared，一个提交会潜在地拥有多个预备序列号。所有 (unprep_seq, commit_seq) 对都需要被加入到提交映射，并且所有 unprep_seq 都必须从 unprepare_heap 删除。

如果提交在没有准备的时候被执行，并且事务没有提前写入未预备批处理，那么当前的未预备批量写会直接写到类似 WritePreparedTxn 的 CommitWithoutPrepareInternal 的情况中。如果事务已经写入为预备批处理，那么我们认为预备阶段也被加入。

Rollback¶

在 WritePreparedTxn 中，回滚实现被限制在只在恢复之后进行回滚。他大概是这样实现的：

对于已经写入的以准备数据，prep_seq = seq
对于每个修改的 key，通过 prep_seq-1 读取原始的数值
回写原有的值，但是使用一个新的序列号，rollback_seq
rollback_seq 被加入到提交映射里
prep_seq 从 PrepareHeap 中移除

这个实现在存在线上快照能看到 prep_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，这个场景不止发生在恢复阶段，同事会发生在用户发起的未预备事务的回滚上。

我们通过写入一个回滚标记解决这个问题，在放弃的事务后追加回滚数据，然后在提交映射里提交事务。因为事务后面追加了回滚数据，尽管被提交了，但是他不会修改数据库的状态，因此他被有效地回滚了。如果 max_evicted_seq 增加到超过 prep_seq 了，由于被加入到 CommitCache，已有路径，比如，增加淘汰项到 old_commit_map，会处理存活的，满足 prep_seq < snapshot_seq < commit_seq 的快照。如果他在回滚过程中崩溃，在恢复的时候，他读取回滚标记，然后完成回滚操作。

如果 DB 在回滚中间泵快，恢复者会看到一些部分写入到 WAL 的回滚数据。因此恢复过程会最终重试完成回滚，这种部分数据会简单地使用之前的数值，覆盖为新的回滚批处理。

回滚批处理会被一次性，或者如果事务很大，分成多个子事务写入。我们未来会探讨其他的可能实现。

其他关于 WriteUnpreparedTxn 的回滚问题就是如何知道应该回滚哪些 key 了。之前，由于整个准备好的批处理缓存在了内存，因此可以值迭代写批处理来找到修改了的，需要回滚的 key 的集合。在这个工程，第一个迭代，我们仍旧保留把 key 集合写入内存的做法。在下一个迭代，如果 key 集合的大小增长到一个阈值，我们会从内存中清理这个 key 的集合，然后如果事务被丢弃了，就从 WAL 中读取 key。每个事务已经在追踪一个列表的未预备序列号，这可以被用于查找 WAL 中正确的位置。

Get¶

读取的路径跟 WritePreparedTxn 基本一致。惟一的区别在于，对于事务可以读自己的写入。目前，GetFromBatchAndDB 会处理这个问题，具体做法是，在从 DB 拉取数据前，在 ReadCallback 被调用已决定哪些可读前，先检查写批处理。在没有写批处理的时候，我们需要其他机制来处理这个。

记得每个事务都维护一个 unprep_seq 的列表。在进入主要的可视性检查前，如 WritePreparedTxn 中描述的，检查一个 key 是否有一个存在 unprep_seq 的序列号，如果是，则这个 key 可见。这个逻辑在 ReadCallback 中调用，目前不能支持一个序列号的集合，但是这个可以被拓展，这样 unprep_seq 的集合就能往下传了。

目前，从 DB 读数据的时候，Get 和 Seek 会直接查找快照声明的序列号，这样同一个事务写入的未提交的数据会潜在地，在检查可视性的逻辑前，被跳过。为了解决这个问题，如果当前事务足够大，使得它的写批处理缓冲被删除然后以未预备批处理写入 DB，这个优化会被删除。

Recovery¶

恢复过程会跟 WritePreparedTxn 一样工作，除了一些修改用于决定事务状态（未预备，预备，放弃，提交）。

在恢复过程中，带相同的 XID 的未预备批处理必须被追踪，直到看到 EndPrepare 标记。如果恢复结束，但是没看到 EndPrepare，那么事务就是未预备的，并且等价的，暗示着一个应用回滚。

如果恢复以 EndPrepare 结束，但是没有提交记录，那么事务已经准备好，然后会出现在应用中。

如果一个回滚标记在 EndPrepare 之后被发现，但是没有提交标记，那么事务就是被丢弃了，并且恢复过程必须使用它们之前的数据覆盖被修改的 key。

如果一个提交标记被发现，那么这个事务就是被提交了。

延迟预备¶

巨大的事务也可能会花费很长时间。如果一个事物在一段时间之后没有提交（对于一个 1k TPS 的工作压力，是 1 分钟），他的序列号会被移入 DelayedPrepared，目前是一个简单的，被锁保护的集合。如果最后当前的实现变成了一个瓶颈，我们会改变 DelayedPrepared，把他从一个集合（set）修改为一个分片的哈希表，类似于事务锁 key 的方式。如果对于 key 锁（发生的更加频繁）已经足够好用，那么用于追踪预备好的事务应该也足够了。

key 锁¶

目前，rocksdb 支持通过一个 TransactionLockMgr 中的分片哈希表来实现点锁。每一次申请一个锁，这个 key 会被哈希然后会检查同一个 key 是否有锁。如果有，线程挂起，否则，获得锁，并且插入哈希表。这意味着所有锁上的 key 会存在内存中，对于巨大的事务，可能造成问题。

为了解决这个问题，当一个事务被探测到在一个区间内申请了非常多锁的时候，区间锁可以用于近似替代这个巨大集合的点锁。我们这里展现一个初步用于解决这个问题的实现，以展现这是可行的。当到达这个项目的这个阶段的时候，我们会重新考虑其他方案，以及/或者是否并行区间锁是否已经解决了这个问题

为了支持去检索，key 空间需要被分割成 N 个逻辑分片，每个分片代表一个 key 空间内的连续的区间。一个分片 key 会代表每个分片，并且可以从 key 本身通过一个应用提供的回调计算得到。如果在一个分片的被上锁的 key 达到一定阈值，一个分片 key 会自动写上锁，此时每个独立的 key 锁会释放。

一个集合会被用于持有所有的分片。一个分片会有以下结构：

struct Partition { 
    map<TransactionID, int> txn_locks; 
    enum { UNLOCKED, LOCKED, LOCK_REQUEST } 
    status = UNLOCKED; 
    std::shared_ptr part_mutex; 
    std::shared_ptr part_cv; 
    int waiters = 0;
     }

当我们申请一个 key 的锁的时候：

检测对应的分片结构。如果它不存在，那么就创建，并插入他。如果状态位 UNLOCKED，那么增加 txn_locks[id]++，否则，增加 waiters，然后在 part_cv 挂起。当线程被唤醒，减少 waiters 然后重复这个步骤。
在点锁哈希表上请求一个点锁
- 如果点锁获取成功，那么检查 txn_locks[id] 以确认阈值是否达到。
- 如果点锁超时，减小 txn_locks[id]--

为了升级一个锁：

把分片状态设置为 LOCK_REQUEST，增加 waiters，然后在 part_cv 挂起，知道 txn_locks 只包含当前当前事务。被唤醒的时候，减少 waiters 然后重新检查 txn_locks。
设置状态为 LOCKED
通过点锁哈希表，删除本分片所有的点锁。需要移除的锁可以通过 tracked_keys_ 来得到。
更新 tracked_keys_ 以移除该分片所有点锁，然后增加分片锁到 tracked_keys_

为了解锁一个点锁：

通过点锁哈希表，删除点锁
减少对应分片的 txn_locks。
如果 waiters 为非零，给 part_cv 发信号。否则，删除分片。

为了解锁一个分批锁（没有用户 API 触发这个，他发生在事务结束的时候）：

如果 waiters 为非零，给 part_cv 发信号。否则，删除分片。

注意，任何时候，只要从分片读数据，他的互斥锁 part_mutex 就必须被持有。