WiredTiger的时间戳事务设计及其正确性证明

摘要

为了更好地支持基于逻辑时钟和混合逻辑时钟的分布式事务，WiredTiger从3.0版开始引入时间戳事务（timestamp transaction）。在本文中，我们将时间戳事务简称为tsTxn。在第一章，我们会说明WiredTiger的事务策略。在第二章中，我们将介绍并证明WiredTiger事务的一个重要特性。第三章中，我们将介绍tsTxn的设计。最后在第四章，我们会看到除了一些限制之外，tsTxn显示了与第二章中类似的属性。

1. WiredTiger的事务策略

WiredTiger以一种乐观的方式进行冲突检查。为了获得更高的吞吐量，WiredTiger没有使用首次提交优先（first-commit-wins）策略进行冲突检查；相反，它使用的是首次更新优先（first-update-wins）策略。在RocksDB中可以找到一个开源的对于首次提交优先冲突策略的实现。RocksDB的乐观事务存在互斥竞争，并且无法使用更多的核去进行规模上的扩展，由于它使用了首次提交优先策略，冲突检查和提交必须以串行化的方式进行[1]。

数据会在其所关联的事务提交之前写入btree。对于btree页上的每个键，都有一个链接到它的多视图列表（multi-view list）。如图1所示，列表中的每个节点都是一个(TxnId, Value)的元组。列表节点的顺序将会在第二章中进行讨论。

图1

引擎会为处于活跃状态的（未提交的）事务维护一个全局的列表，这会有几种用途。具体来说，当一个新的txn启动时，它会将全局事务列表复制到它的本地视图中，每个维护的txn本地视图会用来进行冲突检查。在大多数情况下，冲突是一个双向关系，因此WiredTiger使用单向冲突检查策略，这一点我们稍后会进行描述。在第二章中，我们将证明这个策略的正确性。图2显示了讨论所必需的数据结构，而图3展示了WiredTiger基本事务的核心过程。

事务的本地视图
Transaction -> {
     // 当事务开始时分配的id，全局单调递增
     txnId: int
     // 本地视图的全局事务列表
     snapshots: []int
     // 描述本事务操作的键值对
     mods: []{string, string}
 }
 
 内存中的一个btree页的某个key所关联的MVCC列表
 UpdateListNode -> {
    txnId:    int
    newValue: []byte
    next:     *UpdateListNode
}

全局事务列表
GTL -> {
    // 用来分配一个事务的txnId
    txnIdAllocator: atomic
    // 未提交的事务
    activeTxns: List
    // 在并发访问下保护全局事务列表
    rwlock: RwLock
}

图2

事务的MVCC过程
 1. Begin -> {
 2.     with(GTL.rwlock.wlock()) {
 3.         txn = Transaction {
 4.             txnId: GTL.txnIdAllocator++
 5.             snapshots: GTL.activeTxns.copy()
 6.         }
 7.         GTL.activeTxns.add(txn)
 8.     }
 9.     // txns会以此方式排序
10. }

11. Update(key, value)-> {
12.     // 从btree的key中获取updatelist
13.     // 得到其头节点
14.     upd = GetUpdateList(key).header
15.     if (upd.txnId > self.snapshots.back()) {
16.         throw Conflict
17.     }
18.     if (txn.snapshots.find(upd.txnId) {
19.         throw Conflict
20.     }
21.     GetUpdateList(key).insertAtFront({self.txnId, value})
22. }

23. Commit -> {
24.     With(GTL.rwlock.wlock()) {
25.         GTL.activeTxns.remove(self)
26.     }
27. }

图3

2. 正确性论证

2.1 事务过程保证了快照隔离

如图3所示，WiredTiger使用首次更新优先策略进行冲突检查，所以我们关心的是一个事务的开始时间以及修改时间，这里修改时间指的是对某个特定键进行修改的时间。图4中txn1从t0开始，并尝试在t1时间对这个键进行修改。如果另一个事务在t1之前已经修改了同一个键，但在t0处尚未提交，则这时应抛出冲突。图4展示了仅有的两种可能情况。在（a）中，txn2从t2开始，在t3时发生修改，因此在t0时，txn2一定还没有提交，并且txn2会在txn1的快照列表中。图3中代码的第18行避免了这种情况。另一种情况如（b）中所示，txn2从t4开始，而t4在t0之后，这可以通过图3第15行很好地进行处理。

图4

2.2 UpdateList会自然地按照txnId倒序排列

如图3的第21行所示，事务会将其对某个键做出的修改添加到这个键更新列表的头部。当事务进行修改时，更新列表会随之增长。如何回收更新列表是另一个主题，更多细节请参阅[2]。我们可以证明，更新列表是按照txnId的逆序自然排列的。假如不是这样，那么就如图5中所示，因为txn1的txnId比较小，所以它比txn2启动得早，又因为它在更新列表中位于txn1的后面，所以txn2的修改时间早于txn1。因此，这两个事务在其生命周期中一定会有重叠的部分。也就是说，它们最多只有一个可以成功提交，这是由快照隔离（SI）的定义来保证的。而事务过程会保证快照隔离这一点已由我们在2.1中证明过了。综上所述，更新列表会自然地按照txnId逆序排列。由于txnId的顺序与事务的开始顺序相同，我们也可以说更新列表是按事务的开始顺序排列的。

图5

2.3 对于同一个键, txnId的顺序和提交时的wallclock时间顺序相同

我们在2.2中已经证明，同一个键更新列表会按照txnId排序，这与事务的开始顺序相同。实际上，对于同一个键，事务的开始顺序与其提交顺序相同。这是因为当一个节点要将修改添加到列表头部时，列表上的现有节点必须已经提交，图3中的代码第18行保证了这一点。

3. 引入WiredTiger的tsTxn

WiredTiger从3.0版开始引入了tsTxn机制[3]。具有混合逻辑时钟的分布式系统可以很好地利用这一功能。一个名为commitTimestamp的字段被添加到事务的结构中，如图6所示。所谓的commitTimestamp是由上层应用设定的。它提供了一种可能性，即对同一个键而言，可以保持提交时的wallclock顺序与其给定的commitTimestamp顺序相同。

Transaction -> {
     // 全局单调递增的id，当事务开始的时候分配
     txnId: int
     // 上层应用给定的“想象（as-if）”提交时间
     commitTimestamp: int
     // 全局事务列表的本地视图
     snapshots: []int
     // 以键值对表示的本事务操作
     mods: []{string, string}
}

图6

事实上，除非提交时的wallclock顺序与其commitTimestamp相同，否则WiredTiger并不能保证数据的一致性[4]。该限制可在其手册中找到。这主要是因为：如果违反了这个前提，那么在一次时间漫游读（time-travel read）中定义和/或检查数据可见性将会非常复杂。然而由于事务是并发执行的，上层应用又如何确保事务的wallclock提交顺序？

3.1 后启动单调分配（Post-Begin-Monotonic-Allocation）策略

我们将引入PBMA策略，这一策略使得所有tsTxns在并发执行的同时，可以按照commitTimestamp顺序进行提交。

 1. // 全局时间戳分配器
 2. GTA -> {
 3.     lock     Lock
 4.     globalTs int
 5. }
 
 6. // 时间戳分配过程
 7. Transaction txn
 8. txn.Begin()
 9. with(GTA.lock) {
10.     txn.commitTimestamp = globalTs++
11. }
12. ......
13. txn.Commit()

图7

4. 对于同一个键, PBMA保证了commitTimestamp与txnId顺序相同

我们已经在第二章中证明了，如果两个事务在其生命周期中重叠并尝试修改同一个键，最多只有一个可以成功。那么，是否会出现这样一种情况：具有较大commitTimetamp的事务首先开始并提交，而具有较小commitTimetamp的事务稍后开始并提交，这样它们就不会有重叠呢？答案仍然是否定的。如图8所示，txn1和txn2没有重叠，txn2比txn1更早并且比txn1(commitTimetamp=1)有更大的commitTimetamp(=2)。这是不可能发生的，因为图7代码中第9和第10行保证了会在锁内分配commitTimetamp，它们对于wallclock应该是单调的。

图8

到目前为止我们已经证明，在PBMA策略中，对于同一个键，txnId和commitTimetamp的顺序应该是相同的。它们都应该是单调的。

5. 结论

证明完毕。

第四章所讲的内容在现代的时间戳次序（T/O）事务中非常重要。它提供了一种方法来调解应用层提交顺序和物理提交顺序，这是基于混合逻辑时钟的分布式事务的基础。

参考文献

1. rocksdb’s optimistic transaction suffers from mutex contention
2. https://source.wiredtiger.com/3.0.0/architecture.html
3. https://source.wiredtiger.com/3.0.0/transactions.html#transaction_timestamps

本文译自：The design of wiredTiger’s timestampTransaction and associated correctness proof