by Mark Mc Keown
http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html
转载请注明译者：phylips@bmy
出处：http://duanple.blog.163.com/blog/static/70971767201103051639551/
这是一段关于一致性，事务以及两阶段提交的历史的描述。阅读关于一致性的文献可能会有些困难，因为：各种用语在不断的演化着(比如一致性<consensus>最初叫做协商<agreement>)；各种研究成果并不是以一种逻辑性的顺序产生出来；同时描述整个分布式算法的框架与这些研究工作又是平行地演化着；此外除了Lynch的《分布式算法》外，很少有书籍涉及到这个主题。
下面涉及的这些论文不是按照它们的发表顺序来进行介绍，而是尽量以最容易理解的方式来组织。
我所知道的第一个一致性问题实例应该是Lamport的“Time, Clocks and the Ordering of Events in a Distributed System” (1978),尽管它并没有明确的提出一致性(consensus)或者协商(agreement)的概念。在这篇论文里，Lamport讨论了消息如何在有限的时间内在不同处理器之间传输，同时还利用爱因斯坦的狭义相对论进行了有趣的比喻。最近的博客空间上，人们经常将分布式系统和爱因斯坦的理论放在一起讨论。但是早在1978年，Lamport就采用时空图给出了一个完整的全方位的分析。关键问题在于，在一个分布式系统中，你无法判断事件A是否发生在事件B之前，除非A和B存在某种依赖关系。每个观察者都可能看到不同的事件发生序列，除非这些事件相互之间存在依赖关系，即分布式系统中的事件仅仅是部分有序的。Lamport定义了一个称为”发生在前”的关系和操作符，然后又给出了一个算法，用来确定分布式系统中的事件的全序关系，这样所有的进程就可以看到与其他进程一样的事件排序。
同时，Lamport还提出了分布式状态机的概念：让一组确定性状态机从相同的初始状态开始，之后保证它们以相同的顺序处理相同的消息。这样就可以保证每个状态机都是其他状态机的一个副本。关键的问题就是让每个状态机在“哪个消息是下一个需要处理的消息”这个问题上达成一致，这就是一个一致性问题。这就是一个创建事件排列的算法所需要做的，提供一个关于消息传输顺序的统一约定。然而，这个系统并不是容错的，如果一个进程出错，其他进程将无限等待下去直到它恢复。
大概在这篇论文发表的同一时间，JimGray在“Notes on Database Operating Systems” (1979)中描述了两阶段提交(2PC)。不幸的是，如果事务管理器在某个错误的时间点失败的话，2PC就会被阻塞。Dale Skeen在“NonBlocking Commit Protocols” (1981)中指出，对于一个分布式系统，需要3阶段的提交算法来避免2PC中的阻塞问题。问题关键在于找到一个好的3PC算法，这已花费了将近25年。
Fischer, Lynch 和 Paterson在“Impossibility of distributed consensus with one faulty process” (1985)中指出对于一个异步系统来说即使只有一个进程出错，分布式一致性也是不可能达到的，这就是著名的FLP结论。直到此时，consensus才成为“让一系列处理器在一个value上达成共识的”这一问题的叫法。在一个具有完美网络(所有的消息都会被传输，按序到达，不会重复)的异步系统(处理器以任意的速率运行，处理器间的消息传输可能花费任意时长)中，只要有一个出错进程(即使只有一次故障)分布式一致性就是不可能的。问题的核心在于，你无法区分一个进程到底是终止了还是正在以极低的速度执行，这使得在异步系统中的错误处理几乎是不可能的。此外这篇论文的重要性还在于它展示了如何证明某些事情是不可能的：首先证明解决该问题的算法都必须满足一些属性，然后证明满足这些属性是不可能的，比如通过反证法证明。(这种方法曾经被图灵用于停机问题的证明中)
此时，人们意识到一个分布式算法具有两个属性：安全性(safety)和活性(liveness)。安全性意味着坏的事情不会发生，而活性意味着某些好的事情最终一定会发生。2PC作为一个一致性算法，用来保证所有的进程在“事务要么提交要么失败退出”上达成一致。2PC是安全的，不会有坏的数据被写入到数据库，但是它的活性并不好：如果事务管理器在一个错误的点上失败，那么系统会阻塞。
也是在此时，人们意识到可以将一个分布式系统分为同步的(进程以已知的速率运行，消息会在限制的时间内传输)和异步的(进程以未知的任意的速率运行，消息的传输时间没有上界)。异步与同步相比，是一种更通用的情况。一个适用于异步系统的算法，也能被用于同步系统，但是反过来并不成立。你可以将同步系统看做是异步系统的一个特殊情况，只是消息传输时间恰好有个上界。
在FLP之前，还有这样一篇论文 “The Byzantine Generals Problem” (1982)。在这种形式的一致性问题中，进程还可能会说谎 ，而且它们还会尽力地去欺骗其他进程。这个问题看起来比FLP更难，但是对于同步的情况它确实存在一个解(尽管当这篇论文发表的时候，同步和异步系统的区分还没有明确提出)。但是这个解代价很高，需要大量多轮的消息传递。这个问题最初来源于航天工业：如果飞机上的传感器给出错误的信息会怎么样呢？(很明显，这个系统被认为是同步的)。
在1986年，分布式系统领域关注一致性和事务的人们聚在了一起。在那个时候，最好的一致性算法就是Byzantine Generals，但是这个算法代价太高而无法用于事务处理。关于这场会议JimGray写了一篇文章“A Comparison of the Byzantine Agreement Problem and the Transaction Commit Problem.” (1987) 。
这篇论文的导引里有如下的语句：
“Prior to the conference, it was widely believed that the transaction commit problem faced by distributed systems is a degenerate form of the Byzantine Generals Problem studied by academe. Perhaps the most useful consequence of the conference was to show that these two problems have little in common.”
“在这次会议之前，人们普遍认为分布式系统中的事务提交问题是拜占庭将军问题的一个退化版本。或许这次会议的最大意义在于指出二者很少有共同点。”
最终，分布式事务被认为是一个新的一致性问题，称为uniform consensus (参见“Uniform consensus is harder than consensus” (2000))。在uniform consensus中，所有的进程都必须在一个value上达成一致，即使是那些出错的进程。一个事务当且仅当所有的RM都准备好提交时才会被提交。而大多数的一致性问题只关注那些没有出错的进程可以达到一致。因此，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通过时，那么在以后的任何时刻其他的多数者集合中至少有一个元素能够记住之前的多数者集合做出的决定。比如对于多数者集合AB，那么A，B会记住决定，对于AC，A会记得，对于BC，B还记得。
Paxos可以容忍消息的丢失，延迟，重传和乱序。只要存在一个leader可以跟进程中的一个多数者集合会话两次，就能达到一致性。任何进程，包括leader在内，都可以失败或重启，实际上所有的进程可以在同一时间失败掉，而算法仍然是安全的。同一时间，可能有不止一个leader。
Paxos是一个异步算法，没有显式的超时设置。然而只有当系统表现出同步的方式时，它才能达到一致性。比如消息要在一定的时间内传输。根据FLP结论，存在一种病态的情况，Paxos在这种情况下无法达到一致性，但是在实际中避免出现这种情况相对容易些。
将一个系统简单的划分为同步异步有些宽泛。Dwork, Lynch 和 Stockmeyer在“Consensus in the presence of partial synchrony” (1988) 中定义了部分同步系统。存在两种类型的部分同步系统：其中一种情况是进程以给定边界内的速率运行，消息传输时间是有界的，但是边界的实际取值事先无法得知；另一种情况是处理速度的边界以及消息传输上界事先已知，但是只在未来的某个未知时间才开始成立。对于现实世界来说，部分同步模型是一个比同步异步模型更好的模型。大部分时间网络行为都是以一种可预测的方式发生，但是可能突然会变得很疯狂。
在“Consensus on Transaction Commit” (2005)中，Lamport和Jim Gray将Paxos应用在分布式事务提交问题中。他们使用Paxos来对2PC中的事务管理器进行高效的备份。对于事务中涉及的每个RM使用一个Paxos的实例来决定该RM(resource manager,实际上就是该事务涉及的进程)是否提交该事务。在这里面，为每个RM使用一个Paxos实例看起来很昂贵，但是实际证明情况并不是这样。对于没有错误发生的情况下，Paxos提交可以通过两个阶段完成，与2PC相比尽管有更多的消息需要传输但具有相同的消息延迟。只有当错误发生时，才需要第3个阶段。给定2n+1个事务管理器，当错误副本数小于等于n时，Paxos提交都可以完成。Paxos提交并没有使用Paxos算法来直接解决事务提交问题，它并不是用来解决uniform consensus，而是用来让系统容错。
有一种观点认为分布式事务不应该被使用，因为2PC是阻塞失效的。Paxos提交就是用来解决阻塞的问题。
最近有一些关于CAP(Consistency, Availability 和 Partition.)猜想的讨论。这个猜想指出，在分布式系统中，无法同时满足上述三个属性(即一个系统是一致的，同时具有出错进程还能容忍网络分割)。
我们可以将Consistency等同于consensus来检验下CAP。根据FLP结论，在一个异步系统中，当出现一个出错进程时，无法达到consensus。所以对于一个异步系统来说，我们无法同时得到Consistency和Availability。
假设现在有一个包含三个节点A，B和C的Paxos系统。如果有2个节点在工作，我们就能达到一致性，即我们可以得到consistency 和 availability。现在如果C被分割，而且有查询请求，它就会因无法与其他节点通信而无法响应{!这样就不具有可用性了}。它无法判断到底是自己被分割了，还是其他两个节点down掉了，又或者是网速很慢。其他两个节点可以正常进行，因为它们相互可以通信并形成一个多数者集合。所以对于CAP猜想，Paxos无法处理网络分割，因为C无法对查询做出响应。然而在工程上，我们可以绕过这个问题。假设我们处在一个数据中心内部，可以使用两套独立网络(Paxos并不介意出现重复消息)。如果我们是在因特网上，我们可以让客户端查询所有的节点A，B，C。如果C被分割了，它可以查询A或者B，除非它跟C一样被分割了。
对于一个同步网络，如果C被分割了，如果它在一定的时间内收不到消息就可以知道自己被分割了，因此能够向客户端声明自己down掉了。
Paxos, Paxos 提交 和 HTTP/REST已经被组合起来用于构建高可用的网格计算系统，参见HARC。更多的描述可以参考: “Co-Allocation, Fault Tolerance and Grid Computing” (2006)。