paxos算法
常常在有关分布式的文章中看到paxos算法，于是学习了一下此经典算法，下面记录的是我的一些个人理解。如有不正确之处，请指正。
角色有：
proposer acceptor learner
proposer负责提出议案，每次提案都有一个全局编号，编号唯一且递增
一些约束条件：
1.acceptor必须接受第一次的收到的提案
2.一个提案被选中必须要超过半数的acceptor接受
3.acceptor不会接受编号小于acceptedN的提案
acceptor会记录两个值[acceptedN,acceptedK] ，分别是接受提案的编号和接受提案的值。据个人理解，接受提案的值只会在第二阶段accept阶段被记录。
1.第一阶段，prepare阶段
1.a proposer向大多数的acceptor提交一个提案（不妨设编号为K）
1.b 如果acceptor是第一次收到提案（即acceptedN=null），则记录acceptedN=K，并承诺不会接受编号小于K的提案,返回[K,null].
如果K的值小于acceptedN，则拒绝。
如果K的值大于acceptedN:
1)如果acceptedN=null，则记录acceptedN=K，接受并返回[K,null]
2)如果acceptedN为非空，则记录acceptedN=K，同样接受，但是返回[K,acceptedK]
2.第二阶段，Accept阶段
2.a proposer如果一段时间后，未收到超过一半的acceptor的接受应答，则修改K的值，重新进入prepare阶段
proposer如果收到了超过一半的acceptor的应答:
1)如果返回的是[K,null]，那么Proposer可以选择任何的V值，将[K,V]发送给acceptor（称为accept请求）.
2)如果返回的是[K,acceptedK],那么V=max(acceptedK)],即V的值是收到的应答中编号最大对应的acceptedK， Proposer将[K ,V]发送给acceptor（称为accept请求）.
2.b acceptor收到accept请求后，比较自己的acceptedN 和 accept请求的K值:
1)如果K > acceptedN，则拒绝
2)否则，记录acceptedN = K ，acceptedV = V，并返回。
3.第三阶段，Decide阶段
3.a 如果Learner从绝大多数Acceptor节点获得，则发送给所有Learner学习；否则
3.b 如果Learner没能获得绝大多数Acceptor的，则放弃；
下面是一个实例：
假设现在有五个节点的分布式系统，此时 A 节点打算提议 X 值，E 节点打算提议 Y 值，其他节点没有提议。
Paxos-1.png
假设现在 A 节点广播它的提议（也会发送给自己），由于网络延迟的原因，只有 A，B，C 节点收到了。注意即使 A，E 节点的提议同时到达某个节点，它也必然有个先后处理的顺序，这里的“同时”不是真正意义上的“同时”。
Paxos-2.png
A，B，C接收提议之后，由于这是第一个它们接收到的提议，acceptedProposal 和 acceptedValue 都为空。
Paxos-3.png
由于 A 节点已经收到超半数的节点响应，且返回的 acceptedValue 都为空，也就是说它可以用 X 作为提议的值来发生 Accept 请求，A，B，C接收到请求之后，将 acceptedValue 更新为 X。
Paxos-4.png
A，B，C 会发生 minProposal 给 A，A 检查发现没有大于 1 的 minProposal 出现，此时 X 已经被选中。等等，我们是不是忘了D，E节点？它们的 acceptedValue 并不是 X，系统还处于不一致状态。至此，Paxos 过程还没有结束，
Paxos-5.png
此时 E 节点选择 Proposal ID 为 2 发送 Prepare 请求，结果就和上面不一样了，因为 C 节点已经接受了 A 节点的提议，它不会三心二意，所以就告诉 E 节点它的选择，E 节点也很绅士，既然 C 选择了 A 的提议，那我也选它吧。于是，E 发起 Accept 请求，使用 X 作为提议值，至此，整个分布式系统达成了一致，大家都选择了 X。
Paxos-6.png
网友评论