State Machine Replication (SMR)

Overview

State machine replication (SMR) is the technique that makes Raft- or Paxos-backed services behave like a single fault-tolerant computer. A deterministic state machine consumes a replicated log of commands; as long as every replica applies entries in the same order, their state stays identical despite crashes or message delays.

Transactional key-value engines, distributed coordinators, and queue schedulers all use SMR to provide linearizable APIs. If you understand how to apply, snapshot, and recover logs you can reason about failover bounds, durability guarantees, and maintenance operations.

This document covers log structure, apply pipelines, snapshotting, and operational playbooks that keep SMR clusters consistent even during chaos events.

Core Concepts

• Replicated Log: Ordered, append-only sequence shared by all replicas via consensus.
• Deterministic State Machine: Applying the same command at the same index yields the same new state everywhere.
• Applied Index: Highest log index durably reflected in the state machine.
• Snapshot: Point-in-time image that lets replicas truncate old log entries.

How It Works

Applying the Log

A background worker tails the consensus log. When commit index advances, it batches entries, decodes them, and invokes the deterministic state transition. After each batch, it persists the new applied index and any write-ahead redo artifacts.

Snapshots and Log Compaction

When the log grows beyond a threshold, replicas checkpoint state (e.g., RocksDB backup, serialized B-Tree) plus the last applied index. Older log entries up to that index can be discarded. Followers that fall behind catch up either by streaming remaining log or by installing the snapshot.

Recovery

After a crash, the node replays the snapshot, then re-applies remaining log entries from the persisted applied index + 1. If the log is truncated beyond that point, the node requests a fresh snapshot from peers.

Practical Applications

• Distributed database transaction records: Apply loop updates MVCC metadata and writes intents deterministically before acknowledging client commits.
• Distributed search shards: SMR ensures vector index mutations remain consistent even when replicas are rescheduled across regions.
• Distributed control plane: Rate limit and feature flag changes are replicated via SMR so workers observe the same configuration ordering.

Implementation Patterns

• Separate storage and FSM threads: one handles consensus I/O, another performs deterministic state transitions.
• Encode commands using versioned protobufs so old replicas can reject unsupported operations.
• Keep snapshots stream-friendly (chunked files, CRC blocks) to shorten install time and resume after failures.
• Expose applied index metrics and alert on follower lag to catch stalled apply loops early.

Code Examples

Go: Apply Loop Skeleton

func (a *Applier) run(ctx context.Context) {
    for {
        select {
        case batch := <-a.commitCh:
            for _, entry := range batch {
                if err := a.fsm.Apply(entry.Data); err != nil {
                    a.logger.Error("apply failed", "index", entry.Index, "err", err)
                    panic(err)
                }
                a.applied = entry.Index
            }
            if err := a.store.SetApplied(a.applied); err != nil {
                a.logger.Fatal("persist applied", err)
            }
        case <-ctx.Done():
            return
        }
    }
}

Zig: Snapshot Metadata Header

const SnapshotHeader = struct {
    magic: u32 = 0x5A4D5301,
    term: u64,
    index: u64,
    checksum: u128,
};

fn writeSnapshotHeader(writer: anytype, term: u64, index: u64, checksum: u128) !void {
    var hdr = SnapshotHeader{ .term = term, .index = index, .checksum = checksum };
    try writer.writeStruct(hdr);
}

Common Pitfalls

• Non-deterministic code: Using time.Now() or random IDs inside the FSM creates divergent replicas.
• Applying before durable: If the applied index is flushed before data hits disk, crash recovery may replay incomplete state.
• Slow snapshot install: Sending giant tarballs blocks Raft for minutes. Stream chunked snapshots and throttle them.
• Ignoring backpressure: If the apply loop cannot keep up, commit index outruns applied index and leaders fill memory.

Key Concepts Recap

• SMR turns consensus logs into a deterministic replicated database.
• Applied index tracking separates durability from state visibility.
• Snapshots keep log sizes bounded and accelerate catch-up.
• Instrumentation across commit/apply/snapshot phases is essential for operations.