共识算法之Raft算法模拟数

举报
TiAmoZhang 发表于 2023/04/26 08:49:55 2023/04/26
【摘要】 存在A、B、C三个成员组成的Raft集群,刚启动时,每个成员都处于Follower状态,其中,成员A心跳超时为110ms,成员B心跳超时为150ms,成员C心跳超时为130ms
简介: 存在A、B、C三个成员组成的Raft集群,刚启动时,每个成员都处于Follower状态,其中,成员A心跳超时为110ms,成员B心跳超时为150ms,成员C心跳超时为130ms

01、Leader选举

存在A、B、C三个成员组成的Raft集群,刚启动时,每个成员都处于Follower状态,其中,成员A心跳超时为110ms,成员B心跳超时为150ms,成员C心跳超时为130ms,其他相关信息如图1所示。

640.png


■ 图1 Raft模拟初始状态


由于集群中不存在Leader,A、B、C三个成员都不会收到来自Leader的心跳信息。其中,成员A的超时最短,最先进入选举状态,修改自己的状态为Candidate,并增加自己的任期编号为1,发起请求投票消息,如图2所示。

640.png


■ 图2 请求投票


成员A通过RequestVote广播自己的选票给成员B、C,选票描述了成员A所拥有的数据,其包含成员A所处的term及最新的日志索引。成员B、C根据投票规则处理RequestVote消息。
term大的成员拒绝投票给term小的成员。


日志索引大的成员拒绝投票给日志索引小的成员。

一个term内只投出一张选票,采用先来先获得投票的原则。
很明显,成员B、C的term小于成员A的term,也不存在比成员A日志索引更大的日志索引,并且term为1的选票还没有投给其他成员,因此成员B、C将term为1的选票投给成员A并更新自己的term为1。

成员A获得包括自己在内的3张选票,赢得大多数选票,成员A晋升为Leader,并向其他成员发送心跳信息,维护自己的领导地位,如图3所示。

640.png


■ 图3 Leader晋升示意


如果成员A在等待投票超过约定的时间内没有收到多数派的选票,则会重置自己的超时,并结束本次选举进程。接着会有其他成员在等待心跳超时后发起Leader选举,在当前案例中,发起Leader选举的顺序为A→C→B。


可能因为网络问题,使集群中的所有成员又发起了一轮选举,但是都没有获得多数派的选票,因此会随机产生新的超时,开始下一个循环的选举。

02、日志复制

日志复制是一个一阶段协商的过程,其中,日志项的提交操作由下一轮协商或者心跳消息来代替完成。因此处理事务请求,Raft只需要发送一轮AppendEntries消息即可。

AppendEntries消息除了会包含需要复制日志项的相关信息外,通常会携带Leader的committedIndex参数,标示着最后一个已提交的日志索引。每个Follower的本地都维护了committedIndex,Follower可以对比Leader的committedIndex来推进自己的提交操作。

接着如图3所示的示例,一个三个成员组成的集群,成员A为Leader,成员B和C为Follower,并且在集群中未提交任何日志项。Leader收到客户端发送的Add请求后,Leader和Follower依次执行以下步骤,如图4所示。

640.png


■ 图4 日志复制-复制


(1)Leader将其封装成日志项追加到本地的日志中,日志索引为1。

(2)Leader通过AppendEntries(0, <1, Add>)消息时将日志项广播给所有的Follower。其中:
第一个参数为committedIndex,即Leader最后提交的日志索引。

第二个参数为Leader所处的日志索引,即Add日志项的索引。

第三个参数为事务操作指令,即客户端的指令。
(3)Follower收到消息,将日志项追加到本地的日志中。

此时,成员A、B、C都拥有日志项Add且都已在索引为1上完成了持久化。Follower在处理完AppendEntries消息后需要回复ACK消息给Leader,代表接受该日志项。Leader收到多数派的ACK消息后,可以在本地提交该日志项并执行状态转移,之后将执行结果返回给客户端,如图5所示。

640.png


■ 图5 日志复制-回复


在当前场景中,成员A提交了索引为1的日志项,成员B、C仅仅拥有索引为1的日志项的所有信息但并未提交。成员B、C需要等待下一次AppendEntries消息,根据其committedIndex推进索引为1的日志项的提交操作。以心跳的AppendEntries消息为例,该AppendEntries消息仅携带了committedIndex,此时Leader已经提交了索引为1的日志项,因此committedIndex为1。Follower则可以提交索引为1及其之前的所有日志项,如图6所示。

640.png


■ 图6 日志复制-心跳


03、日志对齐

我们使用<term, logIndex>表示一个日志项,如表1所示为Follower E的日志索引3和Follower D的日志索引4,与当前Leader处理不一致的情况。出现这种情况可能是Follower E和Follower D曾经当选过Leader,并且在自己的term上提出了日志索引为3和4的日志项后立即宕机造成的。

■ 表1 日志对齐


640.png


要使Follower E和Follower D与Leader数据保持一致,大致步骤分为两步:寻找nextIndex,复制nextIndex及其之后的日志项。在Raft中,这个步骤均可由AppendEntries消息来完成。这里以Follower E成员为例,交互细节如下:


(1)Leader为Follower E初始化nextIndex,nextIndex=lastLogIndex+1,即nextIndex=6+1=7。

(2)Leader通过AppendEntries发送探测消息,携带preLogIndex(nextIndex-1)及preLogTerm,其中,preLogIndex=6,preLogTerm=3。

(3)Follower收到探测消息,对比索引为6的日志项,返回失败的响应给Leader并携带lastLogIndex=3。

(4)Leader收到失败的响应,更新nextIndex=lastLogIndexmsg+1,即nextIndex=4。

(5)Leader发送下一轮的探测消息,其中,preLogIndex=3,preLogTerm=2。

(6)Follower收到探测消息,对比索引为3的日志项,返回失败的响应给Leader并携带lastLogIndex=3。

(7)Leader收到失败的响应,此时lastLogIndexmsg+1 ≤ nextIndex,则nextIndex单调递减为3。

(8)Leader发送下一轮的探测消息,其中,preLogIndex=2,preLogTerm=1。

(9)Follower收到探测消息,对比索引为2的日志项,返回探测成功的响应给Leader。

(10)Leader在成功探测到nextIndex之后,通过AppendEntries消息从nextIndex开始发送索引为3的日志项给Follower。

(11)Follower将以Leader的数据为准,覆盖本地的日志项并返回处理成功的响应给Leader。

(12)Leader收到成功响应后,单调递增nextIndex,继续发送下一个日志项。直到nextIndex等于Leader的lastLogIndex,意味着该Follower拥有Leader所有的数据,本次日志对齐即完成。

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。