内容简介：zookeeper入门系列：paxos协议
上一章讨论了一种强一致性的情况，即需要分布式事务来解决，本章我们来讨论一种最终一致的 算法 ，paxos算法。
paxos算法是由大牛lamport发明的，关于paxos算法有很多趣事。比如lamport论文最初由故事描述来引入算法，以至于那班习惯数学公式的评委将该论文打回，导致该论文延误了8年才公开发表。另外，google的chubby的作者Mike Burrows说过，世界上只有一种一致性算法，那就是paxos。
两将军问题
为了引入该算法，首先提出一种场景，即 两将军问题 （见文献1）：
有两支军队，它们分别有一位将军领导，现在准备攻击一座修筑了防御工事的城市。这两支军队都驻扎在那座城市的附近，分占一座山头。一道山谷把两座山分隔开来，并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。不幸的是，这个山谷已经被那座城市的保卫者占领，并且存在一种可能，那就是任何被派出的信使通过山谷是会被捕。 请注意，虽然两位将军已经就攻击那座城市达成共识，但在他们各自占领山头阵地之前，并没有就进攻时间达成共识。两位将军必须让自己的军队同时进攻城市才能取得成功。因此，他们必须互相沟通，以确定一个时间来攻击，并同意就在那时攻击。如果只有一个将军进行攻击，那么这将是一个灾难性的失败。
两将军问题本质上就是通信被篡改时能否解决一致性问题。这个问题已经被很多人证明不能。（见文献1）。因而由此推及的 拜占庭将军 问题（多将军问题）也同样不能被解决。
PAXOS算法
一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。
这里不再赘述算法的推导及证明过程，参考文献2和3。这里简单描述下算法理解。
基本思想也是两阶段提交。但是与两阶段目的不同。
1. 第一阶段主要目的是选出提案编号最大的proposer。
其描述如下，所有的proposer向 超过半数 的acceptor提出编号为n的提案，acceptor收到编号为n的请求，会出现两种情况
a. 编号n大于所有acceptor之前 已经批准过 的proposal的最大编号及内容m。acceptor同意该proposal，响应[n, m]回proposer，并且承诺今后不再批准任何编号小于n的提案。
b. 编号n小于acceptor之前 批准过 的任意proposal的编号。acceptor拒绝该proposal。
2. 第二阶段尝试对某一proposal达成一致。
proposer收到 超过半数 的acceptor返回的响应，proposer就会将响应的最大编号[n, m]对应的提案提交到acceptor要求acceptor批准该提案。
acceptor收到最大编号[n, m]的提案，也分为两种情况
a. 未响应过编号大于n的 prepare请求 。通过该提案。
b. 已响应过编号大于n的 prepare请求 。拒绝该提案。
整个算法表面上并不难理解，难在实现细节的难易程度和各种异常情况的推导及考虑。如果对上述算法有理解困难的，参考文献4和文献5的例子，其中文献5更容易理解，这里 把他的图贴出来，实际过程就不再重复赘述了。
两个参谋先后提议的场景：
两个参谋交叉提议的场景：
需要注意的是参谋1在失败时再次发起请求的过程。
这里着重强调 几个重点 ：
- 算法描述里有好几个地方要求投票必须超过半数，这个超过半数恰恰是保证一致的一个必要条件；
- 算法里也有多处要求只选择编号最大的，这种选择编号最大的方式，是一种最为简单经济的达成共识的方法，能够快速在多个冲突中找到一个突破口；
- paxos算法的关键是，如果一个值m被选中了，那么必须保证更高的proposal其值也为m；
- 注意第一阶段比较的是已经批准过的proposal的最大编号，而第二阶段比较的是prepare请求。即第一阶段比较的是第二阶段的结果，而第二阶段比较的是第一阶段的结果，看似很绕，实际上正好是隔离了阶段外的保证，进入第一阶段的我要保证他是新的开始，跟上一阶段没啥关系，而进入第二阶段的我要保证他是从前面阶段来的，而不是新起的一个阶段，有点像是隔离锁，锁住了阶段一到阶段二这个过程。
参考阅读
以上所述就是小编给大家介绍的《zookeeper入门系列：paxos协议》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- TiDB入门（四）：从入门到“跑路”
- MyBatis从入门到精通(一)：MyBatis入门
- MyBatis从入门到精通(一)：MyBatis入门
- Docker入门（一）用hello world入门docker
- 赵童鞋带你入门PHP（六） ThinkPHP框架入门
- 初学者入门 Golang 的学习型项目，go入门项目
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
C++数据结构与程序设计
克鲁斯 / 钱丽萍 / 清华大学出版社 / 2004-1 / 59.00元
《C++数据结构与程序设计》这本精心制作的课本结合面向对象程序设计和C++强有力的特性，构建数据结构的基本思想，设计了程序和有趣的应用。在此过程中，《C++数据结构与程序设计》探讨了作为软件设计基本工具的问题求解和设计原理、数据抽象、递归和算法的比较分析。《C++数据结构与程序设计》使用真实的案例研究、可重用的软件开发和程序设计项目来增强理解。一起来看看 《C++数据结构与程序设计》 这本书的介绍吧!
