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