转载

第六篇 : Paxos 算法


        先说 Paxos,它是一个基于消息传递的一致性算法,Leslie Lamport 在 1990 年提出,近 几年被广泛应用于分布式计算中,Google 的 Chubby,Apache 的 Zookeeper 都是基于它的理 论来实现的,Paxos 还被认为是到目前为止唯一的分布式一致性算法,其它的算法都是 Paxos 的改进或简化。有个问题要提一下,Paxos 有一个前提:没有拜占庭将军问题。就是说 Paxos 只有在一个可信的计算环境中才能成立,这个环境是不会被入侵所破坏的。

        关于 Paxos 的具体描述可以在 Wiki 中找到:http://zh.wikipedia.org/zh-cn/Paxos 算法。网 上关于 Paxos 分析的文章也很多。这里希望用最简单的方式加以描述并建立起 Paxos 和 ZK Server 的对应关系。

        Paxos 描述了这样一个场景,有一个叫做 Paxos 的小岛(Island)上面住了一批居民,岛上 面所有的事情由一些特殊的人决定,他们叫做议员(Senator)。议员的总数(Senator Count)是确 定的,不能更改。岛上每次环境事务的变更都需要通过一个提议(Proposal),每个提议都有一 个编号(PID),这个编号是一直增长的,不能倒退。每个提议都需要超过半数((Senator Count)/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 号提议。

        好,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 等等等等,需要我们花更多的时间去研究和学习。

推荐一本不错的书 《从Paxos到Zookeeper分布式一致性原理与实践》

PDF 下载 : https://pan.baidu.com/s/1A1qv1U8YWBGK4ROLMSkrkQ 提取密码:on8k

zookeeper
  • 作者:程序员果果
  • 发表时间:2018-11-16 12:51
  • 版权声明:自由转载-非商用-非衍生-保持署名 (创意共享4.0许可证)
  • 公众号转载:请在文末添加作者公众号二维码
  • 评论