分布式之Raft共识算法分析

news/2024/3/29 8:41:21/文章来源:https://blog.csdn.net/wang0907/article/details/129087518

写在前面

在分布式之Paxos共识算法分析 一文中我们分析了paxos算法,知道了其包括basic paxos和multi paxos,并了解了multi paxos只是一种分布式共识算法的思想,而非具体算法,但可根据其设计具体的算法,本文就一起来看下其一种具体的实现算法raft,这也是当前中心化架构分布式系统使用最多的一种分布式共识算法了,下面我们就一起看下吧!

1:raft提供了哪些内容

在multi paxos的描述中有一个霸道总裁的角色leader,因此在raft中就定义了leader的选举策略。除此之外还定义了日志复制策略,成员变更。接下来我们分别看下这三部分内容。

2:leader选举

首先我们先来看下raft中节点的角色,包括领导者,跟随者(非leader大部分时间所处的状态),候选者(竞选leader时所处的状态),另外每个节点还有一个任期编号的属性,代表当前集群的leader是第几任leader(可用于处理多leader场景,以及leader选举投票确定是否投票),任期编号默认为0,如下图:

在这里插入图片描述

在系统初始状态,所有节点所处的状态都是跟随者,并且每个节点都有leader心跳消息的超时时间,该超时时间是随机的,避免多节点同时到期并竞选leader,导致无法快速选举leader的问题。如下节点A,节点B,节点C,超时时间分别是150ms,200ms,300ms:

在这里插入图片描述

很明显,节点A会先超时,转换角色为候选人并将自己的任期编号+1变为1(其认为主节点故障,需要产生新的leader,因此任期编号+1),先向自己投1票,并向其他节点发送申请成为leader消息,如下图:

在这里插入图片描述

其他节点发现自己的任期都小于1,并且自己在term=1都还没有投过票(一个任期只能投一票,即某任期一旦投过票,在收到相同任期申请成为leader的请求则忽略或投拒绝票),因此会投出自己唯一的一票,如下:

在这里插入图片描述

之后节点A获取了3票赞成票,超过了3个节点的半数,因此成为leader,如下:

在这里插入图片描述

接着leader就会周期性的给其他节点发送心跳消息,防止其他节点的leader心跳超时时间到时,并篡权,如下图:

在这里插入图片描述

以上过程源码参考这里 ,运行过程如下图:

在这里插入图片描述

补充下其他的规则:

1:领导者周期性地向所有跟随者发送心跳消息(即不包含日志项的日志复制 RPC 消息),通知大家我是领导者,阻止跟随者发起新的选举。
2:如果在指定时间内,跟随者没有接收到来自领导者的消息,那么它就认为当前没有领导者,推举自己为候选人,发起领导者选举。
3:在一次选举中,赢得大多数选票的候选人,将晋升为领导者。
4:在一个任期内,领导者一直都会是领导者,直到它自身出现问题(比如宕机),或者因为网络延迟,其他节点发起一轮新的选举。
5:在一次选举中,每一个服务器节点最多会对一个任期编号投出一张选票,并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3,先收到了 1 个包含任期编号为 4 的投票请求(来自节点 A),然后又收到了 1 个包含任期编号为 4 的投票请求(来自节点 B)。那么节点 C 将会把唯一一张选票投给节点 A,当再收到节点 B 的投票请求 RPC 消息时,对于编号为 4 的任期,已没有选票可投了。
6:日志完整性高的跟随者(也就是最后一条日志项对应的任期编号值更大,索引号更大),拒绝投票给日志完整性低的候选人。比如节点 B 的任期编号为 3,节点 C 的任期编号是 4,节点 B 的最后一条日志项对应的任期编号为 3,而节点 C 为 2,那么当节点 C 请求节点 B 投票给自己时,节点 B 将拒绝投票。

2.1:常见问题

2.1.1:如何知道选票超过半数

总节点数是固定的,已知的,进行简单数学运算即可。

2.1.2:raft存在的问题

leader的单点问题,以及由此带来的写数据性能瓶颈问题。节点较多时,leader的心跳消息有较高的通信成本。节点较多时,选主获得半数投票时间长,集群不可用时间长。

2.1.3:所有节点都可能成为leader吗?

不是的,必须当前节点的日志完整性高于超过半数的节点(这样才可能获得半数以上选票),但这里并不带代表这些节点不能成为candidate并发起选举,只是说就算发起选举了,最终也会选举失败而已。

2.1.4:leader会一直是leader吗?

如果是机器和网络一直正常的话,是的,但是实际环境并不会,根据chubby团队观察,一个leader的任期大概是在几天左右。

2.1.5:如果集群重启,集群状态如任期编号会清0吗?

不会的,这些信息是持久化存储的,重启后,需要将集群恢复到重启前的状态。

2.1.6:如果某轮leader选举失败,下一轮选举任期编号会+1吗?

会的,因为一个任期一个节点只有一张选票,如果不+1的话,将无法在新一轮投出选票。

2.1.7:如果一个节点孤立,导致leader选举一直失败,任期编号不断增大,则当其回到集群会影响集群吗?

不会,因为当其回到集群后,别的节点发现自己的任期编号小于其任期编号,则会更新自己的任期编号为其任期编号,并且因为自己的日志完整性高于其,所以也不会给其投出选票,其也成不了leader,所以,不会有影响。

2.1.8:心跳随机超时时间怎么确定,如何查看?

这就是属于编码实现问题了,一般设置在某个时间范围内,至于如何查看也是和具体程序实现有关。

2.1.9:raft算法中只有leader才能接收读请求吗?

raft算法本身没有要求,如果是要求最终一致性,则可以允许非leader读取,比如zookeeper就是如此,直接响应本地数据。

2.1.10:如果集群正在选主此时集群还能正常工作吗?

写请求无法执行,需要客户端重试。读请求如果是允许非leader处理的话,则正常,否则也需要重试,等到选主完成。

2.1.11:因为leader心跳超时,导致选举出新leader,当老leader收到新leader心跳时会如何处理?

更新自己的状态为跟随者,并使用新leader的任期编号更新自己的任期编号。

3:日志复制

可以认为为日志即数据,日志由日志项组成,且日志必须是连续的,这不同于multi-paxos。一个日志项包含如下3部分内容:

指令:用户发送的指令,如set x 10这种
任期编号:创建该条日志项leader的任期编号,相当于是给数据标识版本
索引值:单调递增的索引编号,用来标识日志项

如下图:

在这里插入图片描述

日志同步过程如下:

1:leader生成日志条目,发送日志同步RPC消息复制日志条目到其他节点
2:当超过半数的节点返回复制成功消息后,将日志项应用到状态机(通过状态机记录日志项已经写入成功),然后返回成功消息给客户端

这里需要注意,leader在收到了大多数节点写入成功消息后,并不会再次发送提交日志条目消息到其他节点,也就是两阶段提交变为了一阶段提交,这里提交的消息并不是不发了,而只是会随着后续的同步日志消息,或者是leader的心跳消息,来同步给其他节点,这样就可以减少一半的网络交互开销,可通过下图对比查看:

在这里插入图片描述

假设节点A,节点B,节点C,节点D,其中节点A为leader,任期编号为9,索引编号是88,发送的指令是set x=90,即要发送的日志段是(88,9,set x=90),则该过程如下图:

在这里插入图片描述

源码实现参考这里 ,运行效果如下图:

在这里插入图片描述

3.1:如何实现日志一致性

如果节点一直处于正常状态,节点能够正常的复制来自leader的日志段,但是如果是发生了宕机,重启等故障后follower出现了和leader的日志不一致,这种情况raft算法是怎么实现恢复一致的呢?我们一起来看下。首先看以下的点:

1:数据绝对以leader的为准
2:leader可以覆盖和删除follower不一致的数据
3:leader的数据不会被覆盖和删除

为了处理可能出现的日志一致性问题,leader在发送日志同步消息时,除了携带日志段外,还会携带当前日志段的上一个日志段的索引号以及对应的任期编号,如下要发送的索引号就是7,任期编号就是4:

在这里插入图片描述

当follower收到后会对比自己的最新的日志段是否匹配二者,如果匹配的话则接受日志段,否则返回失败,返回失败后leader继续向前找,继续发送,直到follower接受,则从接收的位置发送后续日志段,覆盖follower的日志段,从而使得和leader的日志保持一致,可参考下图:

在这里插入图片描述

3.2:常见问题

3.2.1:如果超过半数follower都收到日志段但是leader还未应用状态到状态机,此时leader挂掉,数据会丢失吗?

不会,因为最终当选为新leader的node是有该未提交日志段的,然后发现超过半数的node都有该日志段(老leader肯定是有的,所以这里的半数要包括老leader),则会提交日志段,并在后续发送消息给其它follower也提交该日志段。

3.2.2:如何保证客户端写操作请求到leader?

一般有两种方式(假定收到请求的节点是follower),1:follower充当代理角色,转发请求给leader 2:follower返回leader地址给客户端,客户端再次向leader发起写请求。

4:成员变更

成员变更是指通过新增节点来增加副本数,成员变更的一个问题就是集群短时间内处于不稳定状态,而可能会导致出现2个leader的情况,这就违背了leader唯一性的原则,而导致出现这个问题的原因一般都是网络分区,如下是有3个节点的集群:

在这里插入图片描述

此时集群配置是[A,B,C],现在加入2个节点D,E,如下图:

在这里插入图片描述

假定集群稳定前的某一刻发生了网络分区,AB处于一个分区,CDE处于一个分区,如下图:

在这里插入图片描述

此时新配置是[A,B,C,D,E],则新配置的大多数就是3,如上图就产生了新leader C,而老配置是[A,B,C],则老配置的大多数就是2,产生了新leader A,此时就出现了2个leader A 和 C,这样就有问题了。raft解决这个问题的方式有联合共识和单节点变更,联合共识是最初的方案,但因为过于复杂,所以后续就有了单节点变更的方案,这种方案可以解决因为一次添加过多节点导致出现分区时同时满足新旧大多数而破坏leader唯一性的问题。接下来我们看下单节点变更的方案,假设依然是3个节点ABC,如下:

在这里插入图片描述

首先添加一个节点D:

在这里插入图片描述

此时老配置是[A,B,C],大多数是2,新配置是[A,B,C,D],大多数是3,只有总节点数至少为5,才能同时满足新旧配置的大多数,而此时节点数是4,所以在出现网络分区不会满足>1个leader的情况,接着我们来增加节点E:

在这里插入图片描述

此时老配置是[A,B,C,D],大多数是3,新配置是[A,B,C,D,E],大多数是3,要想满足新旧配置的大多数,则至少需要有6个节点,而此时只有5个节点,所以不管出现何种情况的分区也不可能出现>1个leader的情况。

写在后面

小结

本文一起看了raft共识算法对分布式系统中leader选举,日支复制,成员变更3个主要问题提供的解决思路。希望本文能够帮助到你。

参考文章列表

分布式之Paxos共识算法分析 。

分布式理论之分布式选举 。

The Secret Lives of Data 。

什么是状态机?一篇文章就够了 。

状态机分析 。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_71592.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DAMA认证|数据治理产业上规模需要做到“三化”

数据治理是开启数据安全体系化建设的第一步,需要从产业层面做大做强,支撑数据安全整体框架,为数据流通提供安全保障,推动促进数字化产业进一步发展。 规模化发展是数据治理产业的瓶颈,行业数字化业务的复杂性和过多的定…

Spring Boot 日志文件,你都会了吗?

目录 1、日志文件的作用 2、日志的使用 2.1、从程序中得到日志对象 2.2、使用日志 2.3、日志格式 3、日志级别 3.1、这样的日志级别有什么用? 3.2、日志级别分类和使用 3.3、日志级别设置 4、日志持久化 5、更简单的日志输出——lombok 5.1、对比 5.2、…

Linux下安装MySQL8.0的详细步骤(解压tar.xz安装包方式安装)

Linux下安装MySQL8.0的详细步骤 第一步:下载安装配置 第二步:修改密码,并设置远程连接(为了可以在别的机器下面连接该mysql) 第三步:使用Navicat客户端连接 搞了一台云服务器,首先要干的活就是…

批处理删除指定文件或文件夹

声明:1-2节参考了 https://blog.csdn.net/weixin_43960383/article/details/1243673841. DEL1.1 DEL 的命令参数使用 del 命令能指定文件,Del (erase)[Drive:][Path]FileName指删除指定文件。指定要删除的文件或文件集的位置和名称。语法格式如下&#x…

Unity毛发系统TressFX Exporter

Unity 数字人交流群:296041238 一:在Maya下的TressFX Exporter 插件安装步骤: 1. 下载Maya的TressFX Exporter插件 下载地址:TressFX Exporter 链接:https://github.com/Unity-China/cn.unity.hairfx.core/tree/m…

利用OpenCV的函数equalizeHist()对图像作直方图均衡化处理

如果一幅图像的灰度值集中在某个比较窄的区域,则图像的对比度会显得比较小,不便于对图像的分析和处理。 图像的直方图均衡化可以实现将原图像的灰度值范围扩大,这样图像的对比度就得到了提高,从而方便对图像进行后续的分析和处理…

Cosmos 基础教程(二)-- Run a Node, API, and CLI

有很多不同的方法来运行Cosmos区块链的节点。您将探索如何使用simapp 进行此操作。 1、编译simapp Cosmos SDK存储库包含一个名为 simapp 的文件夹。在这个文件夹中,您可以找到运行Cosmos SDK模拟版本的代码,这样您就可以在不实际与链交互的情况下测试…

化解射频和微波设计挑战的六个技巧

即使是最自信的设计人员,对于射频电路也往往望而却步,因为它会带来巨大的设计挑战,并且需要专业的设计和分析工具。这里将为您介绍六条技巧,来帮助您简化任何射频PCB 设计任务和减轻工作压力! 1、保持完好、精确的射频…

由浅入深,一起来刷Java高级开发岗面试指南,面试必定无忧!

前言 我只想面个CV工程师,面试官偏偏让我挑战造火箭工程师,加上今年这个情况更是前后两男,但再难苟且的生活还要继续,饭碗还是要继续找的。在最近的面试中我一直在总结,每次面试回来也都会复盘,下面是我根…

【2022.12.9】Lammps+Python 在计算g6(r)时遇到的问题

目录写在前面绘制g6( r )执行步骤【updated】如何检查图像的正确性:不是编程问题,而是数学问题的一个小bug废稿2则:写在前面 全部log: 【2022.11.16】LammpsPythonMATLAB在绘制维诺图时遇到的问题 绘制g6( r )执行步骤【updated…

面试中经常被问到的【宏定义】,改变你对【C\C++】中宏定义的认识。

最近遇到挺多宏定义的代码,其实挺烦的,每次看复杂的宏定义看到一半就懵了,今天盘一盘它。本篇设计宏定义的原理、使用方法、使用技巧。 目录 一、宏定义原理 二、宏定义定义复杂功能函数 2.1 定义注册函数 三、宏定义实现条件编译 四、宏…

扬帆优配|五千亿巨头一度涨停! 4天3倍,港股又现“狂飙”股!

周一,A股三大指数走势分化。到午间收盘,沪指震荡走高涨近1%,深证成指涨0.75%,创业板指继续弱势调整。 盘面上,钢铁、煤炭、大金融等权重板块团体走强,三大通讯运营商一同拉升,其间我国电信盘中一…

超25亿全球月活,字节依然没有流量

(图片来源于网络,侵删) 文|螳螂观察 作者| 搁浅虎鲸 注意看,这个男人叫梁汝波,是字节跳动的联合创始人,也是接棒张一鸣的新任CEO。 在字节跳动十周年之际,他发表了激情昂扬的演讲。“激发创…

linux高级命令之互斥锁

互斥锁学习目标能够知道互斥锁的作用1.互斥锁的概念互斥锁: 对共享数据进行锁定,保证同一时刻只能有一个线程去操作。注意:互斥锁是多个线程一起去抢,抢到锁的线程先执行,没有抢到锁的线程需要等待,等互斥锁使用完释放后&#xff…

02- OpenCV绘制图形及图像算术变换 (OpenCV基础) (机器视觉)

知识重点 OpenCV用的最多的色彩空间是HSV. 方便OpenCV做图像处理img2 img.view() # 浅拷贝img3 img.copy() # 深拷贝split(mat) 分割图像的通道: b, g, r cv2.split(img) # b, g, r 都是数组merge((ch1, ch2, ch3)) 融合多个通道cvtColor(img, colorspace): 颜…

Learning C++ No.11【string类实现】

引言: 北京时间:2023/2/19/8:48,昨天更新了有关进程状态的博客,然后在休息的时候,打开了腾讯视屏,然后看到了了一个电视剧,导致上头,从晚上6点看到了10点,把我宝贵的博客…

【NestJS】中间件

中间件是在路由处理程序之前调用的函数,所以在中间件函数中可以访问请求和响应。 中间件函数需要执行 next() 将控制传递给下一个中间件函数,否则请求会被挂起。 可以使用 nest g mi XXX 创建中间件。 局部中间件 nest g res usernest g mi ajax、编写…

klog bug:仅输出到日志文件,不打印到命令行/stderr

一、 问题描述 开发k8s插件,使用klog作为日志工具,开发完成发现在设置将日志打印到文件后,Error级别的日志信息仍然会输出到命令行,过多日志打印会使后期将服务部署于docker有卡死的风险(docker的bug,日志…

kubectl常用的命令

目录 安装 kubectl 一、命令自动补全 二、常用命令 1、查看所有pod列表 2、查看RC和service列表 3、显示Node的详细信息 4、显示Pod的详细信息, 特别是查看Pod无法创建的时候的日志 5、 根据yaml创建资源, apply可以重复执行,create不行 6、基于nginx.yaml…

优思学院:六西格玛中的水平对比方法是什么?

水平对比,就是比较不同事物之间的差异。 这个概念在六西格玛管理中也很重要,也就是我们经常说的标杆管理,经常被用来寻找行业中最好的做法,以帮助组织改进自身的绩效。 在六西格玛管理中,水平对比有三种常见的应用方式…