MIT 6.824 - Lab 2 (1): Students' Guide to Raft

Posted on Word count in article: 6.3k Reading time ≈ 10 mins.

Students’ Guide to Raft 是 MIT 6.824: Distributed Systems 之前的助教写给学生看的实验生存指南。

实现 Raft

论文中的 Figure 2 和 Figure 13 描述了实现 Raft 的主要接口，以及各节点需要维护的状态和响应接口时的行为逻辑，所以在做 Lab 2 之前需要先充分理解这部分的内容。文中的建议是必须严格落实图中的每一句话，而不是仅仅实现了功能，否则就有可能遇到奇怪的问题或不正确的系统行为。

文中举了三个例子。第一，每次收到 AppendEntries 或 RequestVote 请求就重置 election timeout，因为收到这两个请求说明存在主节点或者正在选主。不过，图中还有描述：

If election timeout elapses without receiving AppendEntries RPC from current leader or granting vote to candidate: convert to candidate.

重置 election timeout 有两个关键条件：AppendEntries 要求发送请求的主节点是当前任期的主节点；RequestVote 要求成功投出选票。

先看第一个条件，假设当前任期的主节点异常，此时还有一个之前任期的主节点存活在不断发送 AppendEntries 请求，假设此时某个从节点马上要进入选主状态，但由于收到了 AppendEntries 请求又没有校验任期就重置了 election timeout，造成无主状态时间延长。这个场景下如果过期的主节点不实现下面的逻辑杀伤力倍增：

If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower

如果不实现上面的逻辑，那么过期的主节点会一直是主节点，然后一直重置其他本来可以成为候选节点的从节点。

再来看第二个条件，假设当前任期的主节点异常，各从节点准备进入选主状态，此时一个不可能成为主节点的从节点先变成了候选节点（该节点的日志相对于其他任何一个从节点来说都不够新，即最后一条日志的任期不够大，或者任期相同但是日志条数不够多），RequestVote 永远不会成功，如果各从节点一收到 RequestVote 就重置 election timeout，就会造成始终没有主节点的情况。

第二个例子，从节点收到心跳 AppendEntries 后就直接返回 success = true 和重置 election timeout。重置 election timeout 的危害上面已经说过，充当心跳的 AppendEntries 是不带日志的请求，文中提到学生在实现时容易将心跳 AppendEntries 特殊对待，而不进行 prevLogIndex 和 prevLogTerm 的校验。从节点返回 true 时主节点就会认为从节点的日志和自己匹配，从而错误的认为某些日志已经复制到了从节点上，从而可以提交日志。不过看到这里可能会有疑问，为什么主节点会在心跳响应中提交日志？通过心跳更新 nextIndex 和 matchIndex 是合理的，如果过半数节点已复制的日志是之前任期的，论文中有描述这是不允许提交的；如果过半数节点已复制的日志是当前任期的，那么可能是之前带日志的 AppendEntries 请求中从节点实际已完成了日志的复制，但是主节点没有收到响应，所以在最新的心跳中提交日志。

引申开来，假设系统中此时 x = 1，有个客户端发送了 write x = 2 的请求，主节点成功将日志复制到了过半数的节点上，但是还没有响应客户端就异常了。系统重新选主后，此时有个客户端发送请求 read x，x 应该返回多少？应该是2，因为在 Raft 层面，一条日志是否已提交只取决于是否在当前任期内复制到了过半数的节点上，而不是取决于客户端是否收到响应，而只要日志提交了就可以被应用到状态机。类似的场景可以想象一下平时填了某个表单，提交时提示系统异常，但是刷新页面后表单信息已更新。

第三个例子，学生在实现 AppendEntries 时，可能将 prevLogIndex 之后的日志都替换为请求中的日志。同样的，图中也有描述：

If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it.

因为当前的 AppendEntries 可能是个过期的请求，假设请求中的日志只是当前从节点已提交的日志的某一段子集，那么如果从节点将 prevLogIndex 之后的日志都替换为请求中的日志就会丢失已提交的日志。

调试 Raft

调试是实验中最花时间的一个部分，文中列举了四个常见的问题：活锁，不正确或不完整的 RPC 实现，没有遵循论文中的 Rules for Servers 以及任期混淆。

活锁

出现活锁时，等同于各节点都在做无用功。选主是最容易出现活锁的场景，例如始终无法选出一个主节点，或者某个候选节点获得了足够的选票后，马上有另外一个节点发起选主，使得刚成为主节点的节点重新退回到从节点（某个节点成为主节点后，还没来得及发送心跳，刚投了票的某个节点 election timeout 到期，发起新的选主，由于它的任期加了1比当前的主节点的任期大，主节点收到 RequestVote 后发现自己的任期小，从而转为从节点）。

常见的原因有以下几种：

第一，没有严格按照 Figure 2 的要求重置 election timeout。重置 election timeout 仅限于几种情况：

  1. 收到当前任期的主节点的 AppendEntries 请求（如果 AppendEntries 中的任期比自身的任期小，则忽略该请求）。
  2. 开启一轮新的选主，这个属于 election timeout 到期，选主的同时需要重置一个新的随机值。
  3. 在某轮选举中，将票投给了某个候选节点。

第二，没有按照 Fiture 2 的要求开启选主。特别的，如果当前节点是候选节点，但是 election timeout 到期了，那么需要开启新的一轮选主。

第三，没有遵循 Rules for Servers 的第二条：

If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower (§5.1)

例如，当前节点已投票，按照 Raft 的要求，一个从节点在一个任期内只能投票一次，此时又收到了一个 RequestVote 请求，请求中的任期大于自身的任期，那么就需要再次投票并更新自身的任期，避免新的候选节点拿不到足够的选票。

不正确的 RPC 实现

这里总结了学生们过往在实现 RPC 接口时容易犯错的点：

  • 如果某一步要求 reply false，那么这说明需要立即回复 false 并返回，不要再执行后续的步骤。
  • 如果收到了一条 AppendEntries 请求，但是请求中的 prevLogIndex 比当前日志的最后一条的索引还要大，也要返回 false，这也属于日志不匹配。
  • 如前面描述，即使 AppendEntries 没有包含任何日志，接收方也需要校验 prevLogIndex 和 prevLogTerm。
  • AppendEntries 中的第五步的 min 是有必要的，而且是和新日志中的最后一条日志的索引相比较，而不是当前日志的最后一条索引。
    • 首先来看 leaderCommit < index of last new entry 的情况，假设 S1 为主节点，日志为 [1, 2, 3, 4, 5]，leaderCommit 为3（索引按从1开始算），S2 为从节点，日志为 [1, 2]，那么 S1 需要将 [3, 4, 5] 发给 S2，S2 收到后 index of last new entry 是5，但是 commitIndex 只能更新到 3，也就是 leaderCommit，因为 [4, 5] 还没有提交。
    • 然后来看 leaderCommit > index of last new entry 的情况，乍看之下好像不可能，因为对于主节点来说，在添加一条新日志的那个时刻，leaderCommit 肯定小于新的日志的索引，复制日志到从节点时这个关系也不会变。这里只能想到的是，leaderCommit 被并发修改了，因为主节点不会删除日志，所以 index of last new entry 不会变，当主节点和从节点的日志不匹配时，主从节点需要来回的就 prevLogIndex 和 prevLogTerm 达成一致（或者单纯就是因为执行的慢），在这个期间，可能过半数的节点已经达成了完成日志复制，主节点就可以提交这条日志，并更新 leaderCommit，所以在原先的 AppendEntries 中，如果 leaderCommit 引用的是全局变量，而 entries[] 是固定的，就会造成 leaderCommit 的值比 entries[] 的最后一条日志的索引还要大，这个时候从节点的 commitIndex 就需要取 index of last new entry。文中举了个例子说明为什么这时候不能取 leaderCommit，假设 S1 为主节点，日志为 [1, 2, 3, 6]，leaderCommit 为3，S2 为从节点，日志为 [1, 2, 3, 4, 5]，那么 S1 需要将 [6] 发给 S2，注意这里 prevLogIndex 和 prevLogTerm 校验通过，而论文中只提到校验不通过时才删除从节点的日志，所以这里就不会删除 S2 的 [4, 5]，又假设此时 S1 通过其他节点的交互将日志成功提交到了 [1, 2, 3, 6, 7]，leaderCommit 变为了第5个位置，S2 收到的 AppendEntries 中 leaderCommit = 5，entries = [6]，如果按照最新的 leaderCommit 更新就会造成把 S2 日志中的5归为已提交。
  • 严格按照论文5.4节的描述来比较两个节点的日志哪个较新，不要只比较日志的长度。

未遵循 Rules for Servers

  • 如果 commitIndex > lastApplied，说明可以应用新的日志到状态机中。应用到状态机的顺序必须严格按照日志的顺序，可以由一个单独的线程顺序执行，也可以由多个线程并行执行，但各线程间必须确保不互相干扰，避免执行覆盖，对于同一个变量的不同写请求，多线程间必须按照日志的顺序写入。
  • 确保周期性的检查 commitIndex > lastApplied 或者在 commitIndex 更新后检查（在 matchIndex 更新后）。这里并没有太明白这个问题，作者举了个例子，假设现在主节点发出了 AppendEntries 请求并同时检查 commitIndex，如果这条日志被过半数的节点复制了，那么需要等到主节点再添加一条新日志后才能应用上一条日志到状态机。不过根据这个例子也没有看出两者的关联，因为如果采用单线程顺序应用日志到状态机的方式，如果 commitIndex > lastApplied 不满足，线程可以先睡眠然后再尝试，除此以外没有依赖其他条件。
  • 假设主节点发出 AppendEntries 请求然后被拒绝了，如果不是因为日志不一致被拒绝，那么这个主节点就必须马上转为从节点，且不能更新 nextIndex，因为这说明当前主节点的任期小于从节点。如果错误的更新了 nextIndex，而这个主节点在转为从节点后又当选了主节点，就会造成 nextIndex 和从节点永远不会匹配的情况（相当于错位了一格）。
  • 如果主节点发现某条过去任期的日志被大多数的节点复制了，但是自身的 commitIndex 却小于这条日志的索引，此时主节点也不能够更新 commitIndex，这个就是论文中 Figure 8 描述的问题，提交一条之前任期的日志存在被新一轮的主节点覆盖的风险。所以提交日之前需要判断 log[N].term == currentTerm。

有一个常见的困惑是 nextIndex 和 matchIndex 的区别。你可能会观察到 matchIndex = nextIndex - 1，然后用 nextIndex 来替代 matchIndex，然而这是有风险的。举一个很明显的反例，假设某个节点被选为主节点，此时收到一个客户端请求并添加了一条日志，那么它发给从节点的 nextIndex 就是最后一条日志的下一条，而 matchIndex 显然不是 nextIndex - 1（新添加的日志的索引）。

任期混淆

任期混淆指的是节点收到了来自之前任期的 RPC 请求。Figure 2 清晰的描述了收到过期任期的请求应该怎么做，但是并没有说明收到过期任期的响应应该怎么做。一个简单的做法就是比较响应中的任期和当前的任期，如果相等则执行相应的逻辑，如果当前任期小则转为从节点（只有主节点、候选节点才能发请求，才有收到响应的可能），如果当前任期大则不处理。

还有一个相关但不同的问题，假设主节点收到 AppendEntries 响应后设置 matchIndex = nextIndex - 1 或 matchIndex = len(log)，这都是不安全的，因为 nextIndex 和 len(log) 在这期间都有可能改变，正确的做法应该是使用原始请求中不变的参数，即 matchIndex = prevLogIndex + len(entries[])。

关于性能

实验中会要求实现两个关于性能方面的优化，一个是日志压缩，另一个是快速确认正确的 prevLogIndex。

关于日志压缩需要注意几点：

  • 当执行快照时，需要确保快照中的状态和指定日志中的索引是严格对应的，即快照不能落后于日志，也不能超前。
  • 论文中并没有描述当节点异常然后恢复后应该如何处理快照。论文中要求创建完快照后，需要删除快照所对应的日志，而系统可能在删除日志前异常，那么系统恢复后会根据快照和日志进行重放。文中说系统可能会重放已经在快照中的日志，这里有点疑问，因为快照中包含了 lastIncludedIndex 和 lastIncludedTerm，和当前日志进行对比就能知道哪些日志已经在快照中了，从而可以跳过。

论文中并没有详细描述如何快速确认正确的 prevLogIndex，这部分的逻辑可以参考 6.824 2022 Lecture 7: Raft (2) 或者文中的建议：

  • 如果从节点在 prevLogIndex 处没有日志，说明从节点的日志较短，则返回 conflictIndex = len(log) 以及 conflictTerm = None。
  • 如果从节点在 prevLogIndex 处有日志，但是日志对应的任期不匹配，那么返回 conflictTerm = log[prevLogIndex].Term，然后找到属于 conflictTerm 的第一条日志的索引。
  • 主节点收到 conflictIndex/conflictTerm 后，首先在日志中搜索 conflictTerm，如果找到有日志属于 conflictTerm，那么 nextIndex 需要更新为主节点中属于 conflictTerm 的最后一条日志的索引加1。
  • 如果主节点没有找到属于 conflictTerm 的日志，那么更新 nextIndex 为 conflictIndex。

其中一个不完善的实现是只考虑 conflictIndex 而忽略了 conflictTerm，这样会简化实现，不过主从节点交互的次数会变多，因为如果考虑了 conflictTerm，那么一次性能跳过的日志会更多。

最后一部分的 Applications on top of Raft 属于 Lab 3 的内容，即基于 Raft 构建应用，在 Lab 2 中暂不描述。

参考