当前位置: 首页 > news >正文

共识算法Raft

引入

在分布式系统中,为了消除单点提高系统可用性,通常会创建副本来进行容错,但这会带来另一个问题就是,如何保证多个副本之间的数据一致性。

为了解决这个问题,计算机行内就提出了共识算法,它允许多个分布式节点就某个值或一系列值达成一致性协议,即使在一些节点发生故障、网络分区或其他问题的情况下,共识算法也能保证系统的一致性和数据的可靠性。

常见的共识算法有:Zab、Paxos、Raft。

  • Paxos:一种经典的共识算法,用于解决分布式系统中的一致性问题。业内某知名程序猿曾经提经过说,共识算法本质上只有Paxos一种,其他就是对该共识算法的变种。
  • Raft:一种较新的共识算法,Paxos不易实现,Raft则是对其的简化和改进,旨在易于理解和实现。
  • Zab:ZooKeeper使用的共识算法,基于Paxos算法,并且大部分和Raft相同。主要区别就是对于Leader的任期,Zap叫做epoch,Raft叫做term;还有就是Raft是Leader向Follower发送心跳包,而Zab则刚好相反。
  • Gossip:该算法没有Leader和Follower之分,每个节点都是对等的。当节点中数据改动时,都会告知其他节点。

概述

总的来说,Raft算法是一种共识算法,他的作用就是实现多个节点的数据一致性。

当我们构建一个Raft集群,并对其内部进行一系列的读写操作时,集群内部是如何工作的呢?

1. Raft集群必须存在一个主节点,客户端向集群发起的写操作必须由主节点处理,所以Raft核心算法的第一部分就是选主。假设当前Raft集群没有主节点,那就没法工作,先选出一个主节点之后,再去考虑其他的内容。这部分工作在Raft中称为选主。

2. 有了主节点之后,当客户端发送过来写请求时,主节点就会将其进行包装同步给其他节点。在保证大多数节点都同步了本次操作之后,主节点就会给客户端发起响应了。这部分工作在Raft中称为日志复制。

3. 主节点在Raft算法中承担着非常大的责任,所以只有符合条件的节点才能当选主节点。为了保证集群对外展现的一致性,主节点在处理日志时,也一定要谨慎。这部分工作在Raft中称为安全性。

综上所述,Raft算法将一致性问题分解成了选主、日志复制以及安全性。

基本概念

领导者

领导者(Leader),负责处理客户端的所有修改请求,并将这些请求作为日志复制给跟随者(Follower)。在Raft中,Leader会定期向Follower发送心跳消息,以维持自己的领导地位,防止Follower进入选举过程。

跟随者

跟随者(Follower),接受来自Leader的日志,并将这些日志进行转换,应用为自己的内容。跟随者不会直接处理客户端的修改操作,但是可以处理客户端的读请求。

跟随者

候选者(Candidate),当Follower在一段时间内没有收到Leader发送过来的心跳消息时,Follower就会将自己的身份转变,并开始尝试通过投票成为新的Leader。

在Raft算法中,只能存在一个Leader,并且在集群启动时,所有节点的状态都是跟随者的状态,然后一段时间之内没有收到心跳包时,才会把自己转变成候选者,从而发起选举,使得集群出现了领导者,然后领导者就会一直工作直到他发生异常。

任期

在Raft中,领导者是没有固定任期的,当某一节点成为领导者之后,都是持续工作直到它出现异常为止。假设A点开始选举,然后成为领导者直到它发生异常的这段时间之内,都属于该节点的任期。因此,一段任期的开始时间都是从选举开始,然后到领导者不工作为止。假设在选举时间内没有选举成功,那么也算是一个任期,只不过该任期是以没有领导者而结束的。

任期更像是一个逻辑时钟的作用,有了它,就可以发现哪些节点已经过期,每一个节点都会保持一个任期号,然后在通信的时候带上这个值。

任期号会随着时间单调递增,并且每个节点都会存储一个任期号。节点之间通信时都会携带该任期号,如果一个节点的任期号比其他节点小,那么他就会变更自己的任期号到较大那个值。如果一个候选者或者领导者发现自己的任期号过期了,那么他就会变更成跟随者的状态。如果一个节点收到了一个带着过期任期号的节点,那么他就会忽略这次请求。

Raft算法中服务器节点之间采用RPC进行通信,主要有两类RPC请求:

RequestVote RPCs:请求投票,由候选者选举时发出。

AppendEntries RPCs:由领导者发出,用来做日志复制和发送心跳消息。

选主

1. Raft服务集群启动时,所有的节点都是跟随者的角色,并且每个节点都会有一个超时时间,当等待时间超过过期时间时,跟随者就会进入候选者的角色。

2. 由于启动时,并没有领导者,所以等到等待时间超过超时时间之后,跟随者就会转换成候选者的角色,继而发起投票(此时是因为没有刚启动没有领导者,也有可能是领导者宕机了,或者领导者和跟随者之间发生了网络故障问题等)。

3. 当跟随者成为候选者之后,任期号就会自动增长,同时投给自己一票,紧接着就会发生RPC请求,请其他节点也投自己一票,然后就是等待其他节点的响应。

到了此阶段,就会出现三种情况:

4.1 赢得选举(选举成功的定义是超过半数节点同意自己成为领导者)之后,就会立刻广发消息给其他节点,说自己选举成功了,大家都变成跟随者的状态吧。然后其他节点一看自己的任期号并没有人家的大,那就只能乖乖变成跟随者的状态了。

4.2 还没有等到半数票同意呢,并且等待时间没有超过超时时间,结果此时突然发来个消息说你跟随我吧,现在我是领导者。然后自己一看,人家的任期号比自己大会跟自己相等,那就只能老老实实跟着人家了,自己当个跟随者。

4.3 没有得到半数票同意,又超过了等待时间,那就只能保持候选者状态了,然后增加自己的任期号,重新发起一轮选举,此时就又成为了这三种情况的开头。(出现这种情况的原因可能有所有的节点超时时间相同,那么同一时间过期,导致所有的节点只会投自己一票,从而使得永远没有节点能达不到半数票同意,导致始终没有领导者出现。解决这种现象可以给节点搞一个随机超时时间,这就不会造成同一时间过期的现象了,即使有那也是个例,不影响整体架构)。

投票要求:

一个节点只能投一票。

候选者的任期号必须不能比投票者的小。

日志复制

当有写请求过来之后,Leader通过日志复制管理实现各个节点间的数据同步。

状态机

Raft算法一致性的实现,是基于日志复印状态机的。状态机最大的特征就是,不同节点的状态机若当前状态相同,然后接收了相同的输入,则一定会得到相同结果的输出。

流程

1. 领导者在收到客户端的写请求时,就会把请求的内容和自己的任期号进行封装,然后发送给跟随者,征求大家对此内容的意见,并同时将该请求内容封装为日志。

2. 跟随者收到此次请求之后,首先对比任期号。只要任期号不比自己小,并且两者的日志编号等内容相同,那么就会回复领导者同意,并将此内容封装成日志。

3. 当收到半数同意之后,领导者就会将此日志提交到自己的状态机,状态机会输出一个结果,同时日志状态变成了已提交。

4. 然后领导者还会向跟随者发送请求,告诉跟随者把日志进行提交。

5. 跟随者对日志进行了提交,日志状态也就变成了已提交。

6. 领导者向跟随者发送要求提交的请求时,还会给客户端发出响应。

日志是由任期号、日志的索引和命令组成的,为了保证可用性,各个节点的日志可以不完全相同,但是领导者会持续不断的发送内容给跟随者,以促使各个节点的日志最终达到相同。因此,Raft算法是保持最终一致性。

脑裂

脑裂指的是本来是在一个集群中处理消息的节点,因为某些原因而不能通信,导致两端都开始处理消息,从而使得系统混乱,数据错误的现象。

Redis集群存在脑裂现象,在多机房部署中,由于网络连接问题,很容易生成多个分区,而多分区的形成,很容易产生脑裂,从而导致数据出现问题。

在日常生产环境中,三机房的容灾能力是最强的,所以以三机房为例,来进行分析断网之后,出现的五种情况的后果:

情况一

在这种情况中,B与领导者A之间发生了网络问题,B的超时时间一过,B就会成为候选者,给C一发请求,C一看任期号比自己大,所以自己就会成为B的跟随者,而A与B此时不能进行交互,导致A也是领导者,B也是领导者。当有请求来时,A接受请求,但是最终由于票数没有大于一半,不会响应该请求,不过B能够成功响应。这就导致了读请求来时,A给出的数据可能不是正确数据。

综上所述,当领导者和某一跟随者之间无法通信时,就会出现脑裂现象。

情况二:

当B和C同时与A发生了网络故障时,两个跟随者无论谁先到达超时时间都会决出新的领导者,这就导致了三机房中出现了两位领导者,从而出现了脑裂问题。

情况三:

 

当ABC三者之间都出现了网络故障,此时虽然BC都会去进行选举,但是没有一个能选举成功,所以此时只有A可以提供读服务,BC则不能提供服务。

情况四:

 当出现上述情况时,B会进行选举,但是并不能选举成功,因为它永远得不到半数票的同意,所以并不会出现脑裂现象。并且,B不会对外提供服务,A和C则可以继续正常对外服务。

情况五:

当出现上述情况时,系统仍会正常工作,不会出现任何问题。

综上所述,在三个机房可能出现的五种情况中,也不是都会出现脑裂现象。并且我们发现,出现脑裂现象之后,从前的领导者都是不能响应写请求,因此我们可以在写项目中,加上一个判断就是当领导者长期不能应对写请求时,就自动下线或者进行其他处理。 

领导者宕机处理

请求到达领导者之前挂了:此时请求并没有到达Raft集群,所以Raft集群中并没有任何一个节点会对此请求有任何的处理。当新领导者上线以后,也不会认为有任何的不妥。此时如果客户端有重试机制的话,就会重新发送请求过来,Raft集群进行正常处理。

请求到达领导者,但是领导者还没有发送数据时挂了:新领导者选举出来之后,由于新领导者并没有该请求的任何消息,所以并不会进行任何响应。并且当新领导者同步各个节点时,由于之前的旧领导者有这条消息,旧领导者还会将此消息丢弃出来。

请求向跟随者发送部分之后挂掉了:此时选举出领导者之后,会有两种情况出现。第一种是新领导者有该消息的存在,所以会进行同步,最后返回响应;第二种就是恰好不存在该消息,那么就不会进行同步,也不会发起响应。

领导者向跟随者发送提交后挂掉了:此时已经成功发送了提交,并且提交的同时还会向客户端响应,那已经成功了,此时新领导者上来也不会处理啥,因为已经成功了。

在日志复制中,对一些较为详细的内容并没有介绍到。其实,向跟随者发送日志条目的啥时候,有很多的内容,因为要保证节点的数据一致性,所以就要判断以前的日志条目是否相同。但是由于并不是详细了解其工作原理,所以只进行了一个大致介绍,同学们也只需要大致了解就能应对面试官的大多数问题了。

概述来说,由于各个节点之间数据是不可能每次都能同步成功,并且由于宕机等问题,数据可能确实很多。所以日志复制,基本上是上述的简单流程,不过假设某一结点数据或缺许多时,领导者也会慢慢找到或缺的数据,然后给他全部补上,保持一个数据的最终一致性。

总的来说,Raft共识算法就是用来保证集群中数据一致性的。为了保证其数据一致性,内部大概分成了选主、日志复制、安全性等内容。 

应用场景

1. 在Redis中,使用哨兵机制时,当Redis主节点发生问题之后,哨兵节点就会进行选主,然后对主从集群进行操作,选主的过程就是使用的Raft算法。

2. 在RabbitMQ构建集群中,仲裁队列内部使用的也是Raft算法。本身创建的是普通队列,这就导致单点问题。不过创建仲裁队列之后,利用Raft算法就可以将队列和消息在不同的节点都进行存储。假设创建队列的节点出现故障之后,其他节点依然能够针对该队列进行工作。


http://www.mrgr.cn/news/48228.html

相关文章:

  • 使用Helm
  • 解决QT制作的软件,全屏显示后最小化,点击任务栏图标打开时不是全屏而是窗口状态的问题
  • MyBatis是什么?为什么有全自动ORM框架还是MyBatis比较受欢迎?
  • HDR视频技术之十:MPEG 及 VCEG 的 HDR 编码优化
  • 【AIStarter:项目管理平台】Krita 5.2.6 + AI 1.29 + ComfyUI 插件:创作与效率的完美结合
  • Redis 7.x如何安装与配置?保姆级教程
  • std::future::then的概念和使用方法
  • 让UE通过EPC连接到互联网
  • 基于JAVA+SpringBoot+Vue的医疗报销系统
  • 微积分复习笔记 Calculus Volume 1 - 2.3 The Limit Laws
  • 上传图片到github上,生成链接在Typora中使用(解决Typora的md文件在分享时的丢失问题)
  • 死磕P7:JVM性能调优必知必会(二)
  • 付费计量系统实体和接口(7)
  • [C语言] 函数详解:库函数与自定义函数
  • 职场上的人情世故你知多少
  • 从automaxprocs库浅窥Linux容器的资源控制
  • 【测试】测试分类
  • 腾讯云-云直播
  • Linux:信号保存与处理
  • H3C OSPF 综合排错实验
  • Breach 2.1靶机渗透
  • 【网络安全】25,000$任意账户接管
  • 基于Python flask的豆瓣电影可视化系统,豆瓣电影爬虫系统
  • 【Spring详解】Maven从安装到应用(Maven Help插件的安装)-国内源的配置(中央仓库及私服的概念)
  • vue3 element table 插槽外的数据更新,插槽内的数据未更新。
  • ESP32—c3实现网页显示ADC电压并实时更新