- 浏览: 208548 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
strong8808:
activemq5.8.0 客户端,服务端启动序列图 -
xurichusheng:
第一题,如果使用 not exists 的话,可以改成:SEL ...
SQL笔试题 -
dingjun1:
cuisuqiang 写道如何解决呢?我的是对了也照样缓存增加 ...
事务未正确关闭引起的HIBERNATE SESSION不能正确关闭 -
dingjun1:
aijezdm915 写道lz ,我也是在写项目描述是犯愁,能 ...
如果在简历中描述项目 -
aijezdm915:
lz ,我也是在写项目描述是犯愁,能否给个你的简历demo,我 ...
如果在简历中描述项目
转载:
http://blog.sina.com.cn/s/blog_5d97745a0101ei6f.html
在分布式系统设计领域,Paxos可谓是最重要一致性的算法。Google的大牛们称
All working protocols for asynchronous consensus we have so far encountered have Paxos at their core.
可见此算法的地位。网络上讨论此算法的文章多如牛毛,但大多数让人看了之后仍然是一头雾水,就连维基百科中,对此算法的描述亦有含糊和错误之处。但实际上,此算法的核心思想还是比较简单的,只是大多数文章的分析脱离了实际应用,或是陷入大量实现细节以致掩盖了算法的核心。本文将先给出Paxos算法的设计目的,和算法流程,再反过来分析算法的原理。
Paxos算法实现的是分布式系统多个结点之上数据的一致性,这个算法有如下特性
1.基于消息传递,允许消息传输的丢失,重复,乱序,但是不允许消息被攥改
2.在结点数少于半数失效的情况下仍然能正常的工作,结点失效可以在任何时候发生而不影响算法正常执行。
下面是Basic Paxos算法,注意,这个算法只具有在多个冲突请求中选出一个的功能,并不具备序列化多个请求依次执行的功能。
Paxos算法包含三个角色Proposor,Acceptor,Learner。
实现的时候采用一组固定数目Server,每个Server同时担任上述三个角色,多个Client将自己的请求值Value_i随机发给一个Server处理,然后这一组Server经过协商后得出统一的一个值Chosen_Value,这个值必须被每个Server学习到,同时回复给所有发起请求的Client。
具体算法流程如下,为避免歧义,关键字眼Propose,Proposal,Accept,Value,Choose等保留英文原文
每个Proposor 拿到某个Client的请求Value_i后,在此阶段还不能发起Proposal,只能发送一个Proposal序号N,将序号发送给所有 Acceptor(即所有Server包括自己),整个系统中所有Proposal的序号不能重复而且每个Proposor自己用到的序号必须是递增的,通常的做法是,假设K台Server协同运行Paxos算法,那么Server_i(i=0...K-1)用的Proposal序号初始值为i,以后每次要产生新序号时递增K,这样保证了所有Server的Proposal序号不重复。
阶段1b---Respond with Promise
每个Acceptor收到Proposal序号后,先检查之前是否Repond序号更高的Proposal,若没有,那么就给出Response,这个 Response带有自己已经Accept的序号最高的Proposal(若还没Accept任何Proposal,回复null),同时,Promise自己不再Accept低于接收序号的Proposal。否则,拒绝Respond。
阶段2a---发起Proposal,请求Accept
Proposal 如果得到了来自超过半数的Acceptor的Response,那么就有资格向Acceptor发起Proposal<N,value>。其中,N是阶段1a中发送的序号,value是收到的Response中序号最大的Proposal的Value,若收到的Response全部是 null,那么Value自定义,可直接选一个Client请求的Value_i
阶段2b--Accept Proposal
检查收到的Proposal的序号是否违反阶段1b的Promise,若不违反,则Accept收到的Proposal。
所有Acceptor Accept的Proposal要不断通知所有Learner,或者Learner主动去查询,一旦Learner确认Proposal已经被超过半数的Acceptor Accept,那么表示这个Proposal 的Value 被 Chosen,Learner就可以学习这个Proposal的Value,同时在自己Server上就可以不再受理Proposor的请求。
这个算法能达到什么效果呢,只要保证超过半数的Server维持正常工作,同时连接工作Server的网络正常(网络允许消息丢失,重复,乱序),就一定能保证,
P2a: 在将来某一时刻,自从某个Proposal被多数派Acceptor Accept后,之后Accept的Proposal Value一定和这个Proposal Value相同。
这就是整个算法的关键,保证了这一点,剩下的Learn Value过程就简单了,无需再为消息丢失,Server宕机而担心,例如,假设5台Server编号0~4,Server0,Server1,Server2已经Accept Proposal 100,然后Server0,Server1学习到Proposal 100,刚学习完成Server0,Server1就都宕机了,但这时候,Server2 Server3和Server4由于没有学习到Chosen value,因此还要继续提出Proposal,然后呢,根据这个神奇的算法,最后能使得Server3 Server4将来Accept的值一定是之前选出来过的Proposal 100的Value。
看到这里,大家应该能够隐隐猜到,在这个过程中,Server2之前Accept Proposal 100的Value起了关键作用,下面,我们就来严格证明上述红色字体表示的算法关键点:
1.发起Proposal前要先获得多数派Acceptor中Accept过的序号最大的Proposal Value。若Value为null才能采用自己的Value。
2.阶段1b Promise自己不再Accept低于接收序号的Proposal。
3.Propsal被超半数的Acceptor Accept才能被认定为Chosen Value从而被Learner学习。
这几个约束条件共同作用,达到了上述P2a要求的效果,Paxos算法提出者Leslie Lamport是怎么构造出来的呢,事实上很简单:
首先,把P2a加强为如下条件:
P2b:自从某个Proposal被多数派Acceptor Accept后,之后Proposor提出的Proposal Value一定和这个Proposal Value相同。
显而易见,由P2b可以推出P2a,那么怎么满足P2b呢,实际上,只要满足如下条件:
P2c:发起的Proposal的Value为任意一个多数派Acceptor集合中Accept过的序号最大的Proposal Value。若这个Acceptor集合中没有Accept过Proposal才能采用自己的Value。
如何从P2c推出P2b呢,利用数学归纳法可以轻易做出证明:假设在某一时刻一个超半数Acceptor集合C共同Accept了某个Proposal K,由于集合C和任意一个多数派Acceptor集合S必有一个共同成员,那么,在这个时刻之后,任意一个多数派Acceptor集合S 中Accept过的最大序号的Proposal只可能是Proposal K或序号比Proposal K更大的Proposal,假设为Proposal K2。同理,Proposal K2的Value等于Proposal K或Proposal K3的Value,而K<K3<K2,递推下去,最终推出根据P2c定出的Value必然是Proposal K的Value。
我们可以看到,P2c条件基本就是上述两阶段协议的关键点1,但是还有一个问题,这个P2c条件要求找出这个“最大序号Value”和提出Proposal必须是一个原子操作,这实际上是难以实现的,所以,上述两阶段协议用了一个巧妙的方法避开了这个问题,这就是上述关键点2 Promise所起的作用了。在Acceptor respond“最大序号Value”的时候,Promise不再Accept低于收到序号的Proposal,这样“找出这个‘最大序号Value’”和“提出Proposal”之间就不可能插入新的被Accept的序号,从而避免P2c条件被破坏。
到这里为止,基本的Paxos算法就已经透彻分析完了,但是,现在这个算法是使用多个Proposal,会造成活锁问题,需要引入leader来优化,而且,这个算法还只能实现在多个冲突Value中选举一个Value的功能,至于序列化多个Value实现状态机,就需要multi-paxos算法。
simple paxos中文译本:
参考:http://www.cnblogs.com/chen77716/archive/2011/01/27/2130804.html
http://blog.sina.com.cn/s/blog_5d97745a0101ei6f.html
在分布式系统设计领域,Paxos可谓是最重要一致性的算法。Google的大牛们称
All working protocols for asynchronous consensus we have so far encountered have Paxos at their core.
可见此算法的地位。网络上讨论此算法的文章多如牛毛,但大多数让人看了之后仍然是一头雾水,就连维基百科中,对此算法的描述亦有含糊和错误之处。但实际上,此算法的核心思想还是比较简单的,只是大多数文章的分析脱离了实际应用,或是陷入大量实现细节以致掩盖了算法的核心。本文将先给出Paxos算法的设计目的,和算法流程,再反过来分析算法的原理。
Paxos算法实现的是分布式系统多个结点之上数据的一致性,这个算法有如下特性
1.基于消息传递,允许消息传输的丢失,重复,乱序,但是不允许消息被攥改
2.在结点数少于半数失效的情况下仍然能正常的工作,结点失效可以在任何时候发生而不影响算法正常执行。
下面是Basic Paxos算法,注意,这个算法只具有在多个冲突请求中选出一个的功能,并不具备序列化多个请求依次执行的功能。
Paxos算法包含三个角色Proposor,Acceptor,Learner。
实现的时候采用一组固定数目Server,每个Server同时担任上述三个角色,多个Client将自己的请求值Value_i随机发给一个Server处理,然后这一组Server经过协商后得出统一的一个值Chosen_Value,这个值必须被每个Server学习到,同时回复给所有发起请求的Client。
具体算法流程如下,为避免歧义,关键字眼Propose,Proposal,Accept,Value,Choose等保留英文原文
每个Proposor 拿到某个Client的请求Value_i后,在此阶段还不能发起Proposal,只能发送一个Proposal序号N,将序号发送给所有 Acceptor(即所有Server包括自己),整个系统中所有Proposal的序号不能重复而且每个Proposor自己用到的序号必须是递增的,通常的做法是,假设K台Server协同运行Paxos算法,那么Server_i(i=0...K-1)用的Proposal序号初始值为i,以后每次要产生新序号时递增K,这样保证了所有Server的Proposal序号不重复。
阶段1b---Respond with Promise
每个Acceptor收到Proposal序号后,先检查之前是否Repond序号更高的Proposal,若没有,那么就给出Response,这个 Response带有自己已经Accept的序号最高的Proposal(若还没Accept任何Proposal,回复null),同时,Promise自己不再Accept低于接收序号的Proposal。否则,拒绝Respond。
阶段2a---发起Proposal,请求Accept
Proposal 如果得到了来自超过半数的Acceptor的Response,那么就有资格向Acceptor发起Proposal<N,value>。其中,N是阶段1a中发送的序号,value是收到的Response中序号最大的Proposal的Value,若收到的Response全部是 null,那么Value自定义,可直接选一个Client请求的Value_i
阶段2b--Accept Proposal
检查收到的Proposal的序号是否违反阶段1b的Promise,若不违反,则Accept收到的Proposal。
所有Acceptor Accept的Proposal要不断通知所有Learner,或者Learner主动去查询,一旦Learner确认Proposal已经被超过半数的Acceptor Accept,那么表示这个Proposal 的Value 被 Chosen,Learner就可以学习这个Proposal的Value,同时在自己Server上就可以不再受理Proposor的请求。
这个算法能达到什么效果呢,只要保证超过半数的Server维持正常工作,同时连接工作Server的网络正常(网络允许消息丢失,重复,乱序),就一定能保证,
P2a: 在将来某一时刻,自从某个Proposal被多数派Acceptor Accept后,之后Accept的Proposal Value一定和这个Proposal Value相同。
这就是整个算法的关键,保证了这一点,剩下的Learn Value过程就简单了,无需再为消息丢失,Server宕机而担心,例如,假设5台Server编号0~4,Server0,Server1,Server2已经Accept Proposal 100,然后Server0,Server1学习到Proposal 100,刚学习完成Server0,Server1就都宕机了,但这时候,Server2 Server3和Server4由于没有学习到Chosen value,因此还要继续提出Proposal,然后呢,根据这个神奇的算法,最后能使得Server3 Server4将来Accept的值一定是之前选出来过的Proposal 100的Value。
看到这里,大家应该能够隐隐猜到,在这个过程中,Server2之前Accept Proposal 100的Value起了关键作用,下面,我们就来严格证明上述红色字体表示的算法关键点:
1.发起Proposal前要先获得多数派Acceptor中Accept过的序号最大的Proposal Value。若Value为null才能采用自己的Value。
2.阶段1b Promise自己不再Accept低于接收序号的Proposal。
3.Propsal被超半数的Acceptor Accept才能被认定为Chosen Value从而被Learner学习。
这几个约束条件共同作用,达到了上述P2a要求的效果,Paxos算法提出者Leslie Lamport是怎么构造出来的呢,事实上很简单:
首先,把P2a加强为如下条件:
P2b:自从某个Proposal被多数派Acceptor Accept后,之后Proposor提出的Proposal Value一定和这个Proposal Value相同。
显而易见,由P2b可以推出P2a,那么怎么满足P2b呢,实际上,只要满足如下条件:
P2c:发起的Proposal的Value为任意一个多数派Acceptor集合中Accept过的序号最大的Proposal Value。若这个Acceptor集合中没有Accept过Proposal才能采用自己的Value。
如何从P2c推出P2b呢,利用数学归纳法可以轻易做出证明:假设在某一时刻一个超半数Acceptor集合C共同Accept了某个Proposal K,由于集合C和任意一个多数派Acceptor集合S必有一个共同成员,那么,在这个时刻之后,任意一个多数派Acceptor集合S 中Accept过的最大序号的Proposal只可能是Proposal K或序号比Proposal K更大的Proposal,假设为Proposal K2。同理,Proposal K2的Value等于Proposal K或Proposal K3的Value,而K<K3<K2,递推下去,最终推出根据P2c定出的Value必然是Proposal K的Value。
我们可以看到,P2c条件基本就是上述两阶段协议的关键点1,但是还有一个问题,这个P2c条件要求找出这个“最大序号Value”和提出Proposal必须是一个原子操作,这实际上是难以实现的,所以,上述两阶段协议用了一个巧妙的方法避开了这个问题,这就是上述关键点2 Promise所起的作用了。在Acceptor respond“最大序号Value”的时候,Promise不再Accept低于收到序号的Proposal,这样“找出这个‘最大序号Value’”和“提出Proposal”之间就不可能插入新的被Accept的序号,从而避免P2c条件被破坏。
到这里为止,基本的Paxos算法就已经透彻分析完了,但是,现在这个算法是使用多个Proposal,会造成活锁问题,需要引入leader来优化,而且,这个算法还只能实现在多个冲突Value中选举一个Value的功能,至于序列化多个Value实现状态机,就需要multi-paxos算法。
simple paxos中文译本:
参考:http://www.cnblogs.com/chen77716/archive/2011/01/27/2130804.html
发表评论
-
jstatd jsp 等不能正常运行的原因
2013-12-11 11:04 592[root@ bin]# ./jstatd Could not ... -
jvm信息查看
2013-06-03 08:28 7331、查看当前服务的cpu 、内存、磁盘等使用情况,看看是不是使 ... -
tomcat配置数据源(转载)
2012-02-23 10:57 913转载:http://www.douban.com/note/7 ... -
UML 用例图中包含(include)、扩展(extend)和泛化(generalization)三种关系详解
2011-10-21 18:59 687转载:http://www.cnblogs.com/fan01 ... -
第三方接口开发注意事项
2011-09-20 15:54 14901、防止业务数据重复保存,要有唯一识别的编号用于标识相同的业务 ... -
Unveiling the java.lang.Out OfMemoryError
2011-04-13 19:02 869Unveiling the java.lang.Out OfM ... -
getOutputStream() has already been called for this response异常的原因和解决方法
2010-11-27 14:32 835getOutputStream() has already b ... -
servlet filter url-pattern
2010-10-28 09:47 1269ApplicationFilterFactory: /** ... -
JVM内存
2010-09-26 16:03 991转载:http://blog.csdn.net/c ... -
java nio 笔记
2010-08-19 20:16 1938一、基础知识 操作系统 ... -
集合框架
2010-08-04 22:09 836集合框架: BitSet:??? Ha ... -
基本数据结构介绍
2010-08-01 18:22 894二叉查找树: 性质:设x为二叉查找树中的一个结点。如果y是x的 ... -
理解弱引用(Understanding Weak References)转
2010-07-31 12:58 1201转载:http://blog.csdn.net/x ... -
设置SESSION超时时间
2010-07-02 15:07 1432设置session时间的3个方法: 1. 在tomcat--c ... -
垃圾收集机制
2010-04-23 16:49 784转载:http://tech.ccidnet.com/art ... -
JAVA语言细节总结
2010-04-17 12:47 8371、java 源代码文件通常称为一个编译单元,每个编译单元内最 ... -
utf8的编码原理
2009-07-20 15:08 1125大概意思: 在UTF8中,字符使用1到6个八位序列编码。 只有 ... -
转发(forward)、包含(include)及转向(redirect)的区别与联系
2009-07-17 15:57 941转发(forward)、包含(include)及转向(redi ... -
对数运算公式
2009-07-03 16:15 2104附件二为自然对数的介绍PPT -
二叉树相关知识
2009-07-03 16:04 903一、二叉树的构建与打印 Node.java publ ...
相关推荐
Paxos算法深入分析.doc
很不错的paxos算法分析文档,值得一看,虽不能深入研究,但是可以初步了解!
在github上找到的paxos算法实现,具体是运行和实现方法可以看README文件,注意acceptor、proposer、以及learner的数量根据打开进程的数量变化,不是局限于.c文件的数量。
Paxos算法的中文翻译,值得参考,讲述了paxos协议的原理
Paxos算法.pdf
Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...
面向云计算基础课程的Paxos算法教学设计研究.pdf
Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...
Paxos算法详解.ppt
融入了作者自己对于paxos 算法的理解 lamport 经典之作 Google chubby 服务核心, 云计算 研究必读
Paxos算法的分析和讲解,Paxos Made Simple的中文说明。一些直观的例子。
paxos算法学习.docx
Paxos算法介绍,paxos个角色的职责和可能的实现分析,离我们把paxos算法变为一个可执行程序的目标又进了一步,使我们对paxos的实现方式大致心里有底,但还有诸多的问题需要进一步讨论,比如错误处理。虽然文中也提到...
Paxos算法虽然可以容忍已经申请到访问权的“提案委员”故障,可以容忍少数派“审批委员”故障;但在出现竞争的情况下,其收敛速度很慢,甚至可能出现活锁的情况,例如当有等于或多于审批委员会数量的“提案委员”在同时...
paxos 算法推导中文版。清晰描述paxos的前世今生。
Paxos算法是分布式技术大师Lamport提出的,主要目的是通过这个算法,让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说,就是在一个选举过程中,让不同的选民最终做出一致的决定。 Lamport为了...
cheap-paxos 的论文
人工智能-项目实践-多线程-Paxos算法的多线程实现 Paxos算法的多线程实现 采用java多线程方式,实现分布式一致性算法Paxos
fast paxos算法与zookeeper leader选举源代码分析.doc
一、paxos算法的背景 Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一,其解决的问题就是在分布式系统中如何就某个值...