State-Machine Replication & Total-Order Broadcast

One machine underneath them all

Almost every strongly consistent distributed system (etcd, ZooKeeper, Kafka's controller, CockroachDB, Spanner) is secretly the same machine underneath. That machine is state-machine replication (SMR), and understanding it collapses a dozen scary systems into one idea.

Start with a deterministic state machine: a program whose next state depends only on its current state and the next input. A key-value store is a perfect example. SET x=5, DELETE y, INCR z are commands, and if you apply the same commands in the same order starting from the same empty state, you land in exactly the same final state, every time, on every machine. That is the whole trick. If you can get N replicas to apply the same sequence of commands in the same order, they will all hold identical state, with no further coordination needed.

So the replication problem reduces to one thing: getting every replica to agree on a single ordered log of commands. This ordering primitive has a name, total-order broadcast (atomic broadcast): every correct node delivers the same set of messages in the same order. The deep result: total-order broadcast is equivalent to consensus. You can build one from the other. This is why "how do I keep my replicas consistent" and "I need a consensus algorithm" are the same question wearing different clothes.

  clients ->  [ append ]  ->  replicated ordered log
                              idx:  1     2     3     4
                              cmd: SET   INCR  DEL   SET
                                    |     |     |     |
              replica A  apply ---> same order ---> state S
              replica B  apply ---> same order ---> state S
              replica C  apply ---> same order ---> state S

The two non-negotiable preconditions

First, apply must be deterministic. If a command reads the wall clock, a random number, a map's iteration order, or calls an external service, two replicas fed the identical log will diverge, and your replicas silently disagree while the log looks perfectly healthy. This is the number one wrong turn. The fix: move all nondeterminism into the command before it enters the log: the leader stamps the timestamp or random seed into the entry, and every replica applies that recorded value. Second, apply should be idempotent enough that replaying an entry twice (after a crash mid-apply) is safe.

The remaining practical problem is that the log grows forever. Bound it with snapshots (log compaction): periodically serialize the full state machine to disk, record the log index it covers, and truncate everything at or below. A recovering or newly added replica installs the latest snapshot and replays only the tail. Raft, Kafka, and etcd all do exactly this.

Interview nuance: if asked "how do you keep replicas consistent," do not jump to gossip or last-write-wins. Say "I model each replica as a deterministic state machine and feed them one agreed ordered log via a consensus protocol; consistency then falls out for free," then mention snapshots for log growth. That framing signals you understand the primitive rather than a specific product.

Recap: identical replicas come from applying the same deterministic commands in the same order, achieving that order is total-order broadcast which is equivalent to consensus, nondeterministic apply is the classic silent-divergence bug, and snapshots bound otherwise-unbounded log growth.