Raft 算法——日志复制

标签：分布式系统首次发布：2023-11-30最近修改：2023-11-30

想象一下，一个木筏（Raft）是由多根整齐一致的原木（Log）组成的，而原木又是由木质材料组成，所以你可以认为日志是由多条日志项（Log entry）组成的，如果把日志比喻成原木，那么日志项就是木质材料。

在 Raft 算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和应用日志项到状态机的过程。

Raft 日志

前面提到，日志是由日志项组成，日志项究竟是什么样子呢？其实，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。那你该怎么理解这些信息呢？

image-20231129143334566

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

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

日志复制

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

image-20231129144749055

  1. 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
  2. 领导者为每一个跟随者广播日志复制 RPC，将新的日志项复制到其他的服务器。
  3. 跟随者在成功接收到领导者的日志 RPC 后会返回一个确认信息，如果领导者接收的确认信息的条数超过机器集群数量的半数，那么领导者就会将日志项应用到它的状态机中（执行客户端的指令）。
  4. 领导者将执行的结果返回给客户端。
  5. 当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机中。

不过，这是一个理想状态下的日志复制过程。在实际环境中，复制日志的时候，你可能会遇到进程崩溃、服务器宕机等问题，这些问题会导致日志不一致。那么在这种情况下，Raft 算法是如何处理不一致日志，实现日志的一致的呢？

日志一致性

Raft 算法设计了以下日志机制来保证不同节点上日志的一致性。

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

第一条特性的满足条件在于，领导人在一个任期里在给定的一个日志索引位置上最多创建一条日志条目，同时该条目在日志文件中的槽位永远也不会改变。

第二条特性的满足条件在于，日志复制RPC有一个简单的一致性检查。领导者在发送一个日志复制 RPC 消息试图向其他节点追加新的日志条目时，会把这些新日志项之前一个槽位的日志项的任期号和索引位置包含在消息体中。如果跟随者在它的日志文件中没有找到相同的任期号和索引的日志，它就会拒绝该日志复制 RPC，即拒绝在自己的状态机中追加新日志项。

在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft 是通过以领导者的日志为准，来实现各节点日志的一致的。具体有 2 个步骤。

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

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

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

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

image-20231129152034766

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

image-20231129152248835

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

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