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