Raft in Production¶

From correct to usable¶

The core algorithm in Raft: Leader Election and Raft: Log Replication is correct but not deployable: its log grows forever, a node that rejoins after a partition disrupts a healthy cluster, an isolated leader never notices it is isolated, the set of servers can never change, and storage costs grow with the log. This page covers the additions that fix each of these in labs/raft and labs/raftwal, and what each one measurably changes. All cluster numbers come from the simulated network under testing/synctest; storage numbers come from a real disk (Apple M1 Pro internal NVMe, macOS, where Go's File.Sync is F_FULLFSYNC, about 4 ms).

Snapshots and log compaction¶

The state machine periodically saves its state and tells Raft:

// Snapshot tells Raft that the state machine has saved its state up to
// and including index; log entries up to there can be discarded. The
// state machine's own data must be durable before calling this.
func (n *Node) Snapshot(index uint64, data []byte) {
    n.mu.Lock()
    defer n.mu.Unlock()
    if index <= n.base() || index > n.lastApplied || n.dead.Load() {
        return
    }
    s := &Snapshot{Index: index, Term: n.at(index).Term, Config: n.configAt(index), Data: data}
    n.log = append([]Entry{{Index: index, Term: s.Term}}, n.log[index-n.base()+1:]...)
    n.snapshot = s
    n.save(Update{HardState: n.hardState(), Snapshot: s})
}

After compaction the log no longer starts at index 1. log[0] becomes a sentinel holding the index and term of the last entry the snapshot covers, and every access goes through n.at(i) = n.log[i - n.base()]. The snapshot records the membership as of its index, because the configuration entries it replaces are gone.

A follower that needs entries the leader has already discarded receives the whole snapshot instead:

func (n *Node) HandleInstallSnapshot(args InstallSnapshotArgs) InstallSnapshotReply {
    // ... term checks, accept the leader ...
    s := args.Snapshot
    if s.Index <= n.commitIndex {
        return InstallSnapshotReply{Term: n.term} // we already have all of it
    }
    discard := true
    if s.Index <= n.lastIndex() && n.at(s.Index).Term == s.Term {
        // Our log agrees with the snapshot: keep the entries after it.
        n.log = append([]Entry{{Index: s.Index, Term: s.Term}}, n.log[s.Index-n.base()+1:]...)
        discard = false
    } else {
        n.log = []Entry{{Index: s.Index, Term: s.Term}}
    }
    n.snapshot, n.commitIndex, n.pendingSnap = &s, s.Index, &s
    n.save(Update{HardState: n.hardState(), Snapshot: &s, DiscardLog: discard})
    n.recomputeConfig()
    n.applyCond.Broadcast() // the applier delivers the snapshot before any later entry
    // ...
}

The applier delivers a pending snapshot before any entry that follows it, so the state machine sees one ordered stream: its state is replaced, then the entries after the snapshot are applied.

Measured:

Test	Result
3 nodes, snapshot every 10 entries, 300 commands with one follower disconnected	Leader's in-memory log never exceeds 20 entries; on reconnect the lagging follower catches up through one InstallSnapshot and then holds 2 log entries
5 nodes, unreliable network, random crashes and partitions, snapshot every 7 entries, 5 seeds	148–168 entries committed per run, 57–72 snapshots installed through apply channels; State Machine Safety checked on every entry and every snapshot
KV store exactly-once test, 10 crash/restart rounds, snapshot every 50	1,503 appends, each present exactly once; largest in-memory log 33 entries (1,549 without snapshots)

The ordering rule that matters: the state machine's data must be durable before Raft discards the log. The KV server writes a synced batch, then dumps the db, then calls Snapshot. If Raft trimmed the log first and the server crashed before its db was flushed, the restarted server would have neither the entries nor their effects.

Durable storage: a WAL instead of rewriting state¶

labs/raftwal stores each Update as one record in an append-only log, reusing the record format of the storage engine's Write-Ahead Log — 32 KB blocks, CRC32-C, torn-write detection — with one fsync per Save. Snapshot data goes to its own file, written atomically, and the WAL record only references it. After a snapshot, once the segment exceeds a size limit, the WAL rolls: it writes the whole current state as the first record of a new segment, makes it durable under its final name, then deletes the old segment. A crash at any point leaves at least one complete segment, and recovery always uses the newest one.

On recovery, a torn final record is an unacknowledged write. It is ignored, and the file is truncated to the end of the last good record before new records are appended. Without that truncation the next record would start right after a broken fragment, and the next recovery would read the fragment as corruption in the middle of the log. The storage engine's log reader gained an End offset for this.

Measured: WAL append vs. rewriting the whole state¶

One durable save that appends a 128-byte entry, with the log already holding N entries:

Log size	WAL append	Rewrite whole state (temp file + fsync + rename + fsync dir)
100 entries	4.70 ms, 145 bytes written	10.42 ms, 16,826 bytes
1,000 entries	4.08 ms, 145 bytes	11.08 ms, 138,320 bytes
10,000 entries	4.08 ms, 145 bytes	12.14 ms, 1,353,320 bytes

On this machine one F_FULLFSYNC costs about 4 ms and dominates everything, so the WAL's cost is one flush regardless of log size. The rewrite needs two flushes (file and directory) and writes the whole log every time: 2.5–3x slower already, getting slower as the log grows, and writing 9,000x more bytes at 10,000 entries — which on an SSD is also 9,000x more wear. Snapshots bound the log, but between snapshots the rewrite approach's cost is O(log size) per write.

Testing the WAL¶

• Model test: 3,000 random updates (appends, conflicting-suffix replacements, snapshots, hard-state changes) are applied to both the WAL and MemStorage; at about 30 random points the WAL is closed, reopened from disk, and compared with the model. It found two bugs: the snapshot file's length prefix stored the number of members instead of the number of bytes of the encoded configuration, and replay tried to read the data of every snapshot ever recorded, although superseded snapshot files had already been deleted. The fix for the second: replay only metadata, then load the data of the final snapshot.
• Torn tail: truncate the segment in the middle of the last record, reopen (9 of 10 entries recovered), write again, reopen again (the new record is readable).
• Raft on the WAL: a 5-node cluster stores everything in WAL directories; for 300 rounds nodes are crashed and reopened from disk, on an unreliable network, with snapshots every 10 entries. 251 entries were committed with safety checked on every entry, and no node held more than one entry in memory at the end.

Pre-vote¶

A follower cut off from the cluster keeps timing out. Without pre-vote it increments its term on every timeout; when the partition heals, its huge term makes the healthy leader step down, and the cluster holds an unnecessary election. With pre-vote, it first asks whether peers would vote for it, and they refuse while they are hearing from a leader:

if args.PreVote {
    heardLeader := n.state == Leader || time.Since(n.lastLeaderContact) < n.cfg.ElectionTimeoutMin
    grant := args.Term > n.term && upToDate && !heardLeader
    return RequestVoteReply{Term: n.term, VoteGranted: grant} // no state changes on the receiver
}

5 nodes; one follower isolated for 10 seconds, then reconnected:

	Isolated node's term	Cluster term before → after
Without pre-vote	23	1 → 24 (the leader was forced through a new election)
With pre-vote	1	1 → 1 (nothing happened)

The first draft of the pre-vote handler missed one case, caught in review before the tests ran: the leader itself never records "last contact from a leader", so it would have granted pre-votes to anyone. The fix is the n.state == Leader term above.

Check-quorum¶

// in the ticker, for a leader:
if n.cfg.CheckQuorum && !n.hasQuorumLocked(now) {
    n.state = Follower // can't reach a majority: stop acting as leader
}

func (n *Node) hasQuorumLocked(now time.Time) bool {
    acks := 0
    for _, p := range n.config {
        if p == n.id || now.Sub(n.lastAck[p]) < n.cfg.ElectionTimeoutMin {
            acks++
        }
    }
    return acks >= n.majority()
}

A leader isolated from every other node:

	Time until the isolated leader stops acting as leader
Without check-quorum	Never (still leader after 5 s)
With check-quorum	310 ms

What it does and does not fix: it bounds how long a deposed leader serves requests, but during that window it still does. In the KV store, local reads on a believed leader were non-linearizable in 5 of 5 runs without check-quorum and in 2 of 5 runs with it (Replicated Key-Value Store). Check-quorum is what makes leader leases possible (a leader that knows it had a quorum recently can bound when a new leader could appear), but lease reads additionally depend on bounded clock drift; ReadIndex does not.

Membership changes, one server at a time¶

Changing the set of servers is dangerous because, during the change, some nodes use the old configuration and some the new one. If the two configurations could form disjoint majorities, two leaders could be elected for the same term. Adding or removing one server at a time makes that impossible: any majority of the old set and any majority of the new set overlap.

func (n *Node) ChangeConfig(peers []int) (uint64, error) {
    // ...
    // One change at a time: the previous one must be committed, and so
    // must an entry of this leader's term.
    if n.configIndex > n.commitIndex || n.at(n.commitIndex).Term != n.term {
        return 0, ErrConfigInProgress
    }
    added, removed := diff(n.config, peers)
    if len(added)+len(removed) != 1 {
        return 0, ErrOneServerAtATime
    }
    n.appendLocal(EntryConfig, EncodeConfig(peers))
    n.broadcastLocked()
    return n.lastIndex(), nil
}

The rules that make it correct:

• The configuration is an ordinary log entry, and each node uses the latest configuration in its log, committed or not. If that entry is truncated by a new leader, the node falls back to the previous one (recomputeConfig runs after every truncation and snapshot install).
• Only one change may be in progress at a time.
• The leader must have committed an entry of its current term first. Without this condition the single-server algorithm, as originally published, was unsafe: Diego Ongaro reported on the raft-dev mailing list in 2015 that a leader could add a server while an uncommitted configuration entry from a previous term might still be overwritten, leading to overlapping configurations that do not share a majority. The no-op each new leader appends makes the condition true quickly.
• A leader that removes itself keeps managing the cluster until the removal commits — without counting its own vote — then steps down.
• A joining node starts with no configuration (peers == nil), never starts elections, and learns the configuration from the leader's log.

Test: a 3-node cluster grows to 4 and 5 members, then removes the current leader, then one more node: 3 → 4 → 5 → 4 → 3, committing commands with the expected number of nodes at every step; a new leader was elected after the old one removed itself. Production systems also add learners — non-voting members that catch up on the log before being promoted — so a new, empty server doesn't lower availability while it is copying data.

Flow control and batching¶

Two changes reduce the per-command cost of replication:

• One RPC in flight per follower. The leader no longer starts a new AppendEntries for every proposal; if one is in flight, it marks the follower as having pending entries, and when the reply arrives sends everything accumulated in one RPC. Followers therefore persist many entries per save.
• StartBatch: the KV server's proposer goroutine drains concurrent client writes from a channel and proposes them together, one durable write on the leader for the whole group — the same group commit as in the storage engine.

Measured in simulation, 3 nodes, counting durable saves on all nodes:

Concurrent clients	Writes/s (simulated time)	Persists per client write, all 3 nodes
1	44	3.00
8	316	1.53
64	2,407	1.08

With one client every write costs three fsyncs (one per node). With 64, it costs about one in total, almost entirely from followers receiving batches through flow control. The leader's proposal batches stayed at an average size of 1.0: in the simulation a save takes no time, so requests never pile up behind it. On real disks, while the leader's fsync is running, new requests queue in the proposer's channel and the next batch picks all of them up. That effect needs real fsync latency to measure; it is measured on real processes over TCP on real disks in Raft on Real Hardware.

Common pitfall¶

Snapshotting before the state machine is durable. A KV server keeps its data in an LSM store with unsynced writes for speed, and calls raft.Snapshot(appliedIndex, ...) after every 1,000 entries. Raft writes the snapshot marker and deletes the log up to appliedIndex. The machine loses power: the LSM store's last few hundred applied writes were still in the page cache and are gone, and the Raft log entries that could have replayed them were just deleted. After restart the node's state is missing writes that the cluster committed, and nothing detects it until a read returns old data. The order must be: make the state machine durable up to appliedIndex (a synced write), then let Raft discard the log.

Review questions¶

1. Why does a snapshot need to carry the cluster configuration?
2. Why must the applier deliver a pending snapshot before entries that follow it?
3. Why does the WAL truncate a torn tail before appending, instead of just skipping it on read?
4. Why did rewriting the whole state cost 2.5–3x more than a WAL append even with a small log?
5. What does pre-vote prevent, and why must a leader refuse pre-votes?
6. Why can single-server membership changes never create two disjoint majorities, and why must the leader first commit an entry of its own term?
7. Why did leader-side batching not show up in simulation?