日志复制

Raft 中日志的组织形式如下图所示,每个 日志条目(LogEntry)都包含一条命令、 任期(Term)信息,以及一个正整数 索引(Log Index) 来标记其在日志中的位置。索引在不同的任期可以重复,但在同一任期内必须唯一。

日志条目在节点中的状态通过两个变量控制:CommitIndexLastApplied,通过这两个变量就可以让日志条目在以下三个状态中进行转换:

  • 已写入:日志条目 Append 到节点上,未进行其他操作,日志条目可以只存在内存中
  • 已提交:Leader 把日志条目复制到集群中大多数节点,Leader 通过更新 CommitIndex 将日志条目置为提交状态。
  • 已应用:Leader 通过 AppendEntries 请求将自己的 CommitIndex 通知给其他节点,其他节点进行提交操作,当大多数节点提交完成后,Leader 更新自己的 LastApplied 并将日志条目中的命令应用到状态机中。

日志状态通过 AppendEntries 请求完成的,如果 Follower 由于故障或网络延迟等原因,未能返回成功,则 Leader 会持续重试 AppendEntries 直到 Follower 返回成功。当 Leader 应用某条日志条目后,就可以返回给客户端了。

当集群中大多数节点,把日志条目提交后,这个日志条目就是 持久 的,并且最终会被所有状态机执行。当 Leader 将创建的日志条目复制到超过半数的节点时,就可以提交这个日志条目,比如:下图中的第五个日志条目$e_5$。当 $e_i$ 被提交时,对于任意 $j<i$ 日志条目 $e_j$ 也都会被提交,即使是 前一个任期 的。

Leader 会将自己的 CommitIndex,放在 AppendEntries 请求中,这样即使其他节点故障,当其恢复时也能感知到。一旦 Follower 发现某个日志条目已提交,则 Follower 会将其应用到本地状态机。

日志一致性

Raft 的日志机制让整个集群的行为十分简单和可预测,同时也是保证安全性的重要环节。Raft 保证如果两个日志序列包含具有相同 索引任期 的日志条目,则直到这个日志条目的所有日志条目都是相同的,这个属性被称为 日志一致性。Raft 通过以下两个属性来保证日志一致性:

  1. 如果不同的日志序列中的两个日志条目具有相同的 索引 和 任期,那么这两个日志条目包含相同的命令
  2. 如果不同的日志序列中的两个日志条目具有相同的 索引 和 任期,那么这两个日志条目 之前 的所有日志条目均一致

Leader 在同一任期内不会创建具有相同索引的日志条目,并且在日志复制过程中,也不会修改日志条目的相关信息,因此第一条属性成立。

当 Leader 在发送 AppendEntries 请求时,会将本地最新日志的前一个日志的索引和任期信息添加到请求中,如果 Follower 在其本地日志中没有匹配上前一个日志,则拒绝本次请求,这就是 AppendEntries日志一致性校验。这个日志一致性校验就保证了第二条属性,可通过以下步骤进行归纳:

  • 初始化状态下,由于没有日志,所以 “日志一致性” 满足
  • 当日志增长时,日志一致性校验可以保证 “日志一致性”

最后,只要 AppendEntries 返回成功,则 Leader 就知道 Follower 的日志与自己最新日志之前的日志保持同步。

日志截断

在正常状态下,Leader 和 Follower 的日志均保持一致, AppendEntries 的日志一致性校验也不会失败。但是当 Leader 故障时,就可能导致不一致的情况,比如:Leader 故障前,没能把日志复制到所有的节点。这种不一致可能同时在多个节点出现,下图展示了 Follower 与新的 Leader 不一致的情况。Follower 可能缺少了一些 Leader 上的日志,可能有多余的日志,也可能两种情况都存在。

上图中,当新 Leader 被选出后,Follower 上日志的状态可能为 a-c 这三种,其中每个方格里的数字表示日志的 Term。(a)表示 Follower 上的日志有缺少,(b)表示 Follower 上的有未提交的日志,(c)表示即有缺少也有多余未提交的日志。

Raft 算法在处理日志不一致的时候,采取 日志截断 的方式,将 Leader 的日志强制覆盖本地的日志。为了将 Follower 的日志状态与自己同步,Leader 需要找到自己的日志和 Follower 日志的公共祖先,就好比两个分叉的链表,需要找到分叉的那个 LogEntry,比如下图中 Log Index 为 3 的 LogEntry

在找到这个日志条目Base 后,Leader 将之后的日志条目按顺序发送给 Follower,Follower 则从 Base 开始覆盖本地日志。这里的所有操作,均通过 AppendEntries 请求完成。

Leader 为每个 Follower 都记录一个变量 nextIndex,表示下一个需要发送给 Follower 的日志索引。当节点转变为 Leader 时,每个 Follower 的 nextIndex 均初始化为下一个日志条目的索引,在上图中为 7。

如果 Follower 的日志与 Leader 不一致,则 AppendEntries 会返回失败,并且 Leader 会递减 nextIndex 再次发起 AppendEntries。最终,nextIndex 会到达一个点,在这个点上 Follower 和 Leader 的日志条目一致。这时,AppendEntries 的日志一致性校验就会成功,Follower 删除不一致的日志,并把 Leader 的日志追加到本地。这样持续追加,Follower 的日志就和 Leader 的日志保持一致。

在这种日志复制的机制下,为了将集群日志恢复为一致的,Leader 不需要进行任何特殊的操作,只需要和正常情况下发送 AppendEntries 请求,在日志一致性校验的作用下,不一致的日志就会自动的变为一致。这样 Leader 就只会追加日志,而不需要删除或覆盖自己的日志。

可用的优化

上面有提到,当不一致发生时,Leader 需要通过请求 “探测” 出一个 Base 节点。理论上来说,这种 “探测” 是低效率的,可以通过修改通信协议,比如:当日志一致性校验失败时,Follower 返回请求 Term 里最小的 Log Index,这样就可以大量减少这种重试。但 Raft 设计者认为,不一致是不常发生的,并且不会有这么多不一致的日志。这种优化会增加算法的复杂度,所以 Raft 算法没有进行这个优化。

前任的日志

当 Leader 将日志复制到超过半数节点后,就会提交这个日志。如果在提交前,Leader 故障了,那么新任 Leader 会尝试完成这个日志的复制过程。然而,新 Leader 不能很快的计算出之前的日志是否已经复制到超过半数的节点。

在上图中展示了一种情况,如果 Raft 新节点 “手动” 提交日志条目所可能发生的情况。

  • (a)S1 作为任期 2 的 Leader,在索引 2 的位置写入新条目,并且复制到部分节点,未提交。
  • (b)S1 故障,S5 被选举为任期 3 的 Leader,在索引 2 的位置写入新条目
  • (c)S5 故障,S1 重新被选举为任期 4 的 Leader,在索引 3 的位置写入条目,并且继续复制之前任期的日志
  • (d)这里就有可能出现两种情况
    • (d1)如果在上一步,S1 复制完成后提交了索引 2 的日志,并且返回给客户端,那么当 S1 故障,S5 重新被选举为任期 5 的 Leader,就会覆盖已提交的日志
    • (d2)S1 继续复制索引 3 的日志,并且在复制到大多数节点后进行提交,这时索引 2 的日志条目也被提交,并且 S5 不会再被选举为 Leader

在上面的示例中,由于 S1 “手动” 提交了日志,导致新 Leader 可以覆盖已提交的日志。为了防止这种情况, Raft 采取上图中 d2 的方式。新 Leader 不会提交前任的日志,而是提交当前任期的日志,根据 “日志一致性” 原则,前任的日志也会被提交和应用。当然,如果新 Leader 能将日志复制到所有节点上,那么它也可以直接提交前任的日志,但 Raft 为了简单没有选择这样做。