Catalog My learning Blog
Raft and Paxos Explained: Consensus, ZooKeeper and etcd · Phase 1 · Lesson 5 · 10 min read

Replicated State Machines Explained

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: A Non-Deterministic Command That Silently Diverges Replicas
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Explain the replicated state machine model, why agreeing on an ordered log of commands is a stronger and more useful primitive than agreeing on a single value, and what determinism requirements this places on the application code sitting above the consensus layer.

Concept Explanation

Every consensus algorithm described so far decides a single value, which on its own is not obviously useful: production systems need to agree on millions of things over their lifetime, not one. The bridge from single-value consensus to a working system is the replicated state machine model, and it is the single most important structural idea in this course. The construction is this: if several deterministic state machines all start in the same initial state and all apply exactly the same sequence of commands in exactly the same order, then they must all pass through exactly the same sequence of states and produce exactly the same outputs. Replication of state therefore reduces entirely to agreement on the order of a log of commands.

This reframing is what makes consensus practical. Rather than running a fresh agreement round about the resulting state of the database, which would be enormous and constantly changing, the cluster runs agreement about what occupies position 1 in the log, then position 2, then position 3. Each position is a small, independent instance of single-value consensus, and the value being agreed is a compact command such as "set key foo to bar" or "grant lease 7 to client C". The database state is then never transmitted or voted on at all; it is derived locally on each node by replaying the agreed log. Multi-Paxos and Raft are both, viewed from this angle, optimisations for running the same single-value consensus repeatedly over a sequence of log positions without redoing the expensive setup each time.

Two indices govern every node in such a system, and understanding the gap between them explains a great deal of real behaviour. The commit index is the highest log position known to be durably replicated on a majority, which makes it permanent and safe to reveal to clients. The applied index, sometimes called lastApplied, is the highest position this particular node has actually fed into its state machine. A node can be fully caught up on the log while still lagging in applied state, which is precisely why a follower serving a read without checking with the leader can return stale data even though it has every committed entry on disk. This gap is the mechanism behind stale reads in etcd when a client does not request linearisable reads, and behind the read barrier that ZooKeeper's sync operation inserts.

The determinism requirement this places on application code is strict and catches teams off guard regularly. Every command in the log must produce identical results on every replica, which means the state machine must not consult anything that can vary between nodes. Reading the system clock is forbidden: the leader must resolve the timestamp before the command enters the log, so that "set expiry to now plus 60s" becomes "set expiry to 1716840000" before replication. Generating a random number, a UUID, or an auto-increment value inside the state machine is forbidden for the same reason, as is iterating a hash map whose order varies by process, consulting the local filesystem, or making a network call to an external service. Any of these produces replicas that diverge silently while the consensus layer reports perfect health, which is a particularly unpleasant class of bug because the consensus metrics all look green.

The log-based construction also dictates several operational properties worth naming. The log is append-only and grows without bound, so it must be periodically compacted against a snapshot of the state machine, which is its own lesson later in this course. Entries must be applied strictly in order, so a single slow command blocks everything behind it, which is why long-running operations belong outside the state machine rather than inside it. And because the log is the authoritative record and the state is merely derived from it, a node whose state machine is corrupted can always be repaired by discarding its state and replaying from a snapshot plus the log, which is the recovery path every consensus-backed database relies on.

LayerResponsibilityFailure If Violated
Consensus moduleAgree on the order and content of log entries across a majorityReplicas disagree about what was committed: classic split brain
Replicated logStore entries durably in order, append-only, with a commit indexCommitted entries lost on restart, so acknowledged writes vanish
State machineApply committed entries deterministically, in strict orderSilent divergence: consensus reports healthy while replicas hold different state
Client interfaceRoute writes to the leader, deduplicate retries, choose read consistencyDuplicate command application, or reads that see less than they already wrote

Worked Example: A Non-Deterministic Command That Silently Diverges Replicas

The determinism rule sounds abstract until you see how ordinary the offending code looks. This is a bug that passes code review easily, passes single-node tests perfectly, and produces divergence that no consensus metric will ever report.

JavaScript
// BROKEN: the state machine consults non-deterministic sources while
// applying a committed entry. Consensus agreed on the COMMAND, but each
// replica now computes a DIFFERENT RESULT from it.
function applyCommand(state, entry) {
  if (entry.op === 'CREATE_SESSION') {
    state.sessions[entry.clientId] = {
      id:        crypto.randomUUID(),      // different on every replica
      createdAt: Date.now(),               // different on every replica
      expiresAt: Date.now() + 60_000,      // different on every replica
      node:      os.hostname(),            // different on every replica
    };
  }
}
// Every replica applied the same entry at the same index and every
// consensus health check is green. The session IDs differ across the
// cluster. A client that creates a session against the leader and then
// reads it from a follower after failover gets "session not found".

// FIXED: the leader resolves every non-deterministic value BEFORE the
// entry is proposed, so the log itself carries the decided facts and
// the state machine is a pure function of (state, entry).
function proposeCreateSession(clientId) {
  return raft.propose({
    op:        'CREATE_SESSION',
    clientId,
    sessionId: crypto.randomUUID(),   // decided ONCE, by the leader
    createdAt: Date.now(),            // decided ONCE, by the leader
    ttlMs:     60_000,
  });
}

function applyCommand(state, entry) {
  if (entry.op === 'CREATE_SESSION') {
    state.sessions[entry.clientId] = {
      id:        entry.sessionId,
      createdAt: entry.createdAt,
      expiresAt: entry.createdAt + entry.ttlMs,   // pure arithmetic
    };
  }
}

// The rule, stated once: apply(state, entry) must be a pure function.
// Same state + same entry => same result, on every node, forever,
// including on a node replaying the log from scratch three years later.
The replicated state machine construction: identical initial state plus an identically ordered log of commands yields identical state on every replica, with the consensus module responsible only for agreeing on log order and the state machine responsible for applying entries deterministically.
The replicated state machine construction: identical initial state plus an identically ordered log of commands yields identical state on every replica, with the consensus module responsible only for agreeing on log order and the state machine responsible for applying entries deterministically.

Real-World Examples

  • CockroachDB structures its entire storage layer as replicated state machines: the key space is divided into ranges of roughly 512 MiB, each range is its own independent Raft group with its own log and its own leader, and a cluster runs many thousands of these groups concurrently. This multi-Raft design exists because a single consensus log over the whole database would serialise every write in the system behind one leader, whereas per-range groups let unrelated writes commit in parallel while each individual range still gets the full ordering guarantee of a replicated state machine.
  • Apache Kafka's KRaft mode, which became the default in Kafka 3.3 and fully replaced ZooKeeper in Kafka 4.0, models all cluster metadata as a replicated state machine over a Raft log: broker registrations, topic configurations, and partition leadership changes are commands appended to a metadata log that every broker replays to build its local view. The redesign was motivated partly by the fact that the old ZooKeeper-based path required brokers to poll and reconcile external state, whereas an ordered log gives every broker an identical, replayable sequence of metadata changes with a single well-defined position marker.
WarningConsensus on a single value becomes a useful system through the replicated state machine construction: agree on the ordered log, replay it identically everywhere. The obligation this places on your code is absolute determinism in the apply path - no clocks, no random values, no hostnames, no external calls, no map iteration order. Resolve every such value on the leader before proposing the entry, because divergence caused by breaking this rule is silent and every consensus health metric will stay green while it happens.

Review Questions & Answers

A single agreed value cannot represent an evolving system, and re-running consensus on the entire current state would mean proposing and transmitting the whole dataset on every change. Agreeing on log position 1, then 2, then 3, keeps each individual agreement small and independent while the accumulated sequence describes arbitrarily complex state evolution. Because deterministic state machines starting from the same state and applying the same ordered commands must reach the same state, replication of unbounded state reduces to agreement on a sequence of compact commands. The log is also independently valuable: it provides recovery by replay, a natural point-in-time marker, and an audit trail.

This is state machine divergence caused by non-determinism in the apply path, and it is a bug in the application code above the consensus layer rather than in the consensus implementation. Matching commit indices prove the nodes agreed on the log contents, so the log is fine; the difference must have been introduced when each node computed its own result from the same entry. The usual culprits are calling a clock or random generator during apply, embedding a hostname or local configuration value, iterating a collection whose order varies between processes, or making an external network call whose response differs per node. The fix is to resolve all such values on the leader before the entry is proposed.

The commit index is the highest log position known to be durably stored on a majority, making it permanent and safe to acknowledge. The applied index is the highest position this specific node has actually executed against its local state machine. Because application happens after commitment and proceeds asynchronously, a node can hold every committed entry on disk while its queryable state still reflects an earlier position. The visible result is a stale read: a client that writes through the leader and immediately reads from a follower may not see its own write. Systems address this with linearisable reads that check with the leader, or with an explicit barrier such as ZooKeeper's sync, which forces the follower to catch up before serving the read.

Because each replica applies the entry at a different wall-clock moment, so evaluating "current time" during apply produces a different expiry on every node, and the replicas diverge permanently despite having identical logs. The divergence also grows worse over time, since a node replaying the log during recovery would compute expiries based on the recovery time rather than the original. The leader must therefore resolve the timestamp before proposing, so the log carries a concrete value such as "set expiry to 1716840000" and every application of that entry, at any node and at any future time, yields the identical result.

Entries must be applied in strict log order to preserve determinism, so a command that takes seconds to execute blocks every entry behind it on every replica, stalling the applied index cluster-wide even though the log continues to commit. Reads that require a current applied state also stall. The structural fix is to keep the state machine to fast, purely computational transitions and move slow work outside it: propose a compact command that records the intent and a result placeholder, perform the expensive work outside the apply path, and propose a second entry recording the outcome. This keeps the apply path deterministic and fast while still ordering the overall operation through the log.