MIT 6.824: Distributed Systems- 实现Raft Lab2C

接上文《MIT 6.824: Distributed Systems- 实现Raft Lab2B》,Lab2C包含2个主要任务:

  • 当currentTerm、voteFor、log[]更新后,调用persister将它们持久化下来,因为这3个状态是要求持久化的。
  • 优化nextIndex的回退性能,即appendEntries被拒时,论文默认反复减1回退重试,导致耗费很长时间才能找到同步位置,优化后可以一次性跳过更多的index,减少RPC往复。

已通过MIT单元测试。

Lab2C实现

实现persist持久化函数非常简单,只需要调用作业提供的persister把3个持久化状态写进去就行。

Lab2C坑了半天,有一个Case一直单测不过:

go test -run TestFigure8Unreliable2C

分析是日志同步协调太慢,导致单测超时失败,发现这个Case通过制造网络分区产生了2个leader,然后不断的向2个leader都写入日志,导致产生了2个很长的歧义链。当网络分区恢复后,2个歧义链之间日志同步过程,会因为不断的prevLogTerm冲突导致nextIndex不断回退,因为每次只回退1位,进而耗时非常长。

另外发现Lab2B中的一个case也是同样道理,存在一定几率超时,原因也是歧义链的冲突处理耗时过长:

go test -run TestBackup2B

一开始怀疑是不是从Lab2B就写Bug了,结果发现的确不是bug,而是冲突处理性能问题。

持久化函数

只要在所有修改持久化状态之后调用persist即可。

appendEntries应答

Reply增加2个字段,用于leader和follower协调同步位置,优化回退性能。

appendEntries服务端

重点是conflictIndex和conflictTerm的理解和处理,看这篇MIT的总结:

https://thesquareplanet.com/blog/students-guide-to-raft/#an-aside-on-optimizations、

appendEntries客户端

在success==false情况下,处理nextIndex回退时遵从了优化后的逻辑。

总结

lab2C只是在lab2B基础上,把持久化状态进行了persist存储,另外对日志同步性能提出了更高要求,因为它会制造网络分区形成2个leader然后向2个leader同时写入大量日志,造成2个很长的歧义日志,然而默认的论文实现每次回退1个下标进行重试是无法通过单测的。

  • 回退优化原理:如果follower日志比leader短,那么leader可以直接从follower末尾的index开始尝试传日志,只有这样follower日志才不会出现空槽的情况;否则follower在prevLogIndex位置冲突的term,如果在leader中也有这个term的日志,则从leader日志中该term最后一次出现的位置开始尝试同步,避免给follower错过这个term的任何一条日志;如果冲突term在leader里压根不在,则从follower日志该term首次出现的下标开始同步,因为leader压根没有这个term的日志,相当于对follower截断。
  • leader可能收到旧的appendEntries RPC应答,因此leader收到RPC应答时重新加锁后,应该注意检查currentTerm是否和RPC时的term一样,另外也不应该对nextIndex直接做-=1这样的相对计算(因为旧RPC应答之前可能新RPC已经应答并且修改了nextIndex),而是应该用RPC时的prevLogIndex等信息做绝对计算,这样是不会有问题的。

多看看MIT对6.824常见问题的总结:https://thesquareplanet.com/blog/students-guide-to-raft/#an-aside-on-optimizations

如果文章帮助您解决了工作难题,您可以帮我点击屏幕上的任意广告,或者赞助少量费用来支持我的持续创作,谢谢~