0%

《区块链》Raft共识算法

Raft 是一个强 Leader 的共识算法,只有 Leader 能处理客户端的请求,集群的数据(Log)的流向是从 Leader 流向 Follower。

Follower如果收到客户端请求,则转发给Leader

Raft 是一个满足BASE理论(基本一致性、高可用性、分区可容忍性)的一致性算法(其中的基本一致性是存在争议的,在我看来Raft不是强一致性的)

概念

Entry

就是指一个日志,raft中有一个数组保存所有日志。任何数据过来先被封装成日志append到数组中,然后等待共识

共识完成就回调应用层

消息(message)

消息是指节点之间传递的消息,一个消息可能包含多个entries,也有很多类型的消息。比如appendMsg、voteMsg等等

快照点(snapshop point)

日志数组中最新一次快照的索引。这个索引之前的一定是已经被apply的,日志数组中不再保存,防止日志数组过大而撑爆内存

应用点(apply point)

日志数组中最新一个被应用层apply的entry的索引。每个entry在共识过后,会通过ready包的方式通知应用层,应用层处理(apply)它

提交点(commit point)

共识达成而成功提交的最新的entry的index就是提交点

附加点(append point)

leader的日志数组中最后一个entry的index就是附加点

Ready包

raft协议层发现有了已提交的entries之后,会以Ready包的形式不断向应用层传递entries以及msgs

Ready包就是包含了已提交但未应用的entries以及需要发送给follower的msg等信息的封装结构

Leader选举过程

  1. 节点刚启动时,成为follower,定时检查是否需要超时选举(leader长时间没有发过来心跳,超时时间在每个节点上具有随机性)
  2. 如果需要超时选举,将自己变成candidate,然后向每个peer发送voteMsg,等待投票(因为超时时间具有随机性,所以不太可能大量节点同时成为candidate)
  3. follower收到投票请求,就会投赞同票,candidate或leader收到则会拒绝。candidate每次收到follower的选举投票都会判断自己的同意票是否超过半数,超过了就成为leader并立马广播entries
  4. 之后leader定时向其他peer发送心跳以及entries,并接受客户端请求

如果leader挂了怎么办

leader挂了会导致followers超时(超时时间在各个follower一般都不一样,因为是随机的)收不到心跳,followers就会将自己变成候选人,开始发起投票,得票超过一般,将成为新leader

如果新增加一个节点会怎样

新增加的节点,通过leader的连接字符串连接到leader,leader会通过给自己发一个DefaultJoinCommand命令将节点加入peers(应用层做的,因为协议层不开启web服务器,只是一些handler),然后开始心跳同步log

如果有一个follower挂了会怎样

follower挂了会导致leader无法向其发送心跳,leader每次发送超时都会通知应用层,由应用层决定是否移除peer

leader移除了peer后,通过心跳会讲新的peer列表同步给followers

Log数据同步过程

Log数据同步其实就是命令的同步,施加到leader上的命令都会被同步到follower上,提交就是执行了命令

假设a、b、c 3个节点,a通过选举成为leader,a收到一个client请求,要求保存某数据

  1. a成为leader,然后向所有follower发送心跳
  2. 每次心跳执行第3步
  3. a append entry,然后分别向b、c发送append msg(并附带a中最新的提交点),并等待结果。此时a没有提交entry
  4. b、c收到命令后,同样append entry,然后向a回复已收到。此时b、c也没有提交entry(但会提交a发送过来的提交点之前的所有entry)
  5. a收到b、c的回复后,a提交entry并更新最新的提交点
  6. 等待下一次心跳,重复第3步

可以看出,leader提交了之后,followers还得等下一轮心跳才能提交,所以这个期间leader和followers之间是存在短暂不一致的

所以可以认为Raft并不是一个满足强一致性的协议,因为不能满足任意时刻各个节点的一致

只有leader才能接收需要共识的命令(除了加入集群的命令可以被follower接收),对leader的请求是同步的,leader提交了或共识失败了才会返回

第3步中,如果b、c中有的没有收到命令会怎样

b、c没有收到就什么也不做,a下次心跳还会继续发送append命令

第4步中,如果b、c的回复没有全部收到或者回复失败会怎样

这个例子中只有3个节点,实际上如果收到了 节点数/2 + 1 个或以上的确认,a就可以认为整个网络已经接受这些entry,a就可以提交了

本例子中,b、c只要有一个回复成功了(自己会自动给自己投一票),a就可以提交了

但是如果b和c都没有回复或者都回复失败,a就什么都不做,不会提交事务。等待下次心跳,b、c继续收到append命令,a又接收b、c回复




微信关注我,及时接收最新技术文章