图解 Raft 共识算法：如何复制日志？

上次讲到 Raft 领导者选举：「图解 Raft 共识算法：如何选举领导者？」，接着这个话题继续跟大家聊下关于 Raft 日志复制的一些细节。

Raft 日志格式

在 Raft 算法中，需要实现分布式一致性的数据被称作日志，我们 Java 后端绝大部分人谈到日志，一般会联想到项目通过 log4j 等日志框架输出的信息，而 Raft 算法中的数据提交记录，他们会按照时间顺序进行追加，Raft 也是严格按照时间顺序并已一定的格式写入日志文件中：

如上图所示，Raft 的日志以日志项（LogEntry）的形式来组织，每个日志项包含一条命令、任期信息、日志项在日志中的位置信息（索引值 LogIndex）。

• 指令：由客户端请求发送的执行指令，有点绕口，我觉得理解成客户端需要存储的日志数据即可。
• 索引值：日志项在日志中的位置，需要注意索引值是一个连续并且单调递增的整数。
• 任期编号：创建这条日志项的领导者的任期编号。

日志复制过程

Raft 的复制过程大致如下：

领导者接收到客户端发来的请求，创建一个新的日志项，并将其追加到本地日志中，接着领导者通过追加条目 RPC 请求，将新的日志项复制到跟随者的本地日志中，当领导者收到大多数跟随者的成功响应之后，则将这条日志项应用到状态机中，可以理解成该条日志写成功了，最后领导者返回日志写成功的消息响应客户端，流程如下图所示：

可以看出，Raft 的复制过程中，领导者接收到大多数跟随者成功响应，并且将日志项应用到状态机之后，不需要将结果响应给跟随者，而是直接将成功消息响应给客户端，这是一种优化方式，同时 Raft 会在下一次 RPC 追加日志请求中附加上本次的日志项信息。

以上仅仅只是一种没有发生任何问题的复制过程，在这过程中难免会发生节点宕机等问题，在这种情况下，Raft 是如何处理的呢？

如何保证日志的一致性？

上面讲到，在正常情况下，领导者的日志追加 RPC 请求响应都成功的情况下，领导人和跟随者的日志保持一致性。然而在领导者突然宕机的情况下有可能会造成领导者与跟随者日志不一致的情况，这种情况会随着后续领导者一些列宕机的情况下加剧问题的严重：

注：例子来源于 Raft 论文。

如上所示，当一个领导者成功当选时，跟随者有可能是 a-f 的情况：

1. a-b 表示跟随者的日志项落后于当前领导者；
2. c-d 表示跟随者有些日志项没有被提交；
3. e-f 情况稍微有点复杂，以上两种情况它们都存在。

下面我来还原上面图所表示的情况是怎么发生的：

假设一开始 e 为领导者，在任期 2 时，f 被推选为领导者，写入了若干日志项之后，在追加 RPC 请求中崩溃了，重启后又被选举为领导者（任期号 3），又在写入了若干日志项之后奔溃了；e 此时又重新选举为领导者（任期号为 4），成功复制了若干日志项，同时还有一部分没有成功追加到大多数跟随者又崩溃了，同时跟随者 b 复制了一部分日志项之后崩溃了；假设 a 在任期 5 时被选举为领导者，c 在任期 6 时被选举为领导者，还未全部将本地日志复制到其他跟随者之前又崩溃了，在任期 7 时 d 被选择为领导者，写入了若干日志项之后，在追加 RPC 请求中崩溃了，最后形成了上图的情况。

面对以上的情况，Raft 是如何解决日志的一致性呢？

在 Raft 的日志机制中，为了简化日志一致性的行为，有以下两点非常重要的特性：

1. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
2. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

第一个特性是因为 Raft 日志项在日志中不会改变，因此只要日志项只要是索引值和任期号相同，就可以认为他们是存储了相同的指令数据信息。

第二个特性是因为领导者会通过强制覆盖的方式让跟随者复制自己的日志来解决日志不一致的问题，领导者在追加 RPC 请求过程中会附带需要复制的日志以及前一个日志项相关信息，如果跟随者匹配不到包含相同索引位置和任期号的日志项，那么他就会拒绝接收新的日志条目，接着领导者会继续递减要复制的日志项索引值，直至找到相同索引和任期号的日志项，最后就直接覆盖跟随者之后的日志项。可认为两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

因此，Raft 的日志追加大致可分为两个步骤：

1. 领导者找到跟随者与自己相同的最大日志项，这意味着跟随者之前的日志都与领导者的日志相同；
2. 领导者强制覆盖之后不一致的日志，实现日志的一致性。

下面我用一个例子充分表达 Raft 在日志复制过程中是如何进行日志强制覆盖的。

假设有一个领导者和一个跟随者，他们的日志项复制情况如下：

可以看出，跟随者在任期号 3 时是领导者，在追加日志过程中崩溃了，重启之后成为跟随者，随后新的领导者向其追加日志，此时他的任期号为 3 最后的一个日志项将被覆盖。

先来看下 Raft 追加条目 RPC 的请求参数：

参数 描述 term 领导者的任期 leaderId 领导者ID 因此跟随者可以对客户端进行重定向（译者注：跟随者根据领导者id把客户端的请求重定向到领导者，比如有时客户端把请求发给了跟随者而不是领导者） prevLogIndex 紧邻新日志条目之前的那个日志条目的索引 prevLogTerm 紧邻新日志条目之前的那个日志条目的任期 entries[] 需要被保存的日志条目（被当做心跳使用是 则日志条目内容为空；为了提高效率可能一次性发送多个） leaderCommit 领导者的已知已提交的最高的日志条目的索引

领导者追加并覆盖跟随者过程如下：

1. 领导者通过日志追加 RPC 请求，将当前最新的要追加到跟随者的日志项以及前一个它的 prevLogIndex=7、prevLogTerm=3 等信息发送跟跟随者；
2. 跟随者判断当前最新的日志的任期号与 prevLogTerm 不一致，拒绝追加；
3. 领导者继续递减需要复制的日志项的索引值，此时 prevLogIndex=6、prevLogTerm=3；
4. 跟随者找到了 LogIndex=6、LogTerm=3 的日志项，跟随者接受追加请求；
5. 领导者接着会将跟随者 LogIndex=6、LogTerm=3 的日志项之后的日志项进行追加并覆盖。