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

栏目: 数据库 · 发布时间: 5年前

内容简介:为了更好地支持基于逻辑时钟和混合逻辑时钟的分布式事务,WiredTiger从3.0版开始引入时间戳事务(timestamp transaction)。在本文中,我们将时间戳事务简称为tsTxn。在第一章,我们会说明WiredTiger的事务策略。在第二章中,我们将介绍并证明WiredTiger事务的一个重要特性。第三章中,我们将介绍tsTxn的设计。最后在第四章,我们会看到除了一些限制之外,tsTxn显示了与第二章中类似的属性。WiredTiger以一种乐观的方式进行冲突检查。为了获得更高的吞吐量,Wire

摘要

为了更好地支持基于逻辑时钟和混合逻辑时钟的分布式事务,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)的元组。列表节点的顺序将会在第二章中进行讨论。

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

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

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

图4

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

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

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

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

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

图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


以上所述就是小编给大家介绍的《WiredTiger的时间戳事务设计及其正确性证明》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

锦绣蓝图

锦绣蓝图

[美] 沃德科 (Christina Wodtke)、[美] 戈夫拉 (Austin Govella) / 蔡芳 / 人民邮电出版社 / 2009-11-01 / 59.00

Web 2.0和社会化大趋势下,你的网站发展喜人,但是问题也接踵而来:信息变得越来越庞杂无序,业务流程愈加复杂,搜索和导航越来越难,用户对使用体验的要求也越来越高……怎么办? 作者非常通俗易懂地讲述了如何规划易用的网站及其背后的信息架构原理。首先介绍了建立信息架构的八项基本原则,然后重点强调了组织系统和元数据在信息架构中的作用,并指出设计搜索和导航需要考虑的问题和方法,另外还补充了当今热门的......一起来看看 《锦绣蓝图》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具