← Back to blogs

State Machine Replication: Why Order Is the Only Thing That Matters

Every replicated database, every Kafka partition, every Raft cluster rests on one brutal invariant: if deterministic replicas start identical and apply identical commands in identical order, they stay identical. Violate the order by one message and you have built two different databases.

1. The Primitive: A Deterministic State Machine

Forget "distributed" for a moment. A state machine is just (state, command) → (newState, output). Determinism is non-negotiable: given state S and command C, every replica must compute exactly the same S'. No rand(), no now(), no iterating over a hash map. In production this is where teams silently break replication.

PostgreSQL's WAL replay, RocksDB's memtable, your bank's ledger — all are deterministic machines under the hood. The trick is not the logic. It is getting every replica to agree on the sequence of commands.

-- Deterministic: same balance every replica, every time
UPDATE accounts SET balance = balance + 100 WHERE id = 42;
-- Non-deterministic: replicas diverge on wall-clock and UUID generation
UPDATE accounts SET last_seen = now(), token = gen_random_uuid() WHERE id = 42;

If your command embeds non-determinism, SMR does not save you — it reliably replicates the divergence. Production systems push that non-determinism to the leader: generate the timestamp and UUID once at the coordinator, then replicate the concrete value as part of the command.

2. The Replicated Log: An Honest Serialization Point

SMR reduces replication to one problem: agree on a totally ordered log of commands. Clients submit to a leader (or an ordering service), the leader appends to its log and ships entries to followers. Followers apply in log order, not arrival order.

Without a log, each replica's state is a function of network scheduling. TCP reorders, retries duplicate, switches buffer. Two replicas receiving [x:=1, x:=2] and [x:=2, x:=1] end with different values, and no repair other than re-syncing full state will converge them again if operations are not commutative — which, in an OLTP workload, they almost never are.

Use the visual below: Each command is a deterministic x = x + N operation on a shared integer starting at 0. In "In-order" mode every replica appends and applies sequentially and stays in sync. Flip to "Out-of-order delivery" and watch Replica C apply entry 2 before entry 1 — the same commands, different order, permanently divergent states.

3. Why Replicas Diverge in Production

Three failure modes dominate real incidents:

• Reordering: Network fabric or retry queues deliver entries out of sequence. If follower eagerly applies on arrival instead of log-index order, states fork.
• Gaps: Message loss leaves a hole at index 4 while 5 is already applied. Reads at 5 are correct on one replica and missing on another.
• Non-determinism leak: Leader does not fix now() or auto-increment offsets before replication. Each replica stamps its own wall time.

That is why mature stacks never apply on receipt. They apply on commit: the leader advances its commit index only when a quorum has persisted the entry, then piggybacks the commit index on the next AppendEntries heartbeat. Followers advance their state machine in strict index order.

4. Exactly-Once Apply vs. At-Least-Once Delivery

The network is at-least-once. The state machine must be exactly-once. Between those two realities sits the log. Each entry carries a monotonic index and term. A follower that crashes and replays from index 37 knows it has already applied 1–36. Without idempotent command identities, retries after a leader failover double-apply.

Client ──► Leader (term=3, index=42, cmd=x+=5) ──► Replicas
              │ retry after timeout
              └──► New Leader (term=4) re-proposes index=42?
                    Without deduplication, x increments twice.

Production fix: client-supplied requestId and a per-replica dedup table keyed by (clientId, seqNo) → result. The log provides ordering; deduplication provides exactly-once semantics at the apply layer.

5. When SMR Is Not Enough

SMR tells you what must be agreed upon — a totally ordered log — but not how to agree when messages are lost and leaders die. A log with a single leader is just a single point of failure with nicer terminology. You need a protocol that elects a leader, survives lost messages, and never lets two leaders commit different commands at the same index.

Which is where every naive retry loop quietly dies: the network can drop any acknowledgement, and no finite chain of "are you sure?" messages can ever give both sides certainty. In practice the only way forward isn't more certainty — it's a different question entirely. That question is why quorums exist, explored in The Unreliable Network: Why Two Generals Can Never Agree →