On this page

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:

  1. The RSM architecture and the life of a command
  2. Why determinism matters, and how systems enforce it
  3. Exactly-once command application with client sessions
  4. Log compaction and snapshots
  5. Reads: through the log, ReadIndex, leader leases, follower reads
  6. Scaling out with many consensus groups
  7. Distributed transactions via consensus: 2PC over consensus groups (Spanner, CockroachDB), deterministic ordering (Calvin), and quorum-based atomic commit (Paxos Commit)
  8. 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
  1. 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.
  2. 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.
  3. 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) replicationPassive (state-change) replication
What goes in the logThe client's command: increment xThe effect computed by the leader: x = 8
Who executesEvery replica executes every commandOnly the leader executes; others apply effects
Determinism requiredOf the whole command executionOnly of applying effects
Log sizeUsually smallCan be larger (effects may be bigger than commands)
ExamplesRaft's model, etcd's KV operationsZooKeeper (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

SourceExampleFix
Wall-clock timeexpiresAt = now() + ttl inside applyLeader puts the timestamp into the command; replicas use the logged value
RandomnessGenerating an ID with uuid4() while applyingLeader generates the ID before proposing; or seed a PRNG from the log index
Hash-map iteration orderGo maps, Python sets of strings with hash randomisationIterate in sorted order; use ordered maps
ConcurrencyApplying entries in parallel threadsApply strictly sequentially (or prove commutativity)
Floating pointDifferent CPUs or compiler flags producing different roundingUse integers/decimals for replicated state
External callsCalling another service or reading a file during applyDo side effects outside the state machine, after commit
Environment differencesReplicas on different binary versions during a rolling upgradeVersion the command format; gate new behaviour behind a log entry that switches it on
Resource limitsOne replica runs out of memory or disk while applyingTreat 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:

  1. Deploy the new binary everywhere, with the new behaviour disabled.
  2. Propose a command enable_feature("v2_semantics") through the log.
  3. 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

FieldWhy
The state machine's state (including the client session table)So the replica can resume from it
Last included index and termSo the consensus module's consistency check works for the next entry after the snapshot
The cluster membership configuration as of that indexSo 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 coversLog retainedLast log index
Leader1 … 10,000 (term 6)10,001 … 10,45010,450
F11 … 9,0009,001 … 10,45010,450
F21 … 2,0002,001 … 2,4002,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

PolicyExampleTrade-off
Every K entriesetcd's --snapshot-count settingSimple; snapshot cost proportional to state size, not log size
When log size exceeds a thresholdBytes of retained log > XBounds disk use directly
Time-basedEvery few minutesPredictable; 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 AppendEntries rather 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 compact operation 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:

  1. 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.)
  2. 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.
  3. The leader waits until its state machine has applied up to readIndex.
  4. 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:

  1. The follower asks the leader for the current readIndex (the leader runs the ReadIndex leadership check).
  2. The follower waits until it has applied up to that index.
  3. 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 serializable reads (--consistency=s on etcdctl 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 sync before 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 pathLinearizable?Extra cost per readDepends on clocks?Used by
Through the logYesDisk write + replicationNoSimple implementations
ReadIndexYesMajority round trip (batchable)Noetcd (default)
Leader leaseYes, if clocks behaveNoneYesTiKV, lease-based systems
Follower read via ReadIndexYesFollower→leader round tripNoTiKV, etcd variants
Local/stale readNo (per-replica prefix)NoneNoetcd serializable, ZooKeeper reads
Timestamped stale readSnapshot at a past timeNoneDepends on timestamp schemeSpanner, 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:

  1. 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.
  2. 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:

  1. 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.
  2. 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.
  3. 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 2PC2PC over consensus groupsParallel commitsCalvinPaxos Commit
Coordinator failure blocks?YesNo (group re-elects)NoNo coordinator voteNo (with F ≥ 1)
Consensus rounds on the commit path0 (single disks)≈ 2 sequential per group≈ 11 (sequencing, batched)Per-participant instances, in parallel
Interactive transactionsYesYesYesNoYes
Must know read/write sets in advanceNoNoNoYes (or OLLP)No
Nondeterministic aborts (crash, deadlock)YesYesYesNoYes
Clock dependenceNoSpanner: TrueTime for external consistencyHLC + max offsetNoNo
ExamplesXA, many databasesSpannerCockroachDBCalvin, FaunaResearch / building block

8. Where Replicated State Machines Run

SystemConsensusWhat the state machine isNotes
etcdRaftMVCC key-value store with watches and leasesKubernetes' source of truth. Defaults: 100 ms heartbeat interval, 1000 ms election timeout; linearizable reads via ReadIndex, optional serializable reads
ZooKeeperZabHierarchical namespace of znodes, sessions, ephemeral nodes, watchesPassive replication of idempotent transactions; fuzzy snapshots + transaction log; reads served locally, sync for freshness
Kafka (KRaft mode)Raft-based protocol for the metadata logCluster metadata — topics, partitions, ISR, configs, ACLs — materialised in memory by controllers and brokersMetadata is a log (the __cluster_metadata topic) replayed into state, with periodic snapshots. KRaft replaced ZooKeeper; Kafka 4.0 (2025) removed ZooKeeper mode entirely
CockroachDBRaft per range (multi-Raft)A slice of the sorted key space stored in PebbleRange leaseholders serve reads, parallel commits for transactions, ranges split/merge/rebalance
TiKVRaft per regionA slice of the key space in RocksDBPlacement Driver schedules regions; lease reads
SpannerPaxos per splitTablets of a globally distributed database2PC across Paxos groups, TrueTime commit-wait
ConsulRaftService catalog, KV store, sessionsConsistency modes per request: default, consistent, stale
ChubbyPaxosLock service and small-file storeThe 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:

ComponentTypical costNotes
Leader fsync of the log entry~0.1–2 ms on NVMe / good SSDs, 5–10+ ms on spinning disks or throttled cloud volumesOften the dominant term inside one datacenter
Replication round trip~0.2–1 ms within a datacenter, tens of ms across regionsMust reach a majority
Follower fsyncSame as leader, in parallel
Apply to state machineMicroseconds 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

FailureSymptomRoot causeDefence
Replica divergenceReplicas answer the same read differentlyNon-deterministic applyDeterministic code reviews, sorted iteration, leader-supplied timestamps, periodic state checksums compared across replicas
Snapshot treadmillA follower never catches up — by the time a snapshot transfers, the leader has truncated past it againSnapshot transfer slower than log growth + aggressive log truncationRetain more log after snapshots; throttle compaction while snapshots are in flight; faster snapshot streaming
Slow disk on leaderWrite latency spikes; leader misses heartbeats; elections churnfsync stallsDedicated low-latency disks, monitor fsync percentiles, tune election timeouts
Stale lease readLinearizability violation under clock jump or long pauseLease reads assume bounded driftPrefer ReadIndex; monitor clock offset; bound lease duration conservatively
Unbounded session tableMemory grows, snapshots growClient sessions never expireDeterministic expiry driven by log timestamps
Huge entriesReplication stalls, heartbeats delayed behind large messagesClients writing large valuesSize limits (etcd has a request size limit), separate large blobs into object storage
Too many groupsCPU spent on heartbeats for idle groupsMulti-Raft with many rangesHeartbeat 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.
NeedPattern
Small, critical config / coordinationOne RSM (etcd, ZooKeeper, Consul)
Large keyspace, single-key opsSharded RSMs (multi-Raft)
Cross-shard transactions, interactive2PC over consensus groups (Spanner, CockroachDB)
Cross-shard transactions, high contention, known access setsDeterministic ordering (Calvin-style)
Non-blocking atomic commit without sharded infraPaxos 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.