【ZooKeeper】Leader 选举

今天药忘吃喽~ 2022-10-21 14:55 165阅读 0赞

# 1 Leader 选举概述 #

Leader 选举是 ZooKeeper 中最重要的技术之一，也是保证分布式数据一致性的关键所在。 在本节中，我们将先从整体上来对 ZooKeeper 的 Leader 选举进行介绍。

## 服务器启动时期的 Leader 选举 ##

在我们讲解 Leader 选举的时候，需要注意的一点是，隐式条件便是 ZooKeeper 的集群规 模至少是2 台机器，这里我们以 3 台机器组成的服务器集群为例。在服务器集群初始化 阶段，当有一台服务器（我们假设这台机器的 myid 为 1, 因此称其为 Server 1）启动的 时候，它是无法完成 Leader 选举的，是无法进行 Leader 选举的。当第二台机器（同样， 我们假设这台服务器的 myid 为 2, 称其为 Server2） 也启动后，此时这两台机器已经能 够进行互相通信，每台机器都试图找到一个 Leader,于是便进入了 Leader 选举流程。

1.  每个 Server 会发出一个投票。  
    由于是初始情况，因此对于 Server 1 和 Server2 来说，都会将自己作为 Leader 服务 器来进行投票，每次投票包含的最基本的元素包括：所推举的服务器的 myid 和 ZXID, 我们以（myid, ZXID） 的形式来表示。因为是初始化阶段，因此无论是 Server 1 还是 Server2, 都会投给自己，即 Server 1 的投票为 （1, 0）, Server2 的投票为 （2, 0）, 然后各自将这个投票发给集群中其他所有机器。
2.  接收来自各个服务器的投票。  
    每个服务器都会接收来自其他服务器的投票。集群中的每个服务器在接收到投票 后，首先会判断该投票的有效性，包括检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
3.  处理投票。  
    在接收到来自其他服务器的投票后，针对每一个投票，服务器都需要将别人的投 票和自己的投票进行 PK, PK 的规则如下。
    
     *  优先检查 ZXID 。 ZXID 比较大的服务器优先作为 Leader 。
     *  如果 ZXID 相同的话，那么就比较 myid 。 myid 比较大的服务器作为 Leader 服务器。
    
    现在我们来看 Server! 和 Server2 实际是如何进行投票处理的。对于 Server 1 来说， 它自己的投票是 （1, 0）, 而接收到的投票为 （2, 0） 。首先会对比两者的 ZXID, 因为都是 0, 所以无法决定谁是 Leader 。接下来会对比两者的 myid, 很显然 ,Serverl 发现接收到的投票中的 myid 是 2, 大于自己，于是就会更新自己的投票为 （2,0）, 然后重新将投票发出去。而对于 Server2 来说，不需要更新自己的投票信息，只是 再一次向集群中所有机器发出上一次投票信息即可。
4.  统计投票。  
    每次投票后，服务器都会统计所有投票，判断是否已经有过半的机器接收到相同 的投票信息。对于 Server 1 和 Server2 服务器来说，都统计出集群中已经有两台机 器接受了 （2, 0） 这个投票信息。这里我们需要对“过半”的概念做一个简单的 介绍。所谓“过半”就是指大于集群机器数量的一半，即大于或等于 （n/2+1） 。 对于这里由 3 台机器构成的集群，大于等于 2 台即为达到“过半”要求。
    
    那么，当 Server 1 和 Server2 都收到相同的投票信息 （2, 0） 的时候，即认为已经 选出了Leader 。
5.  改变服务器状态。  
    一旦确定了 Leader, 每个服务器就会更新自己的状态：如果是 Follower, 那么就 变更为FOLLOWING, 如果是 Leader, 那么就变更为 LEADING 。

## 服务器运行期间的 Leader 选举 ##

在 ZooKeeper 集群正常运行过程中，一旦选出一个 Leader, 那么所有服务器的集群角色 一般不会再发生变化——也就是说， Leader 服务器将一直作为集群的 Leader, 即使集群 中有非 Leader 集群挂了或是有新机器加入集群也不会影响 Leader 。但是一旦 Leader 所 在的机器挂了，那么整个集群将暂时无法对外服务，而是进入新一轮的 Leader 选举。服 务器运行期间的 Leader 选举和启动时期的 Leader 选举基本过程是一致的。

我们假设当前正在运行的 ZooKeeper 服务器由 3 台机器组成，分别是 Server 1, Server! 和 Server3,当前的 Leader 是 Server2 。假设在某一个瞬间， Leader 挂了，这个时候便开 始了 Leader 选举。

1.  变更状态。  
    当 Leader 挂了之后，余下的非 Observer 服务器都会将自己的服务器状态变更为 LOOKING,然后开始进入 Leader 选举流程。
2.  每个 Server 会发出一个投票。  
    在这个过程中，需要生成投票信息 （myid, ZXID） O 因为是运行期间，因此每个 服务器上的 ZXID 可能不同，我们假定 Server 1 的 ZXID 为 123, 而 Server3 的 ZX1D 为 122 。在第一轮投票中， Server! 和 Server3 都会投自己，即分别产生投票 （1, 123） 和 （3, 122）, 然后各自将这个投票发给集群中所有机器。
3.  接收来自各个服务器的投票。
4.  处理投票。  
    对于投票的处理，和上面提到的服务器启动期间的处理规则是一致的。在这个例 子里面，由于 Server1 的 ZXID 为 123, Server3 的 ZXID 为 122, 那么显然， Server 1 会成为 Leader。
5.  统计投票。
6.  改变服务器状态。

# 2 Leader 选举的算法分析 #

我们已经大体了解了 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 选举算法介绍中会出现的一些专有术语进行简单介绍， 以便读者更好地理解本书内容。  
**SID ： 服务器 ID**  
SID 是一个数字，用来唯一标识一台 ZooKeeper 集群中的机器，每台机器不能重复，和 myid 的值一致。

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

**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 、8、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 O
 *  self\_zxid : : 当前服务器自己的 ZXID 。

每次对于收到的投票的处理，都是一个对 （vote sid, vote zxid） 和 （self^sid, seljzxid） 对比的过程。

*  规则 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 集 群的投票变更过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]

每台机器都把投票发出后，同时也会接收到来自另外两台机器的投票。

*  对于 Server1 来说，它接收到了 （4, 8） 和 （5, 8） 两个投票，对比后，由于自己 的 ZXID 要大于接收到的两个投票，因此不需要做任何变更。
 *  对于 Server4 来说，它接收到了 （3, 9） 和 （5, 8） 两个投票，对比后，由于 （3, 9） 这个投票的 ZXID 大于自己，因此需要变更投票为 （3, 9）, 然后继续将这个 投票发送给另外两台机器。
 *  同样，对于 Servers 来说，它接收到了 （3, 9） 和 （4, 8） 两个投票，对比后，由 于 （3, 9）这个投票的 ZXID 大于自己，因此需要变更投票为 （3, 9）, 然后继续 将这个投票发送给另外两台机器。

### 确定 Leader ###

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

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

### 小结 ###

简单地说，通常哪台服务器上的数据越新，那么越有可能成为 Leader, 原因很简单，数 据越新，那么它的 ZXID 也就越大，也就越能够保证数据的恢复。当然，如果集群中有 几个服务器具有相同的 ZXID, 那么 SID 较大的那台服务器成为 Leader 。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221021/8dcec0fd0bf4417a862161ceac6f4b2e.png