快速理解paxos--zookeeper选举--分布式系统一致性问题

paxos协议，发表人，莱斯利·兰伯特(Leslie Lamport)，LaTeX 中的"La"，tex是排版系统
1990年提出的一种基于【消息传递】的分布式一致性算法

【paxos协议过程】完整的paxos很复杂，有空你可以去慢慢研究，下面是一些总结，帮助你理解，提纲掣领

1. paxos协议，是【议会制*选举】原理，目的是在分布式环境下，多个节点可以得出一致性的【值】

2. 【概述】首先分布式环境中各个节点必须【相互连通】，【一些节点】提出议案，然后【可统计选票的节点】统计选票选举，提案被超过可统计选票的节点数量一半以上的通过，即生效。

3. 2个阶段(Phase)

    1阶段，【后来居上】原理，选定【提案号】，n
    多个节点发出提案（Prepare消息），每个提案有递增编号，接收提案的节点，只接受最大的提案号
    然后返回给这个【最大提案号的节点】已收到（Promise消息）(【但注意】并不是每一个接收节点的最大提案号都一样)
   
    2阶段，【先到先得】原理，选定【提案内容】，就是最终的一致性的【值】，v
    上面那些发出提案的节点（这样的节点可能【有多个】）收到超过半数的Promise消息后
    开始发送【提案内容，(n,v)】(Accept消息)
    接收节点只要没有对大于n的提案【发出过】上面的Promise消息，就接受提案，返回（Accepted消息)
   

最终在paxos协议的约束下（提案编号递增，多数接收提案才能发accept消息等等约束），【不断】经过上面的2阶段，分布式节点会不断【收敛于】一个值。

上面是简要的过程，对于每个不同状态并【没有】做完全遍历与论证。比如2阶段最后接受的那个提案后，如果来了一个n+1提案还是会发送Promise消息，然后后面还可能有接受这个【新的值】。

zookeeper中的提案号就是myid，提案内容就是zxid(zookeeper的事务id)，所以一般选举是要么myid大的或者zxid大的做leader。

zxid有64位

高32位是Leader的epoch：选举时钟，每次选出新的Leader，epoch累加1
低32位是在这轮epoch内的事务id：对于用户的每一次更新操作集群都会累加1。

zookeeper在选主过程保证了两个问题：

commit过的数据不丢失
未commit过的数据丢弃

(myid,zxid)的选票设计刚好解决了这两个问题。
1.commit过的数据半数以上参加选举的follwer都有，而且成为leader的条件是要有最高事务id即数据是最新的。
2.未commit过的数据只存在于leader，但是leader宕机无法参加首轮选举，epoch会小一轮，最终数据会丢弃。

延申阅读：
Paxos (computer science)–wiki
paxos协议与一致性
zab协议与选主