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.
On top of that log sits the thing the log is for: a replicated key/value service whose Put is a compare-and-set against a version number, so a retry can’t apply twice, and whose client is told “maybe” rather than a guess when the network loses a reply it can’t disambiguate.
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
}
}A reply that arrives late must not be believed
A new entry doesn't wait for the next heartbeat to go out — appending it fans a round of replication to every peer immediately, which is what keeps commit latency at one round trip instead of one heartbeat interval. The cost is that several AppendEntries can now be in flight to the same follower at once, and their replies come back in any order. So a success only counts if it advances that follower's match index past where it already is, and a rejection is only acted on if the leader's guess hasn't moved since the request went out. Without those two guards a stale reply drags the follower's index backward and the repair loop starts over.
for i := range rf.peers {
if i == rf.me {
continue
}
go rf.replicateToPeer(term, i)
}
if reply.Success {
newMatch := prevLogIndex + len(entries)
if newMatch > rf.matchIndex[server] {
rf.matchIndex[server] = newMatch
rf.nextIndex[server] = rf.matchIndex[server] + 1
rf.updateCommitIndex()
}
}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)
}The log is a means; the service on top is the point
Consensus on its own stores nothing anyone asked for. A replicated state machine sits above the log: every request is wrapped with the identity of the server that proposed it, handed to Raft, and the caller blocks until it comes back out of the apply channel at the index it went in at. A single reader drains that channel and executes each command exactly once, in log order, on every peer — which is what makes five copies agree on what the map holds and not merely on what the log says.
index, term, isLeader := rsm.rf.Start(op)
if !isLeader {
rsm.mu.Unlock()
return rpc.ErrWrongLeader, nil
}
ch := make(chan opResult, 1)
rsm.waiting[index] = ch
rsm.mu.Unlock()
for {
select {
case result := <-ch:
if result.id != op.Id || result.me != op.Me {
return rpc.ErrWrongLeader, nil
}
return rpc.OK, result.value
case <-time.After(50 * time.Millisecond):
curTerm, stillLeader := rsm.rf.GetState()
if !stillLeader || curTerm != term {
return rpc.ErrWrongLeader, nil
}
}
}Waiting on an index isn't the same as waiting on your request
A deposed leader's log entry can be overwritten by the next leader, so the thing that eventually surfaces at your index may not be the thing you put there. Comparing identity on the way out is what catches that — a mismatch means the entry was replaced and the caller is told to find the new leader. The periodic timeout covers the quieter version of the same failure: a leader partitioned away hears nothing at all, so it re-checks its own term rather than blocking a client forever.
The honest answer is sometimes "maybe"
Put carries the version it expects, and the server applies it only if that version still matches — a compare-and-set, so a retry that arrives twice can't apply twice. But a reply lost in the network leaves a real ambiguity: a resend rejected for a stale version might be colliding with the client's own first attempt, which did succeed. The clerk refuses to guess. A first-attempt rejection returns a plain version error; the same rejection on a resend returns "maybe," and the application above decides what to do with an answer nobody can recover.
if reply.Err == rpc.ErrWrongLeader {
continue
}
ck.leader = idx
if reply.Err == rpc.ErrVersion && retried {
return rpc.ErrMaybe
}
return reply.Err- Language
- Go
- Paper
- Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm" (2014)
- Scope
- Leader election, log replication, crash persistence, log compaction with snapshots
- Above it
- A linearizable key/value service replicated over the log, with a versioned compare-and-set Put
- 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