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_indexlast_appliedlast_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_indexcommit_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中只记录序号和校验码。