【公开课】MIT 6.824 Lab 2（Raft）

最近写完了 MIT-6.824 的 Lab，收获非常多。所有 Lab 的内容加在一起是实现一个基于 Raft 的分布式可分片的容错 Key/Value Service，对于编写并发代码以及调试分布式程序有了更深刻的认识。写这几篇文章的目的是为了总结实现过程中的思路以及遇到的问题，如果能够对他人的实现有一点点启发，那就更好了 :）

Raft 原理

Raft 是一种共识算法。为了实现共识，Raft 首先选举出一个 Leader，然后交由 Leader 处理日志的权限。Leader 接受客户端发送的日志，复制到其他的服务器上，并告知其他服务器什么时候可以把日志保存到状态机中。Raft 算法需要保证以下的特性：

• Election Safety：在一个 Term 内至多有一个 Leader。
• Leader Append-Only：一个 Leader 只能添加日志，不能修改或者删除已经添加的日志。
• Log Matching：如果两个日志在同一个索引位置的日志条目 Term 相等，那么两个日志在该位置以及前面的日志都是相等的。
• Leader Completeness：如果一条日志在当前的 Term 内已经提交，那么在之后的 Term 中，这条日志一定会存在在 Leader 中。
• State Machine Safety：如果一条日志已经 Apply 到了复制状态机的特定位置中，那么其他服务器不会在同样的位置 Apply 一条不一样的日志。（可以用于 Client 判断自己的命令是否已经被执行完毕）

Raft 实现

Raft 实现网上已经有很多文章讲解了，这里也就不赘述了。实现的细节可以看一下参考资料 [2]。一些结构上的建议可以阅读参考资料 [3]，一些参考资料 [4]。正确实现 Raft 的关键就是根据论文的 Figure 2，把英语翻译成代码。如果是严格按照 Figure 2 写的，基本不会出现大问题。

这部分主要讲几个实现上的坑，或者说是注意事项。

ElectionTimer

ElectionTimer 的作用是让节点等待一段时间，如果接收到了主节点发送的 AppendEntires 包，就重置该定时器。否则，定时器超时后，节点转变为 Candidate 并发起选举。如果在选举的过程中又超时了，节点就需要重新发起一轮选举，直到某个节点接收到大部分节点的投票并成为新的主节点为止。整个流程如下。

在实现中，有以下几个点需要注意，同时也是我认为有可能会出错得地方。

1. 定时器的超时时间必须是随机的。如果所有定时器的超时时间是一致的，它们会在同一时间失效，在同一时间转换为 Candidate 状态并投票给自己，这样所有的节点都不能获得多数同意并成为一个主节点，选举就会无休无止的进行。

2. 定时器的超时时长必须要大于心跳间隔。如果定时器间隔过小，节点还没有收到 Leader 的心跳包就会超时，开始一轮新的选举。尽管所有节点已经达成了共识，但是还是会有节点发起新的选举。（血泪教训，导致后面的实现总是有问题，查代码还查不出来，明明逻辑都是没问题的。结果打印了重置定时器日志才发现超时时长设置的问题）

3. 重置定时器的时机。论文里面提到的重置定时器只有以下几个地方：接收到了当前主节点发送的 AppendEntires 包、定时器超时自己成为 Candidate、投票给另一个 Candidate。其他时候不能重置定时器。论文中有一个地方没有写明白：当一个 Leader 收到了一个 RPC reply，并且发现了当前的 term 已经大于自己的 term，需要转变为 Follower，此时需不需要重置定时器？

AppendEntries

1. 注意 AppendEntriesReply 的处理。Figure 2 对于 RPC request 的处理已经讲的很详细了，按照流程实现即可。但是，论文并没有对 RPC reply 的响应作出什么规定。参考资料建议的是检查当前节点的 Term 的发送请求的 Term 是否是一致的，如果不一致，说明节点在 RPC 的发送前后出现了状态变更，需要直接丢弃。并且，在此之前需要先检查 reply.Term，确保如果 Leader 已经落后则进入 Follower 状态。

2. 不要简单截断 Follower 的 log。处理 Follower 的 log 需要严格按照论文的说明执行。这样做的原因在于：网络是不可靠的，容易出现延迟或者丢包的情况，导致先发送的 RPC 后到达 Follower，发送和接收 RPC 的顺序是不确定的。

调试

1. 分布式系统的调试要靠日志。因为分布式系统经常会出现莫名其妙的问题，单步调试基本是行不通的，需要在系统崩溃或者测试失败后观察输出日志，反推系统出故障时的状态，检查是否存在实现上的问题。我个人推荐的做法是把每个对象（Raft 节点、RPC request、RPC response、Timer）内部状态打印出来，然后根据打印的日志推断系统变换。例如，Raft 节点的打印日志可以如下实现：

func (rf *Raft) String() string {
	return fmt.Sprintf("[%s:%d;Term:%d;VotedFor:%d;Leader:%d;LogLen:%d;CommitIndex:%d;LastApplied:%d;LastIncludedIndex:%d]",
		rf.state, rf.me, rf.currentTerm, rf.votedFor, rf.leaderId, len(rf.log), rf.commitIndex, rf.lastApplied, rf.lastIncludedIndex)
}

这样做的好处是可以明确是哪个节点出问题了，调试时更有针对性。

同时，也可以通过在加锁 / 解锁处添加日志，判断自己的系统是否出现死锁情况（加了锁但是没有解锁）。

参考

• Raft paper
• 助教写的 Student Guide
• Raft structure advice
• Raft locking advice