Raft 共识算法学习笔记 二：日志复制

发表于 更新于 分类于 阅读次数：

文章 Raft 共识算法学习笔记 一：领导人选举 描述了 Raft 算法如何进行领导者选举，本文描述 Raft 共识算法如何进行日志复制。

复制状态机

在 Raft 集群中，每个服务器可以看成是一个复制状态机（Replicated State Machine），如下图。
复制状态机通常基于复制日志（replicated log）实现。每个服务器存储一个包含一系列指令的日志，并且按顺序执行指令。由于日志都包含相同顺序的指令，状态机会按照相同的顺序执行指令，由于状态机是确定的（deterministic），因此状态机会产生相同的结果。
保持这些日志的一致性（consistent）正是共识（consensus）算法的工作。

图：复制状态机工作过程：1. 客户端请求；2. 共识模块执行共识算法进行日志复制，将日志复制至集群内各个节点；3. 日志应用到状态机；4. 服务端返回请求结果

在 Raft 中，指令以日志形式进行复制。集群内只有领导者才能接收客户端请求，其他所有节点都接收来自领导者的复制日志，以达到所有节点日志的一致，并最终达到状态的一致。

Raft 日志

上面我们提到在 Raft 中，指令以日志形式存在。日志由日志项（log entry）构成。日志项包含日志项索引、任期编号以及指令：

  • 指令：客户端请求状态机需要执行的命令，例如指令 x <- 3 表示将 x 变量赋值为 3
  • 日志项索引：日志项对应的索引值，是一个连续的、单调递增的整型号码
  • 任期编号：创建这条日志项的领导者的任期编号

在上图可以看到，在一届领导者任期内，往往有多个日志项，例如，任期 1 有三个日志项，其日志项索引值分别为 1，2，3。

在 Raft 论文 In Search of an Understandable Consensus Algorithm (Extended Version) 中，多次提到 commit 和 apply 两词。其中，commit （提交）或 committed （已提交）针对的是日志，即日志项被成功复制到集群中大多数节点后，日志项处于 committed 状态，例如上图中索引 1 - 7 的日志项均处于 committed 状态；apply （应用）或 applied （已应用）针对的是状态机，即节点将日志项应用到状态机，真正改变节点变量的值。

关于日志复制的过程，下面会进行更详细的描述。

日志复制

领导者接收到客户端请求后，接下来会进行日志复制的操作，过程如下图所示：

  1. 客户端发送请求，领导者接收到客户端请求，根据请求中的指令，创建一个新的日志项，并附加（append）到领导者日志中
  2. 领导者通过日志复制 RPC（AppendEntries RPC），将新的日志项复制至其他节点
  3. 当领导者将日志项成功复制至集群大多数节点的时候，日志项处于 committed 状态，领导者可将这个日志项应用（apply）到自己的状态机中
  4. 领导者将客户端请求结果返回给客户端
  5. 当其他节点，即跟随者，接收到领导者的心跳消息，或新的日志复制消息（该消息均会附上领导者最大已提交日志项索引），如果跟随者发现领导者已提交某日志项，而自己还没将该日志项应用至状态机，那么，跟随者就将该日志项应用至自己的状态机中

从上面日志复制的过程可以看到，日志复制过程有点类似我们熟悉的二阶段提交（2PC）过程。与 2PC 不同的是，领导者接收到集群内大多数节点响应后，领导者就可以直接返回结果给客户端。这个优化，降低了客户端请求的延迟，将二阶段提交优化为一阶段提交。

为什么可以做这样的优化呢？就像上面所说的，由于领导者与跟随者之间的 RPC 通信 AppendEntries RPC，包括日志复制 RPC 和心跳 RPC，都包含了领导者最大已提交日志项索引，通过此日志项索引，跟随者可以在知道领导者已提交日志项，然后将该日志项按顺序应用至自己的状态机中，达到最终一致性。

日志一致性

Raft 日志具体如下特性：（本文不作具体证明，有兴趣的可以参考 Raft 论文 $5.3 部分，读者可只记住结论即可。）

  • 如果不同日志中的两个日志项具有相同的索引值和任期编号，那么这两个日志项具有相同的指令
  • 如果不同日志中的两个日志项具有相同的索引值和任期编号，那么这两个日志项之前的所有日志项也全部相同

在 Raft 算法中，通过领导者强制跟随者复制自己的日志项，来处理不一致的日志。

具体包括两个步骤：

  1. 领导者通过日志复制 RPC 的一致性检查，找到跟随者与自己相同日志项的最大索引值。即，在该索引值之前的日志，领导者和跟随者是一致的，之后的日志，就不一致了
  2. 领导者强制将跟随者该索引值之后的所有日志项删除，并将领导者该索引值之后的所有日志项同步至跟随者，以实现日志的一致

因此，处理领导者与跟随者日志不一致的关键是找出上述的最大索引值。

Raft 引入两个变量，来方便找出这一最大索引值：

  • prevLogIndex：表示领导者当前需要复制的日志项，前面那一个日志项的索引值。例如，下图，如果领导者需要将索引值为 8 的日志项复制到跟随者，那么 prevLogIndex 为 7
  • prevLogTerm：表示领导者当前需要复制的日志项，前面一个日志项的任期编号。例如，下图，如果领导者需要将索引值为 8 的日志项复制到跟随者，那么 prevLogTerm 为 4

下面以上图为例描述领导者如何通过日志复制 RPC 的一致性检查，找到跟随者与自己相同日志项的最大索引值：

  1. 领导者通过日志复制 RPC 消息，发送当前自己最新日志项给跟随者，该消息的 prevLogIndex 为 7，prevLogTerm 为 4
  2. 由于跟随者在其日志中，无法找到索引值为 7，任期编号为 4 的日志项，即跟随者的日志和领导者的不一致，故跟随者会拒绝接收新的日志项，返回失败
  3. 这时，领导者递减 prevLogIndex 值为 6，prevLogTerm 变为 3，重新发送日志复制 RPC 消息
  4. 此时，跟随者在其日志中，找到了索引值为 6，任期编号为 3 的日志项，故跟随者返回成功
  5. 领导者收到跟随者成功返回后，知道在索引值为 6 的位置之前的所有日志项，均与自己的相同。于是通过日志复制 RPC ，复制并覆盖索引值为 6 之后的日志项，以达到跟随者的日志与领导者的日志一致

领导者通过日志复制 RPC 一致性检查，找到跟随者与自己相同日志项的最大索引值，然后复制并覆盖该索引值之后的日志项，以实现集群内各个节点日志的一致。
需要指出的是，日志复制过程中，只有跟随者的日志项会被领导者的日志覆盖更新，领导者的日志从不会被覆盖或删除。

参考资料