Paxos领导者选举

简介

Paxos是维护多台节点间数据一致性公认的最好的算法。在维持领导者选择或者变量一致性上，Paxos算法采用一种类似一种投票的过半同意机制，比如设定一个领导者，需要将此看做一个议案，征求过半同意，每个节点通过一个议案还有编号记录，再次收到相同议案的不同人选，发现已有编号记录便驳回，最后以多数通过的结果为准。如果一次投票过程，没有超过一半的节点同意，则重新选举。

算法示意

假设我们有5台计算机A、B、C、D、E，每台计算机保存着公司CEO的信息，现在CEO任期到了，需要进行新一届选举了。 现在A提议CEO为“张三”，如果没有其他候选人议案，也没有网络问题，只要半数以上计算机收到并通过提案，那么最终“张三”当选CEO。 当然，也可能同时有多台计算机发起选举。如A提议“张三”，E提议“李四”。这个时候，B、C、D会收到A和E的提案，到底该选举那台节点呢？这就涉及一致性问题了。如果A、B、C先收到A的议案，D、E先收到E的议案。那么A、B、C会选择E的议案，而如果收到E的议案时，因为已经选择了A，因此会驳回E的提案。同样D、E节点也会驳回A的议案。议案提交上去后，发现A、B、C投票给了“张三”，“张三”的追随者超过一半，最后，“张三”成为了CEO，如果当前选举过程中，没有追随者超过一半的候选人，则重新进行选举，直到有追随超过一半的候选人产生。

参考文献

1. 《大规模分布式系统架构与设计实战》，彭渊，P119.

2. Lamport L. Paxos made simple[J]. ACM Sigact News. 2001, 32(4): 18-25.