Lanchester Blog

Leave a leaf

0%

ZooKeeper 服务器启动及Leader选举

Posted on Edited on In

介绍了 ZooKeeper 服务器启动的过程以及启动后 Leader 选举的操作。

服务器启动

ZooKeeper 服务器的整体架构

单机版服务器启动

ZooKeeper 服务器的启动，大体可以分为以下五个主要步骤：配置文件解析、初始化数据管理器、初始化网络 IO 管理器、数据恢复和对外服务。下图所示是单机版 ZooKeeper 服务器的启动流程图。

预启动

预启动的步骤如下：

  1. 统一由 QuorumPeerMain 作为启动类
    无论是单机版还是集群模式启动 ZooKeeper 服务器，在zkServer.cmd和zkServer.sh两个脚本中，都配置了使用org.apache.zookeeper.server.quorum.QuorumPeerMain作为启动入口类。

  2. 解析配置文件 zoo.cfg
    ZooKeeper 首先会进行配置文件的解析，配置文件的解析其实就是对 zoo.cfg 文件的解析。我们曾经提到在部署 Zookeeper 服务器时，需要使用到 zoo.cfg 这个文件。该文件配置了 ZooKeeper 运行时的基本参数，包括 tickTime、dataDir 和 clientPort 等参数。关于 ZooKeeper 参数配置，将在8.1节中做详细讲解。

  3. 创建并启动历史文件清理器 DatadirCleanupManager

    从 3.4.0 版本开始，ZooKeeper 增加了自动清理历史数据文件的机制，包括对事务日志和快照数据文件进行定时清理。

  4. 判断当前是集群模式还是单机模式的启动

    ZooKeeper 根据步骤 2 中解析出的集群服务器地址列表来判断当前是集群模式还是单机模式，如果是单机模式，那么就委托给 ZooKeeperServerMain 进行启动处理。

  5. 再次进行配置文件 zoo.cfg 的解析

  6. 创建服务器实例 ZooKeeperServer

    org.apache.zookeeper.server.ZooKeeperServer 是单机版 ZooKeeper 服务端最为核心的实体类。ZooKeeper 服务器首先会进行服务器实例的创建，接下去的步骤则都是对该服务器实例的初始化工作，包括连接器、内存数据库和请求处理器等组件的初始化。

初始化

初始化的步骤如下

  1. 创建服务器统计器 ServerStats

    ServerStats 是 ZooKeeper 服务器运行时的统计器，包含了最基本的运行时信息，如下表所示。

  2. 创建 ZooKeeper 数据管理器 FileTxnSnapLog

    FileTxnSnapLog 是 ZooKeeper 上层服务器和底层数据存储之间的对接层，提供了一系列操作数据文件的接口，包括事务日志文件和快照数据文件。ZooKeeper 根据 zoo.cfg 文件中解析出的快照数据目录 dataDir 和事务日志目录 dataLogDir 来创建 FileTxnSnapLog。

  3. 设置服务器 tickTime 和会话超时时间限制

  4. 创建 ServerCnxnFactory
    在早期版本中，ZooKeeper 都是自己实现 NIO 框架，从 3.4.0 版本开始，引入了 Netty。读者可以通过配置系统属性 zookeeper.serverCnxnFactory 来指定使用 ZooKeeper 自己实现的 NIO 还是使用 Netty 框架来作为 ZooKeeper 服务端网络连接工厂。

  5. 初始化 ServerCnxnFactory

    ZooKeeper 首先会初始化一个 Thread，作为整个 ServerFactory 的主线程，然后再初始化 NIO 服务器。

  6. 启动 ServerCnxnFactory 主线程

    启动步骤 5 中已经初始化的主线程 ServerCnxnFactory 的主逻辑（run方法）。需要注意的一点是，虽然这里 ZooKeeper 的 NIO 服务器已经对外开放端口，客户端能够访问到 ZooKeeper 的客户端服务端口 2181，但是此时 ZooKeeper 服务器是无法正常处理客户端请求的。

  7. 恢复本地数据
    每次在 ZooKeeper 启动的时候，都需要从本地快照数据文件和事务日志文件中进行数据恢复。

  8. 创建并启动会话管理器

    在 ZooKeeper 启动阶段，会创建一个会话管理器 SessionTracker。关于 SessionTracker，它主要负责 ZooKeeper 服务端的会话管理。创建 SessionTracker 的时候，会初始化 expirationInterval、nextExpirationTime 和 sessionsWithTimeout（用于保存每个会话的超时时间），同时还会计算出一个初始化的 sessionID。

    SessionTracker 初始化完毕后，ZooKeeper 就会立即开始会话管理器的会话超时检查。

  9. 初始化 ZooKeeper 的请求处理链

    ZooKeeper 的请求处理方式是典型的责任链模式的实现，在 ZooKeeper 服务器上，会有多个请求处理器依次来处理一个客户端请求。在服务器启动的时候，会将这些请求处理器串联起来形成一个请求处理链。单机版服务器的请求处理链主要包括 PrepRequestProcessor、SyncRequestProcessor 和 FinalRequestProcessor 三个请求处理器。

  1. 注册 JMX 服务

    ZooKeeper 会将服务器运行时的一些信息以 JMX 的方式暴露给外部。

  2. 注册 ZooKeeper 服务器实例

    在步骤 6 中，ZooKeeper 已经将 ServerCnxnFactory 主线程启动，但是同时我们提到此时 ZooKeeper 依旧无法处理客户端请求，原因就是此时网络层尚不能够访问 ZooKeeper 服务器实例。在经过后续步骤的初始化后，ZooKeeper 服务器实例已经初始化完毕，只需要注册给 ServerCnxnFactory 即可，之后，ZooKeeper 就可以对外提供正常的服务了

至此，单机版的 ZooKeeper 服务器启动完毕。

集群版服务器启动

集群版和单机版 ZooKeeper 服务器的启动过程在很多地方都是一致的。

预启动

预启动的步骤如下。

  1. 统一由 QuorumPeerMain 作为启动类

  2. 解析配置文件 zoo.cfg

  3. 创建并启动历史文件清理器 DatadirCleanupManager

  4. 判断当前是集群模式还是单机模式的启动

    在集群模式中，由于已经在 zoo.cfg 中配置了多个服务器地址，因此此处选择集群模式启动 ZooKeeper。

初始化

初始化的步骤如下

  1. 创建 ServerCnxnFactory

  2. 初始化 ServerCnxnFactory

  3. 创建 ZooKeeper 数据管理器 FileTxnSnapLog

  4. 创建 QuorumPeer 实例

    Quorum 是集群模式下特有的对象，是 ZooKeeper 服务器实例（ZooKeeperServer）的托管者，从集群层面看，QuorumPeer 代表了 ZooKeeper 集群中的一台机器。在运行期间，QuorumPeer 会不断检测当前服务器实例的运行状态，同时根据情况发起 Leader 选举。

  5. 创建内存数据库 ZKDatabase

    ZKDatabase 是 ZooKeeper 的内存数据库，负责管理 ZooKeeper 的所有会话记录以及 DataTree 和事务日志的存储。

  6. 初始化 QuorumPeer

    在步骤 5 中我们已经提到，QuorumPeer 是 ZooKeeperServer 的托管者，因此需要将一些核心组件注册到 QuorumPeer 中去，包括 FileTxnSnapLog、ServerCnxnFactory 和 ZKDatabase。同时 ZooKeeper 还会对 QuorumPeer 配置一些参数，包括服务器地址列表、Leader 选举算法和会话超时时间限制等。

  7. 恢复本地数据

  8. 启动 ServerCnxnFactory 主线程。

Leader选举

Leader选举的步骤如下。

  1. 初始化 Leader 选举

    Leader 选举可以说是集群和单机模式启动 ZooKeeper 最大的不同点。ZooKeeper 首先会根据自身的 SID（服务器ID）、lastLoggedZxid（最新的 ZXID）和当前的服务器 epoch（currentEpoch）来生成一个初始化的投票 —— 简单地讲在初始化过程中，每个服务器都会给自己投票。

    然后，ZooKeeper 会根据 zoo.cfg 中的配置，创建相应的 Leader 选举算法实现。在 ZooKeeper 中，默认提供了三种 Leader 选举算法的实现，分别是 LeaderElection、AuthFastLeaderElection 和 FastLeaderElection，可以通过在配置文件（zoo.cfg）中使用 electionAlg 属性来指定，分别使用数字 0~3 来表示。从 3.4.0 版本开始， ZooKeeper 废弃了前两种 Leader 选举算法，只支持 FastLeaderElection 选举算法了。

    在初始化阶段，ZooKeeper 会首先创建 Leader 选举所需的网络 I/O 层 QuorumCnxManager，同时启动对 Leader 选举端口的监听，等待集群中其他服务器创建连接。

  2. 注册 JMX 服务。

  3. 检测当前服务器状态。

    在上文中，我们已经提到 QuorumPeer 是 ZooKeeper 服务器实例的托管者，在运行期间，QuorumPeer 的核心工作就是不断地检测当前服务器的状态，并做出相应的处理。在正常情况下，ZooKeeper 服务器的状态在 LOOKING、LEADING 和 FOLLOWING/OBSERVING 之间进行切换。而在启动阶段，QuorumPeer 的初始状态是 LOOKING，因此开始进行 Leader 选举。

  4. Leader 选举

    ZooKeeper 的 Leader 选举过程，简单地讲，就是一个集群中所有的机器相互之间进行一系列投票，选举产生最合适的机器成为 Leader，同时其余机器成为 Follower 或是 Observer 的集群机器角色初始化过程。关于 Leader 选举算法，简而言之，就是集群中哪个机器处理的数据越新（通常我们根据每个服务器处理过的最大 ZXID 来比较确定其数据是否更新），其越有可能成为 Leader。当然，如果集群中的所有机器处理的 ZXID 一致的话，那么 SID 最大的服务器成为 Leader。

Leader和Follower启动期交互过程

到这里为止，ZooKeeper 已经完成了 Leader 选举，并且集群中每个服务器都已经确定了自己的角色 —— 通常情况下就分为 Leader 和 Follower 两种角色。Leader 和 Follower 在启动期间的大致交互流程如下图所示。

Leader 和 Follower 服务器启动期交互过程包括如下步骤。

  1. 创建 Leader 服务器和 Follower 服务器

    完成 Leader 选举之后，每个服务器都会根据自己的服务器角色创建相应的服务器实例，并开始进入各自角色的主流程。

  2. Leader 服务器启动 Follower 接收器 LearnerCnxAcceptor

    在 ZooKeeper 集群运行期间，Leader 服务器需要和所有其余的服务器（本书余下部分，我们使用“Learner”来指代这类机器）保持连接以确定集群的机器存活情况。LearnerCnxAcceptor 接收器用于负责接收所有非 Leader 服务器的连接请求。

  3. Learner 服务器开始和 Leader 建立连接
    所有的 Learner 服务器在启动完毕后，会从 Leader 选举的投票结果中找到当前集群中的 Leader 服务器，然后与其建立连接。

  4. Leader 服务器创建 LearnerHandler
    Leader 接收到来自其他机器的连接创建请求后，会创建一个 LearnerHandler 实例。每个 LearnerHandler 实例都对应了一个 Leader 与 Learner 服务器之间的连接，其负责 Leader 和 Learner 服务器之间几乎所有的消息通信和数据同步。

  5. 向 Leader 注册
    当和 Leader 建立起连接后，Learner 就会开始向 Leader 进行注册 —— 所谓的注册，其实就是将 Learner 服务器自己的基本信息发送给 Leader 服务器，我们称之为 LearnerInfo，包括当前服务器的 SID 和服务器处理的最新的 ZXID

  6. Leader 解析 Learner 信息，计算新的 epoch

    Leader 服务器在接收到 Learner 的基本信息后，会解析出该 Learner 的 SID 和 ZXID，然后根据该 Learner 的 ZXID 解析出其对应的 epoch_of_learner，和当前 Leader 服务器的 epoch_of_leader 进行比较，如果该 Learner 的 epoch_of_learner 更大的话，那么就更新 Leader 的 epoch

    epoch_of_leader = epoch_of_learner + 1;

    然后， LearnerHandler 会进行等待，直到过半的 Learner 已经向 Leader 进行了注册，同时更新了 poch_of_leader 之后，Leader 就可以确定当前集群的 epoch 了。

  7. 发送 Leader 状态

    计算出新的 epoch 之后，Leader 会将该信息以一个 LEADERINFO 消息的形式发送给 Learner，同时等待 Learner 的响应。

  8. Learner 发送 ACK 消息。

    Follower 在收到来自 Leader 的 LEADERINFO 消息后，会解析出 epoch 和 ZXID，然后向 Leader 反馈一个 ACKEPOCH 响应

  9. 数据同步

    Leader 服务器接收到 Learner 的这个 ACK 消息后，就可以开始与其进行数据同步了。关于 ZooKeeper 集群服务器间的数据同步。

  10. 启动 Leader 和 Learner 服务器

    当有过半的 Learner 已经完成了数据同步，那么 Leader 和 Learner 服务器实例就可以开始启动了。

Leader和Follower启动

Leader 和 Follower 启动的步骤如下：

  1. 创建并启动会话管理器。

  2. 初始化 ZooKeeper 的请求处理链。

    和单机版服务器一样，集群模式下，毎个服务器都会在启动阶段串联请求处理链，只是根据服务器角色不同，会有不同的请求处理链路。

  3. 注册 JMX 服务。

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选举的算法分析

在 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 选举算法。

术语解释

SID：服务器ID

SID 是一个数字，用来唯一标识一台 Zookeeper 集群中的机器，每台机器不能重复，和 myid 的值一致。

ZXID：事务ID

ZXID 是一个事务 ID，用来唯一标识一次服务器状态的变更。在某一个时刻，集群中每台机器的 ZXID 值不一定全都一致，这和 ZooKeeper 服务器对于客户端“更新请求”的处理逻辑有关。

Vote：投票

Leader 选举，顾名思义必须通过投票来实现。当集群中的机器发现自己无法检测到 Leader 机器的时候，就会开始尝试进行投票

Quorum：过半机器数

这是整个 Leader 选举算法中最重要的一个术语，我们可以把这个术语理解为是一个量词，指的是 ZooKeeper 集群中过半的机器数，如果集群中总的机器数是 n 的话，那么可以通过下面这个公式来计算 quorum 的值：quorum = (n/2 + 1)

算法分析

进入Leader选举

当 ZooKeeper 集群中的一台服务器出现以下两种情况之一时，就会开始进入 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，那么同样坚持自己的投票，不做变更。

根据上面这个规则，我们结合下图来分析上面提到的 5 台机器组成的 ZooKeeper 集群的投票变更过程。

确定Leader

经过这第二次投票后，集群中的每台机器都会再次收到其他机器的投票，然后开始统计投票。如果一台机器收到了超过半数的相同的投票，那么这个投票对应的 SID 机器即为 Leader。

上图 Leader 选举例子中，因为 ZooKeeper 集群的总机器数为 5 台，那么quorum = (5 / 2 + 1)= 3。也就是说，只要收到 3 个或 3 个以上（含当前服务器自身在内）一致的投票即可。在这里，Server3、Server4 和 Server5 都投票（3,9），因此确定了 Server3 为 Leader。

Leader选举的细节

服务器状态

为了能够清楚地对 ZooKeeper 集群中每台机器的状态进行标识，在org.apache.zookeeper.server.quorum.QuorumPeer.ServerState类中列举了 4 种服务器状态，分别是：LOOKINO、FOLLOWING、LEADING 和 OBSERVING。

  • LOOKING：寻找 Leader 状态。当服务器处于该状态时，它会认为当前集群中没有 Leader，因此需要进入 Leader 选举流程。
  • FOLLOWING：跟随者状态，表明当前服务器角色是 Follower。
  • LEADING：领导者状态，表明当前服务器角色是 Leader。
  • OBSERVING：观察者状态，表明当前服务器角色是 Observer。

投票数据结构

以下是 Vote 数据结构图

以下是字段解释

QuorumCnxManager：网络l/O

我们曾讲解过，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）。开启端口监听后，ZooKeeper 就能够不断地接收到来自其他服务器的“创建连接”请求，在接收到其他服务器的 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：选举算法的核心部分

概念

  • 外部投票：特指其他服务器发来的投票
  • 内部投票：服务器自身当前的投票
  • 选举轮次：ZooKeeper 服务器 Leader 选举的轮次，即 Logicalclock
  • PK：指对内部投票和外部投票进行一个对比来确定是否需要变更内部投票

选票管理

现在我们来看对于选票的管理。下图所示是选票管理过程中相关组件之间的协作关系。

  • sendqueue：选票发送队列，用于保存待发送的选票。

  • recvqueue：选票接收队列，用于保存接收到的外部投票。

  • WorkerReceiver：选票接收器。该接收器会不断地从 QuorumCnxManager 中获取出其他服务器发来的选举消息，并将其转换成一个选票，然后保存到 requeue 队列中去。在选票的接收过程中，如果发现该外部投票的选举轮次小于当前服务器，那么就直接忽略这个外部投票，同时立即发出自己的内部投票。当然，如果当前服务器并不是 LOOKING 状态，即已经选举出了 Leader，那么也将忽略这个外部投票，同时将 Leader 信息以投票的形式发送出去。

    另外，对于选票接收器，还有一个细节需要注意，如果接收到的消息来自 Observer 服务器，那么就忽略该消息，并将自己当前的投票发送出去。

  • WorkerSender：选票发送器，会不断地从 sendqueue 队列中获取待发送的选票，并将其传递到底层 QuorumCnxManager 中去。

算法核心

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

  1. 自增选举轮次

    在 FastLeaderElection 实现中，有一个 logicalclock 属性，用于标识当前 Leader 的选举轮次， ZooKeeper 规定了所有有效的投票都必须在同一轮次中。ZooKeeper 在开始新一轮的投票时，会首先对 logicalclock 进行自增操作。

  2. 初始化选票
    在开始进行新一轮的投票之前，每个服务器都会首先初始化自己的选票 Vote 结构，在初始化阶段，每台服务器都会将自己推举为 Leader。

  3. 发送初始化选票
    在完成选票的初始化后，服务器就会发起第一次投票。ZooKeeper 会将刚刚初始化好的选票放入 sendqueue 队列中，由发送器 WorkerSender 负责发送出去。

  4. 接收外部投票
    每台服务器都会不断地从 recvqueue 队列中获取外部投票。如果服务器发现无法获取到任何的外部投票，那么就会立即确认自己是否和集群中其他服务器保持着有效连接。如果发现没有建立连接，那么就会马上建立连接。如果已经建立了连接，那么就再次发送自己当前的内部投票。

  5. 判断选举轮次
    当发送完初始化选票之后，接下来就要开始处理外部投票了。在处理外部投票的时候，会根据选举轮次来进行不同的处理。

    • 外部投票的选举轮次大于内部投票。

      如果服务器发现自己的选举轮次已经落后于该外部投票对应服务器的选举轮次，那么就会立即更新自己的选举轮次（logicalclock），并且清空所有已经收到的投票，然后使用初始化的投票来进行 PK 以确定是否变更内部投票，最终再将内部投票发送出去。

    • 外部投票的选举轮次小于内部投票。

      如果接收到的选票的选举轮次落后于服务器自身的，那么 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,votel)，(2,vote2)，…}。

  9. 统计投票
    完成了选票归档之后，就可以开始统计投票了。统计投票的过程就是为了统计集群中是否已经有过半的服务器认可了当前的内部投票。如果确定已经有过半的服务器认可了该内部投票，则终止投票。否则返回步骤 4。

  10. 更新服务器状态。
    统计投票后，如果已经确定可以终止投票，那么就开始更新服务器状态。服务器会首先判断当前被过半服务器认可的投票所对应的 Leader 服务器是否是自己，如果是自己的话，那么就会将自己的服务器状态更新为 LEADING。如果自己不是被选举产生的 Leader 的话，那么就会根据具体情况来确定自己是 FOLLOWING 或是 OBSERVING。

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