MIT 6.824 lab3B/C

前言花两天把lab3B/C写了一下有了A的基础简单了不少。gitee地址放在末尾。一、3B/3C 前的整体认知1.1 3B 的目标Leader 接收Start(command)→ 追加到rf.logs→ 复制到多数派 → 推进commitIndex→ 通过applyChan交给状态机。1.2 3C 的目标把term / votedFor / logs做到“随时可重启且不违背承诺”同一任期不可能投两次票、日志不可能倒退。二、Part B日志复制Log Replication3B2.1 整体思路把 Raft 看成一条闭环流水线主要流程Start 写入 → AppendEntries 复制 → reply 反馈 → Leader 推进 commit → 心跳携带 LeaderCommit → 双端 applier 应用。客户端 → LeaderStartLeader → FollowersAppendEntries(entries, LeaderCommit)Followers → LeaderAppendEntriesReply(Success/Term)Leader更新 nextIndex/matchIndex → updateCommitIndex → 唤醒 applierFollowers更新 commitIndex → 唤醒 applier2.2 关键数据结构持久化状态3C 才真正持久化rf.term、rf.votedFor、rf.logs易失状态所有节点rf.commitIndex、rf.lastApplied易失状态Leader 专用rf.nextIndex[]、rf.matchIndex[]日志索引约定rf.logs[0]为占位条目term0, commandnil 不仅能够对日志进行更方便的访问在3D中这里放快照的最后一个日志信息第一条真实日志在 index1最后一条 index len(rf.logs)-12.3 Start(command)写这一段时建议按接口语义 并发点 返回值组织语义只有rf.stateLeader才能接收命令否则立即返回(-1, rf.term, false)写入追加LogEntry{Term: rf.term, Command: command}到rf.logs返回(index, term, true)触发复制两种常见方式- 触发一次广播推模式或- 等下一次心跳拉模式简单但可能慢func (rf *Raft) Start(command interface{}) (int, int, bool) { // Your code here (3B). rf.mu.Lock() if rf.Killed() { rf.mu.Unlock() return -1, -1, false } if rf.state ! Leader { rf.mu.Unlock() return -1, -1, false } term : rf.currentTerm index : rf.getLastIndex() 1 rf.logs append(rf.logs, LogEntry{Term: term, Command: command}) rf.persist() rf.mu.Unlock() //Leader 刚追加了一条日志立刻再推一轮 RPC不用干等下面 ticker 的 50ms 心跳周期复制会快一点 go rf.broadcastHeartbeat()//广播心跳 return index, term, true }2.4 AppendEntriesFollower 侧日志一致性检查与截断追加这一节建议用“检查顺序”写跟 Figure 2/论文一致最好对着一步步走term 检查args.Term rf.term直接拒绝回reply.Term rf.term退位与重置计时器收到合法 Leader 的 RPC →lastHeartBeatTime now必要时退回 Follower一致性检查用PrevLogIndex/PrevLogTerm验证日志前缀一致- 本地太短PrevLogIndex 超界→Successfalse- term 不匹配 →Successfalse截断并追加从PrevLogIndex1开始删除本地冲突后缀再追加Entries推进 commitIndexcommitIndex min(args.LeaderCommit, lastNewIndex)func (rf *Raft) AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply) { rf.mu.Lock() defer rf.mu.Unlock() DPrintf([%d] AppendEntries from L%d term%d, my term%d state%d, rf.me, args.LeaderId, args.Term, rf.currentTerm, rf.state) reply.Success false reply.Term rf.currentTerm // 发现任期比自己小 if args.Term rf.currentTerm { DPrintf([%d] AppendEntries: 拒绝 term 更小 leader%d argsTerm%d myTerm%d, rf.me, args.LeaderId, args.Term, rf.currentTerm) return } // 发现更高任期或来自合法 Leader 的心跳 rf.lastHeartBeatTime time.Now() if args.Term rf.currentTerm { rf.currentTerm args.Term rf.votedFor -1 rf.persist() DPrintf([%d] step down to Follower due to AE term%d, rf.me, rf.currentTerm) } rf.state Follower //一致性检查 //日志长度不够 Follower 若还没有 PrevLogIndex 这一条才拒绝 if rf.getLastIndex() args.PrevLogIndex { // 3C reply.ConflictTerm -1 // 3C reply.ConflictIndex rf.getLastIndex() 1 // 3C return // 3C } //一致性检查PrevLogIndex 处的 Term 是否匹配 // 特别注意如果 PrevLogIndex 恰好在快照边界要用 LastIncludedIndex if args.PrevLogIndex rf.LastIncludedIndex { // 3C reply.ConflictTerm -1 // 3C reply.ConflictIndex rf.LastIncludedIndex 1 // 3C return // 3C } //PrevLogIndex处任期不匹配 if rf.getTermByIndex(args.PrevLogIndex) ! args.PrevLogTerm { // 3C reply.ConflictTerm rf.getTermByIndex(args.PrevLogIndex) // 3C idx : args.PrevLogIndex // 3C //从最新的日志位置开始向前找找到冲突任期的下标 //告诉leader这个下标是冲突任期的下标下一步继续找冲突位置若没有则进行同步 for idx rf.LastIncludedIndex rf.getTermByIndex(idx) reply.ConflictTerm { // 3C idx-- // 3C } reply.ConflictIndex idx 1 // 3C return // 3C } //追加日志 isChange : false // 3D for i, entry : range args.Entries { // 3D logicIdx : i args.PrevLogIndex 1 // 3D // 如果 logicIdx 已经落入快照范围跳过或者报错理论上不该发生 if logicIdx rf.LastIncludedIndex { // 3D continue // 3D } phyIdx : rf.getPhysicIdx(logicIdx) // 3D if phyIdx len(rf.logs) { // 3D //如果索引范围内已经有日志了检查任期 if rf.logs[phyIdx].Term ! entry.Term { // 3D //如果追加日志的位置的任期和leader日志的位置的任期不相等 //将idx下标前面的日志进行切片保留 rf.logs rf.logs[:phyIdx] // 3D rf.logs append(rf.logs, entry) // 3D isChange true // 3D } //如果任期一样说明这一段已经同步过了下一条 } else { // 3D //超出本地的日志长度直接追加 rf.logs append(rf.logs, entry) // 3D isChange true // 3D } } if isChange { // 3D rf.persist() // 3D } // 更新 CommitIndex须用「当前日志最后一条」与 LeaderCommit 取 min。 // 心跳时 len(Entries)0若仍用 PrevLogIndex0 会小于 getLastIndex()导致 commit 永远追不上 Leader。 if args.LeaderCommit rf.commitIndex { rf.commitIndex min(args.LeaderCommit, rf.getLastIndex()) rf.applyCond.Broadcast() } reply.Success true }2.5 Leader 侧复制nextIndex / matchIndex 维护这一部分主要分为两个小点发送时构造 args按 peer 单独算-prevIdx : nextIndex[i]-1-entries : logs[nextIndex[i]:] 将日志切片- 心跳就是entries为空但仍携带LeaderCommit收到回复时更新新增关键成员ConflictTerm 冲突任期/ ConflictIndex冲突任期索引-Successtrue更新matchIndex[i]、nextIndex[i]-Successfalse回退nextIndex[i]并重试-优化性能关键ConflictTerm / ConflictIndex让回退“整块跳过”func (rf *Raft) sendAppendEntries(server int, args *AppendEntriesArgs, reply *AppendEntriesReply) bool { ok : rf.peers[server].Call(Raft.AppendEntries, args, reply) if ok { rf.mu.Lock() defer rf.mu.Unlock() // 处理回复任期更新、调整 nextIndex 等 if reply.Term rf.currentTerm { rf.currentTerm reply.Term rf.state Follower rf.votedFor -1 rf.persist() return ok } // 2. 状态检查 if rf.state ! Leader || rf.currentTerm ! args.Term { return ok } // 3B 以后你会在这里处理日志同步的 reply.Success 为 false 的情况 // 如果追加日志成功 —— 对应论文 Leader 规则If successful, update matchIndex and nextIndex if reply.Success { newMathIdx : args.PrevLogIndex len(args.Entries) if newMathIdx rf.matchIndex[server] { rf.matchIndex[server] newMathIdx } rf.nextIndex[server] rf.matchIndex[server] 1 // 更新提交的日志 rf.updateCommitIndex() } else { // 如果失败根据 reply.ConflictIndex 实现快速跳转 —— 对应论文If AppendEntries fails because of log inconsistency, decrement nextIndex and retry if reply.ConflictTerm -1 { // 日志过短 rf.nextIndex[server] reply.ConflictIndex } else { flag : false for i : args.PrevLogIndex; i rf.LastIncludedIndex; i-- { if rf.getTermByIndex(i) reply.ConflictTerm { flag true rf.nextIndex[server] i 1 break } } if !flag { rf.nextIndex[server] reply.ConflictIndex } } } } return ok }2.6 updateCommitIndexLeader 如何合法推进提交这节写清楚 Figure 8 约束非常重要Leader 推进到某个 indexN的条件- 多数派matchIndex[i] N- 且logs[N].Term rf.term只用当前任期的日志推进提交间接提交旧任期日志推荐这样写从后往前找最大的 N更快注意边界len(logs)-1和len(logs)// 日志提交应用-leader专属matchIndex/commitIndex 均为逻辑索引 func (rf *Raft) updateCommitIndex() { if rf.state ! Leader { return } for i : rf.getLastIndex(); i rf.commitIndex; i-- { if rf.getTermByIndex(i) rf.currentTerm { cnt : 1 for j : range rf.peers { if j ! rf.me rf.matchIndex[j] i { cnt } } if cnt len(rf.peers)/21 { rf.commitIndex i rf.applyCond.Broadcast() break } } else if rf.getTermByIndex(i) rf.currentTerm { break } } }2.7 applier把已提交日志送到 applyChan不要持锁发 chan在这部分中需要特别注意的是不要用 sleep 轮询延迟大、测试反馈慢用 sync.CondcommitIndex 增加时Broadcast唤醒 applier锁内拷贝、锁外发送避免applyChan阻塞时卡死整个 Raft来看这个简短伪代码流程lock → 等待commitIndex lastAppliedcond.Wait计算要 apply 的区间拷贝 entriesunlock → 逐条向applyChan发送lock → 更新lastApplied→ unlock2.8 3B 典型 Bug 记录我按表格整理了一下常见的坑我基本都是踩过的问题分类具体描述Agreement FailedcommitIndex 没推进 / applier 没被唤醒就是集群明明已经达成一致了但commitIndex死活不涨或者涨了却没人去 apply。要么是 Leader 忘了给 Follower 发心跳要么是 Follower 收到了心跳却没更新自己的commitIndex再要么是applyLoop没被唤醒卡在 channel 上没人通知。too many RPCs心跳过频缺少节流每个日志条目都单独发一次 RPC或者心跳发得太快把网络打满。正确做法是用lastBroadcastTime做个节流比如 10ms 内只发一次心跳没必要每条日志都立刻广播。回退太慢未实现 conflict 优化日志冲突之后如果只靠nextIndex--一格格往回退遇到恶意日志会退几百次导致同步极慢。用论文里的conflict term 和 conflict index做快速回退一次性跳到冲突点性能好很多。死锁持锁发 chan / 持锁做重活最常见的是持有锁然后向 applyCh 发消息如果对端处理慢或者也来拿同一把锁就死锁了。还有就是持有锁做耗时的磁盘写入虽然不死锁但会卡住整个 Raft 状态机。解决方法是先拷贝需要的数据解锁再发 chan 或写盘。这些 Bug 在 3B 阶段几乎每个人都会遇到提前有个印象能省不少调试时间。三、Part C持久化Persistence3C3.1 3C 的核心持久化“承诺”不是持久化“结果”一句话只要重启可能导致你做出与重启前矛盾的行为就必须在返回 RPC 之前把状态写盘其实很简单只要将需要持久化的内容每次改动的时候进行持久化就可以了。3.2 persist/readPersist持久化内容与编码格式持久化内容Figure 2rf.termrf.votedForrf.logs编码顺序必须和解码顺序一致否则 readPersist 会失忆/乱序这里也是一个坑但是我这里为了方便怎么存的怎么取所以把坑跳过去了。func (rf *Raft) persist() { // Your code here (3C). // Example: // w : new(bytes.Buffer) // e : labgob.NewEncoder(w) // e.Encode(rf.xxx) // e.Encode(rf.yyy) // raftstate : w.Bytes() // rf.persister.Save(raftstate, nil) w : new(bytes.Buffer) e : labgob.NewEncoder(w) e.Encode(rf.currentTerm) e.Encode(rf.votedFor) e.Encode(rf.logs) e.Encode(rf.LastIncludedIndex) e.Encode(rf.LastIncludedTerm) raftstate : w.Bytes() snap : rf.persister.ReadSnapshot()//先读取快照 rf.persister.Save(raftstate, snap)//再持久化状态和快照 } // restore previously persisted state. func (rf *Raft) readPersist(data []byte) { if data nil || len(data) 1 { // bootstrap without any state? return } // Your code here (3C). // Example: r : bytes.NewBuffer(data) d : labgob.NewDecoder(r) var term int var vorfor int var logs []LogEntry var lastincludedindex int var lastincludedterm int if d.Decode(term) ! nil || d.Decode(vorfor) ! nil || d.Decode(logs) ! nil || d.Decode(lastincludedindex) ! nil || d.Decode(lastincludedterm) ! nil { DPrintf(readPersist err) } else { rf.currentTerm term rf.votedFor vorfor rf.logs logs rf.LastIncludedIndex lastincludedindex rf.LastIncludedTerm lastincludedterm } }3.3 何时调用 persist时机与原子性可以按谁改了谁负责 persist写成清单startElectionterm、votedForme之后RequestVote更新term/votedFor之后尤其是投票成功路径AppendEntries看到更大 term 退位时日志截断/追加时Start追加日志后关键点一定要在 handler 返回 reply 之前 persist否则崩溃重启后可能同任期重复投票造成脑裂等一系列问题。3.4 为什么 3B 正常、3C 就崩3B 都过了3C 断电测试出现 Log Inconsistency根因通常是readPersist 没写 / 解码顺序错 / logs 没恢复占位条目commitIndex/lastApplied/nextIndex/matchIndex不需要持久化它们会在重启后通过 Leader 的 LeaderCommit、以及日志复制流程动态恢复。3.5 性能与正确性的取舍persist 频率高会拖慢系统尤其心跳很频繁时心跳频率要“优雅”足够快维持领导权但不能淹没网络too many RPCs正确性优先该 persist 的地方不能省优化要在正确性上做节流/批量/减少无效 RPC四、测试和遇到的问题cd 6.5840/src make RUN-run 3B raft1 make RUN-run 3C raft13B 阶段主要折腾的是 Raft 里两个搬运者谁在什么时候推进提交、谁把已提交日志交给状态机。我对这两块做了比较彻底的重构。updateCommitIndexLeader 侧问题一开始有数组越界len和len-1混用、以及用「日志下标」去当matchIndex的下标这类逻辑错误。做法改成从后往前扫合法的提交点 NN并严格按 Figure 8Leader 只能用「当前任期里复制到多数派的那条日志」去推进commitIndex旧任期的条目只能被顺带提交。Figure 2 流水线自测时心里要有这条链Start写日志 → Leader 发AppendEntries→ Follower 确认并追加 → Leader 用matchIndex推进commitIndex并唤醒 applier → 后续心跳带上LeaderCommitFollower 跟进commitIndex并同样唤醒 applier → 双方经applyChan按序应用。实现中需要注意的点尽量不要在持锁时写 channel。等 commit 用sync.Cond少用忙等 / 固定Sleep。心跳够快以维持领导权但不要打到 RPC 风暴。readPersist这是 3C 里很隐蔽的一类问题没实现、或 Decode 顺序和 Encode 对不上节点等于「失忆」往往在断电测试里表现为大量 Log Inconsistency而纯 3B 有时还能蒙混过关。性能和正确性HeartBeatTimeout、RPC 频率和persist次数会互相拉扯变了就存最安全但心跳极密时无脑persist会把测试拖慢。可以在保证该存必存的前提下适当拉长心跳间隔、减少无意义刷盘具体以你当时通过测试的配置为准。哪些不用存commitIndex等易失状态不必持久化重启后靠 Leader 的 LeaderCommit 和日志一致性检查再对齐即可。其它 3B 测试里碰到的问题现象原因与处理Agreement 失败one(100)等闭环缺一环Leader 收到成功回复没更新提交或 Follower 更新了commitIndex却没唤醒 applier。RPC 过多too many RPCs心跳发得太勤例如 ticker 里固定短间隔全员 RPC。需要按间隔节流如配合选举/心跳超时。冲突回退慢性能测试超时nextIndex一格一格退。应实现 ConflictTerm / ConflictIndex让 Leader 整块对齐。死锁测试 hang持锁路径里 RPC 回调或 apply 过重。缩小锁粒度禁止持锁写 channel。3C持久化测试拉长后才会暴露何时persist、保的是什么我一开始在Start里就落了盘其它 RPC 路径也零零散散加了一些persist跑 3C 才发现还有路径没覆盖全。要点持久化保的不是业务结果而是 承诺——凡是崩溃重启后可能做出和崩溃前矛盾的事例如同一任期投两次票就要在 对外承诺已经形成之后、RPC 返回之前 把该存的状态写盘。applier应用侧问题早期用Sleep轮询commitIndex测试反馈慢还有在持锁时往applyChan里送消息容易把整个节点卡死。做法用sync.Cond在commitIndex前进时Broadcast发送 apply 消息时坚持 锁里只拷贝、锁外再写 channel避免 channel 阻塞拖死持锁路径。这是最终测试通过的输出3Blcziv-yef3xahqtc5i3z5jzmr5:~/mit6.5840/6.5840/src$ make RUN-run 3B raft1go build -race -o main/raft1d main/raft1d.go cd raft1 go test -v -race -run 3B RUN TestBasicAgree3B Test (3B): basic agreement (reliable network)... ... Passed -- time 0.4s #peers 3 #RPCs 14 #Ops 3--- PASS: TestBasicAgree3B (0.71s) RUN TestRPCBytes3B Test (3B): RPC byte count (reliable network)... ... Passed -- time 1.8s #peers 3 #RPCs 58 #Ops 11--- PASS: TestRPCBytes3B (2.14s) RUN TestFollowerFailure3B Test (3B): test progressive failure of followers (reliable network)...... Passed -- time 4.3s #peers 3 #RPCs 188 #Ops 3--- PASS: TestFollowerFailure3B (4.67s) RUN TestLeaderFailure3B Test (3B): test failure of leaders (reliable network)...... Passed -- time 4.7s #peers 3 #RPCs 294 #Ops 3--- PASS: TestLeaderFailure3B (5.03s) RUN TestFailAgree3B Test (3B): agreement after follower reconnects (reliable network)...... Passed -- time 3.9s #peers 3 #RPCs 134 #Ops 7--- PASS: TestFailAgree3B (4.37s) RUN TestFailNoAgree3B Test (3B): no agreement if too many followers disconnect (reliable network)...... Passed -- time 3.3s #peers 5 #RPCs 316 #Ops 2--- PASS: TestFailNoAgree3B (3.81s) RUN TestConcurrentStarts3B Test (3B): concurrent Start()s (reliable network)... ... Passed -- time 0.6s #peers 3 #RPCs 24 #Ops 0--- PASS: TestConcurrentStarts3B (1.07s) RUN TestRejoin3B Test (3B): rejoin of partitioned leader (reliable network)...... Passed -- time 5.7s #peers 3 #RPCs 282 #Ops 4--- PASS: TestRejoin3B (6.05s) RUN TestBackup3B Test (3B): leader backs up quickly over incorrect follower logs (reliable network)...... Passed -- time 19.1s #peers 5 #RPCs 2568 #Ops 102--- PASS: TestBackup3B (19.68s) RUN TestCount3B Test (3B): RPC counts arent too high (reliable network)...... Passed -- time 2.2s #peers 3 #RPCs 72 #Ops 0--- PASS: TestCount3B (2.71s) PASS ok 6.5840/raft1 51.273s3Clcziv-yef3xahqtc5i3z5jzmr5:~/mit6.5840/6.5840/src$ make RUN-run 3C raft1go build -race -o main/raft1d main/raft1d.gocd raft1 go test -v -race -run 3C RUN TestPersist13CTest (3C): basic persistence (reliable network)...... Passed -- time 3.3s #peers 3 #RPCs 98 #Ops 6--- PASS: TestPersist13C (3.75s) RUN TestPersist23CTest (3C): more persistence (reliable network)...... Passed -- time 13.7s #peers 5 #RPCs 568 #Ops 16--- PASS: TestPersist23C (14.36s) RUN TestPersist33CTest (3C): partitioned leader and one follower crash, leader restarts (reliable network)...... Passed -- time 1.5s #peers 3 #RPCs 48 #Ops 4--- PASS: TestPersist33C (1.84s) RUN TestFigure83CTest (3C): Figure 8 (reliable network)...2026/03/18 22:15:05 6PCdkEFTs2eiMT_RlFB1: dmxsrv.reader: clnt ACu3swj2_8gbs1Wd6nbn ReadCall err read unix /tmp/6.5840-6PCdkEFTs2eiMT_RlFB1-: read: connection reset by peer2026/03/18 22:15:47 6PCdkEFTs2eiMT_RlFB1: dmxsrv.reader: clnt 5VPxjteaE_i4P1o9h71T ReadCall err read unix /tmp/6.5840-6PCdkEFTs2eiMT_RlFB1-: read: connection reset by peer... Passed -- time 51.8s #peers 5 #RPCs 2369 #Ops 2--- PASS: TestFigure83C (52.30s) RUN TestUnreliableAgree3CTest (3C): unreliable agreement (unreliable network)...... Passed -- time 3.4s #peers 5 #RPCs 220 #Ops 246--- PASS: TestUnreliableAgree3C (4.02s) RUN TestFigure8Unreliable3CTest (3C): Figure 8 (unreliable) (unreliable network)...... Passed -- time 48.0s #peers 5 #RPCs 7496 #Ops 22026/03/18 22:16:44 T5AgHTtizWPRzjsYwAQ6: dmxsrv.reader: clnt UkD_e2Q-b5OG3f1PBPSa ReadCall err read unix /tmp/6.5840-T5AgHTtizWPRzjsYwAQ6-: read: connection reset by peer--- PASS: TestFigure8Unreliable3C (48.77s) RUN TestReliableChurn3CTest (3C): churn (reliable network)...... Passed -- time 16.6s #peers 5 #RPCs 1084 #Ops 1--- PASS: TestReliableChurn3C (17.17s) RUN TestUnreliableChurn3CTest (3C): unreliable churn (unreliable network)...... Passed -- time 16.8s #peers 5 #RPCs 1028 #Ops 1--- PASS: TestUnreliableChurn3C (17.46s)PASSok 6.5840/raft1 160.685s五、收获在看完论文理解之后lab3还是较简单的但是对于test中其实并不能test出你代码的漏洞就像我之前ticker设置的检索间隔一样。照样是通过了所有test。但是在B中却因为RPC调用太频繁超时了。我们在代码实现中要使用尽量多的调试信息打印以便后续调试希望我的思路可以带给你们思路然后按照自己的思路实现出属于自己的lab1。最后希望有错误的地方多指正指正~完整实现mit6.5840: 用来记录mit6.5840原6.824的实现历程觉得有收获的可以帮忙点个star~