写点什么

共识算法之 Raft 算法模拟数

作者:TiAmo
  • 2023-05-10
    江苏
  • 本文字数:2279 字

    阅读完需:约 7 分钟

共识算法之Raft算法模拟数

01、Leader 选举

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


■ 图 1  Raft 模拟初始状态

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

■ 图 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 所示。

■ 图 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 所示。

■ 图 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 所示。

■ 图 5  日志复制-回复

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

■ 图 6  日志复制-心跳


03、日志对齐

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


■ 表 1  日志对齐

要使 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 所有的数据,本次日志对齐即完成。

发布于: 刚刚阅读数: 7
用户头像

TiAmo

关注

有能力爱自己,有余力爱别人! 2022-06-16 加入

CSDN全栈领域优质创作者,万粉博主;阿里云专家博主、星级博主、技术博主、阿里云问答官,阿里云MVP;华为云享专家;华为Iot专家;亚马逊人工智能自动驾驶(大众组)吉尼斯世界纪录获得者

评论

发布
暂无评论
共识算法之Raft算法模拟数_算法_TiAmo_InfoQ写作社区