MIT 6.824 Lab2 Raft

最近突然想再刷一下 6.824，想试试自己现在做会不会容易得多。上次做已经是大二的时候了，对之前的代码已经毫无记忆了（而且也写得不咋样）。因为 Lab1 MapReduce 没什么难度，感觉兴趣不大，我这次就跳过了，直接从 Lab2 开始。

遵从课程本身的要求，这里不共享实现代码，如果你遇到问题，欢迎联系我一起交流。

这里小小吐槽一下，课程中建议不要使用 time.Ticker，但是我觉得 time.Sleep 更容易写错……总之如果不是之前没写过 golang 的话，建议还是忽略课程中对于语言相关的建议。

Lab2A 选举实现

2A 部分的目标是实现 Raft 的选举机制：

  • 实现 RequestVote
  • 添加 AppendEntries，但不需要完整实现论文中的描述
  • 实现角色的转换逻辑，即 Follower、Candidate 和 Leader 之间的转换和对应的处理逻辑
  • 实现选举逻辑

触发选举

触发选举的条件是：为 Follower，且在 ElectionTimeout 时间内，没有收到合法的 RPC 请求。在触发选举后，转为 Candidate，并开始不断执行选举，每次选举之间需要间隔 ElectionTImeout。需要注意，ElectionTimeout 并不是一个固定值，在论文中，它是 150ms ~ 300ms。在这个 Lab 中，需要设得偏大一些，参考值是 650ms ~ 900ms。

选举流程

一个节点要开始选举后：

  1. 转为 Candidate，自增 Term，为自己投票
  2. 发送 RequestVote 到其它所有节点
  3. 如果获得多数票，则成为 Leader

选举过程中，如果发现其它节点的 Term 更大，则放弃选举，转为 Follower。

选举流程如果没有做任何优化，在部分节点网络故障时很容易发生选举花费太长时间，节点之间轮流为对方投票，导致没有节点胜出的情况。这里在实现上需要注意几个点：

  • 发送请求必须是并发的
  • 不需要等待所有 RPC 返回
    • 如果已经获得了多数票，则可以直接结束
    • 如果已经确定无法获得多数票，也可以提前结束

心跳机制

一旦集群中出现了 Leader，就需要靠 heartbeat 去让 Follower 不要发起新的选举，heartbeat 间隔需要是一个比 ElectionTimeout 小得多的值，Lab 中的测试限制了 heartbeat 的频率为每秒最多 10 次，因此可以直接取 100ms 作为 heartbeat 间隔。

Leader 发送心跳的流程优化与选举类似，这个流程不应该同步地等待所有 RPC 返回，因为如果有节点掉线，一轮心跳就会花费太长的时间，导致 Follower 发起选举。

Lab2B log 复制

在 Lab2B 中需要实现 log 的复制，处理节点上下线，集群切主这些情况下的 log 的一致性。这个阶段需要完整实现 AppendEntries，以及 leader 复制 log 的处理逻辑。Lab2B 难度会比 2A 高一些，但是代码并不多。首先需要理解清楚 Raft 的几个概念。

Commit & Apply

这里简单说一下 log 的复制流程：

  • 在 leader 收到写入请求后，它首先把这条 log entry 写到自己的 logs 里
  • leader 会维护每个节点已经复制到的下标，即 matchIndex
  • leader 还需要维护要复制到每个节点的 log 的起始下标，即 nextIndex
  • leader 在每次心跳时把从 nextIndex[id] 开始的 log 复制给节点
  • 当多数节点都收到了一条 log，则认为这条日志可以 commit，leader 更新自己的 commitIndex
  • 在一条 log 被 commit 后，即认为这条日志可以 apply

这里需要注意一些细节：

  • 会注意到似乎总是有 nextIndex == matchIndex + 1，在多大时候，这一点是满足的。但在 leader 刚被选举出来时上面的条件并不满足。matchIndex 是确定的已经成功复制到节点的 log 最大下标，而 nextIndex 是可能的节点缺失的 log 的起始下标。
  • 由于 nextIndex 是一个猜测值，因为当这个猜测不正确时，follower 会拒绝复制请求中的 logs，这时 leader 需要调整 nextIndex 的值，如果只是简单的 nextIndex -= 1，可能无法通过测试，可以设计一些简单的算法来让这个值减小得更快，来更快找到匹配点。
  • commit 与 apply 其实是独立的两个执行流，commitIndex 是最大可以 apply 的 log 下标。每个节点可以用一个 goroutine 去不断比较 lastApplied 和 commitIndex 去决定是否要 apply log。

边界情况

考虑这样一种 case（下标为 term 值）：

Server/Time t1 t2 t3 t4 t5 t6
S1 (leader) X1X_1 Y1Y_1 发现 S3 的 term 更大，转为 follower 因为有更长的 logs，再次成为 Leader
S2 X1X_1 Y1Y_1
S3 X1X_1 与 S1, S2 分区 发起选举2_2 网络恢复 Y1Y_1

在 S1 再次成为 Leader 并把 Y 复制到 followers 后，由于 Y 并不是 S1 所在 term 写的 log，因此 S1 不能提交 Y。为了解决这个 case，当一个节点成为 leader 后，需要写一条空 log，来让之前的 logs 能正确提交。在这个 lab 中，由于会检查 command 的类型和下标，所以不能这么做直接。可以暂时忽略这个 case，或者采用比较复杂的方式去 hack 测试。

在这个 Lab 中，apply 操作就是把 command 写入到 applyCh 中，测试通过从 applyCh 中读取 command 来确定日志是否正确复制。

Follower 复制 log

Follower 在收到 AppendEntires 请求时：

  • 检查请求中 prevLogIndex 与 prevLogTerm 是否与自己的 log 匹配
  • 将请求中的 logs 写入到自己的 logs 中
  • 更新 commitIndex，并 apply logs

Follower 将请求中的 logs 写入到自己的 logs 中时，需要从 prevLogIndex + 1 这个位置开始写。这里我的描述与论文中不同，是因为这个 Lab 中，我们可以忽略写 log 的开销，所以可以简化成直接从 prevLogIndex + 1 开始写。更成熟的实现是检查从这个位置开始的日志是否与请求中的 logs 匹配，从第一个不匹配的位置开始写剩余的 logs。

这里 commitIndex 是根据请求中的 leaderCommit 来更新，这个值可能小于这次复制的 log 的起始下标。也就是说，一条 log 被写入，到被提交，其实至少需要两次 AppendEntires RPCs，第一次是复制 log，第二次是更新 commitIndex。

当发生切主，节点上下线这类情况时，落后较多的节点可能会收到一个 leaderCommit 不小于复制的 log 的下标的请求，因为 commit 的条件是多数节点已经复制这条 log。

Log Matching Property

这一性质是指：不同节点的相同下标的 log，如果具有相同的 term，则它们一定是相同的 log，且它们的下标之前的 log 也一定都是相同的。

这一性质是上面的复制机制的正确性保证。满足这条性质的关键点是 follower 会检查 prevLogIndex 和 prevLogTerm。可以用反证法来证明这一性质：

  1. 假设存在两个节点 A，B，它们存在 1 条 log，具有相同的 index 和 term，但不相同，设 index, term 为第一条这样的 log 的 index, term
  2. Term 相同表明这条 log 是由同一个 leader 复制的
  3. 考虑 leader 复制日志到 A，B时，prevLogIndex 与 prevLogTerm 都匹配。则 leader 可以确定复制的下一条 log 为自己的 logs[prevLogIndex+1]
  4. 这与 A，B 上的两条 log 不同冲突

Lab2C 状态持久化

Lab2C 的测试会强很多，持久化本身没有多少代码，也没有什么坑点难点。Lab2C 更多的是可以暴露 Lab2A 和 Lab2B 中不完善的地方。这里提几个容易写错的点：

  • 不能在 ElectionTimeout 内收到了任意请求都不发起选举，只有收到合法请求的情况下才保持 follower 状态
  • votedFor 的含义是本次 term 中投票的对象，当 term 发生变化时，这个值需要重置
  • 投票的条件之一是 follower 的日志不比 candidate 新，需要比较两者的最后一条日志的 term，term 更大的更新，term 相同的情况下 logs 更长的更新
  • Leader 只能 commit 自己 term 的 logs

可以用下面的命令来重复多次测试，达到次数后测试结束或者提前测试失败：

go test -failfast -race -timeout=15m -count 5 -run [TestCase] > test.log

Lab2D Log Compaction

Lab2D 的目标是实现 log compaction，raft 通过 snapshot 来实现 log compaction。

Trim Log

当对下标 ii 创建 snapshot 时，需要丢弃 ii 之前的所有日志。Raft 论文中提到 log 的下标从 1 开始，初始化是可以在 slice 中写一条空 log，而对于 snapshot，则可以选择把 ii 放到 log 的最前面，这样就可以保留 logilog_i 的信息了。

Raft 中的所有下标（commitIndex, lastApplied, nextIndex...）都是逻辑下标，而非 log 中的实际访问下标。在做了 snapshot 之后，需要记录 snapshot 的 log 下标，在后续访问 log 时，提供的是逻辑下标 index，需要转换为实际下标 idx ：

idx = index - snapshotIndex

每次创建 snapshot 时，则修改 snapshotIndex 的值为 snapshot 的下标值。

Lab 中提供的 applyCh 是一个 unbuffered channel，因此如果 apply 协程在 apply 一批数据时持续持有锁，当触发 snapshot 时会导致死锁（与 Snapshot 方法）。所以 apply 过程需要用 select 语句去尝试 apply，并在失败时释放锁，稍后重试 apply。

这里的修改会影响 Lab2B 中的测试，当有多个 servers 在 apply 时，会很高概率 apply 失败，导致 apply 效率太低。因此需要用 context/timer 去让 apply 在超时的情况下才失败，不能直接用 default case。