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

P1的不完备问题：

P2c也顺便解决了P1的不完备问题，因为proposer提交的value是受acceptor限制的，就不会在一次选举中提交两个不同的value，即使能提交也会因为proposal编号问题有一个会被拒绝，从而能保证能形成多数派。

另一个关于第二个该怎么选的不完备问题，也是显然的了。

再次证明了，P2里面蕴含了P1，P1只是未知问题P2的不变式。

1.编号处理

根据P2c ，proposer在提案前会先咨询acceptor查看其批准的最大的编号和value，再决定提交哪个value。之前我们一直强调更高编号的proposal，而没有说明低编号的proposal该怎么处理。

--低编号(L<N)----当前编号(N)----高编号(H>N)--

P2c 的正确性是由当前编号N而产生了一些更高编号H来保证的，更低编号L在之前某个时刻，可能也是符合P2c 的，但因为网络通信的不可靠，导致L被延迟到与H同时提交，L与H有可能有不同的value，这显然违背了P2c ，解决办法是acceptor不接受任何编号已过期的proposal，更精确的描述为：

P1a ： An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

显然，acceptor接收到的第一个proposal符合这个条件，也就是说P1a 蕴含了P1。

关于编号问题进一步的讨论请参考下节的【再论编号问题：唯一编号 】。

2. Paxos算法形成

重新整理P2c 和P1a 可以提出Paxos算法，算法分2个阶段：

Phase1：prepare

（a）proposer选择一个proposal编号n，发送给acceptor中的一个多数派

（b）如果acceptor发现n是它已的请求中编号最大的，它会它已accept的最大的proposal和对应的value（如果有）；同时还附有一种承诺：不会批准编号小于n的proposal

Phase2：accept

（a）如果proposer接收到了多数派的回应，它发送一个accept消息到（编号为n，value v的proposal）到acceptor的多数派（可以与prepare的多数派不同）

关键是这个value v是什么，如果acceptor回应中包含了value，则取其编号最大的那个，作为v；如果回应中不包含任何value，则有proposer随意选择一个

（b）acceptor接收到accept消息后check，如果没有比n大的回应比n大的proposal，则accept对应的value；否则拒绝或不回应

感觉算法过程异常地简单，而理解算法是怎么形成却非常困难。再仔细考虑下，这个算法又会产生更多的疑问：

再论编号问题：唯一编号

保证paxos正确运行的一个重要因素就是proposal编号，编号之间要能比较大小/先后，如果是一个proposer很容易做到，如果是多个 proposer同时提案，该如何处理？Lamport不关心这个问题，只是要求编号必须是全序的，但我们必须关心。这个问题看似简单，实际还稍微有点棘 手，因为这本质上是也是一个分布式的问题。

在Google的Chubby论文中给出了这样一种方法：

假设有n个proposer，每个编号为ir (0<=ir <n)，proposol编号的任何值s都应该大于它已知的最大值，并且满足：s %n = ir => s = m*n + ir

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