# Zookeeper源码分析-Zookeeper Leader选举算法 - URL: https://www.yidoo.xyz/zookeeper-leader-election - 作者: 核动力蜗牛 - 发布时间: 2014-10-17 - 更新时间: 2014-10-17 - 分类: Zookeeper源码分析 - 标签: zookeeper 当 Leader 崩溃或者 Leader 失去大多数的 Follower，这时候 zk 进入恢复模式，恢复模式需要重新选举出一个新的 Leader，让所有的 Server 都恢复到一个正确的状态。Zookeeper 中 Leader 的选举采用了三种算法： - LeaderElection - FastLeaderElection - AuthFastLeaderElection 并且在配置文件中是可配置的，对应的配置项为 electionAlg。 # 背景知识 Zookeeper Server 的状态可分为四种： - LOOKING：寻找 Leader - LEADING：Leader 状态，对应的节点为 Leader。 - FOLLOWING：Follower 状态，对应的节点为 Follower。 - OBSERVING：Observer 状态，对应节点为 Observer，该节点不参与 Leader 选举。 成为 Leader 的必要条件： Leader 要具有最高的 zxid；当集群的规模是 n 时，集群中大多数的机器（至少 n/2+1）得到响应并 follow 选出的 Leader。 心跳机制：Leader 与 Follower 利用 PING 来感知对方的是否存活，当 Leader 无法相应 PING 时，将重新发起 Leader 选举。 # 术语 **zxid**：zookeeper transaction id, 每个改变 Zookeeper 状态的操作都会形成一个对应的 zxid，并记录到 transaction log 中。 这个值越大，表示更新越新。 **electionEpoch/logicalclock**：逻辑时钟，用来判断是否为同一次选举。每调用一次选举函数，logicalclock 自增 1，并且在选举过程中如果遇到 election 比当前 logicalclock 大的值，就更新本地 logicalclock 的值。 **peerEpoch**: 表示节点的 Epoch。 # LeaderElection 选举算法 LeaderElection 是 Fast Paxos 最简单的一种实现，每个 Server 启动以后都询问其它的 Server 它要投票给谁，收到所有 Server 回复以后，就计算出 zxid 最大的哪个 Server，并将这个 Server 相关信息设置成下一次要投票的 Server。该算法于 Zookeeper 3.4 以后的版本废弃。 选举算法流程如下： 1. 选举线程首先向所有 Server 发起一次询问(包括自己)； 2. 选举线程收到回复后，验证是否是自己发起的询问(验证 xid 是否一致)，然后获取对方的 id(myid)，并存储到当前询问对象列表中，最后获取对方提议的 leader 相关信息(id,zxid)，并将这些信息存储到当次选举的投票记录表中； 3. 收到所有 Server 回复以后，就计算出 zxid 最大的那个 Server，并将这个 Server 相关信息设置成下一次要投票的 Server； 4. 线程将当前 zxid 最大的 Server 设置为当前 Server 要推荐的 Leader，如果此时获胜的 Server 获得多数 Server 票数， 设置当前推荐的 leader 为获胜的 Server，将根据获胜的 Server 相关信息设置自己的状态，否则，继续这个过程，直到 leader 被选举出来。 ![leader-election](https://www.yidoo.xyz/images/f4377cb09d1a0b73d2aefbacc745e9a9.jpg) 通过流程分析我们可以得出：要使 Leader 获得多数 Server 的支持，则 Server 总数必须是奇数 2n+1，且存活的 Server 的数目不得少于 n+1. 异常问题的处理： 1. 选举过程中，Server 的加入 当一个 Server 启动时它都会发起一次选举，此时由选举线程发起相关流程，那么每个 Serve r 都会获得当前 zxi d 最大的哪个 Serve r 是谁，如果当次最大的 Serve r 没有获得 n/2+1 个票数，那么下一次投票时，他将向 zxid 最大的 Server 投票，重复以上流程，最后一定能选举出一个 Leader。 2. 选举过程中，Server 的退出 只要保证 n/2+1 个 Server 存活就没有任何问题，如果少于 n/2+1 个 Server 存活就没办法选出 Leader。 3. 选举过程中，Leader 死亡 当选举出 Leader 以后，此时每个 Server 应该是什么状态(FLLOWING)都已经确定，此时由于 Leader 已经死亡我们就不管它，其它的 Fllower 按正常的流程继续下去，当完成这个流程以后，所有的 Fllower 都会向 Leader 发送 Ping 消息，如果无法 ping 通，就改变自己的状为(FLLOWING ==> LOOKING)，发起新的一轮选举。 4. 选举完成以后，Leader 死亡 处理过程同上。 5. 双主问题 Leader 的选举是保证只产生一个公认的 Leader 的，而且 Follower 重新选举与旧 Leader 恢复并退出基本上是同时发生的，当 Follower 无法 ping 同 Leader 是就认为 Leader 已经出问题开始重新选举，Leader 收到 Follower 的 ping 没有达到半数以上则要退出 Leader 重新选举。 # FastLeaderElection 选举算法 由于 LeaderElection 收敛速度较慢，所以 Zookeeper 引入了 FastLeaderElection 选举算法，FastLeaderElection 也成了 Zookeeper 默认的 Leader 选举算法。 FastLeaderElection 是标准的 Fast Paxos 的实现，它首先向所有 Server 提议自己要成为 leader，当其它 Server 收到提议以后，解决 epoch 和 zxid 的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息。FastLeaderElection 算法通过异步的通信方式来收集其它节点的选票，同时在分析选票时又根据投票者的当前状态来作不同的处理，以加快 Leader 的选举进程。 ## 算法流程 ### 数据恢复阶段 每个 ZooKeeper Server 读取当前磁盘的数据（transaction log），获取最大的 zxid。 ### 发送选票 每个参与投票的 ZooKeeper Server 向其他 Server 发送自己所推荐的 Leader，这个协议中包括几部分数据： - 所推举的 Leader id。在初始阶段，第一次投票所有 Server 都推举自己为 Leader。 - 本机的最大 zxid 值。这个值越大，说明该 Server 的数据越新。 - logicalclock。这个值从 0 开始递增，每次选举对应一个值，即在同一次选举中，这个值是一致的。这个值越大说明选举进程越新。 - 本机的所处状态。包括 LOOKING，FOLLOWING，OBSERVING，LEADING。 ### 处理选票 每台 Server 将自己的数据发送给其他 Server 之后，同样也要接受其他 Server 的选票，并做一下处理。 #### 如果 Sender 的状态是 LOOKING - 如果发送过来的 logicalclock 大于目前的 logicalclock。说明这是更新的一次选举，需要更新本机的 logicalclock，同事清空已经收集到的选票，因为这些数据已经不再有效。然后判断是否需要更新自己的选举情况。首先判断 zxid，zxid 大者胜出；如果相同比较 leader id，大者胜出。 - 如果发送过来的 logicalclock 小于于目前的 logicalclock。说明对方处于一个比较早的选举进程，只需要将本机的数据发送过去即可。 - 如果发送过来的 logicalclock 等于目前的 logicalclock。根据收到的 zxid 和 leader id 更新选票，然后广播出去。 当 Server 处理完选票后，可能需要对 Server 的状态进行更新： - 判断服务器是否已经收集到所有的服务器的选举状态。如果是根据选举结果设置自己的角色（FOLLOWING or LEADER），然后退出选举。 - 如果没有收到没有所有服务器的选举状态，也可以判断一下根据以上过程之后更新的选举 Leader 是不是得到了超过半数以上服务器的支持。如果是，那么尝试在 200ms 内接收下数据，如果没有心数据到来说明大家已经认同这个结果。这时，设置角色然后退出选举。 #### 如果 Sender 的状态是 FOLLOWING 或者 LEADER - 如果 LogicalClock 相同，将数据保存早 recvset，如果 Sender 宣称自己是 Leader，那么判断是不是半数以上的服务器都选举它，如果是设置角色并退出选举。 - 否则，这是一条与当前 LogicalClock 不符合的消息，说明在另一个选举过程中已经有了选举结果，于是将该选举结果加入到 OutOfElection 集合中，根据 OutOfElection 来判断是否可以结束选举，如果可以也是保存 LogicalClock，更新角色，退出选举。 ![fast-leader-election](https://www.yidoo.xyz/images/94ad53c0060212a74a27579beee3201b.png) ## 具体实现 ### 数据结构 本地消息结构： ```java static public class Notification { long leader; //所推荐的Server id long zxid; //所推荐的Server的zxid(zookeeper transtion id) long epoch; //描述leader是否变化(每一个Server启动时都有一个logicalclock，初始值为0) QuorumPeer.ServerState state; //发送者当前的状态 InetSocketAddress addr; //发送者的ip地址 } ``` 网络消息结构： ```java static public class ToSend { int type; //消息类型 long leader; //Server id long zxid; //Server的zxid long epoch; //Server的epoch QuorumPeer.ServerState state; //Server的state long tag; //消息编号 InetSocketAddress addr; } ``` ### 线程处理 每个 Server 都一个接收线程池和一个发送线程池, 在没有发起选举时，这两个线程池处于阻塞状态，直到有消息到来时才解除阻塞并处理消息，同时每个 Server 都有一个选举线程(可以发起选举的线程担任)。 - 接收线程的处理 notification: 首先检测当前 Server 上所被推荐的 zxid,epoch 是否合法(currentServer.epoch <= currentMsg.epoch && (currentMsg.zxid > currentServer.zxid || (currentMsg.zxid == currentServer.zxid && currentMsg.id > currentServer.id))) 如果不合法就用消息中的 zxid,epoch,id 更新当前 Server 所被推荐的值，此时将收到的消息转换成 Notification 消息放入接收队列中，将向对方发送 ack 消息。 ack: 将消息编号放入 ack 队列中，检测对方的状态是否是 LOOKING 状态，如果不是说明此时已经有 Leader 已经被选出来，将接收到的消息转发成 Notification 消息放入接收对队列 - 发送线程池的处理 notification: 将要发送的消息由 Notification 消息转换成 ToSend 消息，然后发送对方，并等待对方的回复,如果在等待结束没有收到对方法回复，重做三次,如果重做次还是没有收到对方的回复时检测当前的选举(epoch)是否已经改变，如果没有改变，将消息再次放入发送队列中，一直重复直到有 Leader 选出或者收到对方回复为止。 ack: 主要将自己相关信息发送给对方 - 选举线程的处理 首先自己的 epoch 加 1，然后生成 notification 消息,并将消息放入发送队列中，系统中配置有几个 Server 就生成几条消息，保证每个 Server 都能收到此消息,如果当前 Server 的状态是 LOOKING 就一直循环检查接收队列是否有消息，如果有消息，根据消息中对方的状态进行相应的处理。 # AuthFastLeaderElection 选举算法 AuthFastLeaderElection 算法同 FastLeaderElection 算法基本一致，只是在消息中加入了认证信息，该算法在最新的 Zookeeper 中也建议弃用。 # Example 下面看一个 Leader 选举的例子以加深对 Leader 选举算法的理解。 1. 服务器 1 启动,此时只有它一台服务器启动了,它发出去的报没有任何响应,所以它的选举状态一直是 LOOKING 状态. 2. 服务器 2 启动,它与最开始启动的服务器 1 进行通信,互相交换自己的选举结果,由于两者都没有历史数据,所以 id 值较大的服务器 2 胜出,但是由于没有达到超过半数以上的服务器都同意选举它(这个例子中的半数以上是 3),所以服务器 1,2 还是继续保持 LOOKING 状态. 3. 服务器 3 启动,根据前面的理论分析,服务器 3 成为服务器 1,2,3 中的 Leader,而与上面不同的是,此时有三台服务器选举了它,所以它成为了这次选举的 Leader. 4. 服务器 4 启动,根据前面的分析,理论上服务器 4 应该是服务器 1,2,3,4 中最大的,但是由于前面已经有半数以上的服务器选举了服务器 3,所以它只能是 Follower. 5. 服务器 5 启动,同 4 一样,Follower. # 参考资料