【ZooKeeper】Leader 选举实现细节

深藏阁楼爱情的钟 2022-10-21 03:48 226阅读 0赞

# Leader 选举的实现细节 #

我们介绍了整个 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 。

## 投票数据结构 ##

Leader 的选举过程是通过投票来实现的，同时每个投票 中包含两个最基本的信息：所推举服务器的 SID 和 ZXID 。现在我们来看在 ZooKeeper 中对 Vote 数据结构的定义，如图所示。  
![在这里插入图片描述][20210502205335593.png]

Vote 中的几个属性。  
![在这里插入图片描述][2021050221224271.png]

## QuorumCnxManager ： 网络 I/O ##

我们曾讲解过， ClientCnxn 是 ZooKeeper 客户端中用于处理网络 I/O 的一个管理器。在 Leader 选举的过程中也有类似的角色，那就是 QuorumCnxManager ——每台服务器启动的时候，都会启动一个 QuorumCnxManager, 负责各台服务器之 间的底层 Leader 选举过程中的网络通信。

## 消息队列 ##

在 QuorumCnxManager 这个类内部维护了一系列的队列，用于保存接收到的、待发送 的消息，以及消息的发送器。除接收队列以外，这里提到的所有队列都有一个共同点一 按 SID 分组形成队列集合，我们以发送队列为例来说明这个分组的概念。假设集群中除 自身外还有 4 台机器，那么当前服务器就会为这 4 台服务器分别创建一个发送队列，互 不干扰。

*  recvQueue： 消息接收队列，用于存放那些从其他服务器接收到的消息。
 *  queueSendMap： 消息发送队列，用于保存那些待发送的消息。 queueSendMap 是一个 按照 SID 进行分组，分别为集群中的每台机器分配了一个单独队列， 从而保证各台机器之间的消息发送互不影响。
 *  senderWorkerMap： 发送器集合。每个 SendWorker 消息发送器，都对应一台 远程ZooKeeper 服务器，负责消息的发送。同样，在 senderWorkerMap 中，也 按照 SID 进行了分组。
 *  lastMessageSent： 最近发送过的消息。在这个集合中，为每个 SID 保留最近发 送过的一个消息。

## 建立连接 ##

为了能够进行互相投票， ZooKeeper 集群中的所有机器都需要两两建立起网络连接。QuorumCnxManager 在启动的时候，会创建一个 ServerSocket 来监听 Leader 选举 的通信端口（Leader 选举的通信端口默认是 3888,）。开启端口 监听后， 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 ：指对内部投票和外部投票进行一个对比来确定是否需要变更内部投票。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]

**选票管理**  
我们已经讲解了，在 QuorumCnxManager 中， ZooKeeper 是如何管理服务器之间的 投票发送和接收的，现在我们来看对于选票的管理。图所示是选票管理过程中相 关组件之间的协作关系。

*  sendqueue： 选票发送队列，用于保存待发送的选票。
 *  recvqueue： 选票接收队列，用于保存接收到的外部投票。
 *  WorkerReceiver： 选票接收器。该接收器会不断地从 QuorumCnxManager 中 获取出其他服务器发来的选举消息，并将其转换成一个选禀，然后保存到 recvqueue 队列中去。在选票的接收过程中，如果发现该外部投票的选举轮次小 于当前服务器，那么就直接忽略这个外部投票，同时立即发出自己的内部投票。当然，如果当前服务器并不是 LOOKING 状态，即已经选举出了 Leader, 那么也将忽 略这个外部投票，同时将 Leader 信息以投票的形式发送出去。
    
    另外，对于选票接收器，还有一个细节需要注意，如果接收到的消息来自 Observer 服务器，那么就忽略该消息，并将自己当前的投票发送出去。
 *  Workersender： 选票发送器，会不断地从 sendqueue 队列中获取待发送的选票， 并将其传递到底层 QuorumCnxManager 中去。

**算法核心**  
在图中，我们可以看到 FastLeaderElection 模块是如何与底层的网络 I/O 进行 交互的，其中不难发现，在“选举算法”中将会对接收到的选票进行处理。下面我们就来 看看这个选举过程的核心算法实现  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]

图中展示了 Leader 选举算法的基本流程，其实也就是 lookForLeader 方法的逻 辑。当ZooKeeper 服务器检测到当前服务器状态变成 LOOKING 时，就会触发 Leader 选举，即调用lookForLeader 方法来进行 Leader 选举。

1.  自增选举轮次。  
    在 FastLeaderElection 实现中，有一个 logicalclock 属性，用于标识当 前 Leader 的选举轮次， ZooKeeper 规定了所有有效的投票都必须在同一轮次中。 ZooKeeper 在开始新一轮的投票时，会首先对 logicalclock 进行自增操作。
2.  初始化选票。  
    在开始进行新一轮的投票之前，每个服务器都会首先初始化自己的选票。我们已经讲解了 vote 数据结构，初始化选票也就是对 Vote 属性的初始化。 在初始化阶段，每台服务器都会将自己推选为 leader
3.  发送初始化选票。  
    在完成选票的初始化后，服务器就会发起第一次投票。 ZooKeeper 会将刚刚初始 化好的选票放入 sendqueue 队列中，由发送器 Workersender 负责发送出去。
4.  接收外部投票。  
    每台服务器都会不断地从 recvqueue 队列中获取外部投票。如果服务器发现无 法获取到任何的外部投票，那么就会立即确认自己是否和集群中其他服务器保持 着有效连接。如果发现没有建立连接，那么就会马上建立连接。如果已经建立了 连接，那么就再次发送自己当前的内部投票。
5.  判断选举轮次。  
    当发送完初始化选票之后，接下来就要开始处理外部投票了。在处理外部投票的 时候，会根据选举轮次来进行不同的处理。

*  外部投票的选举轮次大于内部投票。
 *  如果服务器发现自己的选举轮次已经落后于该外部投票对应服务器的选举 轮次，那么就会立即更新自己的选举轮次 (logicalclock), 并且清空 所有已经收到的投票，然后使用初始化的投票来进行 PK 以确定是否变更内 部投票(关于 PK 的逻辑会在步骤 6 中统一讲解)，最终再将内部投票发送 出去。
 *  外部投票的选举轮次小于内部投票。如果接收到的选票的选举轮次落后于服务器自身的，那么 ZooKeeper 就会直 接忽略该外部投票，不做任何处理，并返回步骤 4 。
 *  外部投票的选举轮次和内部投票一致。 这也是绝大多数投票的场景，如果外部投票的选举轮次和内部投票一致的话， 那么就开始进行选票 PK 。
    
    总的来说，只有在同一个选举轮次的投票才是有效的投票。

1.  选票 PK 。  
    在步骤 5 中提到，在收到来自其他服务器有效的外部投票后，就要进行选票 PK 了 也就是 FastLeaderElection. totalOrderPredicate 方法的核心逻辑。 选票 PK 的目的是为了确定当前服务器是否需要变更投票，主要从选举轮次、 ZXID 和 SID 三个因素来考虑，具体条件如下：在选票 PK 的时候依次判断，符合任意 一个条件就需要进行投票变更。

*  如果外部投票中被推举的 Leader 服务器的选举轮次大于内部投票，那么就 需要进行投票变更。
 *  如果选举轮次一致的话，那么就对比两者的 ZXID 。如果外部投票的 ZXID 大于内部投票，那么就需要进行投票变更。
 *  如果两者的 ZXID 一致，那么就对比两者的 SID 。如果外部投票的 SID 大 于内部投票，那么就需要进行投票变更。

1.  变更投票。  
    通过选票 PK 后，如果确定了外部投票优于内部投票(所谓的“优于”，是指外部 投票所推举的服务器更适合成为 Leader), 那么就进行投票变更——使用外部投票 的选票信息来覆盖内部投票。变更完成后，再次将这个变更后的内部投票发送出去。
2.  选票归档。  
    无论是否进行了投票变更，都会将刚刚收到的那份外部投票放入“选票集合” recvset 中进行归档。 recvset 用于记录当前服务器在本轮次的 Leader 选举中 收到的所有外部投票——按照服务器对应的 SID 来区分，例如， ( (1, votel), (2, vote2)…\}
3.  统计投票。  
    完成了选票归档之后，就可以开始统计投票了。统计投票的过程就是为了统计集 群中是否已经有过半的服务器认可了当前的内部投票。如果确定已经有过半的服 务器认可了该内部投票，则终止投票。否则返回步骤 4 。
4.  更新服务器状态。  
    统计投票后，如果已经确定可以终止投票，那么就开始更新服务器状态。服务器 会首先判断当前被过半服务器认可的投票所对应的 Leader 服务器是否是自己，如 果是自己的话，那么就会将自己的服务器状态更新为 LEADING o 如果自己不是 被选举产生的 Leader 的话，那么就会根据具体情况来确定自己是 FOLLOWING 或是 OBSERVING 。

以上 10 个步骤，就是 FastLeaderElection 选举算法的核心步骤，其中步骤 4-9 会经过 几轮循环，直到 Leader 选举产生。另外还有一个细节需要注意，就是在完成步骤 9 之后， 如果统计投票发现已经有过半的服务器认可了当前的选票，这个时候， ZooKeeper 并不 会立即进入步骤 10 来更新服务器状态，而是会等待一段时间（默认是 200 毫秒）来确 定是否有新的更优的投票。

[20210502205335593.png]: /images/20221021/42638237255544ff84ec75d54ccddf54.png
[2021050221224271.png]: /images/20221021/3cf6c1850ca549cfa94c329f8468ad79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221021/b38b1f25c2bf4ce6bc707db40d060d3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: /images/20221021/3db00a43b0cd47a49ad28980c53f6f79.png