zookeeper 学习之 paxos 算法
zookeeper
什么是 Zookeeper ?
ZooKeeper 是一个分布式的，开放源码的分布式应用程序协调服务，是Google的Chubby一个开源的实现，是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件，提供的功能包括：配置维护、域名服务、分布式同步、组服务等。
Paxos 算法
唯一的分布式一致性算法
Paxos 算法 小故事
有一个叫做paxos的小岛（Island）上面住了一批居民，岛上面的所有事情由一些特殊的人决定，他们叫做议员（Senator）。议员的总数是确定的，不能更改。岛上每次换次事务的变更都需要通过一个提议（proposal），每个提议都有一个编号（PID），这个编号是一直增长的，不能倒退。每个提议都需要超过半数（（Senator Count）/2+1）的议员同意才能生效。每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。如果议员收到小于等于当前编号的提议，则会拒绝并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本的编号总是相同的。现在议会有一个目标：保证所有的议员对于提议都能达成一致性的看法。
现在议会开始运作，所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议：将电费设定为1元/度。他首先看了一下记事本，当前提议编号是0，那么我这个提议的编号就是1，于是他给所有议员发消息：1号提议，设定电费1元/度。其他议员收到消息以后查了一下记事本，哦，当前提议编号是0，这个1号提议可以接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记录：当前提议编号为1.发起提议的议员收到了超过半数的回复，立即给所有人回复通知：1号提议生效！收到的议员会修改他的记事本，将1号提议有记录改成正式的法令，当有人问他电费是多少时，他会查看法令并告诉对方：1元/度。
现在看冲突的解决：假设总共有3个议员：s1,s2,s3。s1和s2同时发起一个提议：1号提议，设定电费。S1想设为1元/度，s2想设为2元/度。结果s3先收到s1的提议，于是他做了和前面同样的操作。紧接着他又收到了s2的提议，结果他查了一下记事本，这个提议的编号小于等于我当前编号1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是s2的提议被拒绝，s1正式发布了提议：1号提议生效。s2向s1或者s3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。
paxos的精华就是这些内容，现在对号入座，看看ZK Server里面paxos是如何得以贯彻实施的。
小岛（Island）--ZK Server Cluster
议员（Senator） --ZK Server
提议（proposal） -- Znode Change（Create/Delete/SetData..）
提议编号（PID） -- Zxid（Zookeeper Transaction Id）
正式法令 -- 所有Znode及其数据
貌似关键的概念都能一一对应上，但是等一下，paxos岛上的议员应该是人人平等的吧，但是ZK Server还有一个Leader的概念。其实Leader的概念也应该属于paxos范畴的。如果议员人人平等，在某种情况下由于提议的冲突而产生一个“活锁”（所谓活锁我的理解是大家都没有死，都在动，但是一直解决不了冲突问题）。paxos作者Lamport在他的文章“The Part-Time Parliament” 中阐述了这个问题并给出了解决方案--在所有议员中设立一个总统，只有总统有权发出提议，如果议员有自己的提议，必须发给总统并由总统来提出。好，我们又多了一个角色：总统。
总统 --ZK Server Leader
又一个问题产生了，总统怎么选出来的？
现在假设总统已经选好了，下面看看ZK Server是怎么实施的。
-
情况一：
屁民甲（client）到某个议员（ZK Server）那里询问（Get）某条法令的情况（Znode的数据），议员毫不犹豫的拿出他的记事本（local storage），查阅法令并告诉他结果，同时声明：我的数据不一定是最新的。你想要最新的数据？媒体，等着，等我找总统Sync一下再告诉你。 -
情况二：
屁民乙（Client）到某个议员（ZK Server）那里要求政府归还欠他的一万元钱，议员让他在办公室等着，自己将问题反映给了总统，总统询问所有议员的意见，多数议员表示欠屁民的钱一定要换，于是总统发表声明，从国库中拿出一万元还债，国库总资产由100万变成99万。屁民乙拿到钱回去了（Client函数返回） -
情况三：
总统突然挂了，议员接二连三的发现联系不上总统，于是各自发表声明，推选新的总统，总统大选期间政府停业，拒绝屁民的请求。
到此为止，当然还有其他很多的情况，但这些情况总是能在paxos的算法中找到原型并加以解决。这也正是我们认为paxos是Zookeeper的灵魂的原因。当然ZK Server还有很多属于自己特性的东西：Session，Watcher，Version等等，需要我们花更多是时间研究和学习。
