6.824 Lab2

编号对照：本系列写于 2021/2022 版课程。现在课号已改为 6.5840，lab 也重排过——现行编号是 Lab 1 MapReduce、Lab 2 Key/Value server、Lab 3 Raft（3A 选举 / 3B 日志 / 3C 持久化 / 3D 日志压缩）、Lab 4 KV Raft、Lab 5 Sharded KV。对应关系：本文的 Lab2（Raft）= 现行 Lab3，Lab3（KV）= 现行 Lab4，Lab4（Sharded KV）= 现行 Lab5。正文里的 2A/2B/2C/2D、TestSpeed3A、TestFigure8Unreliable2C 这类测试名都是旧编号，没有逐一替换。

Raft

Raft 是一个实现分布式共识的协议，主要解决的是分布式一致性的问题。

Overview

假设现在有一个 Raft 架构的服务。我们将这个服务分为三层，Client，Service，Raft。Client 层首先发送请求给 Service 层，然后 Service 层解析请求为command，将command发送给 Raft 层的 Leader。Leader 在一定时间内通知 Service 层 “apply” 包含这个command的日志，Service 层才可以将这条日志保存到状态机，进而返回对应的结果给 Client 层。并且因为 Raft 层不应该存储过多的 log，所以 Service 层还会将 applied 的 log 压缩成快照，以便快速应用。

我们的任务就是用 go 实现基础的 Raft 层架构。

领导人选举

最初，所有 Raft 节点都是 Follower，如果在election timeout内未收到当前term的heartbeat，就会转为 Candidate。
- election timeout: 选举超时时间。lab 限制心跳不能超过每秒 10 次，所以心跳周期要取 100ms 以上（我建议 100~~150ms），election timeout 取心跳周期的 3~~6 倍，并且要小于 1s——太小会被正常心跳抖动误判，太大则来不及在测试要求的 5s 内选出 Leader。
- term：任期。每个用于实现一致性共识。
- heartbeat：心跳。Raft 节点有三种状态：Follower，Candidate，Leader。Leader 为了维持自己的领导，需要每隔一段时间发送一次心跳。
转为 Candidate 之后，term++，给自己投票，并发送请求投票的 RPC 给 peer 节点。
收到请求 RPC 的 peer 满足以下两个条件才可以投票：
- peer 任期小于 Candidate 的任期或者 peer 任期等于 Candidate 并且当前任期没投过。
- Candidate 的 log 至少和自己一样新（注意是「不比自己旧」，不是「严格比自己新」——两边日志完全相同是最常见的情况，按「严格新」实现根本选不出 Leader）。判定顺序是先比 lastLogTerm，lastLogTerm 更大的更新；相同的话再比 lastLogIndex，更长的更新。
Candidate 得到的票数超过半数的 peer 就可以成为 Leader，因为上述限制，一个集群同一个term只会选出一个 Leader。
Leader 每隔一次heartbeat timeout就发送一次包含 snapshot 或 log 的 heartbeat，发送快照还是日志根据 peer 的 nextIndex 而定。
- nextIndex 是 Leader 对 peer 日志长度的乐观推测，成为 Leader 后会对所有 peer 的 nextIndex 赋值为自己的 lastLogIndex+1，而后会根据 heartbeat 结果更改 nextIndex。
- lastIncludeIndex 每个节点都有，表示 snapshot 包含的最后一个日志的下标，初始为 0。
- 如果 $nextIndex \leq lastIncludedIndex$ ，发送 InstallSnapshot RPC，否则发送 AppendEntries RPC。
Follower 需要对 Leader 发送的心跳进行处理。

日志复制

Service 层会通过 Start(cmd) 发送 command 给 Leader。
Leader 需要保存 command 至 log，并在心跳的时候向 Follower 发送他没有的 log。
Leader 等到含自己在内的多数派都写入了这条日志，再进行 commit。注意是多数派而不是「一半以上的 Follower」：n=5 时只需要 leader 自己加 2 个 Follower 就够了，按「3 个 Follower」实现会白白损失可用性。所以计数要从 1（Leader 自己）起算。
- 判断 Follower 写入日志的标准是 matchIndex，上面有提到 nextIndex 是 Leader 对 peer 日志长度的乐观推测，matchIndex 则是相对悲观的推测，只有在 AppendEntries RPC 返回成功后 Leader 才会更新相应 Follower 的 matchIndex。
- 并且考虑 RPC 调用的非线性返回，需要在修改 matchIndex 的时候判断需要修改的值是否真的大于当前的 matchIndex 的值。
- 还有一个容易漏掉的约束：只有 log[N].Term == currentTerm 的 N 才能被 Leader 直接推进 commitIndex。这就是论文 Figure 8 的那个坑——旧任期的日志即使已经复制到多数派，也不能靠计数直接提交，只能等本任期的日志提交后被顺带提交。
Leader commit 后修改 commitIndex 的值，然后唤醒 applier 把 lastApplied+1 到 commitIndex 的日志推到 applyCh。
这里有个坑：不要每次 commit 就新起一个 go routine 去推 applyCh。多个 goroutine 并发往同一个 channel 发送，顺序完全没有保证，而且两个 goroutine 读到的 lastApplied/commitIndex 区间会重叠，结果就是上层收到乱序或重复的 ApplyMsg。官方的 raft-structure.txt 要求用一个长期运行的 applier goroutine 按序发送，配合 sync.Cond 等待 commitIndex > lastApplied 被唤醒。
另外 lastApplied 要逐条 lastApplied++ 地推进（发一条加一条），不要在循环结束后直接 lastApplied = commitIndex——加上 2D 的快照后，InstallSnapshot 可能在中途把 lastApplied 抬到更高的位置，直接赋值会让它倒退，于是快照里的日志又被重复 apply 一遍。
Follower 在 Leader commit 后也会以 Leader 的 commitIndex 作为限制 commit 自己的 log，并和 Leader 一样，将日志交给 service apply。

日志压缩

Service 层在若干 commit 后，会压缩已提交的日志，并通过 Snapshot(index,snapshot) 提醒 raft 层。
raft 层则需要进行一些处理，比如删掉被压缩的日志，改变日志的索引方式，通过 persister.SaveStateAndSnapshot 把 Raft 状态和快照一起落盘。快照本身是由 Raft 通过 persister 持久化的，Raft 只是不解释它的内容——对 Raft 来说它就是一段不透明的 []byte，怎么编码、里面装了什么都是 Service 层的事。
对于 Leader，在 heartbeat 时，若满足 $nextIndex \leq lastIncludedIndex$ ，则通过 persister.ReadSnapshot() 读取 snapshot 给 Follower。
Follower 收到 InstallSnapshot，先照常做任期检查（args.Term < currentTerm 直接拒），任期不过期时才继续。但在真正安装之前还要加一道判断：如果快照的 lastIncludedIndex $\leq$ 自身的 commitIndex，说明这是一个迟到的快照，自己已经通过日志走得比它更远，必须直接丢弃返回。否则会把 commitIndex/lastApplied 拽回去，让上层重复 apply 一段已经应用过的状态。确认要安装后，再删掉被压缩的日志、改变日志的索引方式、持久化快照，并把快照交给 applier 送上去。

Tips

注意 data race，对大部分 rf 结构的修改和读取都要上锁。
所有 RPC 都要检测任期，并对过期状态进行处理。
在 lab2D 中，需要改变下标的索引方式。

Each log entry also has an integer index iden-tifying its position in the log.

但这个其实很容易改，所以推荐在 2D 之前不要去管下标的问题，直接用 log 数组自己的下标就可以了。

struct

const NULL int = -1
const (
	_ = iota
	Follower
	Candidate
	Leader
)

type ApplyMsg struct {
	CommandValid bool
	Command      interface{}
	CommandIndex int

	SnapshotValid bool
	Snapshot      []byte
	SnapshotTerm  int
	SnapshotIndex int
}

type Entry struct {
	Command interface{} // Command for state machine
	Term    int         // Command received Term
	Index   int
}

// A Go object implementing a single Raft peer.
type Raft struct {
	mu        sync.Mutex          // Lock to protect shared access to this peer's state
	peers     []*labrpc.ClientEnd // RPC end points of all peers
	persister *Persister          // Object to hold this peer's persisted state
	me        int                 // this peer's index into peers[]
	dead      int32               // set by Kill()

	// Persistent state
	currentTerm int     // 0...
	votedFor    int     // null if none
	log         []Entry // index 1...

	// Volatile state
	commitIndex    int // most of the server has been replicated and durable, 0...
	lastApplied    int // highest entry applied to state machine, 0...
	state          int
	heartbeatTimer *time.Timer
	electionTimer  *time.Timer
	applyCh        chan ApplyMsg
	applyWaker     chan int
	// for leader (reinitialized after election)
	nextIndex  []int // last log index+1...
	matchIndex []int // highest log entry be replicated on server, 0..., update: PrevLogIndex+len(Entries)
}

func (rf *Raft) lastIncludedTerm() int {
	return rf.log[0].Term
}

func (rf *Raft) lastIncludedIndex() int {
	return rf.log[0].Index
}

func (rf *Raft) setLastIncludedTerm(term int) {
	rf.log[0].Term = term
}

func (rf *Raft) setLastIncludedIndex(index int) {
	rf.log[0].Index = index
}

func getHeartbeatDuration() time.Duration {
	return time.Millisecond * 60
}

func getElectionDuration() time.Duration {
	return time.Millisecond * time.Duration(rand.Int31n(180)+180)
}

2026-08 更新：上面这段代码里 getHeartbeatDuration() 返回 60ms，这个值是不对的——60ms 约等于每秒 16.7 次心跳，直接违反 lab 的 “no more than ten times per second”，会让统计 RPC 次数的那几个测试挂掉。应该改成 100~~150ms 心跳，getElectionDuration() 相应取 rand(300)+300 这个量级（300~~600ms）。
另外结构体里的 applyWaker chan int 也是个历史包袱：用 channel 唤醒 applier 会在持锁发送时死锁（见 lab2B），换成 sync.Cond 更干净。