6.824 Lab 2A Leader Election

6.824 Lab 2A Leader Election

Administrator 1186 2021-08-27

引言

最近开始写 6.824 的 Lab，截至现在已经有差不多半个月了，目前的进度是 2B 做完，开始 2C 阶段。其实早在几个月之前就有打算去做这个 Lab 了，但是一直存在各种各样的问题导致这个计划延期（雀食有我懒的成分 ~(￣▽￣)~*），最近看面经的时候感觉电商项目实在不禁问，于时又启动了该计划。

现在将自己做 Lab 遇到的一些问题记录下来，方便之后自己回来优化的时候快速上手自己的屎山🤣，同时也可以为后来做这个 Lab 的同学提供参考。

参考资料

首先列举一下我在写这个 Lab 2A 部分的时候所使用的一些参考资料，这些资料为我实现 Leader Election 提供了很大的帮助

  1. Raft (thesecretlivesofdata.com)
  2. Raft Consensus Algorithm
  3. Raft Paper

第一个链接是 Raft 的可视化网站，如果你在读完 Raft 的 Paper 之后还对这个协议的整体情况模棱两可的话，不妨看看这个网站中提供的教程（其实也不能叫教程，但是确实能较快的了解到 Raft 的 Leader Election 和 Log Replication 部分）。

第二个链接是 Raft 在 Github 上的官方可视化，同时这个可视化还支持参数调节，同步速度调节，客户端请求模拟等情况，也是在 2A, 2B 部分对我帮助最大的网站，许多 Paper 中没有描述的，但是确实需要考虑的情况，都是可以通过参数模拟来得到，然后进行编码实现。

第三个链接是 Raft 的 Paper，这是最权威的资料，对于其描述了的部分，需要你在编码过程中严格遵循。

单元测试

课程在 Lab 中也为我们提供了单元测试

  • InitialElection2A - 在该测试中不会出现网络分区或者消息延迟，所以你的 Raft 集群应该在 Term 值为 2 的时候收敛到主从的状态，同时一直保持该状态
  • ReElection2A - 在该测试中会存在网络分区，Leader 节点可能会存在一段时间的不可用，导致其他节点的心跳超时，此时你的集群应该重新选举出一位 Leader，并且在 Old Leader 重新加入集群网络时与 New Leader 通信来收敛到一主多从的状态
  • ManyElections2A - 该测试是 ReElection 的加强版，多了几个节点，依旧是需要在最后收敛到一致性状态

编码流程

  1. 在你阅读完 Raft 协议之后，我建议你在 Raft struct 中加入 Leader Election (without data) 必须的属性，关于日志部分你可以暂时不考虑，只需要考虑心跳包即可。
  2. 如果你的代码没有啰嗦到必须要重构，那么在保证逻辑正确的情况下，优先完成所有的任务，直到最后所有的测试都能 PASS 再进行重构测试
  3. 多 commit ，否则写成了屎山只能 /remake

逻辑部分

无内鬼，这个部分不会包含代码，只是一些提醒。

其实这部分很简单，熟悉了流程大约 2 个小时就可以写完（别问我怎么知道的，我 remake 了三次

你的任务可以分为几个

  1. 实现简单时钟，确定心跳超时和选举超时
  2. 发送选举消息和心跳，以及对应的处理过程，判断是否需要转变角色
  3. 确定在什么时候需要重制时钟，什么时候需要进行时钟检查

还有一些需要你注意的点：

第一个是锁，如果你和我一样并发代码写的不多，并且使用的多是重入锁，那么 Golang 中的锁也需要你注意，它是不可重入的。如果你的代码中需要重复加锁，那么考虑是否必须加锁，是否需要对锁进行拆分，以及如果有提前 return 的流程，需要及时释放锁（Golang 中提供了 defer 关键字，但是个人不太喜欢）

第二个是计时器，这对于 2A,2B 部分来说是最重要组件，直接影响到你的代码能否通过测试，是否会出现奇奇怪怪的 BUG。同时，我也要提醒你，最好不要依赖于时钟的准确性，做好误差区间判断（在我的实现中会记录下一次超时的时间，并与当前时间做对比），最好把心跳超时和选举超时做的足够大，留出空余给误差区间。

第三个是唤醒时间，上面提到了我的实现方式，这种方式就需要你在 Leader 或者 Candidate 变成 Follower 的时候进行唤醒进行检查超时，同时重置过期时间，切记。

测试脚本

在编写完代码之后，你可能会进行测试，并且连续通过，但是并不意味着你的实现是正确的，有可能只是这几次的参数正好没有覆盖到你忽略的部分。

那么此时，你可能就需要进行多次重复的测试，但是自己一次一次在命令行敲完之后再去看日志实在太蠢太不优雅了，你可能想到了用脚本自动化运行测试，没准你又和我一样对 Shell 不太熟悉，那么我现在就把我自己用的测试脚本分享给你。

这个脚本的使用方法很简单，只需要在 Raft 目录下创建一个文件 autotest.sh，然后运行 zsh ./autotest.sh go test -run 2A 10 即可自动化运行，并且会将错误的日志以 err-* 的格式保存到本目录下。

但是现在这个脚本还存在一些缺陷，比如没办法实时显示测试进度，需要你估计一个测试的运行时间，并在 ProcessPrint() 的循环中修改循环次数。我推荐将次数设置的比你的耗时略小，这样跑的时候不会出现鬼畜的现象。

#!/bin/zsh
 
local percent=50
local rep=500
local dir=$(($(date +%s%N)/1000000))
local pre=$(($rep/$percent))
local re=`echo $5|awk '{print int($0)*10}'`
local arr="▁▂▃▄▅▆▇█▇▆▅▄▃▂▁"
 
 
 
function RUN() {
    str=">"
    passed=0
    err=0
 
    clear
 
    echo ""
    echo "\033[34m=== === === === === === === === === === === === === ===\033[0m \033[33mSTART AUTO TEST\033[0m \033[34m=== === === === === === === === === === === === === ===\033[0m"
    echo "                                                      Params: "
    echo "                                                          - REPEAT  [ \033[36m$rep\033[m ]"
    echo "                                                          - EXECUTE [ \033[36m$1 $2 $3 $4\033[0m ]"
    echo "                                                          - OUTPUT  [ \033[36m./$4-$dir\033[0m ]"
    echo "\033[34m=== === === === === === === === === === === === === === === === === === === === === === === === === === === === === === === ===\033[0m"
    echo ""
    
    ProcessPrint $str 0 0 0 &
    for (( i=1; i <= $rep ; i++ )) {
        out=`$1 $2 $3 $4`
        g=`echo $out | tail -1 | awk '{print $1}'`
        if [[ "$g" == "ok" ]] {
            let passed++
        } else {
            if (( `ls -l |grep "^d"|grep "$dir"|wc -l` == 0 )) {
                mkdir "$4-$dir"
            }
            echo $out > "./$4-$dir/err-$err"
            let err++
        }
        if (( $i % $pre == 0 )) {
            str="=$str"
        }
        ProcessPrint $str $i $passed $err &
    }
    
    sleep 2
    echo ""
    echo ">>>>>>>>>>-<<<<<<<<<<"
    echo ">>>>> \033[32mTEST DONE\033[0m <<<<<"
    echo ">>>>>>>>>>-<<<<<<<<<<"
}
 
function ProcessPrint() {
    if (( $2 == $rep )) {
        for (( i=0; i < $re; i++)) {
            printf "[%-50s] [ \033[33mPROCESSED\033[0m / \033[36mTOTAL\033[0m ] : [ \033[33m%d\033[0m / \033[36m%d\033[0m ] [ \033[32mPASS\033[0m / \033[31mFAIL\033[0m ]:[ \033[32m%d\033[0m / \033[31m%d\033[0m ] \033[34m%s%s%s%s\033[0m\r" \
                "=${1:0:49}" "$2" "$rep" "$3" "$4" "$arr[0]" "$arr[1]" "$arr[2]" "$arr[3]" 
        }
    } else {
        for (( i=0; i<$re; i++ )) {
            let a=$(( i % 15 ))
            let b=$(( (a + 1) % 15 ))
            let c=$(( (b + 1) % 15 ))
            let d=$(( (c + 1) % 15 ))
            printf "[%-50s] [ \033[33mPROCESSED\033[0m / \033[36mTOTAL\033[0m ] : [ \033[33m%d\033[0m / \033[36m%d\033[0m ] [ \033[32mPASS\033[0m / \033[31mFAIL\033[0m ]:[ \033[32m%d\033[0m / \033[31m%d\033[0m ] \033[34m%s%s%s%s\033[0m\r" \
                "$1" "$2" "$rep" "$3" "$4" "$arr[$a]" "$arr[$b]" "$arr[$c]" "$arr[$d]" 
            sleep 0.1
        }
    }
}
 
RUN $1 $2 $3 $4 $5

结语

如果你的 Raft 集群通过了 500+ 次的测试，恭喜你通过了 Lab 2A。

但是，这并不意味着你的实现是正确的，你还应该去我提供的第二个链接中仔细对比，是否日志中存在和给出样例行为不一致的地方。如果有，需要你进行修改，使其与图示一致。

最后，注意 DL，一个星期！

最后的最后，祝你在 6.824 的 Lab 玩的开心~

6.824