这就是Raft算法？文末送书

大家好，今天来聊聊Raft算法选举的过程。

1  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。

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

2  日志复制

日志复制是一个一阶段协商的过程，其中，日志项的提交操作由下一轮协商或者心跳消息来代替完成。因此处理事务请求，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。其中：

q第一个参数为committedIndex，即Leader最后提交的日志索引。

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

q第三个参数为事务操作指令，即客户端的指令。

（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  日志复制-心跳

3  日志对齐

我们使用<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=lastLogIndex_msg+1，即nextIndex=4。

（5）Leader发送下一轮的探测消息，其中，preLogIndex=3，preLogTerm=2。

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

（7）Leader收到失败的响应，此时lastLogIndex_msg+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所有的数据，本次日志对齐即完成。

注：本文节选自清华大学出版社出版的《深入理解分布式共识算法》（ISBN 978-7-302-63003-6），略有改动。

《深入理解分布式共识算法》结合理论知识、算法模拟和源码解析，从多个维度详细剖析分布式共识算法的基本原理和应用实践，涵盖分布式共识算法的方方面面。同时《深入理解分布式共识算法》对共识算法开发中的重点和难点问题进行了重点讲解，并提供精心准备的练习题供读者巩固和提高所学的知识。另外，作者针对重点内容录制了教学视频，以帮助读者高效、直观地学习。

文末送书

老规矩，星球抽奖送两本《深入理解分布式共识算法》，免费包邮到家，还没进的同学通过下面连接进入。
星球连接~
也可通过文末卡片购买享受五折优惠！！！