分布式学习九:Raft算法
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的日志重写
领导者将生成一份数据快照,通知跟随者记录保存,跟随者保存之后将删除旧日志