1 / 12
文档名称:

paxos例子[共12页].doc

格式:doc   大小:131KB   页数:12页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

paxos例子[共12页].doc

上传人:qqqqqq 2021/7/29 文件大小:131 KB

下载得到文件列表

paxos例子[共12页].doc

文档介绍

文档介绍:paxos 例子 【篇一: paxos 例子】
2. 只有一个值被选定;
3. 如果某个进程认为某个提案被选定了,那么这个提案必须是真的
被选定的那个。
该一致性算法中有三个角色,分别是: proposer ,acceptor ,
learner 。它们之间通过消息来通讯。
paxos 算法的两阶段
prepare 阶段:
????1. proposer 选择一个提案编号 n,然后向 acceptor 的某个超
过半数的子成员发送编号为 n 的 prepare 请求;
????2. acceptor 收到 prepare 消息后,如果提案的编号 n 大于该
acceptor 已经回复的所有 prepare 请求的编号,则 acceptor 将自
己上次已经批准的最大编号提案回复给 proposer ,并承诺不再回复
小于 n 的提案;
acceptor 阶段:
????1. 当一个 proposer 收到了半数以上的 acceptors 对 prepare
的回复后,就进入批准阶段。它要向回复 prepare 请求的
acceptors 发送 accept 请求,包括编号 n 和根据 prepare 阶段 决
定的 value 。这里的 value 是所有响应中编号最大的提案的 value
(如果根据 prepare 没有已经接受的 value ,那么它可以自由决定
value )。
????2. 在不违背自己向其他 proposer 的承诺的前提下, acceptor
收到 accept 请求后即接受这个请求。即如果 acceptor 收到这个针
对 n 提案的 accep 请求,只要改 acceptor 尚未对编号大于 n 的
prepare 请求做出过响应,它就可以通过这个提案。
流程图如下:
具体实例
首先,给出 proposer 和 acceptor 的消息图:
针对上面提出的两个阶段,分别解释:
prepare 阶段 1.
???? 每个 server 向 proposer 发送消息,表示自己要当 leader ,假
设 proposer 收到消息的时间不一样,顺序是: proposer2 -
proposer1 - proposer3 ,消息编号依次为 1、2、3。
???? 紧接着, proposer 将消息发给 acceptor 中超过半数的子成员
(这里选择两个 ),如图所示, proposer2 向 acceptor2 和 acceptor3
发送编号为 1 的消息, proposer1 向 acceptor1 和 accepto2 发送
编号为 2 的消息, proposer3 向 acceptor2 和 acceptor3 发送编号
为 3 的消息。 2.
???? 假设这时 proposer1 发送的消息先到达 acceptor1 和
acceptor2 ,它们都没有接收过请求,所以接收该请求并返回【 2,
null 】给 proposer1 ,同时承诺不再接受编号小于 2 的请求;
???? 紧接着, proposer2 的消息到达 acceptor2 和 acceptor3 , acceptor3 没有接受过请求,所以返回 proposer2 【1,null 】,并
承诺不再接受编号小于 1 的消息。而 acceptor2 已经接受 proposer1 的请求并承诺不再接收编号小于 2 的请求,所以 acceptor2 拒绝 proposer2 的请求;
???? 最后, proposer3 的消息到达 acceptor2 和 acceptor3 ,它们
都接受过提议,但编号 3 的消息大于 acceptor2 已接受的 2 和
acceptor3 已接受的 1,所以他们都接受该提议,并返回 proposer3
【3,null 】;
???? 此时, proposer2 没有收到过半的回复,所以重新取得编号 4,
并发送给 acceptor2 和 acceptor3 ,此时编号 4 大于它们已接受的
提案编号 3,所以接受该提案,并返回 proposer2 【4,null 】。
accept 阶段 1
????proposer3 收到半数以上(两个)的回复,并且返回的 value
为 null ,所以, proposer3 提交了【 3,server3 】的提案。
????proposer1 也收到过半回复,返回的 value 为 null ,所以
proposer1 提交了【 2,server1 】的提案。
????proposer2 也收到过半回复,返回的 value 为 null ,所以
prop