Leader选举
在4.1.3节中，我们已经了解了ZooKeeper集群中的三种服务器角色：Leader、Follower和 Observer。
接下来，我们将从 Leader 选举概述、算法分析和实现细节三方面来看看ZooKeeper是如何进行Leader选举的。
Leader选举概述
Leader选举是ZooKeeper中最重要的技术之一，也是保证分布式数据一致性的关键所在。
在本节中，我们将先从整体上来对ZooKeeper的Leader选举进行介绍。
服务器启动时期的Leader选举
在我们讲解Leader选举的时候，需要注意的一点是，隐式条件便是ZooKeeper的集群规模至少是2台机器，这里我们以3台机器组成的服务器集群为例。
在服务器集群初始化阶段，当有一台服务器（我们假设这台机器的myid为1，因此称其为Server1）启动的时候，它是无法完成Leader选举的，是无法进行Leader选举的。
当第二台机器（同样，我们假设这台服务器的myid为2，称其为Server2）也启动后，此时这两台机器已经能够进行互相通信，每台机器都试图找到一个Leader，于是便进入了Leader选举流程。
1.每个Server会发出一个投票。
由于是初始情况，因此对于Server1和Server2来说，都会将自己作为Leader服务器来进行投票，每次投票包含的最基本的元素包括：所推举的服务器的 myid 和ZXID，我们以（myid，ZXID）的形式来表示。
因为是初始化阶段，因此无论是Server1还是Server2，都会投给自己，即Server1的投票为（1，0），Server2的投票为（2，0），然后各自将这个投票发给集群中其他所有机器。
2.接收来自各个服务器的投票。
每个服务器都会接收来自其他服务器的投票。集群中的每个服务器在接收到投票后，首先会判断该投票的有效性，包括检查是否是本轮投票、是否来自LOOKING状态的服务器。
3.处理投票。
在接收到来自其他服务器的投票后，针对每一个投票，服务器都需要将别人的投票和自己的投票进行PK，PK的规则如下。
· 优先检查ZXID。ZXID比较大的服务器优先作为Leader。
· 如果ZXID相同的话，那么就比较myid。myid比较大的服务器作为Leader服务器。
现在我们来看Server1和Server2实际是如何进行投票处理的。
对于Server1来说，它自己的投票是（1，0），而接收到的投票为（2，0）。
首先会对比两者的ZXID，因为都是0，所以无法决定谁是Leader。
接下来会对比两者的myid，很显然，Server1发现接收到的投票中的myid是2，大于自己，于是就会更新自己的投票为（2，0），然后重新将投票发出去。
而对于Server2来说，不需要更新自己的投票信息，只是再一次向集群中所有机器发出上一次投票信息即可。
4.统计投票。
每次投票后，服务器都会统计所有投票，判断是否已经有过半的机器接收到相同的投票信息。对于Server1和Server2服务器来说，都统计出集群中已经有两台机器接受了（2，0）这个投票信息。这里我们需要对“过半”的概念做一个简单的介绍。所谓“过半”就是指大于集群机器数量的一半，即大于或等于（n/2+1）。对于这里由3台机器构成的集群，大于等于2台即为达到“过半”要求。 那么，当Server1和Server2都收到相同的投票信息（2，0）的时候，即认为已经选出了Leader。
5.改变服务器状态。
一旦确定了 Leader，每个服务器就会更新自己的状态：如果是 Follower，那么就变更为FOLLOWING，如果是Leader，那么就变更为LEADING。
服务器运行期间的Leader选举
在ZooKeeper集群正常运行过程中，一旦选出一个Leader，那么所有服务器的集群角色一般不会再发生变化——也就是说，Leader服务器将一直作为集群的Leader，即使集群中有非Leader集群挂了或是有新机器加入集群也不会影响Leader。
但是一旦Leader所在的机器挂了，那么整个集群将暂时无法对外服务，而是进入新一轮的Leader选举。
服务器运行期间的Leader选举和启动时期的Leader选举基本过程是一致的。
我们假设当前正在运行的 ZooKeeper 服务器由 3 台机器组成，分别是 Server1、Server2和Server3，当前的Leader是Server2。
假设在某一个瞬间，Leader挂了，这个时候便开始了Leader选举。
1.变更状态。
当 Leader 挂了之后，余下的非 Observer 服务器都会将自己的服务器状态变更为LOOKING，然后开始进入Leader选举流程。
2.每个Server会发出一个投票。
在这个过程中，需要生成投票信息（myid，ZXID）。因为是运行期间，因此每个服务器上的ZXID可能不同，我们假定Server1的ZXID为123，而Server3的ZXID为 122。在第一轮投票中，Server1 和 Server3 都会投自己，即分别产生投票（1，123）和（3，122），然后各自将这个投票发给集群中所有机器。
3.接收来自各个服务器的投票。
4.处理投票。
对于投票的处理，和上面提到的服务器启动期间的处理规则是一致的。在这个例子里面，由于Server1的ZXID为123，Server3的ZXID为122，那么显然，Server1会成为Leader。
5.统计投票。
6.改变服务器状态。
Leader选举的算法分析
在7.6.1节中，我们已经大体了解了ZooKeeper的Leader选举过程，接下来让我们看看ZooKeeper的Leader选举算法。
在ZooKeeper中，提供了三种Leader选举的算法，分别是LeaderElection、UDP版本的FastLeaderElection和TCP版本的FastLeaderElection，可以通过在配置文件zoo.cfg中使用electionAlg属性来指定，分别使用数字0～3来表示。
0代表LeaderElection，这是一种纯UDP实现的Leader选举算法；
1代表UDP版本的FastLeaderElection，并且是非授权模式；
2 也代表 UDP 版本的 FastLeaderElection，但使用授权模式；3 代表 TCP版本的FastLeaderElection。
值得一提的是，从3.4.0版本开始，ZooKeeper废弃了0、1和2这三种Leader选举算法，只保留了TCP版本的FastLeaderElection选举算法。下文即仅对此算法进行介绍。
由于在官方文档以及一些外文资料中，对于概念的描述非常的“晦涩”，因此本书在讲解ZooKeeper的Leader选举算法的时候，尽量使用一些外文的专有术语来保持一致性，以便于读者理解相关内容。
术语解释
首先我们对ZooKeeper的Leader选举算法介绍中会出现的一些专有术语进行简单介绍，以便读者更好地理解本书内容。
SID：服务器ID
SID是一个数字，用来唯一标识一台ZooKeeper集群中的机器，每台机器不能重复，和myid的值一致。
关于myid，我们已经在5.1.2节讲解如何部署一个ZooKeeper集群的时候提到过。
ZXID：事务ID
ZXID是一个事务ID，用来唯一标识一次服务器状态的变更。在某一个时刻，集群中每台机器的ZXID值不一定全都一致，这和ZooKeeper服务器对于客户端“更新请求”的处理逻辑有关。具体可以参见7.8节中对于客户端“更新请求”处理的介绍。
Vote：投票
Leader 选举，顾名思义必须通过投票来实现。当集群中的机器发现自己无法检测到Leader机器的时候，就会开始尝试进行投票。
Quorum：过半机器数
这是整个Leader选举算法中最重要的一个术语，我们可以把这个术语理解为是一个量词，指的是ZooKeeper集群中过半的机器数，如果集群中总的机器数是n的话，那么可以通过下面这个公式来计算quorum的值：
Quorum = (n/2) + 1
例如，如果集群机器总数是3，那么quorum就是2。
算法分析
接下来我们就一起深入Leader选举算法，看看Leader选举的技术内幕。
进入Leader选举
当ZooKeeper集群中的一台服务器出现以下两种情况之一时，就会开始进入Leader选举。
· 服务器初始化启动。
· 服务器运行期间无法和Leader保持连接。
而当一台机器进入Leader选举流程时，当前集群也可能会处于以下两种状态。
· 集群中本来就已经存在一个Leader。
· 集群中确实不存在Leader。
我们首先来看第一种已经存在Leader的情况。这种情况通常是集群中的某一台机器启动比较晚，在它启动之前，集群已经可以正常工作，即已经存在了一台Leader服务器。
针对这种情况，当该机器试图去选举Leader的时候，会被告知当前服务器的Leader信息，对于该机器来说，仅仅需要和Leader机器建立起连接，并进行状态同步即可。
下面我们重点来看在集群中Leader不存在的情况下，如何进行Leader选举。
开始第一次投票
通常有两种情况会导致集群中不存在Leader，一种情况是在整个服务器刚刚初始化启动时，此时尚未产生一台 Leader 服务器；另一种情况就是在运行期间当前 Leader 所在的服务器挂了。
无论是哪种情况，此时集群中的所有机器都处于一种试图选举出一个Leader的状态，我们把这种状态称为“LOOKING”，意思是说正在寻找Leader。
当一台服务器处于LOOKING状态的时候，那么它就会向集群中所有其他机器发送消息，我们称这个消息为“投票”。
在这个投票消息中包含了两个最基本的信息：所推举的服务器的SID和ZXID，分别表示了被推举服务器的唯一标识和事务ID。
下文中我们将以“（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选举。
在第一次投票的时候，由于还无法检测到集群中其他机器的状态信息，因此每台机器都是将自己作为被推举的对象来进行投票。于是SID为3、4和5的机器，投票情况分别为：（3，9）、（4，8）和（5，8）。
变更投票
集群中的每台机器发出自己的投票后，也会接收到来自集群中其他机器的投票。
每台机器都会根据一定的规则，来处理收到的其他机器的投票，并以此来决定是否需要变更自己的投票。
这个规则也成为了整个Leader选举算法的核心所在。为了便于描述，我们首先定义一些术语。
· vote_sid：接收到的投票中所推举Leader服务器的SID。 · vote_zxid：接收到的投票中所推举Leader服务器的ZXID。 · self_sid：当前服务器自己的SID。 · self_zxid：当前服务器自己的ZXID。
每次对于收到的投票的处理，都是一个对（vote_sid，vote_zxid）和（self_sid，self_zxid）对比的过程。
· 规则1：如果vote_zxid大于self_zxid，就认可当前收到的投票，并再次将该投票发送出去。
· 规则2：如果vote_zxid小于self_zxid，那么就坚持自己的投票，不做任何变更。
· 规则3：如果vote_zxid等于self_zxid，那么就对比两者的SID。如果vote_sid大于self_sid，那么就认可当前接收到的投票，并再次将该投票发送出去。
· 规则 4：如果 vote_zxid等于self_zxid，并且vote_sid小于self_sid，那么同样坚持自己的投票，不做变更。
根据上面这个规则，我们结合图 7-32 来分析上面提到的 5 台机器组成的 ZooKeeper 集群的投票变更过程。
图7-32.Leader选举过程中发生投票变更
每台机器都把投票发出后，同时也会接收到来自另外两台机器的投票。
· 对于 Server3 来说，它接收到了（4，8）和（5，8）两个投票，对比后，由于自己的ZXID要大于接收到的两个投票，因此不需要做任何变更。
· 对于 Server4 来说，它接收到了（3，9）和（5，8）两个投票，对比后，由于（3，9）这个投票的 ZXID 大于自己，因此需要变更投票为（3，9），然后继续将这个投票发送给另外两台机器。
· 同样，对于 Server5 来说，它接收到了（3，9）和（4，8）两个投票，对比后，由于（3，9）这个投票的ZXID大于自己，因此需要变更投票为（3，9），然后继续将这个投票发送给另外两台机器。
确定Leader
经过这第二次投票后，集群中的每台机器都会再次收到其他机器的投票，然后开始统计投票。
如果一台机器收到了超过半数的相同的投票，那么这个投票对应的SID机器即为Leader。
如图7-32所示的Leader选举例子中，因为ZooKeeper集群的总机器数为5台，那么
quorum = (5/2) + 1 = 3
也就是说，只要收到3个或3个以上（含当前服务器自身在内）一致的投票即可。在这里，Server3、Server4和Server5都投票（3，9），因此确定了Server3为Leader。
小结
简单地说，通常哪台服务器上的数据越新，那么越有可能成为Leader，原因很简单，数据越新，那么它的ZXID也就越大，也就越能够保证数据的恢复。
当然，如果集群中有几个服务器具有相同的ZXID，那么SID较大的那台服务器成为Leader。
Leader选举的实现细节
在 7.6.2 节中，我们介绍了整个 Leader 选举的算法设计。从算法复杂度来说，FastLeaderElection算法的设计并不复杂，但在真正的实现过程中，对于一个需要应用在生产环境的产品来说，还是有很多实际问题需要解决。在本节中，我们就来看看ZooKeeper中对FastLeaderElection的实现。
服务器状态
为了能够清楚地对 ZooKeeper 集群中每台机器的状态进行标识，在 org.apache.zookeeper.server.quorum.QuorumPeer.ServerState类中列举了4种服务器状态，分别是：LOOKING、FOLLOWING、LEADING和OBSERVING。
· LOOKING：寻找Leader状态。当服务器处于该状态时，它会认为当前集群中没有Leader，因此需要进入Leader选举流程。 · FOLLOWING：跟随者状态，表明当前服务器角色是Follower。 · LEADING：领导者状态，表明当前服务器角色是Leader。 · OBSERVING：观察者状态，表明当前服务器角色是Observer。
投票数据结构
在 7.6.2 节中，我们已经提到，Leader 的选举过程是通过投票来实现的，同时每个投票中包含两个最基本的信息：所推举服务器的 SID 和 ZXID。
现在我们来看在 ZooKeeper中对Vote数据结构的定义，如图7-33所示。
id
zxid
peerEpoch
state
读者可以在org.apache.zookeeper.server.quorum.Vote类中查看其完整的定义，表7-9中列举了Vote中的几个属性。
表7-9.Vote属性说明
QuorumCnxManager：网络I/O
在 7.3.3 节中，我们曾讲解过，ClientCnxn 是 ZooKeeper 客户端中用于处理网络 I/O的一个管理器。
在Leader选举的过程中也有类似的角色，那就是QuorumCnxManager——每台服务器启动的时候，都会启动一个 QuorumCnxManager，负责各台服务器之间的底层Leader选举过程中的网络通信。
消息队列
在QuorumCnxManager这个类内部维护了一系列的队列，用于保存接收到的、待发送的消息，以及消息的发送器。
除接收队列以外，这里提到的所有队列都有一个共同点——按SID分组形成队列集合，我们以发送队列为例来说明这个分组的概念。
假设集群中除自身外还有4台机器，那么当前服务器就会为这4台服务器分别创建一个发送队列，互不干扰。
· recvQueue：消息接收队列，用于存放那些从其他服务器接收到的消息。
· queueSendMap：消息发送队列，用于保存那些待发送的消息。queueSendMap是一个Map，按照SID进行分组，分别为集群中的每台机器分配了一个单独队列，从而保证各台机器之间的消息发送互不影响。
· senderWorkerMap：发送器集合。每个 SendWorker 消息发送器，都对应一台远程 ZooKeeper 服务器，负责消息的发送。同样，在 senderWorkerMap 中，也按照SID进行了分组。
· lastMessageSent：最近发送过的消息。在这个集合中，为每个SID保留最近发送过的一个消息。
建立连接
为了能够进行互相投票，ZooKeeper 集群中的所有机器都需要两两建立起网络连接。QuorumCnxManager在启动的时候，会创建一个ServerSocket来监听Leader选举的通信端口（Leader 选举的通信端口默认是 3888，在 8.1 节中有详细讲解）。
开启端口监听后，ZooKeepr就能够不断地接收到来自其他服务器的“创建连接”请求，在接收到其他服务器的TCP连接请求时，会交由receiveConnection函数来处理。
为了避免两台机器之间重复地创建 TCP 连接，ZooKeeper 设计了一种建立 TCP 连接的规则：只允许 SID 大的服务器主动和其他服务器建立连接，否则断开连接。
在ReceiveConnection 函数中，服务器通过对比自己和远程服务器的 SID 值，来判断是否接受连接请求。如果当前服务器发现自己的SID值更大，那么会断开当前连接，然后自己主动去和远程服务器建立连接。
一旦建立起连接，就会根据远程服务器的 SID 来创建相应的消息发送器 SendWorker和消息接收器RecvWorker，并启动他们。
消息接收与发送
消息的接收过程是由消息接收器 RecvWorker 来负责的。在上面的讲解中，我们已经提到了 ZooKeeper 会为每个远程服务器分配一个单独的 RecvWorker，因此，每个RecvWorker 只需要不断地从这个 TCP 连接中读取消息，并将其保存到 recvQueue队列中。
消息的发送过程也比较简单，由于ZooKeeper同样也已经为每个远程服务器单独分别分配了消息发送器SendWorker，那么每个SendWorker只需要不断地从对应的消息发送队列中获取出一个消息来发送即可，同时将这个消息放入 lastMessageSent 中来作为最近发送过的消息。
在 SendWorker 的具体实现中，有一个细节需要我们注意一下：一旦ZooKeeper发现针对当前远程服务器的消息发送队列为空，那么这个时候就需要从 lastMessageSent 中取出一个最近发送过的消息来进行再次发送。这个细节的处理主要是为了解决这样一类分布式问题：接收方在消息接收前，或者是在接收到消息后服务器挂掉了，导致消息尚未被正确处理。
那么如此重复发送是否会导致其他问题呢？当然，这里可以放心的一点是，ZooKeeper 能够保证接收方在处理消息的时候，会对重复消息进行正确的处理。
FastLeaderElection：选举算法的核心部分
下面我们来看Leader选举的核心算法部分的实现。在讲解之前，我们首先约定几个概念。
· 外部投票：特指其他服务器发来的投票。 · 内部投票：服务器自身当前的投票。 · 选举轮次：ZooKeeper服务器Leader选举的轮次，即logicalclock。 · PK：指对内部投票和外部投票进行一个对比来确定是否需要变更内部投票。
选票管理
我们已经讲解了，在 QuorumCnxManager 中，ZooKeeper 是如何管理服务器之间的投票发送和接收的，现在我们来看对于选票的管理。图 7-34 所示是选票管理过程中相关组件之间的协作关系。
· sendqueue：选票发送队列，用于保存待发送的选票。 · recvqueue：选票接收队列，用于保存接收到的外部投票。 · WorkerReceiver：选票接收器。该接收器会不断地从 QuorumCnxManager 中获取出其他服务器发来的选举消息，并将其转换成一个选票，然后保存到recvqueue队列中去。
在选票的接收过程中，如果发现该外部投票的选举轮次小于当前服务器，那么就直接忽略这个外部投票，同时立即发出自己的内部投票。当然，如果当前服务器并不是LOOKING状态，即已经选举出了Leader，那么也将忽略这个外部投票，同时将Leader信息以投票的形式发送出去。
另外，对于选票接收器，还有一个细节需要注意，如果接收到的消息来自Observer服务器，那么就忽略该消息，并将自己当前的投票发送出去。
· WorkerSender：选票发送器，会不断地从sendqueue队列中获取待发送的选票，并将其传递到底层QuorumCnxManager中去。
算法核心
在图7-34中，我们可以看到FastLeaderElection模块是如何与底层的网络I/O进行交互的，其中不难发现，在“选举算法”中将会对接收到的选票进行处理。
下面我们就来看看这个选举过程的核心算法实现，图7-35展示了Leader选举算法实现的流程示意图。
- 图7-35.Leader选举算法实现的流程示意图
图7-35中展示了Leader选举算法的基本流程，其实也就是lookForLeader方法的逻辑。当 ZooKeeper 服务器检测到当前服务器状态变成 LOOKING 时，就会触发 Leader选举，即调用lookForLeader方法来进行Leader选举。
1.自增选举轮次。
在 FastLeaderElection 实现中，有一个 logicalclock 属性，用于标识当前Leader的选举轮次，ZooKeeper规定了所有有效的投票都必须在同一轮次中。ZooKeeper在开始新一轮的投票时，会首先对logicalclock进行自增操作。
2.初始化选票。
在开始进行新一轮的投票之前，每个服务器都会首先初始化自己的选票。在图7-33中我们已经讲解了 Vote 数据结构，初始化选票也就是对 Vote 属性的初始化。在初始化阶段，每台服务器都会将自己推举为Leader，表7-10展示了一个初始化的选票。
表7-10.选票初始化
3.发送初始化选票。
在完成选票的初始化后，服务器就会发起第一次投票。ZooKeeper 会将刚刚初始化好的选票放入sendqueue队列中，由发送器WorkerSender负责发送出去。
4.接收外部投票。
每台服务器都会不断地从 recvqueue 队列中获取外部投票。如果服务器发现无法获取到任何的外部投票，那么就会立即确认自己是否和集群中其他服务器保持着有效连接。如果发现没有建立连接，那么就会马上建立连接。如果已经建立了连接，那么就再次发送自己当前的内部投票。
5.判断选举轮次。
当发送完初始化选票之后，接下来就要开始处理外部投票了。在处理外部投票的时候，会根据选举轮次来进行不同的处理。
· 外部投票的选举轮次大于内部投票。
如果服务器发现自己的选举轮次已经落后于该外部投票对应服务器的选举轮次，那么就会立即更新自己的选举轮次（logicalclock），并且清空所有已经收到的投票，然后使用初始化的投票来进行PK以确定是否变更内部投票（关于P K的逻辑会在步骤6中统一讲解），最终再将内部投票发送出去。
· 外部投票的选举轮次小于内部投票。
如果接收到的选票的选举轮次落后于服务器自身的，那么ZooKeeper就会直接忽略该外部投票，不做任何处理，并返回步骤4。
· 外部投票的选举轮次和内部投票一致。
这也是绝大多数投票的场景，如果外部投票的选举轮次和内部投票一致的话，那么就开始进行选票PK。 总的来说，只有在同一个选举轮次的投票才是有效的投票。
6.选票PK。
在步骤5中提到，在收到来自其他服务器有效的外部投票后，就要进行选票PK了——也就是FastLeaderElection.totalOrderPredicate方法的核心逻辑。选票PK的目的是为了确定当前服务器是否需要变更投票，主要从选举轮次、ZXID和 SID 三个因素来考虑，具体条件如下：在选票 PK 的时候依次判断，符合任意一个条件就需要进行投票变更。 · 如果外部投票中被推举的Leader服务器的选举轮次大于内部投票，那么就需要进行投票变更。 · 如果选举轮次一致的话，那么就对比两者的ZXID。如果外部投票的ZXID大于内部投票，那么就需要进行投票变更。 · 如果两者的 ZXID 一致，那么就对比两者的 SID。如果外部投票的 SID 大于内部投票，那么就需要进行投票变更。
7.变更投票。
通过选票PK后，如果确定了外部投票优于内部投票（所谓的“优于”，是指外部投票所推举的服务器更适合成为Leader），那么就进行投票变更——使用外部投票的选票信息来覆盖内部投票。变更完成后，再次将这个变更后的内部投票发送出去。
8.选票归档。
无论是否进行了投票变更，都会将刚刚收到的那份外部投票放入“选票集合”recvset中进行归档。recvset用于记录当前服务器在本轮次的Leader选举中收到的所有外部投票——按照服务器对应的SID来区分，例如，{（1，vote1），（2，vote2），…}。
9.统计投票。
完成了选票归档之后，就可以开始统计投票了。统计投票的过程就是为了统计集群中是否已经有过半的服务器认可了当前的内部投票。如果确定已经有过半的服务器认可了该内部投票，则终止投票。否则返回步骤4。
10.更新服务器状态。
统计投票后，如果已经确定可以终止投票，那么就开始更新服务器状态。服务器会首先判断当前被过半服务器认可的投票所对应的Leader服务器是否是自己，如果是自己的话，那么就会将自己的服务器状态更新为 LEADING。如果自己不是被选举产生的 Leader 的话，那么就会根据具体情况来确定自己是 FOLLOWING或是OBSERVING。
以上 10 个步骤，就是 FastLeaderElection 选举算法的核心步骤，其中步骤 4～9 会经过几轮循环，直到Leader选举产生。
另外还有一个细节需要注意，就是在完成步骤9之后，如果统计投票发现已经有过半的服务器认可了当前的选票，这个时候，ZooKeeper 并不会立即进入步骤 10 来更新服务器状态，而是会等待一段时间（默认是 200 毫秒）来确定是否有新的更优的投票。
参考资料
分布式一致性原理与实践
