文档章节

Paxos分布式一致性算法简介和Apache ZooKeeper的概念映射

foodon
 foodon
发布于 2014/12/16 15:50
字数 1561
阅读 2640
收藏 7
Paxos是一个基于消息传递的一致性算法,近几年被广泛应用于分布式计算中,Google的Chubby,Apache的Zookeeper都是基于它的理论来实现的,Paxos还被认为是到目前为止唯一的分布式一致性算法,其它的算法都是Paxos的改进或简化。Paxos只有在一个可信的计算环境中才能成立,这个环境是不会被入侵所破坏的。

由Leslie Lamport发明了Paxos算法,他目前供职于微软研究院。1998年在ACM Transactions on Computer Systems的《The Part-Time Parliament》论文是Paxos算法第一次公开发表,文本可参考微软研究院地址:http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf。Lamport觉得同行无法接受他的幽默感,于是用容易接受的方法重新表述了一遍,文本可参考微软研究院地址:http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf。

Paxos算法的中文译本可参考这里:http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95。

本文部分内容根据http://www.spnguru.com/?p=232的文字整理,但原地址已失效,所以实际是从这个http://blog.csdn.net/cxhzqhzq/article/details/6568040转帖整理。

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号提议。

现在让我们来对号入座,看看在ZK Server里面Paxos是如何得以贯彻实施的。
小岛(Island)——ZK Server Cluster
议员(Senator)——ZK Server
提议(Proposal)——ZNode Change(Create/Delete/SetData…)
提议编号(PID)——Zxid(ZooKeeper Transaction Id)
正式法令——所有ZNode及其数据
在所有议员中设立一个总统,只有总统有权发出提议,如果议员有自己的提议,必须发给总统并由总统来提出。
总统——ZK Server Leader

现在我们假设总统已经选好了,下面看看ZK Server是怎么实施的。
情况一:
屁民甲(Client)到某个议员(ZK Server)那里询问(Get)某条法令的情况(ZNode的数据),议员毫不犹豫的拿出他的记事本(local storage),查阅法令并告诉他结果,同时声明:我的数据不一定是最新的。你想要最新的数据?没问题,等着,等我找总统Sync一下再告诉你。
情况二:
屁民乙(Client)到某个议员(ZK Server)那里要求政府归还欠他的一万元钱,议员让他在办公室等着,自己将问题反映给了总统,总统询问所有议员的意见,多数议员表示欠屁民的钱一定要还,于是总统发表声明,从国库中拿出一万元还债,国库总资产由100万变成99万。屁民乙拿到钱回去了(Client函数返回)。
情况三:
总统突然挂了,议员接二连三的发现联系不上总统,于是各自发表声明,推选新的总统,总统大选期间政府停业,拒绝屁民的请求。

© 著作权归作者所有

foodon
粉丝 64
博文 56
码字总数 27005
作品 0
海淀
技术主管
私信 提问
加载中

评论(2)

java我人生
java我人生
不错,瞬间明白了好多,非常感谢!
m
mpw0563
赞!看了好几篇类似的博文,这篇不错。例子很形象
ZooKeeper学习笔记三 ZooKeeper与Paxos

本文学习内容来自: 《从Paxos到ZooKeeper分布式一致性原理与实践》 电子工业出版社 Apache ZooKeeper是由Apache Hadoop的子项目发展而来,于2010年11月正式成为了Apache的顶级项目。ZooKeep...

xundh
2018/04/27
0
0
【转】可能是全网把 ZooKeeper 概念讲的最清楚的一篇文章

前言 相信大家对 ZooKeeper 应该不算陌生。但是你真的了解 ZooKeeper 是个什么东西吗?如果别人/面试官让你给他讲讲 ZooKeeper 是个什么东西,你能回答到什么地步呢? 我本人曾经使用过 ZooK...

Jinlong_Xu
07/26
0
0
大数据教程(3.3):zookeeper简介

一、概念 ZooKeeper是一个分布式的,开放源码的分布式应用程序协调服务,是Google的Chubby一个开源的实现,是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功...

em_aaron
2018/07/28
99
0
这可能是把ZooKeeper概念讲的最清楚的一篇文章

我本人曾经使用过 ZooKeeper 作为 Dubbo 的注册中心,另外在搭建 Solr 集群的时候,我使用到了 ZooKeeper 作为 Solr 集群的管理工具。 前几天,总结项目经验的时候,我突然问自己 ZooKeeper ...

51CTO技术栈
2018/09/11
0
0
分布式设计与开发(三)------高一致性服务ZooKeeper

分布式环境中大多数服务是允许部分失败,也允许数据不一致,但有些最基础的服务是需要高可靠性,高一致性的,这些服务是其他分布式服务运转的基础,比如naming service、分布式lock等,这些分...

山哥
2012/03/19
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

方法重载和重写是什么?有什么区别?

重写:在子类中将父类的成员方法的名称保留,重新编写成员方法的实现内容,更改方法的访问权限,修改返回类型的为父类返回类型的子类。 一些规则: 重写发生在子类继承父类 参数列表必须完全...

ConstXiong
15分钟前
2
0
Spring-Framework 目录

ls spring-orm/src/main/java/org/springframework/orm/hibernate5/ ObjectRetrievalFailureException.java jpa/ ......

MtrS
33分钟前
3
0
大学慕课

Visual C,Turbo C,Dev C的关系 不管是 Visual C、Turbo C 还是 Dev C,本质都是C语言,不存在高下之分。 三种叫法不同是因为 C 语言在三种不同的开发环境中拥有一些不同的开发习惯的区别。...

电子197徐泽彬
52分钟前
3
0
GC偏方 强行fullgc

转自 https://www.jianshu.com/p/be5389ca93f7 FullGC这么恐怖,有办法缓解么,或者说尽量避免它在白天,甚至业务高峰期出现?有!笔者给你分享一个歪门邪道,不记得是多少年前,在哪里道听途...

os_m
56分钟前
4
0
源码分析Mybatis MappedStatement的创建流程

上文源码分析Mybatis MapperProxy创建流程重点阐述 MapperProxy 的创建流程,但并没有介绍 *.Mapper.java(UserMapper.java) 是如何与 *Mapper.xml 文件中的 SQL 语句是如何建立关联的。本文将...

中间件兴趣圈
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部