Raft

第二个 Lab, 目标是还原 raft paper 定义的 raft 算法, raft 是一个为了解决(有状态服务)(高可用)(强一致)问题的一个算法, 它通过将状态复制到集群里的大多数节点中作为提交完成的标志来实现这一点, 并且只有 leader 能向外界提供服务(读写) , 当 leader 宕机后, 会从集群中重新选举一个新的 leader 提供服务, 从而实现高可用 , 不可用的时间只有短暂的选举时间

CAP

尝试套入 raft 后的理解 :

raft 是强一致的, 因为读和写都是线性操作

raft 是"高可用的", 有选举机制和复制机制, 但出现网络分区时会出现不可用

raft 是允许出现网络分区的, 多数派的一边依然可以提供正常服务

出现了网络分区后, raft 为了保证对外展现出强一致性, 少数派的一边无法提供服务, 所以 raft 是 CP 的

举另一个 AP 的例子, DNS 服务, 出现网络分区后, 为了保持两个分区都有可用性, DNS 的每个节点都能提供读, 解析到的 IP 可能不是最新的, 因此牺牲了强一致性, 所以 DNS 是 AP 的

我对这里可用性的理解: 网络分区后, 两个分区都能提供服务

这里一致性的理解: 网络分区后, 任一时刻依然能读到最新的写入

问题记录

三个版本

  • 第一次

面向测试用例编程, 写出来的代码完全不能用, 到处是 bug

  • 第二次

对整个模型有了大致的理解, 线程安全问题又搞出一堆 bug (锁加的乱七八糟 , 粒度也没有一致)

  • 第三次

在一个伙伴的提点下, 使用了一个并发测试脚本, 每个测试用例并发1000 个执行, 结果发现了许多完全是侥幸通过的 case, 隐藏了许多并发下的线程安全问题未解决, 只好回过头从第一个 case开始排查, 并且将打的日志整理规范(格式,日志级别,分类) , 直接减少锁的使用, 换事件循环的方式写

投票阻塞

在选举阶段的一个 case 中, 某个 follower 会随机断开 , 此时 candidate 发送的投票请求阻塞在了这个 follower 上, 导致了该候选人没有及时获得足够的选票转变成 leader , 所有follower都变成 candidate , 并且不断开始新一轮选举

角色变换,读取到channel 里的旧数据

在 candidate 收到投票处,我使用的是 go 的 channel , 背景是 : candidate 在收到足够的选票后 , 需要立即变成 leader 开始发送心跳 , 这导致了后续多余的选票还在 channel 里 , 当这个 leader 下一次变成 candidate 的时候 , 会取到上一次选举的投票 , 造成了选出多个 leader 的错误现象 , 解决方案是在 candidate 转变成 leader 的时候需要”清空 channel” , 其实就是重新初始化一个 channel , 把清空交给 GC 来处理

日志快速回退

场景: 网络分区, 旧 leader 在少数派分区里, 依然可以接收客户端写请求, 也可以复制到该分区其他节点, 但是由于无法复制到大多数节点, 所以是不可用的, 分区网络恢复后, 这些节点的日志和另一个分区的日志存在不一致, 需要回退到某个一致的状态, 然后重新复制正确的日志

test case 是 UnrealiableFigure83C , 这个测试用例中,所有的raft 实例都会随机的断开,崩溃,请求延迟,乱序 , 造成的问题是实例之间日志的不一致情况经常发生,而且差异很大 , 在这个情况 , 论文中写的是”现实中很少发生 , 所以优化是不必要的” , 但在这个 case 中有超时时间限制 , 如果不进行优化 , 通过率会很低 , 翻阅了资料后在一份 guide 中找到了解决的方案 , 实现快速回退一整个任期 , 而不是一个一个的回退 , follower 会检查自己是否有该冲突的任期的 log , 如果有就把第一个的 index 发过去 , leader 直接回退到这个 index 上开始一致性同步 , 如果没有 , 那么 leader 直接回退到 leader 的 log 中该任期的第一个 index

多线程调试问题

只能依靠日志和并发测试 , 单步调试比较难发现问题

TestFigure8Unreliable2C 一直过不了

https://github.com/springfieldking/mit-6.824-golabs-2018/issues/1

https://segmentfault.com/a/1190000021628173 

协程作用域问题

rf.mu.Lock()
  rf.currentTerm += 1
  rf.state = Candidate
  for <each peer> {
    go func() {
      rf.mu.Lock()
      args.Term = rf.currentTerm
      rf.mu.Unlock()
      Call("Raft.RequestVote", &args, ...)
      // handle the reply...
    } ()
  }
  rf.mu.Unlock()

go发现有其他goroutine引用了变量currentTerm , 把currentTerm移到了堆空间里 , 主和子goroutine都看到同一个任期变量 , 导致变化的时候每个peer看到的可能不一致 , 
所以需要将任期以参数穿进去 , 此时go会对每个goroutine的currentTerm进行一次拷贝 , 保证任期的一致

任期号(term)的变化

follower转变成candidate的时候 , currentTerm +1 candidate变成leader的时候 , 维持currentTerm candidate变成follower的时候 , currentTerm = leader的term

超时时间重置问题

给他人投票的时候忘记重置超时时间了

主要有两个时间要注意, 一个是选举超时时间, 一个是心跳超时时间

后续学习

看看其他人的 raft 是怎么优化的

测试用例第一 , 做那么多 lab 学到的

读 etcd raft 部分

其他

raft 应用 : etcd , github 的 orchestra (一个健康检查服务)实现高可用

spacex 的控制电脑用了三台机器做投票决策 , 降低了太空环境的干扰问题和机器成本

拜占庭将军问题

资料

多次测试脚本:
running tests in parallel makes it easier to find concurrency bugs

[bash script] by a previous TA https://gist.github.com/jonhoo/f686cacb4b9fe716d5aa

论文翻译 https://www.cnblogs.com/linbingdong/p/6442673.html
comiser 参考https://github.com/comiser/MIT-6.824-2016/blob/master/src/raft/raft.go
etcd raft 参考https://gocode.cc/project/14/article/134
raft 运行动画 https://raft.github.io/
lec2 intro https://pdos.csail.mit.edu/6.824/notes/l-gfs.txt
gfs paper https://pdos.csail.mit.edu/6.824/papers/gfs.pdf
lab2 raft https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
gfs faq https://pdos.csail.mit.edu/6.824/papers/gfs-faq.txt

结尾

出于对分布式系统感兴趣 , 开始的一次实践学习 , 难度五颗星, 有的 bug 一卡就几天 , 极其耗时