We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningAdvanced · Distributed Systems Core
Running the same deterministic state machine on multiple nodes, applying the same commands in the same order. If they start in the same state and see the same inputs, they stay in sync.
In short
State machine replication is a technique for keeping multiple servers in sync by running an identical deterministic program on each one and feeding every server the same commands in the exact same order. Because they all start from the same state and apply the same inputs, they end up in the same state, so any replica can answer reads and any replica can take over if another fails.
In short
State machine replication is a technique for keeping multiple servers in sync by running an identical deterministic program on each one and feeding every server the same commands in the exact same order. Because they all start from the same state and apply the same inputs, they end up in the same state, so any replica can answer reads and any replica can take over if another fails.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers State Machine Replication across a run of lessons, not one page. These 4 alone are about 112 minutes of step-by-step reading, 2 of them with code you run in the browser, all with a quiz.
Scaling reads by replicating data to follower databases, primary-replica architecture and replication lag.
Cross-region (cross data center) replication explained: sync vs async, replication lag, RPO and RTO, failover loss, and what AWS, Spanner and CockroachDB do.
Model system behavior as a finite set of states and transitions, the foundation of distributed protocols.
What a finite state machine is, DFA vs NFA, and how TCP and Kubernetes pods use one. Includes a type-safe state machine in code.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Read Replicaspay once,
yours for life
Picture your service as a state machine: it holds some state (account balances, a key-value store, a list of locks) and it changes that state only by processing commands one at a time. Apply command, get new state. Apply the next command, get the next state. There is no clock, no random number, no reading the machine's local time. The output depends only on the current state and the command. That property is called determinism, and it is the whole foundation of state machine replication.
Now run an exact copy of that state machine on three or five servers. If you can guarantee that every copy receives the same commands in the same order, then every copy walks through the same sequence of states and stays identical to all the others. That is the entire idea. You are not copying data after the fact. You are copying the inputs and letting each replica recompute the data itself.
The hard part is not the state machine. The hard part is the words same order. Getting a set of independent servers, over an unreliable network, to agree on one ordered log of commands is exactly the consensus problem, and it is why state machine replication is almost always built on top of a consensus protocol like Raft, Multi-Paxos, or Zab.
The architecture is usually a replicated log. Clients send commands to a leader. The leader assigns each command a position in the log (1, 2, 3, ...) and replicates that log entry to the followers. Once a majority of replicas have stored an entry durably, the entry is committed and can never be lost or reordered. Each replica then applies committed entries to its local state machine strictly in log order.
Two pieces have to hold together. First, the consensus layer guarantees that all replicas agree on the same log: the same commands at the same indexes. Second, the state machine must be deterministic so that applying that agreed log produces identical state everywhere. If a developer sneaks in a call to the system clock or a random generator inside the command handler, the replicas drift apart and the whole guarantee breaks. Real implementations push nondeterministic values (timestamps, IDs) into the command itself before it enters the log, so every replica sees the same value.
Because replaying the full log from the beginning would take forever, systems take periodic snapshots of the state machine and truncate the old log. A recovering or newly added replica installs the latest snapshot, then replays only the log entries that came after it.
Failover is the payoff. If the leader dies, the consensus protocol elects a new leader from a replica that has the most up-to-date committed log. Since that replica already holds the same state, it can start serving immediately. Clients see a brief pause, not data loss.
Reach for state machine replication when you need strong consistency and high availability for a small, critical piece of state: cluster metadata, configuration, service discovery, leader election, distributed locks, or the control plane of a larger system. It gives you a single logical source of truth that survives machine failures without ever returning stale or conflicting answers.
The cost is latency and throughput. Every write has to be replicated to and acknowledged by a majority before it commits, so a single write crosses the network at least once and waits for the slower half of the cluster. A three-node cluster spread across data centers can add tens of milliseconds per write. It also does not scale writes by adding nodes. Five replicas do not give you more write throughput than three; they give you more fault tolerance. In fact more replicas usually means slightly slower writes because the majority is larger.
It also assumes your workload fits the model: commands must be deterministic and the full state should be small enough to snapshot and to fit in memory on every node. This is why you do not run a multi-terabyte analytics database as one giant replicated state machine. You run the coordination layer that way, and let the bulk data live elsewhere.
Etcd, the key-value store behind Kubernetes, is a clean example. Every change to the cluster (a new pod spec, a config update) becomes a command. Etcd's leader appends it to a Raft log, replicates it to the other etcd members, waits for a majority to acknowledge, then every member applies it to its local key-value store in the same order. When you run kubectl apply, that write goes through this pipeline before the API server confirms it.
The win is that any etcd member can answer a read with a consistent view, and if the leader node crashes, a follower is promoted in roughly a second with zero data loss because it already holds the identical log. The trade-off is visible too: writes to etcd are slower than writes to a single unreplicated store, which is exactly why Kubernetes keeps high-volume data (like logs and metrics) out of etcd and stores only the relatively small, critical cluster state there.
etcd / Kubernetes
etcd uses Raft state machine replication to store all Kubernetes cluster state; every kubectl write goes through the replicated log.
Apache ZooKeeper
Uses the Zab atomic broadcast protocol to replicate an ordered log of operations across nodes for coordination and locking.
CockroachDB
Each data range is its own Raft group, applying the same write commands in the same order across replicas for strong consistency.
Google Spanner / Chubby
Google's Chubby lock service and Spanner use Paxos-based replicated state machines so reads and locks stay consistent across data centers.
Copying data (like streaming a database's change log to a follower) replicates the results of operations. State machine replication replicates the inputs (the commands) and has every replica recompute the results itself in an agreed order. Because all replicas agree on the order before applying, they cannot diverge, which is why it gives strong consistency rather than eventual consistency.
If two replicas process the same command but one reads the local clock or a random number, they produce different state and silently drift apart. Determinism guarantees that the same starting state plus the same command always yields the same result, so identical input logs produce identical state. Any nondeterministic value must be decided once and written into the command before it enters the log.
No, but they work together. Consensus protocols like Raft or Paxos solve one job: getting the replicas to agree on a single ordered log of commands. State machine replication is what you build on top of that agreed log by applying the commands to a deterministic application. Raft is the agreement, the state machine is what consumes it.
No. Each write must be acknowledged by a majority before it commits, so more replicas mean a larger majority to wait for, which usually makes writes slightly slower. More replicas buy you more fault tolerance, not more write throughput. A five-node cluster tolerates two failures but does not write faster than a three-node cluster.
Replaying the entire log from the start would be too slow, so the system periodically takes a snapshot of the state machine and discards the older log entries. A lagging or brand-new replica installs the latest snapshot first, then replays only the log entries recorded after that snapshot to reach the current state.
Raft
A consensus algorithm designed to be understandable. Uses leader election and log replication. Powers etcd (used by Kubernetes) and CockroachDB.
Paxos
A family of protocols for solving consensus in unreliable networks. Famously difficult to understand but mathematically proven correct.
Consensus
The process of getting multiple nodes in a distributed system to agree on a single value. The foundation of distributed databases and coordination services.
CAP Theorem
When a network failure splits a distributed data store, each node must either refuse requests to stay consistent or keep answering with possibly stale data. It cannot guarantee both during the partition.
CQRS
Command Query Responsibility Segregation: using different models for reading and writing data. Reads and writes have different performance needs, so separate them.
Event Sourcing
Storing every state change as an immutable event instead of just the current state. You can rebuild any past state by replaying events.
This page explains the idea. The course covers it step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
See the System Design Masterclass coursecourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about State Machine Replication in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
