Zookeeper全解析----Paxos

Zookeeper全解析----Paxos

1. Paxos算法背景

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其他算法都是Paxos的改进或简化，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致。 Paxos有一个前提：没有拜占庭将军问题。就是说Paxos只有在一个可信的计算环境中才能成立，这个环境是不会被入侵所破坏的；即：信道是安全的（信道可靠），发出的信号不会被篡改，因为Paxos算法是基于消息传递的。

什么是拜占庭问题？ 指 拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，只能依靠通讯员进行传递命令，但是通讯员中存在叛徒，它们可以篡改消息，叛徒可以欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。

2. Paxos算法概述

有一个叫做Paxos的小岛(Island)上面住了一批居民，岛上面所有的事情由一些特殊的人决定，他们叫做议员(Senator)。 议员的总数(Senator Count)是确定的，不能更改。 岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一个编号(PID)，这个编号是一直增长的，不能倒退。 每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效。 每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。如果议员收到小于等于当前编号的提议，他会拒绝，并告知对方：你的提议已经有人提过了。 这里的当前编号是每个议员在自己记事本上面记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。

2.1. 如何保证所有的议员对于提议都能达成一致的看法？

最开始，所有议员记事本上记录的编号都是0。 有一个议员发了一个提议：将电费设定为1元/度。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1，于是他给所有议员发消息：1号提议，设定电费1元/度。 其他议员收到消息以后查了一下记事本，哦，当前提议编号是0，这个提议可接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记录：当前提议编号为1。 发起提议的议员收到了超过半数的回复，立即给所有人发通知：1号提议生效！收到的议员会修改他的记事本，将1号提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法令并告诉对方：1元/度。

当提议出现冲突时 ：假设总共有三个议员S1-S3，S1和S2同时发起了一个提议:1号提议，设定电费。S1想设为1元/度, S2想设为2元/度。 结果S3先收到了S1的提议，于是他做了和前面同样的操作。紧接着他又收到了S2的提议，结果他一查记事本，咦，这个提议的编号等于我的当前编号1。 于是他拒绝了这个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，S1正式发布了提议: 1号提议生效。S2向S1或者S3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。

我们把这个故事和ZK server对应起来：

小岛(Island)——ZK Server Cluster议员(Senator)——ZK Server提议(Proposal)——ZNode Change(Create/Delete/SetData…)提议编号(PID)——Zxid(ZooKeeper Transaction Id)正式法令——所有ZNode及其数据

2.2. 无leader冲突问题

Paxos岛上的议员应该是人人平等的吧，而ZK Server有一个Leader的概念。Leader的概念也应该属于Paxos范畴的。如果议员人人平等，在某种情况下会由于提议的冲突而产生一个“活锁”。 Paxos的作者Lamport在他的文章”The Part-Time Parliament“中阐述了这个问题并给出了解决方案——在所有议员中设立一个总统，只有总统有权发出提议，如果议员有自己的提议，必须发给总统并由总统来提出。

总统——ZK Server Leader

2.3. 总统(leader)怎么选出来的

假如node04是总统，node04突然挂了，而此时node03第一个发现node04挂掉了，但是node03的事务ID最小。node01和node02收到node03对自己(node03)的投票会拒绝，进而投自己(node01/node02)一票，然后进行广播，最后由于node02的myid比较大，node02成功上位、变身总统。

2.4. zkServer的运作

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。