「大数据」（三十三）Zookeeper之选举机制
【导读：数据是二十一世纪的石油，蕴含巨大价值，这是·情报通·大数据技术系列第[33]篇文章，欢迎阅读和收藏】
1 基本概念
Leader选举是保证分布式数据一致性的关键所在。当Zookeeper集群中的一台服务器出现以下两种情况之一时，需要进入Leader选举。
(1) 服务器初始化启动。
(2) 服务器运行期间无法和Leader保持连接。
2 术语解释
2.1 服务器状态
服务器具有四种状态，分别是 LOOKING 、 FOLLOWING 、 LEADING 、 OBSERVING 。
· LOOKING ：寻找 Leader 状态。当服务器处于该状态时，它会认为当前集群中没有 Leader ，因此需要进入 Leader 选举状态。
· FOLLOWING ：跟随者状态。表明当前服务器角色是 Follower 。
· LEADING ：领导者状态。表明当前服务器角色是 Leader 。
· OBSERVING ：观察者状态。表明当前服务器角色是 Observer 。
2.2 投票数据结构
每个投票中包含了两个最基本的信息，所推举服务器的 SID 和 ZXID ，投票（ Vote ）在 Zookeeper 中包含字段如下：
· id ：被推举的 Leader 的 SID 。
· zxid ：被推举的 Leader 事务 ID 。
· electionEpoch ：逻辑时钟，用来判断多个投票是否在同一轮选举周期中，该值在服务端是一个自增序列，每次进入新一轮的投票后，都会对该值进行加 1 操作。
· peerEpoch ：被推举的 Leader 的 epoch 。
· state ：当前服务器的状态。
3 详细说明
3.1 QuorumCnxManager ：网络 I/O
每台服务器在启动的过程中，会启动一个 QuorumPeerManager ，负责各台服务器之间的底层 Leader 选举过程中的网络通信。
3.2 FastLeaderElection ：选举算法核心
在 3.4.0 后的 Zookeeper 的版本只保留了 TCP 版本的 FastLeaderElection 选举算法。
3.2.1 算法概述
当一台机器进入 Leader 选举时，当前集群可能会处于以下两种状态
· 集群中已经存在 Leader 。
对于集群中已经存在 Leader 而言，此种情况一般都是某台机器启动得较晚，在其启动之前，集群已经在正常工作，对这种情况，该机器试图去选举 Leader 时，会被告知当前服务器的 Leader 信息，对于该机器而言，仅仅需要和 Leader 机器建立起连接，并进行状态同步即可。
· 集群中不存在 Leader 。
集群中不存在 Leader 情况下则会相对复杂，其步骤如 下：
1) 第一次投票 。无论哪种导致进行 Leader 选举，集群的所有机器都处于试图选举出一个 Leader 的状态，即 LOOKING 状态， LOOKING 机器会向所有其他机器发送消息，该消息称为投票。投票中包含了 SID （服务器的唯一标识）和 ZXID （事务 ID ）， (SID, ZXID) 形式来标识一次投票信息。假定 Zookeeper 由 5 台机器组成， SID 分别为 1 、 2 、 3 、 4 、 5 ， ZXID 分别为 9 、 9 、 9 、 8 、 8 ，并且此时 SID 为 2 的机器是 Leader 机器，某一时刻， 1 、 2 所在机器出现故障，因此集群开始进行 Leader 选举。在第一次投票时，每台机器都会将自己作为投票对象，于是 SID 为 3 、 4 、 5 的机器投票情况分别为 (3, 9) ， (4, 8) ， (5, 8) 。
2) 变更投票 。每台机器发出投票后，也会收到其他机器的投票，每台机器会根据一定规则来处理收到的其他机器的投票，并以此来决定是否需要变更自己的投票，这个规则也是整个 Leader 选举算法的核心所在，其中术语描述如下 ：
§ vote_sid ：接收到的投票中所推举 Leader 服务器的 SID 。
§ vote_zxid ：接收到的投票中所推举 Leader 服务器的 ZXID 。
§ self_sid ：当前服务器自己的 SID 。
§ self_zxid ：当前服务器自己的 ZXID 。
每次对收到的投票的处理，都是对 (vote_sid, vote_zxid) 和 (self_sid, self_zxid) 对比的过程。
§ 规则一：如果 vote_zxid 大于 self_zxid ，就认可当前收到的投票，并再次将该投票发送出去。
§ 规则二：如果 vote_zxid 小于 self_zxid ，那么坚持自己的投票，不做任何变更。
§ 规则三：如果 vote_zxid 等于 self_zxid ，那么就对比两者的 SID ，如果 vote_sid 大于 self_sid ，那么就认可当前收到的投票，并再次将该投票发送出去。
§ 规则四：如果 vote_zxid 等于 self_zxid ，并且 vote_sid 小于 self_sid ，那么坚持自己的投票，不做任何变更。
3) 确定 Leader 。经过第二轮投票后，集群中的每台机器都会再次接收到其他机器的投票，然后开始统计投票，如果一台机器收到了超过半数的相同投票，那么这个投票对应的 SID 机器即为 Leader 。此时 Server3 将成为 Leader 。
总结： 由上面规则可知，通常那台服务器上的数据越新（ ZXID 会越大），其成为 Leader 的可能性越大，也就越能够保证数据的恢复。如果 ZXID 相同，则 SID 越大机会越大。
3.2.2 算法详解
1) 主要概念
· 外部投票 ：特指其他服务器发来的投票。
· 内部投票 ：服务器自身当前的投票。
· 选举轮次 ：Zookeeper 服务器 Leader 选举的轮次，即 logicalclock 。
· PK ：对内部投票和外部投票进行对比来确定是否需要变更内部投票。
2) 模块交互
上图展示了 FastLeaderElection 模块是如何与底层网络 I/O 进行交互的。其中：
· sendqueue ：选票发送队列，用于保存待发送的选票。
· recvqueue ：选票接收队列，用于保存接收到的外部投票。
· WorkerReceiver ：选票接收器。其会不断地从 QuorumCnxManager 中获取其他服务器发来的选举消息，并将其转换成一个选票，然后保存到 recvqueue 中，在选票接收过程中，如果发现该外部选票的选举轮次小于当前服务器的，那么忽略该外部投票，同时立即发送自己的内部投票。
· WorkerSender ：选票发送器，不断地从 sendqueue 中获取待发送的选票，并将其传递到底层 QuorumCnxManager 中。
3) 基本流程
1. 自增选举轮次 。Zookeeper 规定所有有效的投票都必须在同一轮次中，在开始新一轮投票时，会首先对 logicalclock 进行自增操作。
2. 初始化选票 。在开始进行新一轮投票之前，每个服务器都会初始化自身的选票，并且在初始化阶段，每台服务器都会将自己推举为 Leader 。
3. 发送初始化选票 。完成选票的初始化后，服务器就会发起第一次投票。Zookeeper 会将刚刚初始化好的选票放入 sendqueue 中，由发送器 WorkerSender 负责发送出去。
4. 接收外部投票 。每台服务器会不断地从 recvqueue 队列中获取外部选票。如果服务器发现无法获取到任何外部投票，那么就会立即确认自己是否和集群中其他服务器保持着有效的连接，如果没有连接，则马上建立连接，如果已经建立了连接，则再次发送自己当前的内部投票。
5. 判断选举轮次 。在发送完初始化选票之后，接着开始处理外部投票。在处理外部投票时，会根据选举轮次来进行不同的处理。
· 外部投票的选举轮次大于内部投票。若服务器自身的选举轮次落后于该外部投票对应服务器的选举轮次，那么就会立即更新自己的选举轮次 (logicalclock) ，并且清空所有已经收到的投票，然后使用初始化的投票来进行 PK 以确定是否变更内部投票。最终再将内部投票发送出去。
· 外部投票的选举轮次小于内部投票。若服务器接收的外选票的选举轮次落后于自身的选举轮次，那么 Zookeeper 就会直接忽略该外部投票，不做任何处理，并返回步骤 4 。
· 外部投票的选举轮次等于内部投票。此时可以开始进行选票 PK 。
6. 选票 PK 。在进行选票 PK 时，符合任意一个条件就需要变更投票。
· 若外部投票中推举的 Leader 服务器的选举轮次大于内部投票，那么需要变更投票。
· 若选举轮次一致，那么就对比两者的 ZXID ，若外部投票的 ZXID 大，那么需要变更投票。
· 若两者的 ZXID 一致，那么就对比两者的 SID ，若外部投票的 SID 大，那么就需要变更投票。
7. 变更投票 。经过 PK 后，若确定了外部投票优于内部投票，那么就变更投票，即使用外部投票的选票信息来覆盖内部投票，变更完成后，再次将这个变更后的内部投票发送出去。
8. 选票归档 。无论是否变更了投票，都会将刚刚收到的那份外部投票放入选票集合 recvset 中进行归档。recvset 用于记录当前服务器在本轮次的 Leader 选举中收到的所有外部投票（按照服务队的 SID 区别，如 {(1, vote1), (2, vote2)...} ）。
9. 统计投票 。完成选票归档后，就可以开始统计投票，统计投票是为了统计集群中是否已经有过半的服务器认可了当前的内部投票，如果确定已经有过半服务器认可了该投票，则终止投票。否则返回步骤 4 。
10. 更新服务器状态 。若已经确定可以终止投票，那么就开始更新服务器状态，服务器首选判断当前被过半服务器认可的投票所对应的 Leader 服务器是否是自己，若是自己，则将自己的服务器状态更新为 LEADING ，若不是，则根据具体情况来确定自己是 FOLLOWING 或是 OBSERVING 。
以上 10 个步骤就是 FastLeaderElection 的核心，其中步骤 4-9 会经过几轮循环，直到有 Leader 选举产生。