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中遇到的。例如我花费了很长时间在节点销毁时正确处理gRPC的client和server上。在Nuft中,由于是多个TestCase连续跑的,所以要处理节点销毁后到达的RPC消息,我在消息上附带时间戳来处理的,这个在长远看有时间的同步间隔。

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()必须取到等号,不然会越界。