MIT6.824做题笔记

发表于 |

MIT 6.824 2018的Lab。

Lab1 Mapreduce

Lab2 Raft

这个主要是把自己写的C++版本的Nuft精简而成的，在转换到Golang的过程中借鉴了一些较好的实现。
单独运行测试可以使用
go test -run XXX

这里简要介绍一下这个Lab的设计吧，因为它比较考验调试能力。

在Lab中使用config.logs来保存被apply的entry，所以我们必须要apply才能够通过nCommitted检测，仅仅commit是没有用的。然后在处理AppendEntriesArgs的时候删日志也要注意，我之前的写法过不了Figure8(Unreliable)。后来参照了上面提到的实现进行了修改，但这个实现同样是有问题的（参见Nuft注释），我们必须立即删除不正确的日志。

死锁是容易遇到的大问题，但我主要是在Nuft中遇到的，基本上死锁中的一部分来自在一个函数调用链中（一般是node.h）两次请求了锁，这个是一个弱智错误。另外的死锁情形包括在Test里面注册的回调函数中调用了node.h的带锁API。或者一个线程持有锁并被主线程join。例如我花费了很长时间在节点销毁时正确处理gRPC的client和server上。

在Nuft中，由于是多个TestCase连续跑的，所以要处理节点销毁后到达的RPC消息，我在消息上附带时间戳来处理的，这个在长远看有时间的同步间隔。

虽然6.824已经提供了一个labrpc，但是在实际选择rpc的时候，我们并不需要选择流式RPC。这是由于在实现Nuft时我发现流式RPC创建信道的开销很大，并且非优雅地关闭连接很麻烦。流式RPC提供的有序的传输并不是性价比很高的，毕竟Raft本身就能处理乱序到达的RPC（详见Nuft注释）。并且如果单纯为了解决乱序到达的包带来的额外的处理开销，可以通过设置seq号的方式来直接丢弃掉。

Lab3 KVRaft

写了一下，发现在Test1就过不去，阻塞在Commit=102处。发现这是因为没有及时更新ch所致。

1
2
3
get wrong value, key 0, wanted:
x 0 0 y
, got

这里的key，实际上就是客户的序号。这是因为我在server里面打日志的时候忘掉加上Value了。

get wrong value/missing element问题

如下所示，缺失倒数第一或者倒数第二个项目。
missing element

1
2
--- FAIL: TestSnapshotRecover3B (13.47s)
	test_test.go:85: 0 missing element x 0 50 y in Append result x 0 0 yx 0 1 yx 0 2 yx 0 3 yx 0 4 yx 0 5 yx 0 6 yx 0 7 yx 0 8 yx 0 9 yx 0 10 yx 0 11 yx 0 12 yx 0 13 yx 0 14 yx 0 15 yx 0 16 yx 0 17 yx 0 18 yx 0 19 yx 0 20 yx 0 21 yx 0 22 yx 0 23 yx 0 24 yx 0 25 yx 0 26 yx 0 27 yx 0 28 yx 0 29 yx 0 30 yx 0 31 yx 0 32 yx 0 33 yx 0 34 yx 0 35 yx 0 36 yx 0 37 yx 0 38 yx 0 39 yx 0 40 yx 0 41 yx 0 42 yx 0 43 yx 0 44 yx 0 45 yx 0 46 yx 0 47 yx 0 48 yx 0 49 yx 0 51 y

get wrong value

1
2
3
4
get wrong value, key 0, wanted:
x 0 0 yx 0 1 yx 0 2 yx 0 3 yx 0 4 yx 0 5 yx 0 6 yx 0 7 yx 0 8 yx 0 9 yx 0 10 yx 0 11 yx 0 12 yx 0 13 yx 0 14 yx 0 15 yx 0 16 yx 0 17 yx 0 18 yx 0 19 yx 0 20 yx 0 21 yx 0 22 yx 0 23 yx 0 24 yx 0 25 yx 0 26 yx 0 27 yx 0 28 yx 0 29 yx 0 30 yx 0 31 yx 0 32 yx 0 33 yx 0 34 yx 0 35 yx 0 36 yx 0 37 yx 0 38 yx 0 39 yx 0 40 yx 0 41 yx 0 42 yx 0 43 yx 0 44 yx 0 45 yx 0 46 yx 0 47 yx 0 48 yx 0 49 yx 0 50 yx 0 51 y
, got
x 0 0 yx 0 1 yx 0 2 yx 0 3 yx 0 4 yx 0 5 yx 0 6 yx 0 7 yx 0 8 yx 0 9 yx 0 10 yx 0 11 yx 0 12 yx 0 13 yx 0 14 yx 0 15 yx 0 16 yx 0 17 yx 0 18 yx 0 19 yx 0 20 yx 0 21 yx 0 22 yx 0 23 yx 0 24 yx 0 25 yx 0 26 yx 0 27 yx 0 28 yx 0 29 yx 0 30 yx 0 31 yx 0 32 yx 0 33 yx 0 34 yx 0 35 yx 0 36 yx 0 37 yx 0 38 yx 0 39 yx 0 40 yx 0 41 yx 0 42 yx 0 43 yx 0 44 yx 0 45 yx 0 46 yx 0 47 yx 0 48 yx 0 49 yx 0 50 y

这是有关Snapshot的问题，在安装Snapshot的时候需要更新commit_index和last_applied为last_included_index，尽管它们的值可能比last_included_index要大。考虑从Snapshot恢复，此时全部Log等于Snapshot+last_included_index+1开始的所有日志，由于commit_index等式volatile的（Figure 2），所以并不知道目前commit_index如何变化，唯一的标杆是last_included_index，我们知道它一定是applied的。实际上仍然需要回滚last_included_index到commit_index的一段。此外，需要特别注意，在加载Snapshot时要判断它是否为空。
在修改之后发现还是有这个问题，进一步检查发现在崩溃前第85号日志是{Append 0 x 0 48 y 4062585092109805200 84}，到了恢复之后莫名其妙变成了{Append 0 x 0 49 y 4062585092109805200 85}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Leader Commit to 85
Apply base 74 commit_index 85 last index 85 log len 12 i 85 cmd {Append 0 x 0 48 y 4062585092109805200 84}
Apply base 74 commit_index 84 last index 85 log len 12 i 84 cmd {Append 0 x 0 47 y 4062585092109805200 83}
Apply base 74 commit_index 84 last index 85 log len 12 i 84 cmd {Append 0 x 0 47 y 4062585092109805200 83}
Apply base 74 commit_index 84 last index 85 log len 12 i 84 cmd {Append 0 x 0 47 y 4062585092109805200 83}
ALoad Snapshot LastIncludedIndex 74 LastIncludedTerm 1 rf.commit_index 74 rf.last_applied 74 base 74
truncate until (index 74, term 1), i 0, len 11, new len 11
ALoad Snapshot LastIncludedIndex 74 LastIncludedTerm 1 rf.commit_index 74 rf.last_applied 74 base 74
truncate until (index 74, term 1), i 0, len 11, new len 11
ALoad Snapshot LastIncludedIndex 74 LastIncludedTerm 1 rf.commit_index 74 rf.last_applied 74 base 74
truncate until (index 74, term 1), i 0, len 11, new len 11
ALoad Snapshot LastIncludedIndex 74 LastIncludedTerm 1 rf.commit_index 74 rf.last_applied 74 base 74
truncate until (index 74, term 1), i 0, len 13, new len 13
ALoad Snapshot LastIncludedIndex 74 LastIncludedTerm 1 rf.commit_index 74 rf.last_applied 74 base 74
truncate until (index 74, term 1), i 0, len 11, new len 11
Leader Commit to 85

经检查（可以在Load处打印出所有日志比较）发现只有len为13的节点persist了最新Apply的85和86号日志。这是不正确的行为，因为Applied的日志必须要在持久化中有体现。于是核对了一下persist的时机，发现sendAppendEntries有一处笔误，但是并没有发现其他错误。
后来发现，好像必须要rf.persist()才行，我之前裸写了rf.persister.SaveRaftState(rf.encode_raft_state())就不行。经过比较发现可能是defer rf.persister.SaveRaftState(rf.encode_raft_state())的时候里面的rf.encode_raft_state()就已经被求值了。

注意在AppendEntries函数中加上判断args.Prev_log_index > rf.get_base_index()。此外broadcastAppendEntries函数中的rf.next_index[j] <= rf.get_base_index()必须取到等号，不然会越界。

有关提交和应用的问题

对于客户机而言，它会提交一个日志项，并等待其apply成功。这个过程可能是false negative的，即明明已经被提交了，但由于Leader切换的缘故Apply超时了。这时候客户机一般会选择重试，因此必须保证重试的日志和前面的日志是幂等的，比较好的做法是对每个日志项维护一个id号，重试时不增加id。
由于KV的V可能比较大，所以我们可以将V放到某个外部存储中，raft中只记录序号和校验码。