Replicated State Machines
Consensus protocols like Paxos and Raft answer a narrow question: how can a group of machines agree on one value, or on a sequence of values, despite crashes and an unreliable network? On their own, agreed-upon values are not very useful. What turns consensus into infrastructure — a lock service, a configuration store, a database — is the replicated state machine (RSM) pattern:
If every replica starts in the same state and applies the same deterministic commands in the same order, every replica ends up in the same state.
Consensus provides "the same commands in the same order". The application provides "deterministic". Everything else on this page — snapshots, read paths, sharding, transactions — is engineering around those two halves.
The idea goes back to Lamport's 1978 paper on time and clocks, which used a replicated state machine to implement a distributed mutual-exclusion algorithm, and was laid out as a general method by Fred Schneider's 1990 tutorial Implementing Fault-Tolerant Services Using the State Machine Approach. Today it is the backbone of etcd, ZooKeeper, Consul, Kafka's KRaft controller quorum, CockroachDB, TiKV, Spanner and many more.
We will cover:
- The RSM architecture and the life of a command
- Why determinism matters, and how systems enforce it
- Exactly-once command application with client sessions
- Log compaction and snapshots
- Reads: through the log, ReadIndex, leader leases, follower reads
- Scaling out with many consensus groups
- Distributed transactions via consensus: 2PC over consensus groups (Spanner, CockroachDB), deterministic ordering (Calvin), and quorum-based atomic commit (Paxos Commit)
- Where RSMs run in production, and what goes wrong
1. The Architecture
1.1 Three components
Every replica in an RSM has the same three parts:
flowchart LR
Client["Client"] -->|"command"| CM
subgraph Replica["Each replica"]
CM["Consensus module<br/>(Raft / Paxos / Zab)"] -->|"append"| Log["Replicated log<br/>1: set x=3<br/>2: set y=5<br/>3: del x"]
Log -->|"committed entries, in order"| SM["Deterministic<br/>state machine"]
end
CM <-->|"replication RPCs"| Peers["Other replicas"]
SM -->|"result"| Client
- The consensus module receives commands from clients, agrees with the other replicas on their position in the log, and tells the local state machine which entries are committed.
- The log is an ordered sequence of commands. Once an entry is committed at index i, every replica will eventually hold the same entry at index i, forever.
- The state machine is the application: a key-value map, a lock table, a cluster metadata model. It consumes committed entries strictly in index order and produces results.
The contract between them is a single invariant called State Machine Safety: if any replica has applied an entry at index i, no other replica will ever apply a different entry at index i. Raft and Multi-Paxos exist to maintain that invariant under crashes, restarts, message loss and partitions (in the crash-recovery, partially synchronous model described in System Models).
1.2 The life of a command
Using Raft terminology, with a leader and two followers:
sequenceDiagram
participant C as Client
participant L as Leader
participant F1 as Follower 1
participant F2 as Follower 2
C->>L: set x = 7 (client 42, seq 9)
Note over L: Append entry at index 101, term 5, fsync
par Replicate
L->>F1: AppendEntries(index 101, term 5)
and
L->>F2: AppendEntries(index 101, term 5)
end
F1-->>L: success (after fsync)
Note over L: Majority (leader + F1) holds 101 — commitIndex = 101
Note over L: Apply 101 to state machine, x = 7
L-->>C: ok
F2-->>L: success (late, harmless)
L->>F1: next AppendEntries carries commitIndex 101
L->>F2: next AppendEntries carries commitIndex 101
Note over F1,F2: Followers apply 101 in order
Key details:
- The leader responds after applying, not after appending. The response reflects the state machine's result (e.g., "the lock was already held").
- A command is committed once a majority stores it durably — not when the leader applies it, and not when all replicas apply it.
- Followers learn of the commit on the next message and apply lazily. Their state machines lag the leader's slightly — which is why reading from a follower is not automatically fresh (section 5).
1.3 Active vs passive replication
There are two ways to replicate a state machine, and real systems use both:
| Active (command) replication | Passive (state-change) replication | |
|---|---|---|
| What goes in the log | The client's command: increment x | The effect computed by the leader: x = 8 |
| Who executes | Every replica executes every command | Only the leader executes; others apply effects |
| Determinism required | Of the whole command execution | Only of applying effects |
| Log size | Usually small | Can be larger (effects may be bigger than commands) |
| Examples | Raft's model, etcd's KV operations | ZooKeeper (leader turns requests into idempotent transactions), primary-backup databases shipping WAL records |
ZooKeeper's design is instructive. Its leader executes each write request, computes the resulting state change, and broadcasts it as an idempotent transaction via the Zab protocol (see Zab). A setData with a version check becomes "set node /a to data D with version 5" — a transaction that can be applied twice with the same result. That idempotence is what lets ZooKeeper take fuzzy snapshots (section 4.4).
2. Why Determinism Matters
2.1 The failure
If two replicas apply the same command and get different results, they have diverged — and the consensus layer cannot detect it. Consensus guarantees that the log is identical; it says nothing about what the application does with it. A diverged replica will answer reads differently, and if it later becomes leader, its divergent state becomes the "truth" that future commands build on.
Divergence is a silent safety failure of exactly the kind described in System Models: no error, wrong answers.
2.2 Sources of non-determinism
| Source | Example | Fix |
|---|---|---|
| Wall-clock time | expiresAt = now() + ttl inside apply | Leader puts the timestamp into the command; replicas use the logged value |
| Randomness | Generating an ID with uuid4() while applying | Leader generates the ID before proposing; or seed a PRNG from the log index |
| Hash-map iteration order | Go maps, Python sets of strings with hash randomisation | Iterate in sorted order; use ordered maps |
| Concurrency | Applying entries in parallel threads | Apply strictly sequentially (or prove commutativity) |
| Floating point | Different CPUs or compiler flags producing different rounding | Use integers/decimals for replicated state |
| External calls | Calling another service or reading a file during apply | Do side effects outside the state machine, after commit |
| Environment differences | Replicas on different binary versions during a rolling upgrade | Version the command format; gate new behaviour behind a log entry that switches it on |
| Resource limits | One replica runs out of memory or disk while applying | Treat as fatal for that replica; never "skip" an entry |
The last row is subtle. If replica A applies entry 500 successfully and replica B fails to apply it (disk full) and continues to 501, they have diverged. The only safe response to an apply failure is to stop the replica and repair it, not to continue.
2.3 Feature flags through the log
Rolling upgrades are a common source of non-determinism: version 2 of the state machine may handle a command differently from version 1. The standard technique is to make the behaviour change itself a log entry:
- Deploy the new binary everywhere, with the new behaviour disabled.
- Propose a command
enable_feature("v2_semantics")through the log. - Every replica switches behaviour at exactly the same log index.
etcd uses a related idea — the cluster version is stored in the replicated state, and new features take effect only once the whole cluster agrees on a version that supports them. Kafka KRaft records the metadata.version feature level in its metadata log for the same reason.
3. Exactly-Once Application with Client Sessions
Clients retry. If a client sends increment x, the leader commits it, and the response is lost, the client will retry — and a naive RSM will increment twice. The network is a Two Generals channel, so this is not avoidable at the transport level.
The Raft dissertation's solution is to make deduplication part of the replicated state:
- Each client gets a unique client ID (often registered via the log itself).
- Each request carries a sequence number.
- The state machine stores, per client, the last sequence number applied and its response.
- If a command arrives with a sequence number already applied, the state machine returns the cached response instead of re-executing.
Because the dedup table lives in the state machine, it is replicated, snapshotted and restored like everything else — so deduplication survives leader changes.
A compact, deterministic state machine with sessions:
type Command =
| { op: "put"; key: string; value: string }
| { op: "cas"; key: string; expected: string | null; value: string }
| { op: "del"; key: string };
type Entry = { index: number; term: number; clientId: string; seq: number; cmd: Command };
type Result = { ok: boolean; value?: string | null };
export class KvStateMachine {
private data = new Map<string, string>();
private sessions = new Map<string, { seq: number; result: Result }>();
lastApplied = 0;
/** Must be called with committed entries in strictly increasing index order. */
apply(e: Entry): Result {
if (e.index !== this.lastApplied + 1) {
// Never skip or reorder: that is divergence. Crash and let ops repair the replica.
throw new Error(`apply gap: expected ${this.lastApplied + 1}, got ${e.index}`);
}
this.lastApplied = e.index;
const s = this.sessions.get(e.clientId);
if (s && e.seq <= s.seq) return s.result; // duplicate retry: same answer, no re-execution
const result = this.execute(e.cmd);
this.sessions.set(e.clientId, { seq: e.seq, result });
return result;
}
private execute(c: Command): Result {
switch (c.op) {
case "put":
this.data.set(c.key, c.value);
return { ok: true };
case "cas": {
const cur = this.data.get(c.key) ?? null;
if (cur !== c.expected) return { ok: false, value: cur };
this.data.set(c.key, c.value);
return { ok: true };
}
case "del":
return { ok: this.data.delete(c.key) };
}
}
/** Deterministic serialisation: sorted keys, so every replica's snapshot is byte-identical. */
snapshot(): string {
const sorted = <V>(m: Map<string, V>) => [...m.entries()].sort(([a], [b]) => (a < b ? -1 : a > b ? 1 : 0));
return JSON.stringify({ lastApplied: this.lastApplied, data: sorted(this.data), sessions: sorted(this.sessions) });
}
restore(blob: string): void {
const s = JSON.parse(blob);
this.lastApplied = s.lastApplied;
this.data = new Map(s.data);
this.sessions = new Map(s.sessions);
}
}
Real systems also expire sessions (otherwise the table grows forever) — and expiry must itself be deterministic, e.g. driven by timestamps the leader writes into the log, not by each replica's local clock.
4. Log Compaction and Snapshots
4.1 Why the log cannot grow forever
An RSM's log grows with every write. Left alone it would:
- Fill the disk
- Make restarts slow (replaying millions of entries)
- Make catching up a new or lagging replica slow (shipping the entire history)
But most of the log is redundant: if key x was set 10,000 times, only the last value matters for the current state. Snapshotting captures the state machine's state at some index and discards every log entry up to that index.
4.2 What a snapshot contains
| Field | Why |
|---|---|
| The state machine's state (including the client session table) | So the replica can resume from it |
| Last included index and term | So the consensus module's consistency check works for the next entry after the snapshot |
| The cluster membership configuration as of that index | So a replica restored from a snapshot knows who its peers are |
The snapshot replaces the log prefix; entries after the last included index are kept.
4.3 Worked example
A three-node cluster. The leader snapshots periodically. Follower F2 has been partitioned away for a long time.
| Snapshot covers | Log retained | Last log index | |
|---|---|---|---|
| Leader | 1 … 10,000 (term 6) | 10,001 … 10,450 | 10,450 |
| F1 | 1 … 9,000 | 9,001 … 10,450 | 10,450 |
| F2 | 1 … 2,000 | 2,001 … 2,400 | 2,400 |
F2 reconnects. The leader wants to send it entry 2,401 — but the leader discarded entries below 10,001 when it snapshotted. It cannot send what it no longer has. Instead it sends its snapshot:
sequenceDiagram
participant L as Leader
participant F2 as Follower F2 (behind)
L->>F2: AppendEntries(prevIndex 10,450 ...)
F2-->>L: reject — my log ends at 2,400
Note over L: nextIndex for F2 backs off to 2,401, below the leader's snapshot point 10,000
L->>F2: InstallSnapshot(lastIndex 10,000, lastTerm 6, chunk 1 of n)
L->>F2: InstallSnapshot(chunk n, done)
Note over F2: Discard state and log up to 10,000, load snapshot, lastApplied = 10,000
F2-->>L: ok
L->>F2: AppendEntries(entries 10,001 to 10,450)
F2-->>L: success
Note over F2: Caught up — applies 10,001 onwards
Raft's InstallSnapshot RPC transfers the snapshot in chunks. If the follower already has entries beyond the snapshot that match, it keeps them; otherwise it discards its whole log.
4.4 Taking snapshots without stopping the world
Serialising a multi-gigabyte state machine takes time. Blocking all writes while it happens is not acceptable. Common techniques:
- Copy-on-write / fork. Fork the process (or use a persistent/immutable data structure) so the snapshot sees a frozen copy while new writes continue. Redis's RDB persistence uses
fork()this way; the same trick works for an RSM. - Storage-engine snapshots. If the state machine lives in an LSM-tree or B-tree engine (RocksDB, Pebble, bbolt), use the engine's consistent snapshot/checkpoint feature. CockroachDB and TiKV ship range snapshots by streaming data out of the storage engine at a consistent point.
- Fuzzy snapshots. ZooKeeper writes its snapshot while transactions keep being applied, so the snapshot does not correspond to any single point in time. This is safe because ZooKeeper's transactions are idempotent: on recovery it loads the fuzzy snapshot and replays the transaction log from a point before the snapshot started, and re-applying already-included transactions changes nothing.
4.5 When to snapshot
| Policy | Example | Trade-off |
|---|---|---|
| Every K entries | etcd's --snapshot-count setting | Simple; snapshot cost proportional to state size, not log size |
| When log size exceeds a threshold | Bytes of retained log > X | Bounds disk use directly |
| Time-based | Every few minutes | Predictable; may snapshot when nothing changed |
Two subtleties:
- Keep some log after the snapshot. If the leader retains a margin of entries before its snapshot point, slightly lagging followers can catch up with cheap
AppendEntriesrather than expensive full snapshots. - Separate state-machine compaction from log compaction. etcd, for example, keeps a multi-version history of keys in its MVCC store (so clients can watch from a past revision) and compacts that history separately from Raft's log via an explicit
compactoperation or auto-compaction settings.
5. Reads
Writes must go through the log. Reads do not change state, so it is tempting to answer them directly from a replica's state machine. Whether that is correct depends on which replica, and on what guarantee you want.
5.1 Why "just read from the leader" is not linearizable
A leader can be deposed without knowing it. Suppose leader L1 is partitioned from the other two nodes. They elect L2 in a new term and commit writes. L1, still believing itself leader, answers a read from its local state — returning a value that L2 has already overwritten. The read is stale, and if another client has already observed the new value, the history is not linearizable.
sequenceDiagram
participant C1 as Client 1
participant L1 as Old leader (term 3)
participant L2 as New leader (term 4)
participant C2 as Client 2
Note over L1,L2: Partition — L1 cut off from the majority
Note over L2: Elected in term 4 with the third node
C2->>L2: write x = 2
L2-->>C2: ok (committed by majority)
C1->>L1: read x
L1-->>C1: x = 1 (stale, L1 does not know it was deposed)
Note over C1,C2: Client 2's write completed before Client 1's read began, yet Client 1 saw the old value
There are four ways to fix this, trading latency against assumptions.
5.2 Option 1: reads through the log
Treat reads as commands: append read x to the log, wait for it to commit and apply, return the value. Correct and simple, but every read costs a disk write and a replication round trip. Rarely used for hot paths.
5.3 Option 2: ReadIndex
Described in Ongaro's Raft dissertation. The leader proves it is still the leader at the moment of the read, without writing anything to the log:
- The leader records its current commitIndex as the read's
readIndex. (A new leader must first commit an entry from its own term — usually a no-op — so that its commitIndex is up to date.) - The leader sends a round of heartbeats and waits for acknowledgements from a majority. If a majority still accepts it as leader for its term, no other leader with a higher term could have committed anything at that moment.
- The leader waits until its state machine has applied up to
readIndex. - It serves the read from local state.
sequenceDiagram
participant C as Client
participant L as Leader
participant F1 as Follower 1
participant F2 as Follower 2
C->>L: read x
Note over L: readIndex = commitIndex = 205
par Confirm leadership
L->>F1: heartbeat (term 5)
and
L->>F2: heartbeat (term 5)
end
F1-->>L: ack term 5
Note over L: Majority confirmed — still leader at the time of the read
Note over L: Wait until lastApplied is at least 205
L-->>C: x = 7
Cost: one network round trip to a majority, but no disk write, and the heartbeat round can be shared by many concurrent reads (batch them all behind one confirmation). etcd's default linearizable reads use this mechanism.
5.4 Option 3: leader leases
ReadIndex still costs a round trip per batch of reads. Leases remove it by relying on time:
- Followers promise not to vote for another leader until some time after they last heard from the current one (in Raft, this follows from the election timeout).
- The leader, after a successful heartbeat round started at time t, considers itself to hold a lease until t + electionTimeout / clockDriftBound — conservatively less than the election timeout.
- While the lease is valid, the leader serves reads locally with no network round trip.
The catch is the system model: leases assume bounded clock drift and that the leader is not paused past its lease. A leader stalled in a GC pause can wake up and serve a read after its lease expired and a new leader was elected. This is the timing-affects-safety pattern from System Models, so lease reads are opt-in in most systems. Leases & Fencing covers lease safety margins and fencing in depth.
- TiKV uses lease-based reads by default for its Raft regions.
- CockroachDB serves reads from a range's leaseholder — a single replica holding a time-based lease — and builds its transaction protocol around hybrid logical clocks and a configured maximum clock offset.
- etcd has used leader-lease checks in specific places, but its documented linearizable read path is ReadIndex.
5.5 Option 4: follower reads
Followers can serve linearizable reads too, offloading the leader:
- The follower asks the leader for the current
readIndex(the leader runs the ReadIndex leadership check). - The follower waits until it has applied up to that index.
- It serves the read locally.
This costs a round trip from follower to leader, but the read's data transfer and execution happen on the follower — useful when reads are large or when the follower is closer to the client. TiKV and etcd both support variants of this.
5.6 Option 5: stale reads
Many reads don't need linearizability. Serving directly from any replica's local state gives sequential consistency per replica (each replica applies a prefix of the log, in order), but possibly stale data:
- etcd offers
serializablereads (--consistency=sonetcdctl get), served from the local member without consensus. - ZooKeeper serves all reads from the server the client is connected to. Each client sees a consistent prefix of the update order, but a read may lag writes committed elsewhere. A client that needs the latest data calls
syncbefore reading, which makes its server catch up with the leader. - CockroachDB offers follower reads for historical timestamps via
AS OF SYSTEM TIME follower_read_timestamp(), served by any replica that has closed that timestamp. - Spanner serves reads at a timestamp from any replica that is sufficiently up to date (its "safe time" is past the read timestamp).
5.7 Comparison
| Read path | Linearizable? | Extra cost per read | Depends on clocks? | Used by |
|---|---|---|---|---|
| Through the log | Yes | Disk write + replication | No | Simple implementations |
| ReadIndex | Yes | Majority round trip (batchable) | No | etcd (default) |
| Leader lease | Yes, if clocks behave | None | Yes | TiKV, lease-based systems |
| Follower read via ReadIndex | Yes | Follower→leader round trip | No | TiKV, etcd variants |
| Local/stale read | No (per-replica prefix) | None | No | etcd serializable, ZooKeeper reads |
| Timestamped stale read | Snapshot at a past time | None | Depends on timestamp scheme | Spanner, CockroachDB follower reads |
6. Scaling Out: Many Consensus Groups
A single RSM has hard limits. Every write passes through one leader and is replicated to every node. Throughput is bounded by that leader's CPU, disk and network, and the entire state must fit on every replica.
The standard way out is sharding into many independent consensus groups — often called multi-Raft or multi-Paxos groups:
flowchart TB
subgraph N1["Node 1"]
A1["Range A (leader)"]
B1["Range B"]
C1["Range C"]
end
subgraph N2["Node 2"]
A2["Range A"]
B2["Range B (leader)"]
C2["Range C"]
end
subgraph N3["Node 3"]
A3["Range A"]
B3["Range B"]
C3["Range C (leader)"]
end
A1 <--> A2
A2 <--> A3
B1 <--> B2
B2 <--> B3
C1 <--> C2
C2 <--> C3
- The keyspace is split into ranges (CockroachDB), regions (TiKV) or splits / tablets (Spanner). Each is an independent RSM with its own log and its own leader.
- Leaders are spread across nodes, so write load is balanced.
- Ranges split when they grow too large or too hot, and merge when they shrink; ranges are rebalanced across nodes by adding a replica on one node and removing one elsewhere (a membership change in that group's consensus).
- A placement layer (CockroachDB's meta ranges, TiKV's Placement Driver, Spanner's placement driver) tracks which nodes hold which ranges.
This scales throughput nearly linearly with nodes — for operations that touch one range. Operations that touch several ranges need a transaction protocol across consensus groups. That is the next section.
Engineering detail that matters at scale: with tens of thousands of groups per node, per-group heartbeats become a real cost. Systems coalesce heartbeats between node pairs and let idle groups go quiet (CockroachDB calls this quiescing ranges).
7. Distributed Transactions via Consensus
The Distributed Transactions page covers Two-Phase Commit and its central weakness: if the coordinator crashes after participants vote yes, they are blocked — holding locks, unable to commit or abort — until the coordinator recovers. 2PC is an atomic-commit protocol in the crash-recovery model with a single point of failure.
Replicated state machines remove that weakness by making every participant — including the coordinator — a consensus group instead of a single machine. A group does not "crash"; it loses at most a minority of replicas and elects a new leader that knows everything the old one committed.
There are three main families of design.
7.1 Family 1: 2PC over consensus groups (Spanner style)
Google's Spanner (OSDI 2012) shards data into Paxos groups. A transaction that touches several groups runs 2PC, but:
- Each participant is a Paxos group. Its leader acquires locks, and the prepare record is written through Paxos — so the "I voted yes" decision is replicated, not just on one disk.
- The coordinator is one of the participant groups (its leader acts as coordinator). The commit decision is also written through Paxos.
- If any leader fails, its group elects a new leader that reads the replicated prepare/commit state from the log and continues the protocol.
sequenceDiagram
participant C as Client
participant G1 as Group 1 leader (coordinator)
participant G2 as Group 2 leader
participant G3 as Group 3 leader
C->>G1: commit txn T (writes in G1, G2, G3)
G1->>G2: prepare T
G1->>G3: prepare T
Note over G2: Acquire locks, Paxos-replicate PREPARED record
Note over G3: Acquire locks, Paxos-replicate PREPARED record
G2-->>G1: prepared (with prepare timestamp)
G3-->>G1: prepared (with prepare timestamp)
Note over G1: Choose commit timestamp, Paxos-replicate COMMIT record
Note over G1: Commit-wait until TrueTime says the commit timestamp has passed
G1-->>C: committed
G1->>G2: commit T at timestamp s
G1->>G3: commit T at timestamp s
Note over G2,G3: Paxos-replicate COMMIT, apply writes, release locks
Two things make this work:
- No single point of blocking. Every durable step is a consensus decision. The protocol still blocks if an entire group loses its majority — but that is a much rarer event than one machine failing.
- Commit timestamps from TrueTime. Spanner's TrueTime API returns an interval guaranteed (under its clock model) to contain true time. The coordinator picks a commit timestamp and waits until it is certainly in the past (commit-wait) before making the commit visible. That is what makes Spanner externally consistent (strictly serializable): if T1 commits before T2 starts in real time, T1's timestamp is smaller. See Clock Synchronization for TrueTime and NewSQL for the broader family.
The cost: a cross-group transaction pays the 2PC message rounds plus a consensus round per durable step in each group, plus commit-wait (bounded by clock uncertainty, typically a few milliseconds in Google's environment according to the paper).
7.2 Family 1, variant: CockroachDB's transaction records and parallel commits
CockroachDB also runs a commit protocol across Raft groups (ranges), with a different shape:
- During the transaction, writes are laid down as write intents — provisional values — in each range, each replicated through that range's Raft log.
- One range holds the transaction's transaction record, whose status (
PENDING,COMMITTED,ABORTED) is the single source of truth for whether the transaction committed. Updating the record is a Raft write in its range. - Readers that encounter an intent look up the transaction record to decide whether to see the value.
Classic 2PC would take two sequential consensus rounds at commit: first make all intents durable, then mark the record COMMITTED. CockroachDB's parallel commits (introduced in version 19.2) do both at once: the record is written with a STAGING status listing all the transaction's writes, in parallel with the last intent writes. The transaction is defined to be implicitly committed once the staging record and all listed writes are durable — any observer can verify that condition and finalise the record. The client gets its acknowledgement after one round of consensus latency instead of two.
This is a good example of a general principle: once each piece of commit state lives in an RSM, you can redefine "committed" as a condition over replicated state rather than a message from a coordinator.
7.3 Family 2: deterministic ordering (Calvin style)
Calvin (Thomson et al., SIGMOD 2012) takes a radically different approach. Instead of agreeing on the outcome of each transaction across partitions, it agrees on the order of inputs up front and lets every partition execute deterministically:
- Sequencing layer. Transaction requests are collected into batches (the paper used 10 ms epochs). Each batch is replicated — via Paxos or asynchronous replication — before anything executes. Concatenating the batches gives a single global order of transactions.
- Scheduling layer. Each partition reads the global order and acquires locks for its part of each transaction in that order, deterministically. Because every partition sees the same order and uses the same locking rule, there are no deadlocks and no disagreement.
- Execution. Each partition executes its piece; partitions exchange the reads that other partitions need. Since execution is deterministic and the input order is agreed, every replica of every partition reaches the same result.
flowchart LR
Clients["Clients"] --> Seq["Sequencer<br/>(10 ms batches)"]
Seq -->|"replicate batch via Paxos"| Log["Agreed global<br/>input order"]
Log --> P1["Partition 1<br/>deterministic locks + execute"]
Log --> P2["Partition 2<br/>deterministic locks + execute"]
Log --> P3["Partition 3<br/>deterministic locks + execute"]
P1 <-->|"exchange remote reads"| P2
P2 <-->|"exchange remote reads"| P3
What this buys:
- No 2PC at commit. There is nothing to vote on: a transaction cannot "fail to commit" for nondeterministic reasons like a crash, because a crashed replica will replay the same input and reach the same outcome. Aborts can only be deterministic (e.g., application logic decides "insufficient funds"), and every partition reaches the same abort decision.
- High throughput for contended workloads, because locks are held only for execution, not across commit network rounds.
What it costs:
- Read and write sets must be known before execution, because locks are acquired in sequence order up front. Transactions whose access set depends on data they read (look up an index, then update the row it points to) need Calvin's OLLP technique: run a reconnaissance read to guess the set, then submit the transaction, and restart it deterministically if the guess turns out wrong.
- Batching latency — every transaction waits for the next epoch.
- No interactive transactions (client sends a statement, thinks, sends another): the whole transaction must be submitted as one unit.
FaunaDB (later Fauna) publicly described its transaction protocol as inspired by Calvin.
7.4 Family 3: quorum-based atomic commit (Paxos Commit)
Gray and Lamport's Paxos Commit (2006) attacks 2PC's blocking problem directly, without relying on sharded RSM infrastructure:
- In 2PC, each participant's vote ("prepared" or "aborted") is sent to one coordinator, whose failure blocks everyone.
- In Paxos Commit, each participant's vote is decided by its own Paxos instance, with a shared set of 2F + 1 acceptors. A participant proposes "prepared" (or "aborted") for its instance.
- The transaction commits iff every participant's instance chose "prepared". Any acceptor quorum can reveal the outcome, so the failure of any F acceptors — including the one acting as leader/coordinator — does not block.
- If a participant is slow or dead, another process can propose "aborted" for that participant's instance; Paxos ensures that the instance decides exactly one value, so the transaction can be aborted safely without waiting.
Gray and Lamport show that 2PC is the special case of Paxos Commit with F = 0 (one acceptor, the coordinator), and that with F ≥ 1 it is non-blocking with only a small additional message delay in the failure-free case.
The Spanner and CockroachDB designs are close relatives in spirit: they make the commit-relevant state of each participant and of the coordinator fault-tolerant by putting it in a consensus-replicated log.
7.5 Comparison
| Classic 2PC | 2PC over consensus groups | Parallel commits | Calvin | Paxos Commit | |
|---|---|---|---|---|---|
| Coordinator failure blocks? | Yes | No (group re-elects) | No | No coordinator vote | No (with F ≥ 1) |
| Consensus rounds on the commit path | 0 (single disks) | ≈ 2 sequential per group | ≈ 1 | 1 (sequencing, batched) | Per-participant instances, in parallel |
| Interactive transactions | Yes | Yes | Yes | No | Yes |
| Must know read/write sets in advance | No | No | No | Yes (or OLLP) | No |
| Nondeterministic aborts (crash, deadlock) | Yes | Yes | Yes | No | Yes |
| Clock dependence | No | Spanner: TrueTime for external consistency | HLC + max offset | No | No |
| Examples | XA, many databases | Spanner | CockroachDB | Calvin, Fauna | Research / building block |
8. Where Replicated State Machines Run
| System | Consensus | What the state machine is | Notes |
|---|---|---|---|
| etcd | Raft | MVCC key-value store with watches and leases | Kubernetes' source of truth. Defaults: 100 ms heartbeat interval, 1000 ms election timeout; linearizable reads via ReadIndex, optional serializable reads |
| ZooKeeper | Zab | Hierarchical namespace of znodes, sessions, ephemeral nodes, watches | Passive replication of idempotent transactions; fuzzy snapshots + transaction log; reads served locally, sync for freshness |
| Kafka (KRaft mode) | Raft-based protocol for the metadata log | Cluster metadata — topics, partitions, ISR, configs, ACLs — materialised in memory by controllers and brokers | Metadata is a log (the __cluster_metadata topic) replayed into state, with periodic snapshots. KRaft replaced ZooKeeper; Kafka 4.0 (2025) removed ZooKeeper mode entirely |
| CockroachDB | Raft per range (multi-Raft) | A slice of the sorted key space stored in Pebble | Range leaseholders serve reads, parallel commits for transactions, ranges split/merge/rebalance |
| TiKV | Raft per region | A slice of the key space in RocksDB | Placement Driver schedules regions; lease reads |
| Spanner | Paxos per split | Tablets of a globally distributed database | 2PC across Paxos groups, TrueTime commit-wait |
| Consul | Raft | Service catalog, KV store, sessions | Consistency modes per request: default, consistent, stale |
| Chubby | Paxos | Lock service and small-file store | The 2006 paper that popularised consensus-backed lock services |
For the consensus protocols themselves see Raft: Full Walkthrough, Paxos Made Simple, Zab and Viewstamped Replication.
8.1 Real numbers
Approximate costs for a single RSM write, from first principles:
| Component | Typical cost | Notes |
|---|---|---|
| Leader fsync of the log entry | ~0.1–2 ms on NVMe / good SSDs, 5–10+ ms on spinning disks or throttled cloud volumes | Often the dominant term inside one datacenter |
| Replication round trip | ~0.2–1 ms within a datacenter, tens of ms across regions | Must reach a majority |
| Follower fsync | Same as leader, in parallel | |
| Apply to state machine | Microseconds for in-memory, more for storage engines | |
| Total commit latency | ≈ max(leader fsync, RTT + follower fsync) | With pipelining, leader fsync and replication overlap |
Throughput comes from batching (many commands per log entry or per fsync) and pipelining (sending the next AppendEntries before the previous one is acknowledged). A single Raft group can sustain tens of thousands of small writes per second on good hardware with batching; beyond that, shard into more groups. etcd's own guidance emphasises low-latency disks precisely because fsync latency feeds directly into both write latency and heartbeat health.
9. Failure Modes
| Failure | Symptom | Root cause | Defence |
|---|---|---|---|
| Replica divergence | Replicas answer the same read differently | Non-deterministic apply | Deterministic code reviews, sorted iteration, leader-supplied timestamps, periodic state checksums compared across replicas |
| Snapshot treadmill | A follower never catches up — by the time a snapshot transfers, the leader has truncated past it again | Snapshot transfer slower than log growth + aggressive log truncation | Retain more log after snapshots; throttle compaction while snapshots are in flight; faster snapshot streaming |
| Slow disk on leader | Write latency spikes; leader misses heartbeats; elections churn | fsync stalls | Dedicated low-latency disks, monitor fsync percentiles, tune election timeouts |
| Stale lease read | Linearizability violation under clock jump or long pause | Lease reads assume bounded drift | Prefer ReadIndex; monitor clock offset; bound lease duration conservatively |
| Unbounded session table | Memory grows, snapshots grow | Client sessions never expire | Deterministic expiry driven by log timestamps |
| Huge entries | Replication stalls, heartbeats delayed behind large messages | Clients writing large values | Size limits (etcd has a request size limit), separate large blobs into object storage |
| Too many groups | CPU spent on heartbeats for idle groups | Multi-Raft with many ranges | Heartbeat coalescing, quiescing idle groups |
War Story (illustrative) — the map that iterated differently
A team built an internal scheduler as a Raft-replicated state machine in Go. One command, rebalance, iterated over a map of workers and assigned pending tasks to the first worker with free capacity. Go deliberately randomises map iteration order, so each replica assigned tasks differently. Nothing failed — the leader's assignments were the ones clients saw. Three weeks later the leader was replaced during a node upgrade, and the new leader's state machine had a completely different task assignment. Tasks ran twice, others were orphaned. The fix was a one-line change to iterate over sorted worker IDs, plus a new invariant check: each replica periodically hashes its state at a given log index and proposes the hash through the log, and replicas whose hash disagrees halt themselves.
War Story (illustrative) — the follower that could not catch up
A configuration store held about 8 GB of state. After a long network outage, one follower fell behind and needed a full snapshot. The snapshot took 12 minutes to stream over a throttled link. The leader, configured to keep only a small log tail after each snapshot, had taken two newer snapshots and truncated the log in that time — so when the follower finished installing, the entries it needed next were gone, and it requested another snapshot. The follower stayed in a snapshot loop for a day, leaving the cluster running with no failure margin. The fix was to retain log entries for at least as long as the slowest expected snapshot transfer, and to alert on any follower that installs two snapshots in a row.
10. Decision Guide
Use a replicated state machine when:
- You need linearizable operations: locks, leader election, unique constraints, configuration that must not diverge.
- The state is small enough for each replica (or you are prepared to shard into many groups).
- You can make the state machine deterministic and keep side effects out of
apply.
Reach for something else when:
- The workload is write-heavy and conflict-tolerant — a leaderless store may be cheaper and more available (see Quorums & Leaderless Replication).
- You need to survive partitions with writes on both sides — RSMs only progress on the majority side by design (CAP Theorem).
- The state is huge and you are not ready to run a sharded system — use a database that has already solved this.
| Need | Pattern |
|---|---|
| Small, critical config / coordination | One RSM (etcd, ZooKeeper, Consul) |
| Large keyspace, single-key ops | Sharded RSMs (multi-Raft) |
| Cross-shard transactions, interactive | 2PC over consensus groups (Spanner, CockroachDB) |
| Cross-shard transactions, high contention, known access sets | Deterministic ordering (Calvin-style) |
| Non-blocking atomic commit without sharded infra | Paxos Commit |
Interview Questions
1. What is a replicated state machine and what does each component guarantee?
A deterministic state machine replicated on several nodes, fed the same sequence of commands via a consensus-replicated log. Consensus guarantees every replica sees the same committed entries in the same order (State Machine Safety). Determinism guarantees that the same sequence of commands produces the same state everywhere. Together they make the group behave like a single fault-tolerant server.
2. Give four sources of non-determinism and how to remove each.
Wall-clock time (leader puts timestamps into commands); randomness (leader generates IDs before proposing, or seed from log index); hash-map iteration order (sort keys); external I/O or calls during apply (move side effects outside the state machine, after commit). Also floating point (use integers), concurrency in apply (apply sequentially), and version skew during upgrades (feature flags activated via a log entry).
3. How do you get exactly-once semantics for client commands in an RSM?
Clients carry a unique client ID and a per-request sequence number. The state machine stores, per client, the last applied sequence number and its response. Retries with an already-applied sequence number return the cached response without re-executing. Because the session table is part of the replicated state, it survives leader changes and is included in snapshots. Sessions must expire deterministically.
4. Why are snapshots needed, what goes in them, and how does a far-behind follower catch up?
Without compaction the log grows forever, restarts replay everything, and new replicas need the whole history. A snapshot holds the state machine state (including sessions), the last included index and term, and the membership configuration. A follower that needs entries the leader has already discarded receives the snapshot via InstallSnapshot (in chunks), loads it, and then receives the remaining entries via AppendEntries.
5. Why is reading from the leader's local state not linearizable, and how does ReadIndex fix it?
A leader may have been deposed by a partition without knowing it, and a new leader may have committed newer writes. ReadIndex: the leader records its commitIndex, confirms it is still leader by getting heartbeat acks from a majority, waits until it has applied up to that index, then serves the read locally. No log write is needed and the confirmation round can be shared across many reads.
6. Compare ReadIndex with lease-based reads.
ReadIndex costs a majority round trip per batch of reads but relies on no timing assumptions. Lease reads cost no round trip but assume bounded clock drift and no process pauses beyond the lease: followers won't elect a new leader until the lease expires, so the leader can serve locally while it holds it. A GC pause or clock jump can violate linearizability with leases. TiKV defaults to lease reads; etcd's linearizable reads use ReadIndex.
7. How does ZooKeeper's read consistency differ from etcd's default?
ZooKeeper serves reads from the local server the client is connected to; writes are linearizable but reads may be stale (each client sees a consistent prefix, FIFO per client). Clients call sync before a read when they need the latest committed state. etcd's default reads are linearizable via ReadIndex; its serializable option behaves like ZooKeeper's local reads.
8. How does Spanner avoid 2PC's blocking problem?
Each 2PC participant and the coordinator are Paxos groups, not single machines. Prepare and commit records are written through Paxos, so a leader failure is handled by electing a new leader that recovers the protocol state from the replicated log. The protocol can only block if a whole group loses its majority. TrueTime commit-wait makes commit timestamps respect real-time order, giving external consistency.
9. What are CockroachDB's parallel commits?
Instead of two sequential consensus rounds (make intents durable, then mark the transaction record committed), the coordinator writes the transaction record in STAGING status with the list of its writes in parallel with the final intent writes. The transaction is implicitly committed once the staging record and all listed writes are replicated — a condition any reader can verify — so the client can be acknowledged after roughly one consensus latency.
10. How does Calvin avoid 2PC entirely, and what does it require?
Calvin agrees on a global order of transaction inputs (replicated batches) before execution. Every partition acquires locks deterministically in that order and executes deterministically, so all replicas reach the same outcome and there is nothing to vote on; aborts can only be deterministic. It requires read/write sets to be known in advance (OLLP reconnaissance for dependent transactions), adds batching latency, and doesn't support interactive transactions.
11. What is Paxos Commit and how does it relate to 2PC?
Each participant's prepared/aborted vote is decided by its own Paxos instance over a shared set of 2F+1 acceptors. The transaction commits iff every instance chose prepared. Any F acceptors (including the coordinator) can fail without blocking, and a stalled participant's instance can be driven to "aborted". 2PC is the special case F = 0.
12. Why do systems like CockroachDB and TiKV run thousands of Raft groups instead of one?
A single group's throughput is bounded by one leader and every replica must hold all data. Splitting the keyspace into ranges/regions, each its own Raft group with leaders spread across nodes, scales throughput and storage horizontally. Costs: cross-range operations need a transaction protocol, and per-group overhead (heartbeats) must be managed with coalescing and quiescing.