zookeeper跟经典paxos的对比(附源码)

    周一的时候公司的技术大牛分享了一下zookeeper的使用与实现，其中提到了我不怎么关注的客户端，回家看了一下，挺有意思的，于是干脆连同服务端对比一下它跟经典paxos的异同：

zookeeper跟paxos不可盲目相提并论，因为两者既不包含也不相等，首先看下定义

• paxos：一套处理多个节点一致性协商的算法

• zookeeper：一套分布式存储系统，分客户端与服务端，其中服务端使用的是改装后的paxos算法，强制保证存储在各个节点里面的数据的一致，请注意“强制”两个字

第一阶段：选举leader

    paxos里面不叫选举leader，而是叫prepare，但目的都是一样的：找一个具备某种资质的节点，而且寻找的方法的原理基本一致：paxos是通过一个全局的自增编号的发放来选举leader，zk也是通过一个叫zxid的编号、以“人传人，逐渐做大”的方式确定leader，具体如下：

1.  FastLeaderElection.sendNotifications()

   这个方法是用来周知其它竞选的节点——我所“提议”的leader的信息

   不考虑Observer这种角色，zk一开机就会去确认leader，即不是Leading状态就是Following，Looking只是暂时的

    而FastLeaderElection的精髓就是Looking时第一步就去提议自己当leader，同时会将logicalclock这个竞选轮数变量+1

2.  FastLeaderElection.totalOrderPredicate()

   这个方法是用来判断别人“提议”的leader信息是不是比我们更新（即我们是不是out了），其中判断的优先级是epoch>zxid>id,即epoch不相同则不用比较剩下两个参数了，如果相同再看zxid，以此类推

   如果当前节点状态为looking，且收到的notification使得上述方法返回true，则会使当前节点也支持notification里所“提议”的leader，即达成一次“人传人”的过程

   请注意，如果收到的notification的logicalclock更大，但是该方法却返回false了，这就出问题了，需要重跑，即重新提议自己当leader

3. FastLeaderElection.termPredicate()

   这个方法是用来确认当前节点所“提议“的leader是否赢得选举，这是由于每个节点在收到notification后都会保存这张选票（对应数据结构为HashMap recvset），而且每次收到一张选票后都会去用这个方法检查它所提议的leader是否当选

   请注意，当且仅当recvqueue中更新的notification为空的时候，该方法确定选举结果才有效，否则继续跟进该更新的notification

    上述三个方法是选举leader的核心逻辑，但跟大多数高并发网络程序一样，都会提供类似WorkerReceiver，WorkerSender这样的线程来异步操作发送和接受队列，zk也不例外，比较恶心的是这里面也写了逻辑-_-

WorkerReceiver：

• 如果其它节点a发来的response表示a跟当前节点b一样，也是looking状态，并且a的竞选轮数logicalclock还小于b，则a要拉b一把，把自己的提议强加给b

• 如果当前节点已经确定leader是谁了，则把leader信息通知a

    有了这些，就能轻易的在整个集群中确定leader是谁，有人问，这跟经典paxos相比也差复杂了太多啊，但个人认为这么做有一个好处，就是不需要去保证每次提案的提出都要带一个全局的自增编号，而是试探性的提出一个提议，交由大家去判定是否合法

第二阶段：投票阶段

    请不要把这个投票跟第一阶段的投票混淆了，这个是分布式协商算法的最后一段，哎都怪zk版的paxos改动太大：经典paxos算法是一次提案一次leader选举的，但是这样做太浪费了，于是zk取了个巧，在节点当选leader后，会启动2F个线程跟follower们保持联系，且设置了超时时间，一旦有过半的follower断线则改变leading状态，否则一直当leader

明确了这个问题后，zk的玩法就清晰了：大部分时间内，zk处于两种角色和两个端，客户端提交请求：

• 如果它连接的服务端的角色是Leader，则Leader直接发起投票，在获得过半的集群节点的投票同意后，通过ServerCnxn将结果回馈给客户端;

• 如果它连的服务端的角色是Follower，则follower转发该请求给Leader，在投票最终通过后，Leader会通知全体服务端，那个转发了客户端请求的Follower也会收到，并将结果回馈给客户端

第二阶段大致就这样，下面我们来看看细节

zk巧妙的利用了处理链，最大限度的复用了代码

对于leader：PrepRequestProcessor -> ProposalRequestProcessor ->

CommitProcessor -> Leader.ToBeAppliedRequestProcessor → FinalRequestProcessor

对于follower：FollowerRequestProcessor -> CommitProcessor ->

FinalRequestProcessor

1. PrepRequestProcessor.pRequest()

   大家可能会好奇第一阶段的zxid是怎么来的，其实它是由两部分组成的，高32位是每诞生出一个新leader时需要自增的一个编号，而低32位则是该方法执行（即leader接受处理了一个请求）时自增一个1的，就在这个方法里

2. ProposalRequestProcessor.processRequest()

   如果request.getHdr()不为空，则说明该请求是写请求，需要进行投票，实施一致性算法，同时leader会给自己投上一票

3. CommitProcessor.run()

   这个方法是leader跟follower共用的，用到了三个变量，其目的就是：“写阻塞读，同时读也会阻塞写”，具体来说：

   如果提交的是写请求，则将nextPending置为该请求并阻塞其他请求进来

   如果是读请求，则将numRequestsProcessing++

   什么时候才能把nextPending擦除呢，当然是投票通过了（对于leader，就是跟follower达成一致了;对于follower，就是leader通知整个集群提案已达成），即committedRequests队列里有数了，这样才处理链才能继续工作，否则阻塞到底（这不是bug，如果投票没通过说明集群一半的机器down掉了）

4. FinalRequestProcessor.processRequest()

   这个方法是用来给客户端发送操作结果的，也是leader跟follower共用的，分水岭是判断request绑定的cnxn那一行

   if (request.cnxn == null) {//当前zk实例角色为leader，获取不到跟客户端的连接

   return;

   }

   这还要追溯到LearnerHandler.run()，当leader收到follower转发过来的请求时

   
   

   case Leader.REQUEST:
   ...
   si = new Request(null, sessionId, cxid, type, bb, qp.getAuthinfo());

   
   

   request是不绑定cnxn连接对象的，因此leader的FinalRequestProcessor不需要负责向客户端回馈操作结果，那这种通过转发形式递交请求的客户端如何知道操作结果呢，请看下一点

5. ZooKeeperServer.processPacket()

   大家看到new Request()的那一行，这是follower在接收到客户端请求时自动绑定上了cnxn，再看一下第3点里的擦除nextPending那几行，传递给处理链下一环的request对象是来自pending的，而不是来自committedRequests，如果还不懂请看注释

   
   

   /*
   * We match with nextPending so that we can move to the
   * next request when it is committed. We also want to
   * use nextPending because it has the cnxn member set
   * properly.
   */

   
   

   这样通过转发形式递交的请求也能反馈给正确的客户端

    本文着重比较了zk跟paxos的异同，其中zk快照+日志的这种持久化方式部分就省略了;还有源码只给了方法名，详细请看