Zookeeper里Leader选举算法

Zookeeper里Leader选举算法

ZooKeepe集群中的三种服务器角色：Leader、Follower、Observer，本文主要概述Leader选举算法相关的知识。

一、Zookeeper里三种角色

1.Leader：Leader是整个集群中的核心，主要工作内容是

事务请求的唯一调度和处理者，保证集群事务处理的顺序性。集群内部各服务器的调度者

2.Follower:Follower服务器是Zookeeper集群状态的跟随者，其主要工作内容是：

处理客户端非事务请求，转发事务请求给Leader服务器参与事务请求Proposal的投票参与Leader选举投票

3.Observer：在工作原理上基本与Follower一致，不参与任何形式的投票，观察同步集群的最新状态并同步

二、选举算法

Zookeeper中主要提供了三种Leader选举算法，分别是LeaderElection、UDP版本的FastLeaderElection和TCP版本的FastLeaderElection，可以在配置文件zoo.cfg中使用electionAlg属性来指定，分别使用数字0-3来表示。下文介绍的是TCP版本的FastLeaderElection选举算法。

1. 相关术语

SID：服务器ID，SID是一个数字，用来标识一台Zookeeper中的机器，取值和myid配置文件中的值一致。

ZXID：事务ID，用来标识一次服务器状态的变更。

Vote：投票。一个Vote包含以下几个属性：

        id：被推举的Leader的SID值。

        zxid：被推举的Leader的事务ID。

        electionEpoch：逻辑时钟，用来判断多个投票是否在同一轮选举周期中。

        peerEpoch：被推举Leader的epoch。

        state：当前服务器的状态，LOOKING、FOLLOWING、LEADEING、OBSERVING

2. 算法分析

当ZooKeeper集群中的一台服务器出现以下两种情况之一时，就会开始进入Leader选举。

服务器初始化启动服务器运行期间无法和Leader保持连接

注：当一台服务器加入集群中时，如果当前集群中已经存在一台正常工作的Leader，那么这个服务器会连接Leader进行数据同步，若无Leader，则会进行Leader选举阶段。

开始第一次投票    

当集群中的机器进行Leader选举阶段，机器的状态会变更为LOOKING，当一台机器处于LOOKING转态时，它会向集群中的其他所有机器发送消息，这个消息为“投票”，同时该机器也会接受其他机器的“投票”。

我们用（SID，ZXID）这样的形式来表示一次投票信息。例如，当前服务器要推举SID为1、ZXID为8 的服务器成为Leader，那么它这次的投票信息可以表示为：（1，8）。

我们假设Zookeeper由5台机器组成，SID分别为1、2，3、4、5，ZXID分别为9、9、9、8、8。

并且此时SID为2的机器是Leader服务器。在某一时刻，1和2所在机器发生故障，此时集群开始进行Leader选举。

在第一次投票时，因为无法检测到集群中其他机器的状态信息，每台机器在第一次投票时，会将自己作为推举对象进行投票。即集群中正常运行的3、4、5号机器第一次投票的信息为（3，9）、（4，8）、（5，8）。

变更投票

集群中的每台机器发出自己的投票，也会接收到来自集群中其他机器的投票。机器会根据相应的规则来处理接收到的其他机器的投票，在这个过程中，可能会保持自己的投票，也可能会丢弃自己的投票更改为接收到的投票。下面定义一些术语：

vote_sid:接收到的投票中所推举的Leader服务器的SIDvote_zxid：接收到的投票中所推举的Leader服务器的ZXIDself_sid:当前服务器自己的SIDself_zxid:当前服务器自己的ZXID

处理投票的规则：

处理收到的投票，都是对（vote_sid,vote_zxid）和（self_sid,self_zxid）的比较。

规则一：如果vote_zxid 大于 self_zxid，就认可当前收到的投票，并将该投票（vote_sid,vote_zxid）发送出去规则二：如果vote_zxid 小于 self_zxid，那么就坚持自己的投票（self_sid,self_zxid）规则三：如果vote_zxid 等于 self_zxid，继续比较vote_sid和self_sid，如果vote_sid大于self_id，那么就认可接收到的投票，并将该投票（vote_sid,vote_zxid）发送出去，如果vote_sid小于self_sid，同样坚持自己的投票（self_sid,self_zxid）

根据以上规则，我们来分析上面提到的例子。

正常工作的3台机器发出第一轮投票（投给自己的投票），其他两台机器也会收到相应的投票。下面我们对每台机器的投票情况进行分析：

对于Sever3：Sever3接收到了Server4的投票（4，8）和Sever5的投票（5，8），然后按照上面阐述的规则，对比（3，9）（4，8）（5，8），Sever3的ZXID要大于Sever4和Sever5的ZXID，所以Sever3保留自己的投票，不做任何变更。对于Sever4：Sever4接收到了Sever3的投票（3，9）和Sever5的投票（5，8），然后进过对比，发现（3，9）这个投票的ZXID大于自己，因此需要变更投票为（3，9），然后变更后的投票发送给Sever3和Sever5两台机器。对于Sever5：处理的逻辑与Sever4相同。

确认Leader

如果一台机器收到了超过半数的相同的投票，那么这个投票对应的SID机器即为Leader。

当Zookeeper集群中的机器为5台，那么quorum= （5/2 +1） = 3，即只要收到3个或3个以上的相同投票即可确定Leader。在上面的例子中，Sever3、Sever4和Sever5最终都投了Sever3作为Leader，因此 Sever3成为Leader。

总结

通常具有最大的ZXID的机器越容易成为Leader，具有最大的ZXID的机器成为Leader可以保证集群数据的恢复。如果相同ZXID，那么较大的SID的那台服务器成为Leader。