瞎扯淡 MIT 6.824 Distributed Systems Reading Notes

yfractal · August 24, 2022 · Last by femto replied at September 18, 2022 · 828 hits

阅读笔记

Distributed Systems 这门课断断续续学了很久,总算是看完了。

没有像学习其他课程一样看资料 + 做 project,而是采取资料 + 做笔记的方式,一个是对 project 不是特别感兴趣,更主要的原因是懒。。。之后有机会会把项目做完。

笔记如下:

有的没的

Why

之前对并发相关的一直很感兴趣,工作上也需要对架构有更好的理解。

上一份工作的后端系统,几年间架构经过了几次改进,从最初的相对合理、可以应对一定的性能要求,到中期的局部重构,以及后期整体重构以应对较高的性能要求和扩展要求。

都是架构上的调整,看不同的人用不同的方式做同一个项目,是件很有趣的事情。

MIT 这门课程,主要是讲解各种 paper 从 MapReduce 到 Spanner,再到 Bitcoin 和 Blockstack。

具体的东西比抽象的东西有趣一些,比如 DDIA,讲数据密集型应用各种原理,讲的很好,但记起来不容易。

而 paper 就有趣的多,有具体的问题,还可以和相似的问题做横向比较。

非常喜欢这门课的老师,总能用最简单的语言描述问题的本质。

感受

最大的感受是开阔眼界。学完这个,后端玩法至少有一个大体的了解,催牛的时候不至于无话可说。

分布式系统也很有趣,没有完美的解决方案,但可以做 trade-off,比如在性能,可用性,一致性之间做取舍。

可以看到软件的发展,比如开始的 MapReduce 到后来的 Spark。

可以看到不同的玩法。比如从一开始,就把一致性放到较低优先级的 Faceboke Memache 集群,选择强一致的 Spanner,选择 Causal Consistency 的 COPS。

后端很有趣,工程上的问题也好,纯粹的技术、理论也好,总是有很多有趣的事物出现。

兄弟你作业做了没有?我看了第一集,上来就要求写一个 mapreduce.

Reply to femto

我做了 mapreduce 和 raft 的部分实现。Golang 写复杂的并非程序太难受了 :facepalm:

共享一下,抄作业~

Reply to femto

😂 很久以前做的,找不到了。。。不过可以在 github 搜一下 6.824

做到 raft 2d 部分,还是很开心的,distributed system 还是很容易出一些奇奇怪怪的 bug 的, 改了好久才好。paper 中算法有几个有歧义的地方,1.Candidates: If AppendEntries RPC received from new leader: convert to follower. 这个 new leader 的定义是什么?Leader Term>=Candidate's Term 么?我实际做的时候不管, 看见有 leader 来的 AppendEntries RPC 就从 Candidates Convert 成 follower,反正如果 Leader Term currentTerm: set currentTerm = T, convert to follower, 所以 Leader 也会在这次 reply 被 convert 成 Follower,无非是多一次选举。 2.heartbeat 头一次是送 empty entries,但是如果 prevLogIndex/prevLogTerm 导致 nextIndex[i] 减了,那么 heartbeat 是否送 entries? 还是说 heartbeat 只管 heartbeat,而送 entries 的只由 normal AppendEntries RPC 不断重试? 目前我的实现是 heartbeat 一旦发现 prevLogIndex/prevLogTerm 导致 nextIndex[i] 减了,是会送出 entries 的。 这样比较简单,反正都是幂等操作。 3.Leaders Rule:If AppendEntries fails because of log inconsistency: decrement nextIndex and retry 和 If there exists an N such that N > commitIndex, a majority of matchIndex[i] ≥ N, and log[N].term == currentTerm: set commitIndex = N 这个检查在 leader 接收到 reply 的时候检查,但是接收到 reply 是否要重新检查自己还为 Leader, 因为如果网络延时,reply 时可能都新 term 了,leader 可能变成新 term 的 follower,当然也可能仍然是新 term 的 leader 目前他这个 Rule 在 Leaders section 下面,所以我猜他是要检查的,我的检查 比较简单,判断仍然 term==rf.currentTerm,也就是一旦新 term,所有老 term 的 request 都失效, 我不会再用它来更新 nextIndex/matchIndex,也不会更新 commitIndex

Reply to femto

1 的问题,new leader 是指老 leader 离线了之后,出了若干个 candidates, 这 1 波/几波 election 之后定下来的 leader, 成了 leader 才能发 Append Entries RPC, candidates 收到的 AE RPC 可能是离线了那个老 leader 又上线了发的 (才睡醒,不知道它自己已经下台了,还在发 AE RPC), 也可能是新选出来的 leader 发的,那么这时候老 leader 的 term 肯定小于 candidate 的,这时候这个 candidate 就不能 convert 到 follower, 时间到了还要发起 election, 如果你把它直接不管 term 是大还是小都 convert 成 follower 了,那可能有这么一段时间所有人都成不了 leader(假设老 leader 的网卡坏了,只能发不能收), 导致这段时间将无 leader 可用。

2 的问题,Heartbeat 实际上就是空 entries 的 AppendEntriesRPC, 如果近段时间发过带 entries 的 RPC 就不用发 HB 了,否则就要发 HB, 以防 follower 觉得现在没有 leader. 所以你的问题的答案是,heartbeat 不带 entries, 但如果发现有 follower 缺 entries 了,那么下次就给这个 follower 单独发带 entries 的 (AE RPC), 给其他 followers 发不带 entries 的 (AE RPC, 也叫 heartbeat).

3 的问题,要检查 follower 发给 leader 的所有信息的 term, 当然也包含 AE RPC 的 reply 的 term. 因为 Leader 首先属于 All servers, 要先执行 all servers 的规定,而后才执行 leader 的规定。

上次看这篇论文还是在 19 年,可能记不太清了

Reply to femto

你要严格执行它论文的每一个检查,一条都不能漏,不能换,不然,相信我,肯定出 bug 😄

目前我 lab 2 的所有 test 都能 pass😀 1.确实如你所说,new server 意思是本 term 之后的所有 term,不包括那些老的 server 发过来的 AppendEntries rpc,我的实现虽然没有 bug,但是不 performant, 有可能需要新一轮的选举

2.我的 code 是有 heartbeat() 函数和 AppendEntries() 函数,heartbeat() 中,如果 prevLogIndex/prevLogTerm,马上就会在 heartbeat() 中进行重试,送一些 entries 出来,其实按照你说的,定义就是普通的带 Entries 的 AppendEntries RPC,只不过我是写在 heartbeat() 中而已

3.All leader 的 Rule 我肯定是执行的: All Servers:

• If commitIndex > lastApplied: increment lastApplied, apply log[lastApplied] to state machine (§5.3)

• If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower (§5.1)

这两条我都有执行,我问的是 Leaders 下面的 Rule:

• If AppendEntries fails because of log inconsistency: decrement nextIndex and retry (§5.3)

• If there exists an N such that N > commitIndex, a majority of matchIndex[i] ≥ N, and log[N].term == currentTerm: set commitIndex = N (§5.3, §5.4).

这两条,在拿到 reply 的时候,是否需要检查我自己仍然为 Leader,

我猜是需要的,我是加了 if term == rf.currentTerm 的 check

这样老的 reply 不会更新 nextIndex/matchIndex 和 commitIndex,

我觉得这是正确的语义

Reply to femto

如果 test case 不同的随机种子下能运行 15 次都没 bug, 那基本上就是没 bug 了,这种分布式的和时间差有关的代码不好 debug.

  1. 里面的问题,按你目前的设计,是不是不只是可能需要选举,甚至可能几分钟都没有 leader? 比如 candidates 在等票的时候收到了老 leader 的 AE RPC, 而 candidate 返回给老 leader 的 term 因为网络防火墙原因被老 leader 丢掉,这样老 leader 一直发,而 candidates 一直变回 follower, 每次都没选举成功。

  2. 应该可以,但是可能没有做到 DRY? 这个问题不大的,怎么实现都行。

  3. 不用检查,因为先执行 all server 的 term 检查,如果 leader 自己 term 比 reply 的 term 小了,leader 直接就 convert 到 follower 了,就不继续进行 leader 的工作了。如果没 convert 到 follower 就还是 leader.

对的 1.改了 3.还是要检查的,比如现在 term 8 我是 server,发出去的一个 AppendEntries rpc delay 了,然后经过一些奇怪的超时,我现在是 term 10 的 leader 了,然后 term 8 的 reply 回来, 我如果更新 nextIndex/matchIndex,就不对了。 同样 If last log index ≥ nextIndex for a follower: send AppendEntries RPC with log entries starting at nextIndex • If successful: update nextIndex and matchIndex for follower (§5.3)

If successful 这个分支忘记问了,但是我感觉也是同样,必须检查是否仍然为同 term 时候的 leader,跟

If AppendEntries fails because of log inconsistency 需要的检查是一样的。

然后想了一下,那么同样 Candidates 的 Rule:

If votes received from majority of servers: become leader

同样也要对 reply 检查是否同一 term,

否则我 term 8 选举一个 reply delay 了,然后我 term 9 选举收了 majority-1 个 reply,

然后突然 term 8 的 reply 到了,这样我 succcesful vote + 1 还以为变成了 majority vote,

这就不对了,所以同样也要对 reply 检查是否同一 term

Reply to femto

"If a server receives a request with a stale term number, it rejects the request." 过期的 term 是不是应当直接无视?

这句话在哪里?我怎么没有找到?

我读的是这个 raft extended https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf

另外,这说的是接受 request 端吧?我问的是拿到 reply 端的情况,reply 端估计应该也检查 term

另外一个问题是写 goroutine 中发现的,goroutine 好像允许一个 goroutine 锁 lock,然后另一个 goroutine unlock, 简单说明代码如下:

var mu sync.Mutex
mu.Lock()
    var wg sync.WaitGroup
    wg.Add(1)
    go func() {
        mu.Unlock()
        wg.Done()
    }()
    wg.Wait()
    fmt.Println("locking again")
    mu.Lock()
    mu.Unlock()

也就是对于 go 的 mutex 的实现来说,只管 lock/unlock,而不管是在那个 goroutine unlock? (通常我们是同一个 goroutine lock/unlock)

主要问题是因为调试 raft 代码中一大堆 goroutine 和一堆 lock, 当 hold lock 的时候,起 goroutine,这些 goroutine 相当于是看到这个锁 lock 的? 代码如下:

rf.mu.Lock()
go func() {
            rf.applyCh <- ApplyMsg{SnapshotValid: true, Snapshot: args.Data, SnapshotTerm: args.LastIncludedTerm, SnapshotIndex: args.LastIncludedIndex}
}()
rf.mu.Unlock()

), 在实现 snapshot 的时候,这个 goroutine 会有一段时间看见这个锁 lock?

所以感觉这里锁的语义不是很明确

14 Floor has deleted

pass 3A 了。但是有个问题,我在 kv 层维护了 responses map[string]string, 从 client 的 requestId 映射到 responses(防止 client 发重复的 requestid),但是随着 client 不断发 request, 这个 map 会不断增长。实际应用肯定是有问题的。

You need to Sign in before reply, if you don't have an account, please Sign up first.