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

很显然，为了给每个数据唯一编号，每次表决只能产生一个数据，否则表决就没有任何意义。Paxos的算法的所有精力都放在如何在一次表决只产生一个数据。再进一步，我们称表决的数据叫Value，Paxos算法的核心和精华就是确保每次表决只产生一个Value。

3.Paxos算法

翻译：

--->Acceptor 接受者

--->proposer 申请者

--->proposal 建议

--->accept 决策

promise（许诺）：Acceptor对proposer承诺，如果没有更大编号的proposal会accept它提交的proposal

accept（决策）：Acceptor没有发现有比之前的proposal更大编号的proposal，就批准了该proposal

chosen（决定）：当Acceptor的多数派都accept一个proposal时，该proposal就被最终选择，也称为决议

也就是说，Acceptor对proposer有两个动作：promise和accept

下面的解释也主要围绕着”Only a single value is chosen,“，再看下条件P1，

P1：An acceptor must accept the first proposal that it receives.

乍一看，这个条件是显然的，因为之前没有任何value，acceptor理所当然地应该accept第一个proposal，但仔细想想，感觉P1这个条件很不严格，到底是一个对问题的简单描述还是一个数学上严格的必要条件？这些疑问归结为2个问题：

（1）这个条件本质上在保证什么？

（2）第二个proposal怎么办？

在后续的算法中看到一个Acceptor是否批准一个Value与它是否是第一个没有任何关系，而与这个Proposal的编号有关。那岂不说明 P1没有得到保证？开始我也百思不得其解，后来经过跟朋友交流发现，P1中的"accept"其实是指acceptor对proposer 的"promise"，就是语言描述跟算法的步骤描述之间存在歧义，因此我认为对算法问题还是应该采用数学语法而非文字语言。

所以，P1是强调了第一个proposal要被promise，但第二个还未提到，这也是疑问之一。

也很显然的是，单靠P1是无法保证Paxos算法的，因可能无法形成多数派，那接下来的讨论应该是考虑如何弥补P1的缺点，使其可以保证Paxos算法，就是我们希望未来的条件应该说明：

如何解决P1中无法形成多数派的问题

第二个proposal如何选择

于是约束P2出现了：

P2：If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

P2的出现让人大跌眼镜，P2并没沿着P1的路向下走，也没有解决P1的上述2个不完备，而是从另一个侧面讨论如何保证只能选出一个Value。 P1讨论的是该如何选择，P2讨论的是一旦被选出来，之后的选择应该不变，就是P1还在讨论选的问题，P2已经选出来了，中间有个断层，怎么选的没有讨 论。

其实从后面Lamport不断对P2增强可以看出，P2里面蕴含着P1（通过proposal编号，第一次之前没有编号，所以选择），P2才真正给 出了怎么选择的具体过程，从事后分析看，P1给出了第一个该怎么选，P2给出了所有的该怎么选，条件有点重复。所以，把P1和P2看作是两个独立条件的做 法是不准确的，因而中文wiki中提到“如果 P1 和 P2 都能够保证，那么约束2就能够保证”，对细微理解有一定的影响。

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