内容简介:为了更好地支持基于逻辑时钟和混合逻辑时钟的分布式事务,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)的元组。列表节点的顺序将会在第二章中进行讨论。
图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)事务中非常重要。它提供了一种方法来调解应用层提交顺序和物理提交顺序,这是基于混合逻辑时钟的分布式事务的基础。
参考文献
- rocksdb’s optimistic transaction suffers from mutex contention
- https://source.wiredtiger.com/3.0.0/architecture.html
- https://source.wiredtiger.com/3.0.0/transactions.html#transaction_timestamps
本文译自: The design of wiredTiger’s timestampTransaction and associated correctness proof
以上所述就是小编给大家介绍的《WiredTiger的时间戳事务设计及其正确性证明》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 流处理系统正确性基石:ExactlyOnce 的设计和实现
- 流处理系统正确性基石:ExactlyOnce的设计和实现
- Spring中循环依赖的正确性与Bean注入的顺序关系
- Mybatis sql 如何进行全自动补全 检测sql的正确性 提升开发效率
- 证明系统哪家强:欺诈证明(Fraud Proof)vs.有效性证明(Validity Proof)
- 零知识证明介绍
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Bulletproof Ajax中文版
Jeremy Keith / 刘申、宋薇 / 人民邮电出版社 / 2007-11 / 39.00元
本书介绍了如何构建无懈可击的Ajax Web应用程序,重点讲述如何在已有Web站点使用Ajax增强网站用户体验,从而尽可能地保证网站拥有最大限度的可移植性和亲和力,这正是目前大多数网站面临的需求。书中主要介绍了JavaScript、DOM、XMLHttpRequest、数据格式等,同时还提出了一种Hijax方法,即可以让Web应用程序平稳退化的方法。 本书适合各层次Web开发和设计人员阅读......一起来看看 《Bulletproof Ajax中文版》 这本书的介绍吧!