中国建设银行云南官网站纪念币,seo搜索优化网站推广排名,赤峰网站建设招聘,站长seo计费系统这是一段关于一致性#xff0c;事务以及两阶段提交的历史的描述阅读关于一致性的文献可能会有些困难#xff0c;因为#xff1a; 各种用语在不断的演化着(比如一致性consensus最初叫做协商agreement)#xff1b; 各种研究成果并不是以一种逻辑性的顺序产生…这是一段关于一致性事务以及两阶段提交的历史的描述阅读关于一致性的文献可能会有些困难因为 各种用语在不断的演化着(比如一致性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)这篇论文的导引里有如下的语句“在这次会议之前人们普遍认为分布式系统中的事务提交问题是拜占庭将军问题的一个退化版本或许这次会议的最大意义在于指出二者很少有共同点”最终分布式事务被认为是一个新的一致性问题称为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的核心是给定固定数目的进程任何一个多数者集合与其他的多数者集合必然至少存在一个公共元素比如给定三个元素AB和C那么可能的多数者集合是AB, AC, 或者 BC当一个决定由其中一个多数者集合比如AB通过时那么在以后的任何时刻其他的多数者集合中至少有一个元素能够记住之前的多数者集合做出的决定比如对于多数者集合AB那么AB会记住决定对于ACA会记得对于BCB还记得Paxos可以容忍消息的丢失延迟重传和乱序只要存在一个leader可以跟进程中的一个多数者集合会话两次就能达到一致性任何进程包括leader在内都可以失败或重启实际上所有的进程可以在同一时间失败掉而算法仍然是安全的同一时间可能有不止一个leaderPaxos是一个异步算法没有显式的超时设置然而只有当系统表现出同步的方式时它才能达到一致性比如消息要在一定的时间内传输根据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个阶段给定2n1个事务管理器当错误副本数小于等于n时Paxos提交都可以完成Paxos提交并没有使用Paxos算法来直接解决事务提交问题它并不是用来解决uniform consensus而是用来让系统容错有一种观点认为分布式事务不应该被使用因为2PC是阻塞失效的Paxos提交就是用来解决阻塞的问题有一些关于CAP(Consistency(一致性), Availability(可用性) 和 Partition tolerance(分区容错性))猜想的讨论这个猜想指出在分布式系统中无法同时满足上述三个属性(即在分布式系统的设计中无法同时满足对数据的实时一致性要求、完全无故障的可用性以及分区容错性)我们可以将Consistency等同于consensus(共识)来检验下CAP根据FLP结论在一个异步系统中当出现一个出错进程时无法达到consensus所以对于一个异步系统来说我们无法同时得到Consistency和Availability(在网络分区(网络故障)的情况下系统需要在可用性和一致性之间作出选择即是选择保持可用性而降低一致性还是放弃一些可用性以维持一致性)假设现在有一个包含三个节点AB和C的Paxos系统如果有2个节点在工作我们就能达到一致性即我们可以得到consistency 和 availability现在如果C被分割而且有查询请求它就会因无法与其他节点通信而无法响应{!这样就不具有可用性了}它无法判断到底是自己被分割了还是其他两个节点down掉了又或者是网速很慢其他两个节点可以正常进行因为它们相互可以通信并形成一个多数者集合所以对于CAP猜想Paxos无法处理网络分割因为C无法对查询做出响应然而在工程上我们可以绕过这个问题假设我们处在一个数据中心内部可以使用两套独立网络(Paxos并不介意出现重复消息)如果我们是在因特网上我们可以让客户端查询所有的节点ABC如果C被分割了它可以查询A或者B除非它跟C一样被分割了对于一个同步网络如果C被分割了如果它在一定的时间内收不到消息就可以知道自己被分割了因此能够向客户端声明自己down掉了
