breezes

分布式事务处理论文摘选

PNUTS: Yahoo!’s Hosted Data Serving Platform

大名鼎鼎的Yahoo PNUTS,地理分布高可用数据库。与普通的只提供EC一致性的KV系统相比,支持Range Query,支持读时一致性选择(任何版本、指定版本或最新版本等)。

Ganymed: Scalable Replication for Transactional Web Applications

只是通过复制来Scalable,保证可读Slave且数据一致,用SI。用SI保证分布式读一致没什么新意,复制就叫Scalable脸皮太厚了吧。

G-Store: A Scalable Data Store for Transactional Multi key Access in the Cloud

这个论文有些意思,有些用。允许动态创建由存储在多个节点上的实体组成的KeyGroup,一个实体在同一时刻只能属于一个KeyGroup。一个KeyGroup内的实体由一个节点来管理,因此支持KeyGroup内部的事务ACID。创建KeyGroup时先选一个主节点,主节点发创建组请求给所有参与节点,各参与节点检查请求的实体,若不在另一个KeyGroup中则同意参与,大家都同意由组队完成。组队完成后组内的分布式事务就变成非分布式事务,好办了。与MegaStore类静态的EntityGroup相比,G-Store的动态KeyGroup更灵活,如果一个KeyGroup能被多个事务重用,会有效。比如多个游戏玩家组队打游戏,只要一开始建个KeyGroup,接下来都好搞了。玩了过段时间再跟别人组队,再换个KeyGroup。

Hyder – A Transactional Record Manager for Shared Flash

听起来很牛B,基于共享存储实现Scalable的分布式事务处理。数据库是一个多版本COW索引树,事务指定要更新的数据项,事务意向写到分布式共享日志,所有服务器按序处理这一日志(大家处理的结果都会一致)。共享日志,事务要广播到所有服务器是瓶颈,但确实天花板比较高。

Optimistic Concurrency Control by Melding Trees

用于上述Bernstein提出的共享存储型分布式数据库Hyder,因为Hyder需要一个并发度非常高的树。

Sinfonia: a new paradigm for building scalable distributed systems

有效的支持由一系列compare items, read items, write items三部曲组成的分布式minitransaction处理。主要是piggyback分布式提交。事务执行分为两个阶段,第一个阶段加锁、比较和读,如果第一个阶段大家都通过,第二个阶段通知大家执行写操作就行了,不需要在写操作完成后再用两阶段提交协议来提交。另外coordination不写日志,所有participant都vote commit就commit。这个系统可以用来构建分布式基础软件,作者基于Sinfonia构建了分布式文件系统和Group Communication Service,都只用了几K行代码。

ElasTraS: An Elastic Transactional Data Store in the Cloud

可伸缩但只支持Sinfonia提出的minitransaction。

The Case for Determinism in Database Systems

挺牛逼。让事务在各参与节点(或复本)中按预定顺序执行,从而避免分布式死锁检测和分布式提交(当事务不会因为逻辑约束导致回滚时)。这样事务执行很快。用于复制不需要协调的事务很好,因为可以在事务执行之前批量的复制到replica,而且大家都按同样的顺序执行结果一定相同,不需要在事务提交前问别的replica验证。

Calvin: Fast Distributed Transactions for Partitioned Database Systems

上一篇的改进,只使用廉价服务器集群和硬盘存储提供高性能可伸缩和分布式事务处理,无单点故障,远程复制不降低事务吞吐率。还演示了底层只要是个提供了CRUD操作的非事务存储系统。核心思想每10ms给待执行的事务排好统一顺序提交然后按此既定顺序执行,这样复制不会延长事务持锁时间,分布式事务的内部协调开销类似于一阶段提交。要求事务预先定义好一次性提交,并要求事务readset/writeset事先也定义好。

Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore

名字很吓人,实际上只是搞定复制,也不能算真正的Scalable。

F1 -- The Fault-Tolerant Distributed RDBMS Supporting Google's Ad Business

Google大名鼎鼎的F1系统还没论文,根据PPT的简单介绍,还是类似于MegaStore,Entity Group内部的事务是单点处理好搞,多分区事务还是2PC。

这里面比较有新意的是G-Store的灵活组队、Hyder的共享存储、Calvin的统一顺序,但Hyder的单点瓶颈比较明显,G-Store和Calvin比较有实用价值,另外Sinfonia是一个很好用的分布式系统构建工具。

读了这些论文的一些体会:

1、分布式事务处理最大的问题是分布式死锁,基于等待图的检测不可伸缩性能也不可接受,超时则不及时。规避分布式死锁的好方法是统一顺序,在事务涉及的节点已知时可完美处理,在涉及的节点需要动态扩时要通过时间戳来判断是否违反顺序,违反则restart

2、按既定顺序确定的执行的价值是可以在事务还未开始时就批量的持久化事务,对于复制和一定会成功的分布式事务,可以做到事务过程里没有网络交互和sync日志。

3、对执行中才能确定命运的分布式事务,应该将验证过程靠前,等大家都通过认证后就可不必分布式提交

4、只读分布式事务用mvcc相当好处理

5、逻辑时钟加client id是很好的全局时间戳,还能支持read-your-write。如果在PaaS环境中通信都被logical clock aware的rpc接管,则能保证casual consistency。


分布式事务很难,通用分布式事务目前还没有有效的方法,但也远不是像NoSQL那样只能提交单实体一致性,操作多实体时只要一次性作为一个批量操作提交,用Calvin那样的方法很好处理。只读事务无论怎么复杂,都能用MVCC加SI读到一致的数据,如果结合逻辑时钟基本还能保证casual consistency。当然保证一致性始终比EC的可用性差一些。

评论(1)

热度(6)