zookeeper(三):选举算法

2024-03-09 17:59
文章标签 算法 zookeeper 选举

本文主要是介绍zookeeper(三):选举算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

脑裂

网络分区(脑裂): 群集发生管理网络故障时,该群集中的部分主机可能无法通过管理网络与其他主机进行通信。一个群集中可能会出现多个分区。已分区的群集会导致虚拟机保护和群集管理功能降级。请尽快更正已分区的群集。通俗来讲就是一个黑帮中出现了两个老大,所谓一山不容二虎,就造成了领导混乱。
我们拿ZooKeeper集群来讲一下脑裂是如何产生的。
首先,我们有一个集群,集群里只有一个leader

在这里插入图片描述
但是此时由于网络波动,使得一部分服务器脱离了集群,形成了一个小的集群,此时群龙无首,他们就会选举出一个新的leader.
在这里插入图片描述

解决脑裂:集群要防止出现Split-Brain(脑裂)的问题出现,Quoroms(法定人数)是一种方式,即只有集群中超过半数节点投票才能选举出Leader。这样的方式可以确保leader的唯一性,要么选出唯一的一个leader,要么选举失败.ZooKeeper默认采用了这种方式。

领导者选举算法底层数据流程图
在这里插入图片描述

Leader选举

Leader选举是保证分布式数据一致性的关键所在。当Zookeeper集群中的一台服务器出现
以下两种情况之一时,需要进入Leader选举。1.服务器初始化启动。2.Leader 挂掉

服务器启动时期的Leader选举

若进行Leader选举,则至少需要两台机器,这里选取3台机器组成的服务器集群为例。在
集群初始化阶段,当 有一台服务器Serverl启动时,其单独无法进行和完成Leader选
举,当第二台服务器Server2启动时,此时两台 机器可以相互通信,每台机器都试图找到
Leader,于是进入Leader选举过程。选举过程如下:
1.每个Server发出一个投票。由于是初始情况,Serverl和Server2都会将自己作为
Leader服务器来进行投 票,每次投票会包含所推举的服务器的myid和ZXID,使用
(myid, ZXID)来表示,此时Serverl的投票为 (1,0), Server2的投票为(2, 0),然后
各自将这个投票发给集群中其他机器。
2.接受来自各个服务器的投票。集群的每个服务器收到投票后,首先判断该投票的有效
性,如检查是否是 本轮投票(检查ZXID)、是否来自L。OKING状态的服务器。
3.处理投票。针对每一个投票,服务器都需要将别人的投票和自己的投票进行PK, PK规则
如下:(1).优先检查ZXID。ZXID比较大的服务器优先作为Leader。(2).如果ZXID相同,那么就比较myid。myid较大的服务器作为Leader服务器。(3).对于Server 1而言,它的投票是(1,0),接收Server2的投票为(2, 0),首先会比较两者的ZXID,均 0,再比较myid,此时Server2的myid最大,于是更新自己的投票为(2, 0),然后重新投票,对 于S erver 2而言,其无须更新自己的投票,只是再次向集群中所有机器发出上一次投票信息即 可。
4.统计投票。每次投票后,服务器都会统计投票信息,判断是否已经有过半机器接受到相
同的投票信息, 对于Server, Server2而言,都统计出集群中已经有两台机器接受了(2, 
0)的投票信息,此时便认为已 经选出了 Leader。
5.改变服务器状态。一旦确定了 Leader,每个服务器就会更新自己的状态,如果是
Follower,那么就变更  FOLLOWING,如果是 Leader,就变更为 LEADING。

服务器运行时期的Leader选举

在Zookeeper运行期间,Leader与非Leader服务器各司其职,即便当有非Leader服务器宕机或新加入,此时也 不会影响Leader,但是一旦Leader服务器挂了,那么整个集群将暂停对外服务,或者Follower挂掉了导致,进 入新一轮Leader选举,其过程和启动时期的Leader选举过程基本一致。假设正在运行的有Server1、Server2、 Server3三台服务器,当前Leader是Server2,若某一时亥0Leader挂了,此时便开始Leader选举。选举过程如下:
1.变更状态。Leader挂后,余下的服务器都会讲自己的服务器状态变更为LOOKING,然后
开始进入 Leader选举过程,这个时候可以开启只读模式让服务器可以读数据。
2.每个Server会发出一个投票。在运行期间,每个服务器上的ZXID可能不同,此时假定
Serverl的ZXID为 123, Server3的ZXID为122;在第一轮投票中,Serverl和Server3
都会投自己,产生投票(1, 123), (3, 122),然后各自将投票发送给集群中所有机器。
3.接收来自各个服务器的投票。与启动时过程相同。
4.处理投票。与启动时过程相同,此时,Server 1将会成为Leader(只是投票为Leader
阶段,真正修改为
Leader状态在第六步)
5.统计投票。与启动时过程相同。
6.改变服务器的状态。与启动时过程相同。

Leader选举算法分析

3.4.0后的Zoo keeper的版本只保留了 TCP版本的FastLeaderElection选举算法。当一台机器进入Leader选举时,当前集群可能会处于以下两种状态。•集群中已经存在Leader。•集群中不存在Leader。
对于集群中已经存在Leader而言,此种情况一般都是某台机器启动得较晚,在其启动之前,集群已经在正常工 作,对这种情况,该机器试图去选举Leader时,会被告知当前服务器的Leader信息,对于该机器而言,仅仅需 要和Leader机器建立起连接,并进行状态同步即可。
而在集群中不存在Leader情况下则会相对复杂,其步骤如下:
1.第一次投票。无论哪种导致进行Leader选举,集群的所有机器都处于试图选举出一个Leader的状态,即LOOKING状态,LOOKING机器会向所有其他机器发送消息,该消息称为投票。投票中包含了SID ( 务器的唯一标识,MYID )和ZXID (事务ID), (SID, ZXID)形式来标识一次投票信息。假定Zookeeper 5台机器组成,SID分别为12345, ZXID分别为99988(为什么会出现不同?),并且 此时SID为2的机器是Leader机器,某一时刻,12所在机器出现故障,因此集群开始进行Leader选 举。在第一次投票时,每台机器都会将自己作为投票对象,于是SID为345的机器投票情况分别为 (3, 9), (4, 8), (5, 8)
2.变更投票。每台机器发出投票后,也会收到其他机器的投票,每台机器会根据一定规则来处理收到的其 他机器的投票,并以此来决定是否需要变更自己的投票,这个规则也是整个Leader选举算法的核心所 在,其中术语描述如下:(1).vote_sid:接收到的投票中所推举Leader服务器的SID。(2).vote_zxid :接收到的投票中所推举Leader服务器的ZXID。(3).self_sid :当前服务器自己的SID。(4).self_zxid:当前服务器自己的ZXID。(5).每次对收到的投票的处理,都是对(v ote_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,那么坚持自己的投票,不做任 何变更。
3.确定L eader。经过第二轮投票后,集群中的每台机器都会再次接收到其他机器的投
票,然后开始统计 投票,如果一台机器收到了超过半数的相同投票,那么这个投票对应的
SID机器即为Leader。此时 Server3 将成为 Leader。由上面规则可知,通常那台服务器上的数据越新(ZXID会越大),其成为Leader的可能性越
大,也就越能够保 证数据的恢复。如果ZXID相同,则SID越大机会越大。

在这里插入图片描述

Leader选举实现细节

服务器状态

服务器具有四种状态,分别是L。OKING、FOLLOWING、LEADING、OBSERVING。
・LOOKING:寻找Leader状态。当服务器处于该状态时,它会认为当前集群中没有
Leader,因此需要进入L eader选举状态。
・FOLLOWING:跟随者状态。表明当前服务器角色是Follower。
・LEADING:领导者状态。表明当前服务器角色是Leader。
・OBSERVING :观察者状态。表明当前服务器角色是Observer。

投票数据结构

投票数据结构 每个投票中包含了两个最基本的信息,所推举服务器的SID和ZXID,投票(Vote)在Zookeeper中包含字段如 下:
・id:被推举的Leader的SID。
・zxid :被推举的Leader事务ID。
•electionEpoch :逻辑时钟,用来判断多个投票是否在同一轮选举周期中,该值在服务
端是一个自 增序列,每次进入新一轮的投票后,都会对该值进行加1操作。
•peerEpoch :被推举的 Leader  epoch。
・state:当前服务器的状态。

QuorumCnxManager

每台服务器在启动的过程中,会启动一个QuorumPeerManager,负责各台服务器之间的底层Leader选举过程 中的网络通信,对应的类就是QuorumCnxManager。
1.	消息队列。QuorumCnxManager内部维护了一系列的队列,用来保存接收到的、待发送的消息以及消 息的发送器,除接收队列以外,其他队列都按照SID分组形成队列集合,如一个集群中除了自身还有3 台机器,那么就会为这3台机器分别创建一个发送队列,互不干扰。1.recvQueue:消息接收队列,用于存放那些从其他服务器接收到的消息。2.queueSendMap:消息发送队列,用于保存那些待发送的消息,按照SID进行分组。3.senderWorkerMap :发送器集合,每个SenderWorker消息发送器,都对应一台远程Zookeeper 服务器,负责消息的发送,也按照SID进行分组。4.lastMessageSent :最近发送过的消息,为每个SID保留最近发送过的一个消息。
2.建立连接。为了能够相互投票,Zookeeper集群中的所有机器都需要两两建立起网络连
接。QuorumCnxManager在启动时会创建一个ServerSocket来监听Leader选举的通信端口(默认为3888)。开 启监听后,Zookeeper能够不断地接收到来自其他服务器的创建连接请求,在接收到其他服务器的TCP 连接请求时,会进行处理。为了避免两台机器之间重复地创建TCP连接,Zookeeper只允许SID大的服 务器主动和其他机器建立连接,否则断开连接。在接收到创建连接请求后,服务器通过对比自己和远程 服务器的SID值来判断是否接收连接请求,如果当前服务器发现自己的SID更大,那么会断开当前连 接,然后自己主动和远程服务器建立连接(自己作为“客户端”)。一旦连接建立,就会根据远程服务器 的SID来创建相应的消息发送器SendWorker和消息接收器RecvWorker,并启动。
3.消息接收与发送1.消息接收:由消息接收器RecvWorker负责,由于Zookeeper为每个远程服务器都分配一个单独 的RecvWorker,因此,每个RecvWorker只需要不断地从这个TCP连接中读取消息,并将其保存 至OrecvQueue队列中。RecvWorker是一个单独的线程。2.消息发送:由于Zookeeper为每个远程服务器都分配一个单独的S endWorker,因此,每个SendWorker只需要不断地从对应的消息发送队列中获取出一个消息发送即可,同时将这个消息 放入lastMessageSent中。在SendWorker中,一旦Zookeeper发现针对当前服务器的消息发送队 列为空,那么此时需要从lastMessageSent中取出一个最近发送过的消息来进行再次发送,这是 为了解决接收方在消息接收前或者接收到消息后服务器挂了,导致消息尚未被正确处理。同 时,Zookeeper能够保证接收方在处理消息时,会对重复消息进行正确的处理。SendWorker是 —个单独的线程。

FastLeaderElection:选举算法核心

-外部投票:特指其他服务器发来的投票。
・内部投票:服务器自身当前的投票。
•选举轮次:Zookeeper服务器Leader选举的轮次,即logicalclock。
-PK:对内部投票和外部投票进行对比来确定是否需要变更内部投票。

选票管理

・sendqueue:选票发送队列,用于保存待发送的选票。
・recvqueue:选票接收队列,用于保存接收到的外部投票。
 WorkerReceiver :选票接收器。其会不断地从QuorumCnxManager中获取其他服务器发来的选举
消息,并将其转换成一个选票,然后保存到recvqueue中,在选票接收过程中,如果发现该外部 选票的选举轮次小于当前服务器的,那么忽略该外部投票,同时立即发送自己的内部投票。
・WorkerSender:选票发送器,不断地从sendqueue中获取待发送的选票,并将其传递到底层
QuorumCnxManager 中。

算法核心
在这里插入图片描述

上图展示了FastLeader曰ection模块是如何与底层网络I/O进行交互的。Leader选举的基本流程如下:
1.自增选举轮次。Zookeeper规定所有有效的投票都必须在同一轮次中,在开始新一轮投票时,会首先对 logicalclock进行自增操作。
2.初始化选票。在开始进行新一轮投票之前,每个服务器都会初始化自身的选票,并且在初始化阶段,每 台服务器都会将自己推举为Leader。
3.发送初始化选票。完成选票的初始化后,服务器就会发起第一次投票。Zookeeper会将刚刚初始化好的 选票放入sendqueue中,由发送器WorkerSender负责发送出去。
4.接收外部投票。每台服务器会不断地从recvqueue队列中获取外部选票。如果服务器发现无法获取到任 何外部投票,那么就会立即确认自己是否和集群中其他服务器保持着有效的连接,如果没有连接,则马 上建立连接,如果已经建立了连接,则再次发送自己当前的内部投票。
5.判断选举轮次。在发送完初始化选票之后,接着开始处理外部投票。在处理外部投票时,会根据选举轮 次来进行不同的处理。1.外部投票的选举轮次大于内部投票。若服务器自身的选举轮次落后于该外部投票对应服务器的 选举轮次,那么就会立即更新自己的选举轮次(logicalclock),并且清空所有已经收到的投票,然 后使用初始化的投票来进行PK以确定是否变更内部投票。最终再将内部投票发送出去。2.外部投票的选举轮次小于内部投票.若服务器接收的外选票的选举轮次落后于自身的选举轮次,那么Zookeeper就会直接忽略该外部投票,不做任何处理,并返回步骤43.外部投票的选举轮次等于内部投票。此时可以开始进行选票PK。
6.选票PK。在进行选票PK时,符合任意一个条件就需要变更投票。1.若外部投票中推举的Leader服务器的选举轮次大于内部投票,那么需要变更投票。2.若选举轮次一致,那么就对比两者的ZXID,若外部投票的ZXID大,那么需要变更投票。3.若两者的ZXID一致,那么就对比两者的SID,若外部投票的SID大,那么就需要变更投票。
7.变更投票。经过PK后,若确定了外部投票优于内部投票,那么就变更投票,即使用外部
投票的选票信息来覆盖内部投票,变更完成后,再次将这个变更后的内部投票发送出去。
8.选票归档。无论是否变更了投票,都会将刚刚收到的那份外部投票放入选票集合
recvset中进行归档。 recvset用于记录当前服务器在本轮次的Leader选举中收到的所
有外部投票(按照服务端的SID区别,如 ((1, votel), (2, vote2)...})
9.统计投票。完成选票归档后,就可以开始统计投票,统计投票是为了统计集群中是否已
经有过半的服务 器认可了当前的内部投票,如果确定已经有过半服务器认可了该投票,则
终止投票。否则返回步骤4
10.更新服务器状态。若已经确定可以终止投票,那么就开始更新服务器状态,服务器首选
判断当前被过半 服务器认可的投票所对应的Leader服务器是否是自己,若是自己,则将
自己的服务器状态更新为 LEADING,若不是,则根据具体情况来确定自己是FOLLOWING或
是OBSERVING。
以上10个步骤就是FastLeaderElection的核心,其中步骤4-9会经过几轮循环,直到有Leader选举产生。

这篇关于zookeeper(三):选举算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/791493

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种,单机模式和集群模式以及伪集群模式。 ■ 单机模式:Zookeeper只运行在一台服务器上,适合测试环境; ■ 伪集群模式:就是在一台物理机上运行多个Zookeeper 实例; ■ 集群模式:Zookeeper运行于一个集群上,适合生产环境,这个计算机集群被称为一个“集合体”(ensemble) Zookeeper通过复制来实现

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

搭建Kafka+zookeeper集群调度

前言 硬件环境 172.18.0.5        kafkazk1        Kafka+zookeeper                Kafka Broker集群 172.18.0.6        kafkazk2        Kafka+zookeeper                Kafka Broker集群 172.18.0.7        kafkazk3

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int