Distributed systems · 2026 · completed
Raft
Consensus in Go — election, replication, crash recovery, and snapshots.
Five machines, one truth, and no way to tell a crashed peer from a slow one. Raft is the answer to that problem — a consensus algorithm written to be understood rather than merely proved — and this is an implementation of it in Go, built up test by test rather than pulled in as a library. The cluster picks its own leader with nothing but randomized timers and term numbers; it agrees on a log as well as a leader, with followers refusing any batch that doesn’t line up behind what they already hold; and nothing counts as committed until a majority carries it. Term, vote, and log reach stable storage before the reply that depends on them goes out, so a killed server comes back with its promises intact. Once the service above has checkpointed its state, the log behind that point is discarded and every index rebased on what remains — and a follower that falls off the back of the snapshot is caught up with the checkpoint itself rather than with entries nobody kept. It holds through leaders failing, followers dropping out, partitioned machines rejoining, and a network that drops, delays, and reorders: 28 of 28 failure scenarios.
The instrument
One timer decides who leads
Every peer redraws a 300–600 ms deadline each cycle; the first to run out becomes a candidate and asks the rest for a term. The randomness is the whole trick — it makes simultaneous candidacies rare, so a split vote resolves on the next round instead of repeating forever. Replies are discarded by term, because a vote arriving after the election belongs to a different one.
A rejection that says where to look
A follower that refuses a batch doesn't just say no — it names the term that conflicted and the index where that term begins in its own log. The leader jumps its guess straight past its own last entry of that term instead of walking back one index per round trip, collapsing what could be dozens of RPCs into one or two.
Everything before the line stops existing
When the service above checkpoints its state, Raft discards the log behind it and keeps a single sentinel entry carrying the index and term it stood at — every index in the implementation is then relative to that boundary. A follower that falls behind it can't be repaired with entries that no longer exist, so the leader ships the checkpoint itself.
28 failure scenarios, all green
The harness runs under a simulated network that drops, delays, and reorders RPCs; kills peers and restarts them holding nothing but their persisted bytes; and partitions the cluster mid-agreement. Election, replication, crash persistence, and snapshots — 28 of 28.
The movement
The engineering underneath
A majority, not everyone. Every other piece here exists to protect that one rule.
A leader with no one to appoint it
Each server waits out a randomized timeout and calls an election if no heartbeat arrives in time; the randomness is what keeps split votes from repeating forever. No fixed leader, no external coordinator — just timers and term numbers deciding who's in charge. A candidate fans its request out in parallel and stops counting the moment the term it was elected under has moved on: a vote that arrives late belongs to an election that's already over.
go func(server int) {
reply := RequestVoteReply{}
if !rf.sendRequestVote(server, &args, &reply) {
return
}
rf.mu.Lock()
defer rf.mu.Unlock()
if reply.Term > rf.currentTerm {
rf.currentTerm = reply.Term
rf.state = follower
rf.votedFor = -1
rf.persist()
return
}
if rf.state != candidate || rf.currentTerm != term {
return
}
if reply.VoteGranted {
voteMu.Lock()
votes++
count := votes
voteMu.Unlock()
if count > len(rf.peers)/2 && rf.state == candidate {
rf.state = leader
rf.nextIndex = make([]int, len(rf.peers))
rf.matchIndex = make([]int, len(rf.peers))
for i := range rf.peers {
rf.nextIndex[i] = rf.lastIncludedIndex + len(rf.log)
rf.matchIndex[i] = 0
}
go rf.sendHeartbeats(term)
}
}
}(i)The follower is the one who says no
A leader can't simply announce the log — it has to prove it lines up. Every batch names the entry that should come just before it, and a follower that doesn't have that exact index and term refuses outright. Where the two diverge, the follower truncates its own tail rather than keeping a record nobody else has. The guard for a matching prefix is what stops it from cutting away entries a delayed, reordered RPC has already delivered.
for i, entry := range args.Entries {
absIdx := args.PrevLogIndex + 1 + i
if absIdx <= lastLogIndex {
if rf.log[rf.idx(absIdx)].Term != entry.Term {
rf.log = rf.log[:rf.idx(absIdx)]
rf.log = append(rf.log, args.Entries[i:]...)
break
}
} else {
rf.log = append(rf.log, args.Entries[i:]...)
break
}
}The rejection carries a hint
Refusing is correct but slow: learning "conflict at index N" and retrying at N-1, then N-2, costs one round trip per entry, and a follower partitioned for a while can be hundreds behind. So the reply carries the term that conflicted and the first index of that term in the follower's log. The leader either jumps past its own last entry of that term or takes the follower's hint outright — one RPC either way.
if reply.ConflictTerm == -1 {
rf.nextIndex[server] = reply.ConflictIndex
} else {
idx := prevLogIndex
for idx > rf.lastIncludedIndex &&
rf.log[rf.idx(idx)].Term > reply.ConflictTerm {
idx--
}
if idx > rf.lastIncludedIndex &&
rf.log[rf.idx(idx)].Term == reply.ConflictTerm {
rf.nextIndex[server] = idx + 1
} else {
rf.nextIndex[server] = reply.ConflictIndex
}
}Committed means "on a majority," not "on everyone"
Electing a leader settles who speaks; the log settles what was said. An entry becomes safe to apply once it sits at the same index on more than half the cluster — the leader scans backward for the highest such index and moves the commit line there. The extra condition is the one that's easy to miss: only entries from the leader's own term count. Counting an inherited entry into a majority is how a committed record can still be lost. Stragglers catch up later; the majority is what makes it durable now.
func (rf *Raft) updateCommitIndex() {
lastLogIndex := rf.lastIncludedIndex + len(rf.log) - 1
for n := lastLogIndex; n > rf.commitIndex; n-- {
if rf.log[rf.idx(n)].Term != rf.currentTerm {
continue
}
count := 1
for i := range rf.peers {
if i != rf.me && rf.matchIndex[i] >= n {
count++
}
}
if count > len(rf.peers)/2 {
rf.commitIndex = n
break
}
}
}A promise you can't take back has to be on disk first
A vote and a log entry are both promises, and a server that forgets one after a restart can hand the cluster two leaders in the same term or lose an entry a majority already acknowledged. So term, vote, log, and the snapshot boundary go to stable storage before the reply that depends on them leaves — never after. Snapshot bytes are carried through untouched on an ordinary persist, which keeps a state save from quietly discarding a checkpoint.
func (rf *Raft) persist() {
rf.persistWithSnapshot(rf.persister.ReadSnapshot())
}
func (rf *Raft) persistWithSnapshot(snapshot []byte) {
w := new(bytes.Buffer)
e := labgob.NewEncoder(w)
e.Encode(rf.currentTerm)
e.Encode(rf.votedFor)
e.Encode(rf.log)
e.Encode(rf.lastIncludedIndex)
e.Encode(rf.lastIncludedTerm)
rf.persister.Save(w.Bytes(), snapshot)
}A log that grows forever isn't a log, it's a leak
Once the service above has checkpointed its state, the entries that produced it are dead weight — replaying them would only rebuild what the checkpoint already holds. Trimming them means every absolute index in the paper now has to be translated through the snapshot boundary, which is where the real difficulty lives: one dummy entry survives at the front, carrying the index and term of the last thing folded away, so log matching still has something to check against.
func (rf *Raft) idx(absIndex int) int {
return absIndex - rf.lastIncludedIndex
}
func (rf *Raft) Snapshot(index int, snapshot []byte) {
rf.mu.Lock()
defer rf.mu.Unlock()
if index <= rf.lastIncludedIndex {
return
}
newLastIncludedTerm := rf.log[rf.idx(index)].Term
newLog := make([]LogEntry, 1)
newLog[0] = LogEntry{Term: newLastIncludedTerm}
newLog = append(newLog, rf.log[rf.idx(index)+1:]...)
rf.log = newLog
rf.lastIncludedIndex = index
rf.lastIncludedTerm = newLastIncludedTerm
rf.persistWithSnapshot(snapshot)
}- Language
- Go
- Paper
- Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm" (2014)
- Scope
- Leader election, log replication, crash persistence, log compaction with snapshots
- Safety rule
- A leader commits only entries from its own term — inherited entries ride along
- Repair
- Conflict-term backup — one round trip where a naive decrement takes many
- Testing
- 28 of 28 failure scenarios — packet loss, reordering, partition, crash-restart
- Basis
- MIT 6.5840 (Distributed Systems), self-study