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

P3发起新编号时必须保证new no >16，按照前面的规则必须选择：5*3+2 = 17，而不能仅按自己的规则选择：1*3+2=5

这要求acceptor要在reject消息中给出当前的最大编号，proposer可能出现宕机，重启后继续服务，reject消息会帮助它迅速找到下一个正确编号。但是当多个acceptor各自不一的reject消息时，事情就变得复杂起来。

当proposer发送proposal给一个acceptor时，会有三种结果：

timeout：超时，未接收到aceptor的response

reject：编号不够大，拒绝。并附有当前最大编号

promise：接受，并确保不会批准小于此编号的proposal。并附有当前最大编号及对应的value

在判断是否可以进行Phase2时的一个充分条例就是：必须有acceptor的多数派promise了当前的proposal。

下面分别从Phase1和Phase2讨论proposer的行为：

Phase1-prepare：发送prepare到acceptor

Proposer在本地选择proposal编号，发送给acceptor，会收到几种情况的response：

(a). 没有收到多数派的回应

消息丢失、Server宕机导致没有多数派响应，在可靠消息传输(TCP)下，应该报告宕机导致剩余的Server无法继续提供服务，在实际中一个多数派同时宕机的可能性非常小。

(b). 收到多数派的reject

Acceptor可能会发生任意的错误，比如消息丢失、宕机重启等，会导致每个acceptor看到的最大编号不一致，因而在reject消息中 response给proposer的最大编号也不一致，这种情况proposer应该取其最大作为比较对象，重新计算编号后继续Phase1的 prepare阶段。

(c). 收到多数派的promise

根据包含的value不同，这些promise又分三种情况：

多数派的value是相同的，说明之前已经达成了最终决议

value互不相同，之前并没有达成最终决议

返回的value全部为null

全部为null的情况比较好处理，只要proposer自由决定value即可；多数派达成一致的情况也好处理，选择已经达成决议的value提交即可，value互不相同的情况有两种处理方式：

方案1：自由确定一个value。原因：反正之前没有达成决议，本次提交哪个value应该是没有限制的。

方案2：选择promise编号最大的value。原因：本次选举（instance）已经有提案了，虽未获通过，但以后的提案应该继续之前的，Lamport在paxos 的论文中选择这种方式。

其实问题的本质是：在一个instance内，一个acceptor是否能accept多个value？约束P2只是要求，如果某个value v已被选出，那之后选出的还应该是v；反过来说，如果value v还没有被多数派accept，也没有限制acceptor只accept一个value。

感觉两种处理方式都可以，只要选择一个value，能在paxos之后的过程中达成一致即可。其实不然，有可能value v已经成为了最终决议，但acceptor不知道，如果这时不选择value v而选其他value，会导致在一次instance内达成两个决议。

会不会存在这样一种情况：A、B、C、D为多数派的promise，A、B、C的proposal编号，value为(1,1)，D的为(2,2)？就是说，编号互不一致，但小编号的已经达成了最终决议，而大编号的没有？

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