Raft

前言 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的安装。...