前言

10月份没有更新过博客，一个原因是自己太懒，没有养成写博客的习惯，但主要的原因还是自己太摸，没有什么工作值得记录的。这个月断断续续花了两周时间，把6.824的Lab2给实现了，稍微总结一下水过这个月吧。第一篇博客发完之后我意识到贴代码可能不太合适，因为这是别人学校的作业，但是转念一想不会有什么人会看到我的博客吧（哈哈哈）。无论怎样，之后的Lab还是不要把我的菜鸡代码贴上来了。

6.824的Lab2主要是实现Raft论文里除了configuration change之外的所有内容，包括Leader Election、Log Replication和Snapshot，其中Log Replication包括了减少AppendEntries RPC匹配错误的优化。这篇博客的侧重点更多是在实现方案上的讨论，Raft的核心主要就在这两张精简图里面了，关于Raft的算法本身，请直接看作者的论文：https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf

Leader Election

首先，我们需要一个计时器去控制Election Timeout的计时，在Election Timeout被触发时server成为候选人，进入选举流程。如果server接收到leader的请求或者投票给一个候选人时，需要重置计时器，所以计时器还需要随时检查自己是否已经被重置。这种情况下使用channel和信号量都不是很方便，因为阻塞的时候想要重置的话实现起来很麻烦，所以我用的是一个保存在server元数据结构体中的状态变量，在一个循环中“锁-检查状态-释放锁-sleep”的笨办法。

server成为候选人后，需要给其他server发送投票请求，但是如果使用并发发送请求的策略，有时候我们不知道其他server有没有回复，如何统计大多数人的回复呢？这里我在每个发送投票请求的函数中带了一个计数变量的指针，在投票请求回复同意后对这个计数变量进行原子性的自增操作，如果检查到计数变量超过大多数，就进入leader初始化的阶段。在我的实现里，其他server是有“一票否决权”的，被一票否决后server会从候选人变回follower并重置计时器，所以在投票请求回复后还需要检查自己还是不是当前term的候选人。

其他server在决定要不要投票的时候，需要确定对方是不是"at least up-to-date"，也就是对方的term必须至少跟自己一样，如果对方的term跟自己一样则最后一个log entry的索引要至少和自己一样，否则就直接一票否决。

server在成为leader之后，需要进行一个no-op，即马上增加一个当前term的空日志并发给其他server，否则会导致存在一致性的隐患。实验中会因为实现了no-op而导致测试不通过，因为部分测试对log的索引顺序有要求，需要魔改一下测试。

我选择的Heartbeat Timeout是50ms，Election Timeout是150ms到300ms，使用助教的并行测试脚本，进程数等于逻辑核数量时测试可以稳定通过。

Log Replication

AppendEntries

leader发送AppendEntries RPC请求主要是根据对应follower的next index来决定是发送log entry还是仅发送heartbeat，当接收到超过半数follower的确认后，leader就认为这个log entry是可以commit的，便会提交apply并在下一次AppendEntries RPC请求通知其他follower也提交。有时候leader可能因为经历了网络隔离后是落后的，这时follower对leader的AppendEntries RPC请求会回复自己的term，leader收到后会回到follower状态。如果是leader本身接收到了来自更高term的leader的AppendEntries RPC请求，那么他应该直接成为新leader的follower，因为这里隐藏的含义是有超过半数的server在一个更高的term里投出了一个leader。

对于follower，AppendEntries有很多需要注意的地方。如果请求的term比自己大，需要把自己的last log index回复给leader；如果请求的term比自己小，需要把自己的term回复给leader；如果不是自己投出来的leader，忽略请求；如果匹配错误(last log index < prev log index或者prev log index对应的term不对)，也返回不成功。写入log时要注意，如果发生了重写，last log index不一定是log slice的最后一个元素，需要进行一些处理来分成rewrite和append两类操作。

在我的实现中，无论是leader还是follower，在commit index发生改变时都会马上提交apply，并且等所有apply都推到apply channel后才继续执行之后的代码。相比于计时器定时apply，状态变化的复杂性会少一点。

在我的实现中，last log term和last log index都是有额外的变量保存的，并且和log保持一致，因为有时候AppendEntries RPC匹配错误之后，如果不作额外标识，很难直接定位到最后一个有效的log entry。不过如果只保存last log index也是可以的。

Persistence

需要持久化的变量如下，每次变量发生变化的时候都要进行持久化。其中offset会在后文Snapshot中使用到。

Log          []*LogEntry
Offset       int
Term         int
VoteFor      int
LastLogIndex int
LastLogTerm  int
LastApplied  int

Snapshot

snapshot在实验框架中的实现是这样的：由上层服务向raft发起snapshot的请求，raft会收到一个snapshot的数据，raft只需要将它持久化即可。在follower需要得到一个snapshot时，leader将自己持久化的这个snapshot的数据取出来发给follower，follower如果确定这个snapshot是最新的，就将它发送到apply channel，并在上层的applier中再次调用follower的接口实现snapshot的安装。

在follower收到leader的安装snapshot请求时，只需要判断leader和term的合法性，并且snapshot的index比自己last applied index大就可以了。因为apply channel的FIFO特性，大部分是否安装snapshot的判断还需要放到applier调用follower的接口的时候。首先要满足请求snapshot的term不能小于自己snapshot；其次如果snapshot的index不比last log index小，直接抛弃自己的所有log即可，如果snapshot的index比last log index小，需要把snapshot没有覆盖到的，还在log slice里保存的那部分log保留下来。

snapshot对前面代码的改动较大，各种index现在无法直接对应log的索引了。我的实现是所有index都保持全局的，但是额外加一个offset，offset初始化为0，在每一次snapshot使得log被截断时，会将offset的值设为snapshot的最后一个log entry index。这样所有对log的访问中，index减去这个offset就是正确的对应位置。在一些corner case中，有时候修改会使得某些index小于offset，如next index、conflict index等，这时需要将它们调整为offset+1，以免出现数组越界。

Tips

1. 如果你有两个相邻的临界区，如果性能影响不大的话，不如考虑下合成一个。这样可以减少复杂性，因为你不希望在两个临界区的中间，server的状态发生了翻天覆地的变化。
2. 提交到apply channel的时候不能锁，因为applier会调用snapshot，如果你的snapshot也加锁了就会导致死锁，这是一个实验在设计上的小bug。如果你想保证apply的顺序，不妨考虑下给apply channel提交的部分加锁。
3. 打印调试日志建议一开始就整理出一个整洁的格式，debug能更轻松。分布式程序的debug真的是地狱难度。

测试

测试我用的是助教写的并行测试脚本https://gist.github.com/jonhoo/f686cacb4b9fe716d5aa，进程数设置为等于逻辑核的数量，每次测试平均使用实际时间6.5min，cpu时间1.5min。测试了2000次没有出现错误，应该基本是没有什么bug了。