前面介绍了ZooKeeper的基本知识，这一节我们介绍一下ZooKeeper使用的协议。只有了解了ZooKeeper的协议，才能更好得理解ZooKeeper源代码的实现。ZooKeeper使用的是Zab（ZooKeeper Atomic Broadcast）协议，它是基于Paoxs算法实现的。所以这一节我们按照这个顺序来讲解：
- Paoxs算法
- Zab协议
Paoxs算法
首先看一下Paoxs算法，一般说到zookeeper,我们都会提起Paoxs算法和Lesile Lamport.
Paoxs算法是zookeeper的灵魂,这个算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法.Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。在ZooKeeper中的应用场景就是Leader选举。
该算法由Leslie于1990年在文章The Part-Time Parliament中首次提出,但是这篇文章相当的晦涩难懂(也有一些轶事,可以看文章链接中Leslie自己写的内容),于是,Lesilie在2001年写下了Paxos Made Simple.他对此解释道:
At the PODC 2001 conference, I got tired of everyone saying how difficult it was to understand the Paxos algorithm, published in [122]. Although people got so hung up in the pseudo-Greek names that they found the paper hard to understand, the algorithm itself is very simple. So, I cornered a couple of people at the conference and explained the algorithm to them orally, with no paper. When I got home, I wrote down the explanation as a short note, which I later revised based on comments from Fred Schneider and Butler Lampson. The current version is 13 pages long, and contains no formula more complicated than n1 > n2.
Paxos Made Simple的abstract只有一句话:
The Paxos algorithm, when presented in plain English, is very simple.
在上文中是这样描述Paoxs算法执行过程的:
Phase 1.
(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.
Phase 2.
(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
这几乎就是Paxos的全部了. 这里就不一句一句翻译了。
Zab协议
Zab是一个高性能的广播协议，主要用于主备系统，它是专门为ZooKeeper设计的。Zab协议的详细内容请参考论文《Zab: High-performance broadcast for primary-backup systems》。
ZAB相比Paxos的优点有：
- 状态一致性保证，为了保证状态一致性，Zookeeper提出了两个安全属性（Safety Property） ：
- 全序（Total order）：如果消息a在消息b之前发送，则所有Server应该看到相同的结果。
- 因果顺序（Causal order）：如果消息a在消息b之前发生（a导致了b），并被一起发送，则a始终在b之前被执行。
- 更高效得从失败中恢复。状态一致性保证了多个ZooKeeper客户端同时进行多个事务操作的正确性。所以当一个leader挂掉之后，新的leader只需要从选举它的一个多数派中获得当前最大的事务号作为它的恢复点，这样leader最多只需要跟具有最大的事务号的那一个进程（如果有多个，由于状态一致性保证，随机挑一个即可）同步即可。而在Paoxs中，由于同一个事务（这里实际上是指序列号）可以有多个不同的投票，不同的进程对于同一个事务可能接受不同的值，所以不能简单的使用事务号来选择恢复点，新的leader需要找到当前最大的事务号，然后对于它已经commit的事务号跟这个最大的事务号之间的每一个事务号都需要重新执行一遍Phase1得到最终commit的值，这样的恢复过程 复杂而且不够高效。
Paxos的一致性不能达到ZooKeeper的要求。因为Paoxs只是保证最终一致性，如果处理的请求之间有依赖关系，利用Paoxs处理的时候可能满足不了这些依赖关系。举个例子：假设一开始Paxos系统中的leader是P1，它发起了两个事务<t1, v1>（表示序号为t1的事务要写的值是v1）和<t2, v2>，过程中挂了。新来个leader是P2，它发起了事务<t1, v1'>。而后又来个新leader是P3，它汇总了一下，得出最终的执行序列<t1, v1'>和<t2, v2>，即P2的t1在前，P1的t2在后。对应到ZooKeeper中的操作，P1对应的事务t1要创建"/a"，事务t2要创建"/a/test"，而P2的事务t1要创建"/b"，P3汇总了之后得出的结论是先创建"/b"，再创建"/a/test"。而对于ZooKeeper中的创建操作，只有父节点已经存在的情况下才能创建子节点，也即只有先成功创建了"/a"，接下来创建"/a/test"才能成功，所以创建完"/b"之后再创建"/a/test"就会失败，这不是我们希望的结果。
为了保证这一点，ZAB要保证同一个leader的发起的事务要按顺序被apply，同时还要保证只有先前的leader的所有事务都被apply之后，新选的leader才能发起新的事务。ZAB的核心思想，形象的说就是保证任意时刻只有一个节点是leader，所有更新事务都由leader发起去更新所有复本（称为follower），更新时用的就是两阶段提交协议，只要多数节点prepare成功，就通知他们commit。各follower要按当初leader让他们prepare的顺序来apply事务。因为ZAB处理的事务永远不会回滚，ZAB的2阶段提交做了点优化，多个事务只要通知zxid最大的那个commit，之前的各follower会统统commit。
剩下的就是怎么来保证leader的可靠性，因为leader是会crash的，所以引入了leader选举机制。leader选举是基于Paoxs协议的，成为leader的条件是必须要有一个多数派支持，此外还需要知道以下知识：
- leader跟follower之间通过心跳来检测异常；
- follower检测到leader心跳异常之后，会重新发起leader选举，一个follower若试图成为新的leader，首先要获得一个多数派的支持，然后从状态最新的节点同步事务，完成后才可正式成为leader发起新的事务；
Leader选举遇到的最大问题是：新Leader是否要继续老Leader的状态。这里要按老Leader Crash的时机分两种情况：
- 老Leader在COMMIT前Crash（已经提交到本地）
- 老Leader在COMMIT后Crash，但有部分Follower接收到了Commit请求
第一种情况，这些数据只有老Leader自己知道，当老Leader重启后，需要与新Leader同步并把这些数据从本地删除，以维持状态一致。
第二种情况，新Leader应该能通过一个多数派获得老Leader提交的最新数据。
老Leader重启后，可能还会认为自己是Leader，可能会继续发送未完成的请求，从而因为两个Leader同时存在导致算法过程失败，ZooKeeper的解决办法是把Leader信息加入每条消息的id中，Zookeeper中称为zxid，zxid为一64位数字，高32位为leader信息又称为epoch，每次leader转换时递增；低32位为消息编号，Leader转换时应该从0重新开始编号。通过zxid，Follower能很容易发现请求是否来自老Leader，从而拒绝老Leader的请求。
综上可见，Zab协议实际上还是基于Paoxs衍生出来的，Paoxs中没有保证请求之间的逻辑顺序，只考虑数据的全序，Zab在这方面进行了完善补充，同时由于leader的存在，简化了Paoxs的二段提交为一段提交（Phase2），最后为了确保leader的可靠性，又基于Paoxs协议实现了leader的选举机制。