paxos协议_从paxos到zookeeper_raft算法paxos算法(10)

设：小编号的proposal为P1，value为v1；大编号的proposal为P2，value为v2

如果P1选出最终决议，那么肯定是完成了phase1、phase2。存在一个acceptor的多数派C1，P1为其最大编号，并且每个acceptor都accept了v1；

当P2执行phase1时，存在多数派C2回应了promise，则C1与C2存在一个公共成员，其最大编号为P1，并且accept了v1

根据规则，P2只能选择v1继续phase2，也就是说v1=v2，无论phase2是否能成功，绝不会在acceptor中遗留下类似（2，2）这样的value

也就是说，只要按照【方案2】选择value就能保证结果的正确性。之所以能有这样的结果，关键还是那个神秘的多数派，这个多数派起了两个至关重要的作用：

在phase1拒绝小编号的proposal

在phase2强迫proposal选择指定的value

而多数派能起作用的原因就是，任何两个多数派至少有一个公共成员，而这个公共成员对后续proposal的行为起着决定性的影响，如果这个多数派拒 绝了后续的proposal，这些proposal就会因为无法形成新的多数派而进行不下去。这也是paxos算法的精髓所在吧。

Phase2-accept：发送accept给acceptor

如果一切正常，proposer会选择一个value发送给acceptor，这个过程比较简单

accept也会收到2种回应：

(a). acceptor多数派accept了value

一旦多数派accept了value，那最终决议就已达成，剩下的工作就是交由learn学习并关闭本次选举(instance)。

(b). acceptor多数派reject了value或超时

说明acceptor不可用或提交的编号不够大，继续Phase1的处理。

proposer的处理大概如此，但实际编程时还有几个问题要考虑：

来自acceptor的重复消息

本来超时的消息又突然到了

消息持久化

其他2个问题比较简单，持久化的问题有必要讨论下。

持久化的目的是在proposer server宕机“苏醒”时，可以继续参与paxos过程。

从前面分析可看出，proposer工作的正确性是靠编号的正确性来保证的，编号的正确性是由proposer对编号的初始化写及acceptor的reject一起保证的，所以只要acceptor能正常工作，proposer就无须持久化当前编号。

3. acceptor

acceptor的行为相对简单，就是根据提案的编号决定是否接受proposal，判断编号依赖promise和accept两种消息，因此 acceptor必须对接收到的消息做持久化处理。根据之前的讨论也知道，acceptor的持久化也会影响着proposer的正确性。

在acceptor对proposal进行决策的时候，还有个重要的概念没有被详细讨论，即instance。任何对proposal的判断都是 基于某个instance，即某次paxos过程，当本次instance宣布结束（选出了最终决议）时，paxos过程就转移到下一个 instance。这样会衍生出几个问题：

instance何时被关闭？被谁关闭？

acceptor的行为是否依赖instance的关闭与否？

acceptor的多数派会不会在同一个instance内对两个不同的value同时达成一致？

根据1中对各角色职能的讨论，决议是否被选出是由learn来决定的，当learn得知某个value v已经被多数派accept时，就认为决议被选出，并宣布关闭当前的instance。与2中提到的一样，因为网络原因acceptor可能不会得知 instance已被关闭，而会继续对proposer回答关于该instance的问题。也就是说，无论如何acceptor都无法准确得知 instance是否关闭，acceptor程序的正确性也就不能依赖instance是否关闭。但acceptor在已经知道instance已被关闭 的情况下，在拒绝proposer时能提供更多的信息，比如，可以使proposer选择一个更高的instance重新提交请求。paxos协议

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29826-10.html