原创

分布式学习九:Raft算法

温馨提示:
本文最后更新于 2022年03月03日,已超过 774 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

raft算法

由于paxos算法难以理解,今天来理解下 "易于理解的一致性算法"  raft

raft本质是选举领导,领导进行管理日志,实现的一致性算法

选举领导

每个节点角色都会在以下几种切换:

1:领导者

2:候选者

3:跟随者

在服务初始化时,所有节点为跟随者,在没有领导者的情况时,每个跟随者都有权发起候选投票,投票半数赞成后成为领导者

仙士可博客

选举的详细过程


服务初始化启动选举过程:

1:所有节点为跟随者,任期号为0

2:跟随者尝试获取领导者信息,选举信息

3:获取不到领导者信息,根据自身的超时时间,超出后开始投票选举,任期号为1

4:其他跟随者接收到选举信息,发起投票

5:如果超出半数,直接成为领导者,通知所有候选者以及跟随者,其他候选者成为跟随者,同步任期号为1

多个候选者情况

节点ABCDE,在选举过程中,有可能A,B同时成为选举者发起投票,恰好E节点断开,此时C支持A,D支持E,发生了选票相同,解决方案如下:

1:避免同时选举,每个节点设置一个不同的超时时间,例如A 100ms超时,B 200ms,这样可以保证A提前发起选票,CD只能支持A

2:在投票僵持时,每个节点设置一个随机的超时时间并且重新选举, 例如A在选票相同时,100ms之后重新发起任期为2的选举,B在200ms之后发起任期为2的选举

日志复制

领导者负责整个分布式节点的数据复制同步,不同节点产生了数据变化,都需要先同步到领导者节点,由领导者节点管理控制数据,流程如下:

仙士可博客

日志复制过程如下:

1:跟随者(领导者也可以提交数据)提交数据给领导者

2:领导者向所有跟随者发送日志数据

3:跟随者记录数据更新,记录日志

4:跟随者确认接收数据,发送给领导者

5:领导者发送确认提交数据

如果领导者无法接收到半数以上的跟随者确认数据时,将判断这条数据插入失败

日志

在raft算法中,所有的数据同步,都由日志来实现的,日志有以下特点:

1:日志不会被删除

2:可以认定集群的领导者日志最全,最新

日志存储

raft日志存储附带了任期号和具体操作数据的日志(类似于redis 的命令)

仙士可博客

领导者只有当跟随者超过半数完成确认数据之后,才会写入日志

当跟随者节点断开重连后,领导者将负责与跟随者同步日志(以领导者数据为准)

当领导者宕机后,跟随者将选出存储日志最新的领导者,并且以其通信同步日志

旧领导者恢复后,成为跟随者,同步新领导者的日志

日志压缩

由于日志不会被删除,在运行中,日志将会无限增长,所以raft实现了日志压缩功能,类似于redis的日志重写

领导者将生成一份数据快照,通知跟随者记录保存,跟随者保存之后将删除旧日志

其他

本文参考 https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md#52-%E9%A2%86%E5%AF%BC%E4%BA%BA%E9%80%89%E4%B8%BE

正文到此结束
本文目录