【ZooKeeper】Leader 选举 今天药忘吃喽~ 2022-10-21 14:55 172阅读 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
还没有评论,来说两句吧...