State Machine Replication

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.