一致性, 两阶段提交和事务提交的发展史(译)
原文地址: http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html
[注: 初次翻译, 这里面提到的论文可能理解不够, 有错误的地方感谢帮忙指出]
这是关于一致性, 事务和两阶段提交的历史, 因为用词的变化导致阅读一致性相关的文章非常的麻烦(consensus 在较早以前都叫做agreement), 这些分布式相关的论文并没有按照逻辑的顺序产出, 并且整体的分布式算法是在并行发展的. 目前只有Lynch 的 Distributed Algorithm 这本书有这些主题
接下来描述的Paper主要按他们的关联性排序, 并没有根据他们的出版时间进行排序.
第一个我知道的关于一致性问题的实例是Lamport’s “Time, Clocks and the Ordering of Events in a Distributed System” (1978), 虽然这篇文章没有严格的定义了一个一致性的问题. 在这个文章里面 Lamport 讨论了在有限的时间内消息是怎么在进程之间进行传输, 并且将进程之间传递消息和爱因斯坦的相对论进行的对比. 最近在博客上讨论分布式系统和爱因斯坦的相对论的关联非常的热门,但是在1978年的时候 Lamport就已经给出了一个完整的时空图的分析. 这个结论是在一个分布式系统里面, 只有A事件能够触发B事件的发生, 你才能够说明A事件发生在B事件前面, 否则是不行的. 不同的进程看到的事件的顺序是不一致的, 也就是在一个分布式系统里面, 只存在一个偏序关系, 不存在一个全序关系. Lamport 定义了”happens before” 关系和操作, 并且给出了一个在分布式系统里面全局的定义事件顺序关系的算法, 这样所有的进程看到的事件的顺序关系就是一致的
Lamport还介绍了一个分布式的状态机: 所有的状态机以一个相同的初始状态启动, 并且保证所有的状态机处理的消息是一模一样的. 那么每一个状态机就是其他状态机的副本. 那么, 关键的问题是保证每一个副本约定好下一条要处理的消息: 一个一致性问题. 这个用上面给出的全局的定义事件顺序关系的算法可以做到的. 但是这个系统容错能力是不行的, 假如有一个进程失败了, 那么其他的进程必须等待他恢复.
大约在这边论文发布的相同的时间, Gray 发布了两阶段提交协议的算法 “Notes on Database Operating Systems” (1979). 两阶段提交协议存在的问题是, 如果TM(Transaction Manager)在某些时刻如果失败了, 整个Transaction 就会阻塞. Skeen又发布了“NonBlocking Commit Protocols” (1981)这篇论文. 论文指出在一个分布式的事务里面, 需要一个三阶段的提交协议来避免在两阶段提交中存在的阻塞问题. 但是问题是这个一个完美三阶段提交协议需要将近25年的时间来完成一次提交!
Fischer, Lynch and Paterson 在论文 “Impossibility of distributed consensus with one faulty process” (1985)证明, 在一个异步系统里面, 只要有一个错误的进程, 一致性就不可能达成. 这个也就是著名的”FLP”结论. 在这个时间”一致性” 代表的是一堆进程同意同一个值的问题. 一个异步系统(异步系统指的是进程运行的速度不一定, 并且进程之间传递消息所需要的时间也不一定, 有可能无限长)在最完美的网络环境(这里的环境指的是所有的消息都会被送达, 消息送达的顺序和消息被发送的顺序是一致的, 并且消息是不会被多次的发送)下, 只要有一个进程出错, 这个一致性就无法达成. 这个问题的难点在于你不能判断一个进程是停止了还是跑的非常的慢. 处理一个在异步系统里面的错误几乎是不可能的. 这篇论文是非常重要的, 因为它告诉了我们什么事情是不可能的, 就像能量守恒定律对于永动机一样. 这篇文章证明过程是所有想要解决异步系统的一致性问题的算法必须有某些属性, 然后他们通过反证法证明了这些属性是不可能存在的.
在这个阶段, 人们认为分布式系统分成同步的(进程运行在已知的速度, 并且在进程之间消息的传递在规定的时间到达) 和 异步的(进程运行在任意的速度, 并且进程间消息的传递时间不能保证). 异步的系统是一个更为常见的系统. 一个算法能够解决异步系统的一致性问题, 肯定也能够解决同步系统的一致性问题, 但是反过来不行.你可以把一个同步系统看成一个异步系统的特例, 同步系统是进程运行在规定速度, 进程之间传递消息有时间上线的一个异步系统.
在FLP之前, 就有“The Byzantine Generals Problem” (1982)这篇论文. 在这个一致性问题里面, 进程可以传递错误信息, 并且他们积极的将这个错误信息传递给其他进程. 这个问题看起来比FLP结论更难, 但是在同步系统下, 还是有方法能够达成一致的(虽然在这篇文章发布的时候, 同步系统和异步系统的定义还没那么的明确). 但是这个方法在消息的传递的总量, 以及消息传递的轮数都非常的多, 因此性能不行. 这里Byzantine 将军问题最早的想法来自于航空业: 当一个飞机上的传感器捕获一个错误信息的时候该怎么办(这里的系统可以看成是同步系统).
在1986年, 关注一致性的问题和事务的问题的人们聚集起来. 在那个时候, 最好的一致性算法就是上面提出的Byzantine Generals, 但是这个算法用来处理事务时间开销又太大. Jim Graw 在会议上发布了一篇文章 “A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem.” (1987).
这篇论文包含了这样一段话在开头 :-)
“在这个会议之前, 大量的研究认为在分布式系统里面的事务提交是一个退化版本的Byzantine 将军问题. 可能这个会议最有用的结论是这两个问题没有任何的相关性”
最终分布式事务被看成了一个新版的一致性问题, 叫 uniform consensus (“Uniform consensus is harder than consensus” (2000)). 在uniform consensus 里面, 所有的进程必须同意一个值, 包括哪些出错的进程. 一个事务在当且仅当所有的RMs(资源管理者)已经准备好要提交的时候, 才能够提交. 大部分的一致性只考虑到不出错的进程达成一致. Uniform consensus考虑的是所有的进程都达成一致, 所以Uniform consensus 是更难实现的
最后 Lamport 在论文“The Part-Time Parliament” (submitted in 1990, published 1998).提出了Paxos一致性算法. 不幸的是这篇论文用希腊明主投票做类比的写法让人们很难看懂, 所以这篇文章一直被忽略. 直到被Butler Lampson 在他的论文“How to Build a Highly Availability System using Consensus” (1996) 提起. 这篇论文介绍了如何使用Paxos来建立一个容错的系统. 后来Lamport 才又发布了“Paxos Made Simple (2001)”, 写的让大家都看的明白.
Paxos最核心的问题是, 给定一个固定数目的进程, 这些进程的大部分定义为至少和其他的这个进程的大部分有一个相同的进程. 比如: 有A, B, C三个进程. 那么可能的这些进程大部分是AB, AC, BC. 如果有一个决定被某一个大部分通过, 比如AB. 那么任意一个时刻一个大部分的集合包含A或者B. 这样这些大部分的集合其它元素就可以从A, B那边获得这个决定的值.
Paxos能够容忍信息丢失, 消息的延迟, 消息的重复发送以及消息的乱序到达. 如存在一个唯一一个在足够长的时间内能够对某一个大部分集合进行两次访问的Leader, 那么这个系统就能达到一致. 任何进程, 包括Leader都可以失败或者重启. 实际上所有的进程允许在同一个时刻同时失败, 这个时候这个算法仍然是安全. 并且这个算法容忍在某一个时候有多个主存在.
Paxos是一个解决异步系统一致的算法; 这里并没有严格的超时限定. 然而只有当这个异步的系统表现出在同步的状态的情况下, 这个系统才能够达到一致. 在这个系统表现出在异步的状态的时候, 这个系统无法达成一致, 但是这个时候是安全的, 不会返回错误的结果. 有一个特殊的情形下Paxos是无法达成一致的, 这也是符合”FLP”的结论. 但是在实现的时候很容易避免这个情形.
明确的将系统分成同步和异步有点太过宽泛. Dwork, Lynch 和 Stockmeyer定义了一个偏序的同步系统 “Consensus in the presence of partial synchrony” (1988). 存在两个版本的偏序同步系统: 一种是进程运行在某一个固定的速度并且消息在某一个规定的时间内传达, 但是这个某一个值是多少事先是不知道的. 另一种是进程运行的速度范围以及消息送达的时间是事先可以知道的, 但是他们保持这种状态仅仅是在未来的一段时间内, 这个时间有多长, 我们不知道. 比起同步系统和异步系统, 这个偏序的同步系统更接近现实世界.网络在绝大部分的情况下应该是可预测的, 但是偶然还是会变的不可预测.
Lamport 和 Gray 在论文“Consensus on Transaction Commit” (2005)里继续尝试将Paxos应用到分布式事务系统里, 他们使用Paxos替换掉了两阶段提交里面的Transtraction Manager, 并且对每一个Resource Manager使用一个Paxos实例用来判断是否同意这个Resource Manager提交这个事务.表面上, 每一个Resource Manager 使用一个Paxos看过去成本特别高, 但是事实上不是的. 在没有错误的情况下, Paxos提交在两个阶段就会完成. 它和两阶段提交有着相同的消息延迟, 虽然可能会多传送一部分消息. 在有错误的情况下, Paxos的第三个阶段是需要的, 这个和Skeen 的结论也是一致的. 给定2n + 1个TM副本, Paxos的提交可以容忍n个错误的副本. Paxos提交不需要用Paxos直接解决事务提交的问题. Paxos 没有用来解决uniform consensus, 而是用来使这个系统容灾能力更强.
因为两阶段提交是阻塞的是无效的, Paxos 提交忙于解决阻塞这个问题. 所以有些人认为分布式事务不应该被使用.
最近有一些关于CAP(Consistency, Availability, Partition)猜想的讨论.这个猜想断言你不可能在一个分布式系统里面同时满足这三个属性, 也就是不存在一个系统, 它是一致的, 在有错误的进程存在并且有可能出现网络分区的情况下.
我们通过把Consistency 看成Consensus来检查一下这个CAP猜想, 对于一个异步系统, 根据FLP理论, 只要存在一个进程错误的情况下, 这个系统就无法达成一致. 所以对于一个异步的系统我们不能同时有一致性和可用性.
现在我们再看一下一个有三个节点的Paxos系统:A, B, C. 加入有两个节点在工作, 我们就能够达到一致. 那么我们就能实现一致性和可用性. 现在假如C被单独隔离了, 而这个时候有请求访问到C, 这个时候C是无法返回的, 因为必须有超过两个节点才能够返回结果, 而这个时候C无法和A, B节点通信的. C此刻是不知道是它自己被分区隔离了还是另外的两个节点都挂掉了, 还是说这个时候的网络特别慢的问题. 另外的两个节点能够继续的工作, 因为她们两个能够通信, 就可以超过半数的返回结果了. 所以对于CAP理论而言, Paxos并没有分区容错性, 因为这个时候C是无法对用户的请求回应的. 然而我们在工程上绕过这个问题. 假如在同一个数据中心里面, 我们可以使用两个独立的网络连接不同的节点, 因为Paxos可以容忍数据的重复发送.
对于一个同步的网络,假如C被分区了, 假如C在规定的周期内没有收到信息, 那么C能够知道它自己被分区了. 然后C就能够从客户端的访问中摘除掉了.
Paxos, Paxos Commit 和 HTTP/REST 已经被合并起来建立一个高可用的同配置网格计算系统. 详细的信息可以从这里获得HARC, 以及更多的在这个文章里面的讨论“Co-Allocation, Fault Tolerance and Grid Computing” (2006).