Log replication.

Article 3.1 established the abstract "why" — agree on an ordered sequence of commands, and matching state follows automatically. This article gets concrete about the "how": the actual data structure — an append-only log — that carries that sequence in every real consensus system, and the surprisingly deep engineering that a seemingly simple append-only list demands in practice. Entries, indexes, and terms; how logs briefly diverge and get repaired; snapshotting and compaction (because a log can't grow forever); and how a brand-new or long-dead replica catches up from nothing. This is the concrete machinery Raft's log-replication mechanics (Phase 5.6) and every other classical algorithm's storage layer builds directly on top of.

Why a log specifically, not some other data structure

An append-only log is the natural implementation of "an ordered sequence of commands" for reasons that go beyond convenience — each property maps directly to something the SMR guarantee (article 3.1) actually needs:

• Append-only means the past is immutable. Once an entry is durably written at position N, it never changes. This gives every replica a stable, unambiguous reference point — "I've applied up through index 47" is a complete, unambiguous description of a replica's progress, because entry 47 (and everything before it) will never retroactively change.
• A total order is built in for free. A log's positions (indexes) are, by construction, a total order — there's no separate ordering mechanism needed once entries are placed in the log; their position is their order.
• It's naturally resumable. A replica that falls behind just needs "give me everything after index N" — no complex reconciliation, no diffing of arbitrary data structures, just "the tail of the log I'm missing."
• It doubles as an audit trail and a durability mechanism. Because it's append-only and persisted, a log written to disk (this is exactly the WAL — write-ahead log — concept familiar from the pgBackRest guide's PostgreSQL context) survives a crash and lets a replica recover its exact state by simply replaying from the beginning, or from the last known-good checkpoint.

Anatomy of a log entry

A real consensus log entry (this shape is essentially universal across Raft, Multi-Paxos, and their descendants) carries three pieces of information, not just the raw command:

class LogEntry:
    def __init__(self, index, term, command):
        self.index = index      # position in the log -- the total order
        self.term = term        # the "epoch" during which this entry was proposed
        self.command = command  # the actual, opaque command bytes for the state machine

The index is the log's own position counter — simple, and exactly what article 3.1's abstract "sequence position" concretely is. The term (sometimes called "epoch" or "view number" in other algorithms — Raft's exact terminology, previewed here and covered in full in Phase 5) is subtler and worth pausing on: it's a monotonically increasing counter that identifies which leadership period an entry was proposed during. Every time a new leader is elected (after the previous one is suspected failed, per article 2.4's failure detectors), the term increments. This gives every log entry a compound identity — "index 47, term 3" is a more specific, more useful piece of information than "index 47" alone, because it lets replicas detect exactly the scenario the next section describes: two different, conflicting entries that both claim to be at index 47, proposed by different leaders during different terms.

How logs diverge, and how they're repaired

Recall the leader-election machinery previewed across articles 1.2, 2.4, and now 3.1 — a leader can be suspected dead (correctly or not) and a new one elected. This creates a real, common scenario: a leader proposes an entry, replicates it to some but not all followers, then is suspected dead and replaced before that entry reaches everyone or gets fully committed. The result: different replicas' logs can genuinely diverge at their tails.

The repair mechanism, in essentially every classical algorithm, is variations on the same rule: when a follower finds its log conflicts with what the current leader says should be there (same index, different term), the follower's conflicting entry — and everything after it — is discarded and overwritten with the leader's version. This is safe specifically because of a property every classical consensus algorithm carefully guarantees (proven formally when Raft's safety argument is covered in Phase 5.6): an entry is only ever discarded this way if it was never actually committed — meaning it never reached a majority of replicas and was therefore never applied to any state machine or exposed to any client as durable. A committed entry, once committed, is never rolled back — that's the actual, load-bearing safety guarantee; uncommitted, in-flight entries from a deposed leader are fair game for overwriting, precisely because no correct process ever treated them as final.

Snapshotting and log compaction

An append-only log that genuinely never deletes anything grows forever — for a long-running production system processing thousands of commands per second, this becomes a real, practical problem within days or weeks, not years: unbounded disk usage, and unboundedly slow replica catch-up (a brand-new replica joining after a year of operation would need to replay a year's worth of commands from scratch before being useful).

The fix is snapshotting: periodically, a replica serializes its entire current state machine state (not the log — the actual resulting state, article 3.1's current_state) to a durable snapshot, then safely discards every log entry before the point that snapshot represents — because the snapshot already captures the cumulative effect of every command up to that point, and article 3.1's determinism guarantee means "replay from snapshot + remaining log entries" produces an identical result to "replay the entire log from the very beginning."

This compaction is a real, necessary piece of engineering in every production consensus system — Raft's paper devotes a full dedicated section to it, and every serious implementation (etcd, CockroachDB's Raft usage, and others covered in Phase 8/9) has a snapshotting subsystem, usually triggered automatically once the log grows past a configured size threshold, running as a background process so it doesn't block ongoing command replication.

How a replica catches up from nothing

Putting the log and snapshot mechanisms together gives the complete, practical answer to a question every real deployment eventually faces: how does a brand-new node — or one that's been offline so long its log is drastically behind — get caught up efficiently, without replaying potentially millions of individual historical commands one at a time?

1. Install the latest snapshot. The lagging/new replica receives the leader's (or any sufficiently caught-up replica's) most recent full-state snapshot in one transfer — this alone brings it to "current as of snapshot time," a single bulk operation rather than millions of small ones.
2. Replay the log tail. Only the log entries created after the snapshot was taken need to be replayed individually — typically a small, bounded number if snapshots are taken reasonably often, regardless of how far behind the replica started.
3. Rejoin normal replication. Once caught up to the current log tail, the replica participates in ongoing replication exactly like any other follower, receiving new entries as they're proposed.

FAQ

Takeaways

• An append-only log is the natural concrete implementation of article 3.1's abstract "ordered command sequence" — immutable history, built-in total order, naturally resumable, and durable.
• Real log entries carry index, term, and command — the term (incremented on every leadership change) is what lets replicas detect and resolve conflicting entries at the same index.
• Logs can genuinely diverge after a leader change; the universal repair rule is that uncommitted entries from a deposed leader are safely discarded and overwritten — because "committed" specifically means majority-replicated, and only committed entries carry the never-rolled-back guarantee.
• Snapshotting/compaction is a necessary, real piece of engineering — periodically capture full state, discard the log entries it supersedes, relying directly on SMR's determinism guarantee (article 3.1) to prove the shortcut is safe.
• Snapshot + remaining log tail is exactly how a new or badly-lagging replica catches up efficiently, keeping the cost of adding capacity roughly bounded regardless of cluster age.

References & further reading

• Ongaro & Ousterhout — In Search of an Understandable Consensus Algorithm (Raft, 2014) — Section 5.3 (log replication) and Section 7 (snapshotting) are the concrete reference implementation of everything in this article; full Raft treatment in Phase 5.
• cvam.sight — Consensus 3.1: State Machine Replication — the abstract guarantee this article's snapshotting shortcut relies on.
• cvam.sight — pgBackRest with S3 — write-ahead logging in a real, adjacent production context (PostgreSQL).