Raft 共识算法3-日志复制

Raft 共识算法3-日志复制

Raft算法中译版地址：https://object.redisant.com/doc/raft中译版-2023年4月23日.pdf

英原论文地址：https://raft.github.io/raft.pdf

Etcd Assistant 是一款 etcd 可视化管理软件，便捷高效地操作您的 etcd 集群；支持多种键的视图；管理租约、用户、角色和权限。

一旦领导者被选出，它就开始为客户请求提供服务。 每个客户端请求都包含要由复制状态机执行的命令。 领导者将该命令作为新条目附加到其日志中，然后向每个其他服务器并行发出 AppendEntries RPC 以复制该条目。 当条目已被安全复制（如下所述）后，领导者将条目应用于其状态机并将该执行的结果返回给客户端。 如果跟随者崩溃或运行缓慢，或者网络数据包丢失，领导者会无限期地重试 AppendEntries RPC（即使在它已经响应客户端之后）直到所有跟随者最终存储所有日志条目。

日志的组织方式如 @fig6 所示。每个日志条目都存储一个状态机命令以及领导者收到该条目时的任期号。 日志条目中的任期号用于检测日志之间的不一致，并确保 @fig3 中的某些属性。每个日志条目还有一个整数索引，用于标识其在日志中的位置。

fig6.png

日志是由条目组成的，这些条目按顺序编号。每个条目都包含创建它的任期（每个框中的数字）和状态机的命令。如果一个条目已被安全复制，那么该条目就被认为是已提交的。

领导者决定何时将日志条目应用到状态机是安全的； 可以被安全地应用到状态机的条目称为已提交的。 Raft 保证已提交的条目是持久的，并且最终会被所有可用的状态机执行。 一旦创建条目的领导者已将其复制到大多数服务器（例如，@fig6 中的条目 7），那么该日志就被称为已提交的（此时将该日志条目应用到状态机是安全的）。 这也会提交领导者日志中所有先前的条目，包括前任领导者创建的条目。 5.4 节讨论了在领导者变更后应用此规则时的一些微妙之处，并且还表明此提交定义是安全的。 领导者跟踪它知道的已提交条目的最高索引，并将该索引包含在未来的 AppendEntries RPC（包括心跳）中，以便其他服务器最终找到。 一旦跟随者得知日志条目已提交，它会将条目应用于其本地状态机（按日志顺序）。

我们设计了 Raft 日志机制来保持不同服务器上的日志之间的高度一致性。 这不仅简化了系统的行为并使其更具可预测性，而且还是确保安全的重要组成部分。 Raft 维护了以下属性，它们共同构成了 @fig3 中的日志匹配（Log Matching ）属性：

• 如果不同日志中的两个条目具有相同的索引和任期，则它们存储相同的命令。
• 如果不同日志中的两个条目具有相同的索引和任期，则在该条目之前的所有条目都是相同的。

第一个属性源于这样一个事实，即领导者在给定任期内最多创建一个具有给定日志索引的条目，并且日志条目永远不会改变它们在日志中的位置。 第二个属性由 AppendEntries 执行的简单一致性检查保证。 当发送 AppendEntries RPC 时，领导者在其日志中包含紧接在新条目之前的条目的索引和任期。 如果跟随者在其日志中没有找到具有相同索引和任期的条目，那么它会拒绝新条目。 一致性检查作为一个归纳步骤：日志的初始空状态满足日志匹配属性，并且只要追加日志，一致性检查就会保留日志匹配属性。 因此，每当 AppendEntries 成功返回时，领导者就知道了跟随者的日志与自己的日志相同。

在正常运行期间，领导者和跟随者的日志保持一致，因此 AppendEntries 一致性检查永远不会失败。 但是，领导者崩溃可能会使日志不一致（旧领导者可能没有完全复制其日志中的所有条目）。 这些不一致可能会导致一系列领导者和追随者崩溃。 @fig7 说明了跟随者的日志可能与新领导者的日志不同的情况。 跟随者可能缺少领导者中存在的条目，它可能具有领导者中不存在的额外条目，或两者兼而有之。 日志中缺失和多余的条目可能跨越多个任期。

fig7.png

当领导者上台时，追随者日志中可能会出现任何场景 (a–f)。 每个方框代表一个日志条目； 框中的数字是它的任期。 追随者可能缺少条目 (a–b)，可能有额外的未提交条目 (c–d)，或两者都有 (e–f)。 例如，如果该服务器是任期 2 的领导者，则可能会发生场景 (f)，向其日志添加多个条目，然后在提交其中任何一个之前崩溃； 它很快重新启动，成为第 3 任期的领导者，并在其日志中添加了更多条目； 在任期 2 或任期 3 中的任何条目被提交之前，服务器再次崩溃并保持停机几个任期。

在 Raft 中，领导者通过强制追随者的日志复制自己的日志来处理不一致。 这意味着跟随者日志中的冲突条目将被领导者日志中的条目覆盖。 第 5.4 节将表明，在再加上一个限制时，这是安全的。

为了使跟随者的日志与其自己的一致，领导者必须找到在跟随者的日志中和自己一致的最新日志条目，然后在跟随者日志中删除该点之后的所有条目，并将该点之后的所有领导者日志条目发送给跟随者。 所有这些操作都在通过 AppendEntries RPC 执行的一致性检查时发生。 领导者为每个跟随者维护一个 nextIndex，这是领导者将发送给该跟随者的下一个日志条目的索引。 当一个领导者第一次掌权时，它会将所有 nextIndex 值初始化为其日志中最后一个索引之后的索引（@fig7 中的 11）。 如果跟随者的日志与领导者的日志不一致，则在下一个 AppendEntries RPC 中，一致性检查将失败。 拒绝后，领导者递减 nextIndex 并重试 AppendEntries RPC。 最终 nextIndex 将达到领导者和跟随者日志匹配的点。 当发生这种情况时，AppendEntries RPC 将成功，它会删除跟随者日志中的所有冲突条目并追加领导者日志中的条目（如果有的话）。 一旦 AppendEntries RPC 成功，跟随者的日志与领导者的一致，并且在剩余的任期内保持这种状态。

如果需要，可以优化协议以减少被拒绝的 AppendEntries RPC 的数量。 例如，当拒绝 AppendEntries 请求时，跟随者可以包括冲突条目的任期和它为该任期存储的第一个索引。 有了这些信息，领导者可以减少 nextIndex 以绕过该任期中的所有冲突条目； 每个有冲突条目的任期都需要一个 AppendEntries RPC，而不是每个条目一个 RPC。 在实践中，我们怀疑这种优化是否必要，因为故障很少发生，而且不太可能有很多不一致的条目。

使用这种机制，领导者上台时不需要采取任何特殊措施来恢复日志一致性。 它刚刚开始正常运行，日志自动收敛以响应 AppendEntries RPC 一致性检查的失败。 领导者永远不会覆盖或删除自己日志中的条目（@fig3 中的领导者仅附加（Leader Append-Only）属性）。

这种日志复制机制展示了第 2 节中描述的理想的共识属性：只要大多数服务器正常运行，Raft 就可以接受、复制和应用新的日志条目； 在正常情况下，可以通过单轮 RPC 将新条目复制到集群的大多数； 单个慢速跟随者不会影响性能。