Raft共识算法图二解释

下面是有关Raft协议中不同术语和概念的翻译及解释：

术语和概念：

• 任期号（term number）：用来区分不同的leader。
• 前一个日志槽位的信息（prelogIndex）：这是前一个日志条目的索引（第几个）。
• 前一个槽位的任期号（prelogTerm）：这是前一个日志条目的任期号。
• 下一个槽位的索引（nextIndex{follow}）：应当给特定追随者（follow）发送的下一个日志条目的索引。
• 快速恢复：特定机制用于解决日志不一致问题。
  • XTerm：在日志不一致时，追随者中与领导者冲突的日志条目对应的任期号。如果追随者在对应位置的任期号不匹配，它会拒绝领导者的AppendEntries消息，并将自己的任期号放在XTerm中。如果在对应位置没有日志，则XTerm为-1。
  • XIndex：在追随者中，对应任期号为XTerm的第一条日志条目的索引。
  • XLen：如果追随者在对应位置没有日志，那么XTerm返回-1，XLen表示空白的日志槽位数。

State：

• 持久化数据：需要在服务器重启后依然保持的数据，包括：

  • 当某个服务器刚刚重启，在它加入到Raft集群之前，它必须要检查并确保这些数据有效的存储在它的磁盘上。服务器必须要有某种方式来发现，自己的
    确有一些持久化存储的状态，而不是一些无意义的数据。
  • Log：所有的日志条目。
  • currentTerm：当前任期号。
  • votedFor：当前任期内投票给的候选人。

• 非持久化数据（适用于所有服务器）：

  • commitIndex：已知已提交的最高日志条目的索引（初始化为0，单调增加）。
  • lastApplied：应用于状态机的最高日志条目的索引（初始化为0，单调增加）。

• 非持久化数据（仅适用于领导者）(选举后重新初始化)：

  • nextIndex[]：对于每个服务器，下一个需要发送的日志条目的索引（初始化为领导者的最后一个日志条目索引+1）。
  • matchIndex[]：对于每个服务器，已知在该服务器上复制的最高日志条目的索引（初始化为0，单调增加）。
    

Rules for Servers：

• All Servers：所有服务器的共通行为规则。

  • 如果 commitIndex > lastApplied：lastApplied 自增，应用 log[lastApplied] 到状态机（§5.3）
  • 如果 RPC 请求或响应包含任期 T 大于 currentTerm：设置 currentTerm = T，转变为追随者（§5.1）

• Followers：追随者的特定行为规则。

  • 对来自候选人和领导者的 RPC 做出响应
  • 如果在没有收到当前领导者的 AppendEntries RPC 或未向候选人授予投票的情况下，选举超时过期：转变为候选人

• Candidates：候选人的特定行为规则。

  • 转变为候选人时，开始选举：
    • 增加 currentTerm
    • 为自己投票
    • 重置选举计时器
    • 向所有其他服务器发送 RequestVote RPC
    • 如果从大多数服务器收到投票：成为领导者
    • 如果收到新领导者的 AppendEntries RPC：转变为追随者
    • 如果选举超时过期：开始新的选举

• Leaders：领导者的特定行为规则。

  • 选举成功后：向每个服务器发送初始的空 AppendEntries RPC（心跳），在空闲期间重复以防止选举超时（§5.2）
  • 如果从客户端收到命令：将条目追加到本地日志，条目应用到状态机后回应（§5.3）
  • 如果最后的日志索引 ≥ 追随者的 nextIndex：从 nextIndex 开始发送 AppendEntries RPC
  • 如果成功：更新追随者的 nextIndex 和 matchIndex（§5.3）
  • 如果因日志不一致导致 AppendEntries 失败：减少 nextIndex 并重试（§5.3）
  • 如果存在一个 N，使得 N > commitIndex，大多数 matchIndex[i] ≥ N，且 log[N].term == currentTerm：设置 commitIndex = N（§5.3, §5.4）。

AppendEntries RPC

目的：由领导者调用以复制日志条目，同时也作为心跳信号，以维持权威并防止超时。

参数：

• term（任期号）：领导者的当前任期。
• leaderId（领导者ID）：领导者的标识符，使得追随者可以在必要时重定向客户端。
• prevLogIndex（前一个日志索引）：紧接在新条目之前的日志条目的索引。
• prevLogTerm（前一个日志条目的任期）：与 prevLogIndex 对应的日志条目的任期。
• entries[]（日志条目数组）：要存储的日志条目（心跳时为空；为了效率可能发送多个）。
• leaderCommit（领导者的提交索引）：领导者的 commitIndex。

结果：

• term（当前任期）：用于领导者更新自己的任期。
• success（成功标志）：如果追随者包含与 prevLogIndex 和 prevLogTerm 匹配的条目，则为真。

接收者实现：

1. 如果 term < currentTerm，回复假（§5.1）
2. 如果日志中不存在在 prevLogIndex 位置且任期与 prevLogTerm 匹配的条目，回复假（§5.3）
3. 如果现有条目与新条目发生冲突（索引相同但任期不同），删除现有条目及其后所有条目（§5.3）
4. 将任何未在日志中的新条目追加到日志中
5. 如果 leaderCommit > commitIndex，将 commitIndex 设置为 leaderCommit 与最后一个新条目的索引中的较小者
   

RequestVote RPC

目的：由候选者调用，用于在选举中收集选票。

参数：

• term（任期号）：候选者的当前任期。
• candidateId（候选者ID）：请求投票的候选者的标识符。
• lastLogIndex（最后日志条目的索引）：候选者最后一个日志条目的索引（§5.4）。
• lastLogTerm（最后日志条目的任期）：候选者最后一个日志条目的任期（§5.4）。

结果：

• term（当前任期）：用于候选者更新自己的任期。
• voteGranted（授予选票）：如果候选者收到了选票，则为真。

接收者实现：

1. 如果 term < currentTerm，回复假（§5.1）
2. 如果 votedFor 为空或等于 candidateId，并且候选者的日志至少与接收者的日志一样新，授予选票（§5.2, §5.4）

要求：

• 具体来说，您应该仅在以下情况下重新启动选举计时器：
  • a) 您AppendEntries从当前领导者处获得 RPC（即，如果参数中的术语AppendEntries已过时，则不应重置计时器）；
  • b) 您正在开始选举；
  • c) 您向另一个同行授予投票权。
• 请按照图 2 的指示了解何时开始选举。特别要注意的是，如果您是候选人（即您当前正在进行选举），但选举计时器触发，您应该开始另一次选举。这对于避免由于 RPC 延迟或丢失而导致系统停顿非常重要。
• 以下是我们一遍又一遍地看到的一些内容，您应该在实施中留意：
  • 如果某个步骤显示“回复错误”，则意味着您应该立即回复，而不是执行任何后续步骤。
  • 如果您收到一个AppendEntriesRPC，其 prevLogIndex指向日志末尾之外，您应该像确实有该条目但术语不匹配一样处理它（即回复 false）。
  • 即使领导者没有发送任何条目，也AppendEntries应该执行 RPC 处理程序的检查 2 。
  • min最后一步（#5）中的是AppendEntries必要的，并且需要使用最后一个新条目的索引来计算。仅仅拥有应用日志中的内容并在到达日志末尾时停止的函数是不够的。这是因为在领导者发送给您的条目（全部与您的日志中的条目匹配）之后，您的日志中可能有与领导者日志不同的条目。因为#3 规定只有在存在冲突条目时才截断日志，这些条目不会被删除，并且如果 超出领导发送给您的条目，您可能会应用不正确的条目。lastApplied``commitIndex``leaderCommit
  • 严格按照第 5.4 节中的描述实施“最新日志”检查非常重要。没有作弊，只是检查长度！