Distributed Consensus Architecture: Raft, Paxos, and Beyond, in depth: protocol choice, read paths, reconfiguration and placement

What consensus buys you and what it costs

Consensus gives you one thing: a replicated log in which every entry, once committed, is in the same position on every correct replica and is never lost or reordered. Apply the log in order to a deterministic state machine and every replica computes the same state. This is state machine replication, and it is what turns a group of unreliable machines into one reliable, linearizable service.

The price is fixed by arithmetic. A group of 2f+1 voting members tolerates f failures, because any two majorities overlap in at least one member, and that member carries the committed history forward. Three voters survive one failure, five survive two. Every write waits for a majority to persist the entry to stable storage, so write latency is at least one round trip to the closest majority plus an fsync.

The FLP result proves that no deterministic protocol can guarantee progress in a fully asynchronous network with even one crash. Practical protocols accept this: they are always safe, and they make progress whenever the network is calm enough for timeouts to elect a stable leader. When the network is not calm, a correct system stalls rather than diverges. Your architecture must treat that stall as a real outcome.

What consensus buys you and what it costs

Consensus gives you one thing: a replicated log in which every entry, once committed, is in the same position on every correct replica and is never lost or reordered. Apply the log in order to a deterministic state machine and every replica computes the same state. This is state machine replication, and it is what turns a group of unreliable machines into one reliable, linearizable service.

The price is fixed by arithmetic. A group of 2f+1 voting members tolerates f failures, because any two majorities overlap in at least one member, and that member carries the committed history forward. Three voters survive one failure, five survive two. Every write waits for a majority to persist the entry to stable storage, so write latency is at least one round trip to the closest majority plus an fsync.

The FLP result proves that no deterministic protocol can guarantee progress in a fully asynchronous network with even one crash. Practical protocols accept this: they are always safe, and they make progress whenever the network is calm enough for timeouts to elect a stable leader. When the network is not calm, a correct system stalls rather than diverges. Your architecture must treat that stall as a real outcome.

The shared core, in code

Raft and Multi-Paxos share the same skeleton. A leader, elected for a numbered term (Paxos calls it a ballot), is the only member that appends to the log. Followers accept entries only from the current leader and only when the log before the new entry matches. The code below is a condensed version of the rules that matter for correctness; the full algorithm and its proofs are in the Raft deep dive.

# Follower side of AppendEntries (Raft)
def on_append_entries(req):
    if req.term < current_term:
        return reject(current_term)              # stale leader
    become_follower(req.term, leader=req.leader_id)
    # Log matching: the entry at prev_log_index must carry prev_log_term,
    # the term OF THAT ENTRY, not "the current term minus one".
    if log.term_at(req.prev_log_index) != req.prev_log_term:
        return reject(current_term, hint=log.conflict_hint(req.prev_log_index))
    log.truncate_conflicts_and_append(req.prev_log_index + 1, req.entries)
    log.fsync()                                  # durable before acking
    last_new = req.prev_log_index + len(req.entries)   # verified prefix only
    commit_index = max(commit_index, min(req.leader_commit, last_new))
    return accept(current_term, match_index=last_new)

# Leader side: advancing the commit index
def maybe_advance_commit():
    for n in range(log.last_index(), commit_index, -1):
        replicated = 1 + sum(1 for f in followers if match_index[f] >= n)
        # Only entries from the CURRENT term are committed by counting.
        # Older entries become committed indirectly when one of these is.
        if replicated > len(voters) // 2 and log.term_at(n) == current_term:
            commit_index = n
            break

# Voting: never elect a candidate whose log is behind ours
def on_request_vote(req):
    if req.term > current_term:
        become_follower(req.term, leader=None)   # new term clears voted_for
    up_to_date = (req.last_log_term, req.last_log_index) >= (log.last_term(), log.last_index())
    if req.term == current_term and voted_for in (None, req.candidate_id) and up_to_date:
        persist(voted_for=req.candidate_id, term=req.term)
        return grant()
    return deny()

Three rules in that snippet are where hand-written implementations go wrong. The log-matching check uses the term stored at the previous index. The commit rule refuses to commit an older-term entry by counting replicas, because an entry stored on a majority can still be overwritten by a later leader if it was never committed in its own term (the scenario in Figure 8 of the Raft paper). And the vote and term must be persisted before replying, or a restarted node can vote twice in the same term.

Snapshots are local. Each member snapshots its own state machine on its own schedule and discards the log prefix it covers. Only a follower that has fallen behind the leader's retained log receives the leader's snapshot through InstallSnapshot.

Raft, Paxos and the family tree

The protocols differ less in safety than in what they make cheap. The Paxos article covers single-decree Paxos; in production everyone runs a multi-decree variant with a stable leader, which looks very much like Raft.

Flexible Paxos is worth understanding even if you never implement it. Classic majorities are one choice; the actual requirement is that every leader-election quorum intersects every replication quorum. With six nodes you could replicate to any 3 and elect with any 4. Writes get faster, and elections need more nodes. Raft with witnesses or learners is applying the same reasoning in a restricted form.

Read paths without stale answers

A read served by any replica's local state can be stale: a deposed leader that does not yet know about its replacement will happily return old data. There are four read paths, in descending order of cost.

Lease reads are the common trap. They are only correct if no new leader can be elected before the old leader's lease runs out by its own clock, which assumes clocks advance at roughly the same rate everywhere. A VM pause or a stepped clock breaks that. If you cannot bound drift, use ReadIndex. Spanner instead makes the clock assumption explicit and bounded with TrueTime, as described in the TrueTime article.

Changing membership safely

Changing the set of voters is the most dangerous routine operation. If half the members switch to a new configuration while the rest still use the old one, two disjoint majorities can exist and elect two leaders. Raft offers two safe mechanisms. Joint consensus commits a transitional configuration in which decisions need majorities of both the old and the new set. Single-server changes add or remove one voter at a time, because any majority of N and any majority of N plus or minus one always overlap.

Never add an empty voter directly. Add it as a learner (a non-voting member that receives the log), wait until it has caught up, then promote it. Adding an empty voter to a three-node group makes a four-node group whose majority is three, one of which cannot acknowledge anything for minutes. Replacing a failed machine is therefore add-learner, promote, then remove the dead voter, never the other way round when you are already one failure from losing quorum.

Placement, sizing and timeouts

Placement decides both availability and latency. The rule is to put voters in independent failure domains so that losing any one domain leaves a majority.

Even numbers buy nothing: four voters still tolerate one failure but need three acknowledgements. Seven voters tolerate three failures at the cost of slower commits and slower elections; most systems stop at five and add learners or read replicas for read scale. Timeouts must match the topology. The etcd tuning guide gives defaults of 100 ms for --heartbeat-interval and 1000 ms for --election-timeout, and advises an election timeout of at least ten times the round-trip time between members. A cross-region group with an 80 ms round trip therefore needs timeouts near one second or more.

Large systems do not run one giant group. They shard data into ranges and run one consensus group per range (multi-Raft in CockroachDB and TiKV, Paxos groups per split in Spanner), batching heartbeats and log writes across groups. The protocol stays simple; throughput scales with the number of groups.

Worked example: a three-region configuration store

Suppose you run a configuration store for a platform with services in three regions: us-east, us-central and us-west, with round trips of 25 ms east to central, 35 ms central to west and 60 ms east to west. You need it to survive a region loss.

Five voters placed 2 in us-east, 2 in us-central and 1 in us-west, with the leader preferred in us-east. A write from us-east needs three acknowledgements: the leader, its zone peer (about 1 ms away) and one us-central voter (25 ms). Commit latency is about 25 ms plus fsync. If us-east fails, the four survivors elect a leader in us-central, and with three survivors every commit needs all of them, including us-west at 35 ms, and one more failure stops writes. If us-central fails instead, the us-east leader needs the us-west voter at 60 ms.

Reads are mostly watches and gets of configuration keys. Use ReadIndex for anything that gates a deploy and serve dashboards from followers. Set the heartbeat to about 100 ms and the election timeout to about 1 s, so a single slow cross-region packet does not trigger an election. Watch-heavy clients in us-west talk to a learner there, which absorbs read load without slowing commits.

Failure modes

• Lost quorum. Two of three voters down means no writes and no linearizable reads. Recovery by forcing a new single-member configuration can discard committed writes; document it as a last resort.
• Disk stalls. An fsync that takes seconds on the leader stalls every write. Put the WAL on a dedicated low-latency disk and alert on fsync p99.
• Election storms. A partitioned node increments its term repeatedly and disrupts the group when it rejoins. Enable PreVote and CheckQuorum where your implementation supports them.
• Asymmetric partitions. A leader that can send but not receive keeps its followers from electing a replacement. CheckQuorum makes it step down when it stops hearing from a majority.
• Oversized state. A snapshot that takes minutes to transfer means a lagging member never catches up. Keep the state machine small; consensus stores are for metadata, not bulk data.
• Non-deterministic apply. Reading the wall clock or a random number inside apply makes replicas diverge silently. Put such values into the log entry instead.

Operating a consensus group

Monitor term changes (more than a handful a day is a symptom), leader changes, commit latency, fsync latency, the gap between commit index and applied index, follower lag and snapshot sizes. Rehearse the three operations you will need under pressure: replacing a dead member, restoring the whole group from backup, and moving the leader before maintenance. Back up with the system's own snapshot tool, not by copying data directories from a running node. Keep members on the same version except during a planned, rolling upgrade, and read the release notes for storage-format changes before you start.

For streaming platforms the same decisions show up in Kafka's move from ZooKeeper to a built-in Raft quorum; see KRaft versus ZooKeeper for the operational differences, and Raft log replication for the mechanics of catch-up.

Trade-offs

Use consensus where the cost of disagreement is high and the data is small: leadership, locks, membership, schemas, configuration, and the commit point of transactions. Do not route high-volume data through one group; shard it, or use leaderless replication with conflict resolution when temporary divergence is acceptable. Prefer an existing, well-tested implementation over writing your own, because the dangerous bugs live in recovery, membership and storage, not in the happy path. Choose Raft for understandability and tooling, Multi-Paxos variants when you already have one in your platform, and leaderless protocols only with a measured reason.

What to do next

1. List every component in your system that needs a single agreed answer and name the consensus group it uses.
2. For each group, write down voter count, failure domains, and which single failure would lose quorum.
3. Check the read path: replace lease reads with ReadIndex unless clock drift is bounded and monitored.
4. Set heartbeat and election timeouts from measured round trips, not defaults copied from a single-zone setup.
5. Turn on PreVote and CheckQuorum if available, and alert on term changes and fsync p99.
6. Write and rehearse a replace-member runbook that adds a learner first and removes the dead voter last.
7. Run a game day that kills the leader, partitions one zone and restores the group from backup.