ZooKeeper的内部数据模型和Leader选举算法

之前的一篇文章有介绍ZooKeeper的使用场景，安装及简单的使用过程，本篇主要介绍下ZooKeeper的内部数据模型和Leader选举算法。

ZooKeeper内部数据模型

znode

ZooKeeper集群维护和操作一个小型的数据节点，这些节点被称之为znode，采用类似于文件系统的层级树状结构进行管理，下图具体描述了一个znode树的结构，根节点包含四个节点，其中三个子节点拥有下一级节点，叶子节点存储了数据信息。每一个znode默认能够存储1MB的数据，这对于记录状态性质的数据来说足够了。znode除了包含名称、数据以外，还有一个非常重要的属性：zxid, zxid与时间戳对应，记录znode不同的状态。

screenshot

znode类型

ZooKeeper的客户端负责创建znode，所以znode的类型与客户端很较大关系。znode节点主要分为两大类型(持久节点与临时节点), 每种类型又分为顺序编号节点和非顺序编号节点。
持久节点只能通过调用delete删除，临时节点与之相反，当创建该节点的客户端崩溃或关闭了与Zookeeper服务器的链接时，这个节点就会被删除。
一个节点还可以被设置成有序的，一个有序的znode节点被分配了一个单调递增的整数，当创建有序节点的时候，一个序号会被追加到路径之后。例如，客户端创建了一个有序节点，路径为/tasks/task-, 那么ZooKeeper会为其分配一个序号，例如1，最后该节点的路径变为/tasks/task-1。通过这种方式，非常直观的可以查看到znode的创建顺序。总之，znode一共有四种类型，持久节点，临时节点，持久有序节点，临时有序节点。

Leader选举算法

在ZooKeeper集群中存在多个服务节点，其中一个节点是Leader节点，其余节点是Follower节点，那为什么要有Leader节点呢，而且为什么只有一个Leader节点, 这个Leader节点是怎么选出来的呢？

为什么要有Leader节点

分布式系统中，如果所有节点的功能都是一样的，那么在保持数据的一致性上一顶会面临较大考验，当然现在有很多方式能保持数据的一致性，但是在性能上定会有较大损失。所以最好有一个节点来协调整个分布式集群的服务。

为什么只有一个Leader节点

想象一下，如果存在多个Leader节点，这就像一山不容二虎似的，当存在多个领导者的时候，局面一定会失控；相反，如果没有领到者，那么局面也会失控。所以需要有Leader节点，而且只能有一个。

Leader节点是怎么选出来的

ZooKeeper提供le三种算法选择Leader节点，今天主要了解下其中的一种FastLeaderElection(也是默认的算法)，其他两种算法思想类似，有兴趣的可以研究下。下面是FastLeaderElection算法的描述，理解起来有些困难，建议配合最下面的流程图和相关的源码一起理解。假设服务器第一次启动，也就是预先没有数据存储在服务器中。假设ZooKeeper集群中存在三台服务器。

首次发送自己的投票值

每个zookeeper服务器发送自己选举的leader,这个协议中包含了以下几部分的数据，每台服务器将自己服务器的以上数据发送到集群中的其他服务器之后,同样的也需要接收来自其他服务器的数据.

1. 所选举leader的id(就是配置文件中写好的每个服务器的id) ,在初始阶段,每台服务器的这个值都是自己服务器的id,也就是它们都选举自己为leader.
2. 服务器最大数据的id,这个值大的服务器,说明存放了更新的数据.
3. 逻辑时钟的值,这个值从0开始递增,每次选举对应一个值,也就是说:如果在同一次选举中,那么这个值应该是一致的, 逻辑时钟值越大,说明这一次选举leader的进程更新.
4. 本机在当前选举过程中的状态,有以下几种, LOOKING, FOLLOWING,LEADING, OBSERVING.

处理接收到的消息

1. 如果所接收数据服务器的状态还是在选举阶段(LOOKING 状态),那么首先判断逻辑时钟值,又分为以下三种情况:
   1)如果发送过来的逻辑时钟大于目前的逻辑时钟,那么说明这是更新的一次选举,此时需要更新一下本机的逻辑时钟值,同时将之前收集到的来自其他服务器的选举清空,因为这些数据已经不再有效了.然后判断是否需要更新当前自己的选举情况.在这里是根据选举leader id,保存的最大数据id来进行判断的,这两种数据之间对这个选举结果的影响的权重关系是:首先看数据id,数据id大者胜出;其次再判断leader id,leader id大者胜出.然后再将自身最新的选举结果(也就是上面提到的三种数据广播给其他服务器).代码如下:
   

   screenshot
   其中的totalOrderPredicate函数就是根据发送过来的封包中的leader id,数据id来与本机保存的相应数据进行判断的函数,返回true说明需要更新数据,于是调用updateProposal函数更新数据; 发送过来数据的逻辑时钟小于本机的逻辑时钟
   说明对方在一个相对较早的选举进程中,这里只需要将本机的数据发送过去就是了;两边的逻辑时钟相同,此时也只是调用totalOrderPredicate函数判断是否需要更新本机的数据,如果更新了再将自己最新的选举结果广播出去就是了.
   上面情况的处理完毕之后,再处理两种情况:
   1)服务器判断是不是已经收集到了所有服务器的选举状态,如果是那么根据选举结果设置自己的角色(FOLLOWING还是LEADER),然后退出选举过程就是了.
   2)即使没有收集到所有服务器的选举状态,也可以判断一下根据以上过程之后最新的选举leader是不是得到了超过半数以上服务器的支持,如果是,那么尝试在200ms内接收一下数据,如果没有新的数据到来,说明大家都已经默认了这个结果,同样也设置角色退出选举过程.
   screenshot 代码如下:

2. 如果所接收服务器不在选举状态,也就是在FOLLOWING或者LEADING状态
   做以下两个判断:
   1) 如果逻辑时钟相同,将该数据保存到recvset,如果所接收服务器宣称自己是leader,那么将判断是不是有半数以上的服务器选举它,如果是则设置选举状态退出选举过程
   2) 否则这是一条与当前逻辑时钟不符合的消息,那么说明在另一个选举过程中已经有了选举结果,于是将该选举结果加入到outofelection集合中,再根据outofelection来判断是否可以结束选举,如果可以也是保存逻辑时钟,设置选举状态,退出选举过程.

   
   screenshot
   screenshot

最后的最后

根据网上的一些信息绘制了一个FastLeaderElection的状态图，仅供参考，如有错误，请指正。

Zookeeper_Fast_Leader_Selection