文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

分布式系统必须知道的一个共识算法:Raft

2024-11-30 16:43

关注

如果​​掌握​​​了这个算法,就可以较容易地处理绝大部分场景的​​容错​​​和​​一致性​​需求。比如分布式配置系统、分布式 NoSQL 存储等等,轻松突破系统的单机限制。

Raft 算法是通过一切以领导者为准的方式,实现一系列值的共识和各节点日志的一致。

二、Raft 角色

2.1 角色

跟随者(Follower):​​普通群众​​,默默接收和来自领导者的消息,当领导者心跳信息超时的时候,就主动站出来,推荐自己当候选人。

候选人(Candidate):​​候选人​​将向其他节点请求投票 RPC 消息,通知其他节点来投票,如果赢得了大多数投票选票,就晋升当领导者。

领导者(Leader):​​霸道总裁​​,一切以我为准。处理写请求、管理日志复制和不断地发送心跳信息,通知其他节点“我是领导者,我还活着,你们不要”发起新的选举,不用找新领导来替代我。

如下图所示,分别用三种图代表跟随者、候选人和领导者。

角色

三、单节点系统

3.1 数据库服务器

现在我们想象一下,有一个单节点系统,这个节点作为数据库服务器,且存储了一个值为 X。

数据库服务器

3.2 客户端

左边绿色的实心圈就是客户端,右边的蓝色实心圈就是节点 a(Node a)。Term 代表任期,后面会讲到。

客户端

3.3 客户端向服务器发送数据

客户端向单节点服务器发送了一条更新操作,设置数据库中存的值为 8。单机环境下(单个服务器节点),客户端从服务器拿到的值也是 8。一致性非常容易保证。

客户端向服务器发送数据

3.4 多节点如何保证一致性?

但如果有多个服务器节点,怎么保证一致性呢?比如有三个节点:a,b,c。如下图所示。这三个节点组成一个数据库集群。客户端对这三个节点进行更新操作,如何保证三个节点中存的值一致?这个就是分布式一致性问题。Raft 算法就是来解决这个问题的。当然还有其他协议也可以保证,本篇只针对 Raft 算法。

在多节点集群中,在节点故障、分区错误等异常情况下,Raft 算法如何保证在同一个时间,集群中只有一个领导者呢?下面就开始讲解 Raft 算法选举领导者的过程。

四、选举领导过程

4.1 初始状态

初始状态下,集群中所有节点都是跟随者的状态。

如下图所示,有三个节点(Node) a、b、c,任期(Term)都为 0。

初始状态

4.2 成为候选者

Raft 算法实现了随机超时时间的特性,每个节点等待领导者节点心跳信息的超时时间间隔是随机的。比如 A 节点等待超时的时间间隔 150 ms,B 节点 200 ms,C 节点 300 ms。那么 a 先超时,最先因为没有等到领导者的心跳信息,发生超时。如下图所示,三个节点的超时计时器开始运行。

超时时间

当 A 节点的超时时间到了后,A 节点成为候选者,并增加自己的任期编号,Term 值从 0 更新为 1,并给自己投了一票。

成为候选者

4.3 投票

我们来看下候选者如何成为领导者的。

Leader 选举

4.4 任期

英文单词是 term,领导者是有任期的。

4.5 选举规则

4.6 大多数

假设一个集群由 N 个节点组成,那么大多数就是至少 N/2+1。例如:3 个节点的集群,大多数就是 2。

4.7 心跳超时

为了防止多个节点同时发起投票,会给每个节点分配一个随机的选举超时时间。这个时间内,节点不能成为候选者,只能等到超时。比如上述例子,节点 A 先超时,先成为了候选者。这种巧妙的设计,在大多数情况下只有一个服务器节点先发起选举,而不是同时发起选举,减少了因选票瓜分导致选举失败的情况。

成为候选者

五、领导者故障

如果领导者节点出现故障,则会触发新的一轮选举。如下图所示,领导者节点 A 发生故障,节点 B 和 节点 C 就会重新选举 Leader。

领导者故障

总结

Raft 算法通过以下几种方式来进行领导选举,保证了一个任期只有一位领导,极大减少了选举失败的情况。

本篇通过动图的方式来讲解 Raft 算法如何选举领导者,更容易理解和消化。

来源:悟空聊架构内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯