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

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

共享一下，抄作业~

很久以前做的，找不到了。。。不过可以在 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

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 年，可能记不太清了

你要严格执行它论文的每一个检查，一条都不能漏，不能换，不然，相信我，肯定出 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,

我觉得这是正确的语义

如果 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

"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?

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

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