Skip to content

Raft-Style Replicated-Log Protocol

Replicated-log consensus protocol — instantiates Assumption-Bounded Distributed Agreement

Keeps a fleet of replicas byte-for-byte identical by funnelling every command through one elected leader into a single append-only log, and treating an entry as decided only once a majority has stored it.

Where the base commit act decides a single value and Paxos chooses one value per decree, Raft-Style Replicated-Log Protocol agrees on an ordered sequence of them: a replicated log. Its defining idea is the pairing of a single strong leader with the Log Matching Property. All writes flow through one leader, which stamps each command with a term and an index and appends it to its log; followers copy that log verbatim. Log Matching guarantees that if two replicas hold an entry with the same term and index, their logs are identical up to that point — so consistency is maintained not entry-by-entry but by whole prefixes. An entry becomes committed once the leader has replicated it to a majority. The design's real achievement is not a new safety frontier — it is the same crash-fault guarantee as Paxos, deliberately restructured into leader-plus-log so that it can actually be understood and implemented correctly.

Example

A Kubernetes control plane keeps its entire desired state in an etcd cluster of five replicas, and etcd keeps that state as a Raft log. An operator applies three changes in quick succession — create a deployment, scale it to ten replicas, delete an old service. The current leader appends the three commands as log entries (term 4, index 17..19) and ships them to the followers in AppendEntries messages. Each command is committed the moment a majority — three of five — has appended it, in that order; only then does the API server report success and the controllers act. When one follower reconnects after a blip with a stale, divergent tail (it had an uncommitted entry from an old leader), the leader's consistency check finds the last index where the two logs agree and overwrites everything after it, dragging the follower back into lockstep. Every replica ends up with the same ordered history, so any of them can serve a consistent read of the cluster's state.[1]

How it works

  • One leader owns the writes. Every command enters through the leader, which assigns it a monotonic (term, index) and appends it; there is never more than one log-author at a time, which is what removes the dueling-proposer complexity.
  • Followers match, they do not merge. AppendEntries carries the index/term of the preceding entry; a follower accepts only if that matches, otherwise it rejects and the leader walks backward until the logs converge, then overwrites the follower's tail.
  • Commit by majority, apply in order. An entry is committed once stored on a majority; the leader advances a commit index and replicas apply committed entries to their state machines strictly in log order.
  • Repair is automatic. A crashed or lagging replica is caught up by replaying the leader's log (or a snapshot), never by ad-hoc reconciliation.

Tuning parameters

  • Batch / pipeline depth — how many entries the leader replicates per round and how many are in flight at once. Deeper batching raises throughput but adds latency and enlarges the window lost if the leader fails.
  • Snapshot threshold — how large the log grows before it is compacted into a snapshot. Frequent snapshots keep restart-replay short but cost steady I/O.
  • Read strategy — serve reads through the leader with a lease, via a read-index confirmation, or from any replica. Leader-lease reads are fast but assume bounded clock drift; quorum reads are safe but slow.
  • Heartbeat interval — how often the leader asserts liveness to suppress elections. Shorter heartbeats hold leadership more firmly but add constant traffic.

When it helps, and when it misleads

Its strength is understandability: by decomposing agreement into leader election, log replication, and a small set of safety restrictions, it makes a correct implementation reachable in a way bare Paxos notoriously does not — which is why it underpins so many production coordination stores. The ordered log is also directly useful: it is a replicated state-machine history, not just a single decided value.

Its costs come from the same strong leader that buys the clarity. Every write is serialized through one node, so the leader is a throughput ceiling and a single point of latency, and each leader change brings a brief unavailability while a new one is elected and catches up. Like Paxos it assumes crash faults only — a leader that lies or equivocates breaks it, which is the boundary where a Byzantine-tolerant protocol takes over. The classic misuse is serving a read from a stale leader or an unconfirmed follower — a deposed leader that has not yet noticed can answer with data that has since been overwritten, silently violating linearizability. The discipline is to gate reads behind a lease or read-index, and never to shrink the commit majority for latency.

How it implements the components

  • state_consistency_guard — the Log Matching Property is the monotone safety invariant: equal (term, index) implies identical prefixes, so no two replicas' committed histories can diverge.
  • quorum_or_voting_rule — an entry is committed exactly when a majority of replicas have appended it (with the restriction that a leader commits earlier entries only by committing one from its own term).

It does not elect or rotate the single leader it depends on (round_epoch_and_leadership_state → Term/Epoch Leader Election), make each replica's log survive a crash (event_log, recovery_policy → Write-Ahead Vote Log), or preserve in-flight entries safely across a leadership change (safety_liveness_contract → View-Change Protocol).

Notes

Raft and Paxos give the same crash-fault safety; the difference is packaging, not power. Raft trades the flexibility of leaderless, multi-proposer agreement for a single-leader structure that a team can actually build and operate correctly — a deliberate exchange of theoretical generality for engineering tractability. Because the log is the single source of truth, even membership changes must be entered as log entries, which is exactly the job of Joint-Consensus Membership Change.

References

[1] Raft (Ongaro and Ousterhout, In Search of an Understandable Consensus Algorithm) is defined by its Log Matching and Leader Completeness properties, which together let a single leader keep replicas consistent by prefix. It is presented as an equivalent-safety, more-understandable alternative to Multi-Paxos, not as a stronger fault model. ↩