详解共识算法的Raft算法模拟数

摘要：Raft算法是一种分布式共识算法，用于解决分布式系统中的一致性问题。

本文分享自华为云社区《共识算法之Raft算法模拟数》，作者： TiAmoZhang 。

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

点击关注，第一时间了解华为云新鲜技术~