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)的元组。列表节点的顺序将会在第二章中进行讨论。

15555561412891
图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行很好地进行处理。

15556923450667
图4

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

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

15555565998028
图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应该是单调的。

15557356690141
图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

发表评论