掌握了这个算法就可以较容易地处理绝大部分场景的容错和数据一致性需求

Raft三大角色

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

大王不在掀杆而起自立为王哈哈

RPC

消息通知其他节点来投票如果赢得了大多数投票选票就晋升当领导者。

领导者Leader霸道总裁一切以我为准。

主要功能处理写请求、管理日志复制数据同步和不断地发送心跳信息保持连接通知其他节点“我是领导者我还活着你们不要”发起新的选举不用找新领导来替代我。

大王还在你们不要起义

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

aNode

算法实现了随机超时时间的特性每个节点等待领导者节点心跳信息的超时时间间隔是随机的。

比如

150

先超时最先因为没有等到领导者的心跳信息发生超时。

如下图所示三个节点的超时计时器开始运行。

为什么follower等待leader心跳不同节点进行随机超时呢因为follower节点也想当大王呀但如果多个follower同一时间点发起投票进行选举从而会导致选票相同的情况又重新进行选举所以还是每个节点的随机超时的时间是不同的

2、发起投票

次投票得到了大多数节点的投票从候选者成为本届任期内的新的领导者。

第四步节点

和节点

自动增加跟随者在等待领导者心跳信息超时后推荐自己为候选人会增加自己的任期号如上图所示节点

任期为

更新为较大值当节点发现自己的任期编号比其他节点小时会更新到较大的编号值。

比如节点

1节点

恢复为跟随者如果一个候选人或者领导者发现自己的任期编号比其他节点小那么它会立即恢复成跟随者状态。

这种场景出现在分区错误恢复后任期为

拒绝消息如果一个节点接收到较小的任期编号值的请求那么它会直接拒绝这个请求比如任期编号为

A收到任期编号为

一个任期内领导者一直都会领导者直到自身出现问题如宕机或者网络问题延迟其他节点发起一轮新的选举。

在一次选举中每一个服务器节点最多会对一个任期编号投出一张选票投完了就没了。

假设一个集群由

问题为什么要定义leaderfollowercandidate

集群数据同步保证一致性一般有两种做法

1、如果想要实现集群数据同步必然要实现节点数据传送如果各个节点都是平等地位那么对于写操作而言是对于每个节点都生效的处理起来变得很复杂

2、拿到数据要统一给每一个集群节点发送可能会存在并发问题写覆盖导致数据不一致

为了防止多个节点同时发起投票会给每个节点分配一个随机的选举超时时间。

这个时间内节点不能成为候选者只能等到超时。

比如上述例子节点

先超时先成为了候选者。

这种巧妙的设计在大多数情况下只有一个服务器节点先发起选举而不是同时发起选举减少了因选票瓜分导致选举失败的情况。

问题leader出现故障怎么办

如果领导者节点出现故障则会触发新的一轮选举。

如下图所示领导者节点

发生故障节点

1、领导者心跳超时节点定义不同的超时时间进行选举投票避免选举时票数相同

2、先超时先投票

什么是脑裂假如在一个集群或系统中同时出现2个及以上的Leader这样的现象就是脑裂。

多个Leader会向Follower同时发号施令Follower不清楚该接受哪个Leader的指令最终会造成内部混乱。

每个节点在一个任期内只能投票一次。

获得半数以上的选票才能成为Leader。

在固定的选票下获得半数以上选票的才能成为Leader有效避免了脑裂问题。

如果在网络分区下网络不畅怎么避免脑裂

先说结论其实和Leader宕机恢复很像低任期的Leader在发现有高任期的Leader后会主动降级为Follower。

一开始集群内部只有一个Leader。

后来发生了网络分区L1无法向F3、F4与F5发送心跳。

总结日志复制数据同步

F3、F4与F5将会开启新一轮选举接着F4获得当前所有的选票即3份为半数以上当选为新的Leader。

L1发现L4的任期比自己的大于是主动降级为Follower并接收来自L4的心跳。

leader自动降级可以一定程度上解决当然脑裂的解决少不了日志复制技术

问题如果有多个服务器节点怎么保证一致性呢

索引值可以理解为该条日志在文件中所处的行号任期编号创建这条日志的Leader所处的任期客户端的指令在提交后会被状态机执行

因此Raft集群的重点在于Leader需要将自己的日志同步到Follower节点以保证整个Raft集群的数据一致性。

当L1接收到客户端的数据修改的指令后首先会append到自己的本地日志中状态为未提交之后会向Follower节点发起append请求。

当Follower节点接收到append请求后同样也会append到自己的本地日志中状态为未提交。

注意:

当半数以上的Follower写入成功后Leader会将日志提交并应用到状态机中执行同时回应客户端修改成功。

上图描述的是一个在理想状态下的复制过程在实际场景中可能会出现Leader宕机、网络分区的情况这些情况会导致日志的不一致那么Raft是怎么保证日志的一致性的呢

leader的系统因此会强制Follower复制Leader的日志。

日志复制细节

Leader会在心跳信息中将已提交的日志数据不断发送给Follower复制请求中包含上一条日志的索引值与任期记为L.pre.index与L.pre.term当前日志的索引值与任期记为L.cur.index与L.cur.term。

Follower在收到复制请求后先查找自身L.pre.index索引值的日志term是否等于L.pre.term如果等于则将L.cur.index与L.cur.term追加到本地日志中并返回复制成功。

如果Follower中L.pre.index索引值的日志term不等于L.pre.term则返回复制失败。

此时Leader会将更前面一条的日志发送过来如果依然复制失败则继续往前一直从后往前找到第一个共同的日志。

并从这里开始往后复制使得Follower与Leader的日志一致。

举个例子

假设该集群在运行一段时间后Leader与其中一个Follower的日志情况如下

1、此时Leader需要Follower复制索引为5的日志于是将索引4和5的日志一起发送给了Follower。

2、Follower发现索引4的日志任期和Leader日志不一致因此返回复制失败。

3、Leader发现复制失败后将索引3和4的日志一起发送给了Follower。

4、Follower发现索引3的日志任期是一致的这就找到了和Leader共同的日志项于是覆盖索引4的本地日志返回复制成功。

6、下一轮的心跳信息中Leader将索引4和5的日志一起发送给了Follower。

7、Follower比对发现索引4的日志一致于是将索引5的Leader日志追加到本地日志中此时Leader与Follower的日志一致了。

https://www.coonote.com/distributed-system/raft-algorithm.html

https://www.cnblogs.com/crazymakercircle/p/14343154.html#autoid-h2-1-8-0