State-machine snapshots

Deep dive

How it works

Parts:

• State machine — deterministic apply(index, entry); remembers applied.
• Log — ordered entries; after compaction it starts at snapshot.index + 1.
• Snapshot — canonical state bytes plus metadata: last included index, its term or epoch, cluster configuration.
• Capturer — gives a consistent view at one index while applying continues.
• Publisher — temp file, fsync, rename, fsync directory.
• Installer — sends the snapshot to a replica whose next entry was compacted away.

1. Trigger: entries or bytes since the last snapshot pass a threshold (etcd and ZooKeeper default: 100,000 entries).
2. Capture at an apply boundary, so the view holds exactly entries ≤ i: fork, a copy-on-write version, or hard-linked immutable files.
3. Serialize with metadata (index i, its term, configuration) in a canonical order.
4. Publish atomically: temp file, fsync, rename, fsync directory.
5. Only then delete log entries ≤ i (optionally keep a short tail for slightly slow followers).
6. Recover: load the newest valid snapshot, set applied = i, replay log entries i+1.. in order; entries ≤ i are skipped.
7. Catch-up: a follower needing a compacted entry gets the snapshot in chunks (Raft InstallSnapshot: lastIncludedIndex, lastIncludedTerm, offset, data, done), replaces its state and resumes at i+1.

log:   1 ........ i | i+1 ...... n        before: log holds 1..n
snap:  [state@i, idx=i, term, config]
disk:  snapshot(i)  +  log(i+1..n)         after truncation
restart:   load(snapshot) ──► apply(i+1) ... apply(n)
lagging follower (next = j <= i):  leader ──chunks──► snapshot(i), then entries i+1..

Code

use std::{collections::BTreeMap, fs::{self, File}, io::Write, path::Path};

#[derive(Clone)]
pub enum Cmd { Put(u64, u64), Del(u64) }

#[derive(Default, PartialEq, Debug)]
pub struct Kv { pub map: BTreeMap<u64, u64>, pub applied: u64 }

impl Kv {
    /// Deterministic: no clock, no RNG, ordered map only.
    pub fn apply(&mut self, index: u64, cmd: &Cmd) {
        if index <= self.applied { return; } // already inside the snapshot
        match cmd {
            Cmd::Put(k, v) => { self.map.insert(*k, *v); }
            Cmd::Del(k) => { self.map.remove(k); }
        }
        self.applied = index;
    }
    /// index, count, then sorted (key, value) pairs: canonical bytes.
    pub fn encode(&self) -> Vec<u8> {
        let mut b = Vec::with_capacity(16 + self.map.len() * 16);
        b.extend_from_slice(&self.applied.to_le_bytes());
        b.extend_from_slice(&(self.map.len() as u64).to_le_bytes());
        for (k, v) in &self.map {
            b.extend_from_slice(&k.to_le_bytes());
            b.extend_from_slice(&v.to_le_bytes());
        }
        b
    }
    pub fn decode(b: &[u8]) -> Kv {
        let n = |i: usize| u64::from_le_bytes(b[i..i + 8].try_into().unwrap());
        // sorted input: BTreeMap builds bottom-up instead of inserting one by one
        let map = (0..n(8) as usize).map(|i| (n(16 + i * 16), n(24 + i * 16))).collect();
        Kv { map, applied: n(0) }
    }
}

/// Atomic publish: temp file in the same directory, fsync, rename, fsync directory.
pub fn write_snapshot(dir: &Path, bytes: &[u8]) -> std::io::Result<()> {
    let tmp = dir.join("snapshot.tmp");
    let mut f = File::create(&tmp)?;
    f.write_all(bytes)?;
    f.sync_all()?;
    fs::rename(&tmp, dir.join("snapshot"))?;
    File::open(dir)?.sync_all() // persist the rename itself
}

/// Entries after compaction: entries[0] has index `first`.
pub struct Log { pub first: u64, pub entries: Vec<Cmd> }
impl Log {
    pub fn truncate_prefix(&mut self, upto: u64) { // call only after write_snapshot returned
        if upto >= self.first {
            self.entries.drain(..(upto + 1 - self.first) as usize);
            self.first = upto + 1;
        }
    }
}

pub fn recover(dir: &Path, log: &Log) -> Kv {
    let mut kv = fs::read(dir.join("snapshot")).map(|b| Kv::decode(&b)).unwrap_or_default();
    assert!(kv.applied + 1 >= log.first, "gap between snapshot and log");
    for (i, c) in log.entries.iter().enumerate() { kv.apply(log.first + i as u64, c); }
    kv
}

#[test]
fn snapshot_then_replay_equals_full_replay() {
    let dir = std::env::temp_dir().join("sms-test");
    let _ = fs::remove_dir_all(&dir);
    fs::create_dir_all(&dir).unwrap();
    let all: Vec<Cmd> = (1..=1000u64)
        .map(|i| if i % 5 == 0 { Cmd::Del(i * 7 % 100) } else { Cmd::Put(i * 7 % 100, i) })
        .collect();
    let (mut full, mut live) = (Kv::default(), Kv::default());
    for (i, c) in all.iter().enumerate() { full.apply(i as u64 + 1, c); }
    for (i, c) in all[..600].iter().enumerate() { live.apply(i as u64 + 1, c); }
    write_snapshot(&dir, &live.encode()).unwrap();
    let mut log = Log { first: 1, entries: all };
    log.truncate_prefix(600);
    assert_eq!(log.first, 601); // log now starts at i + 1
    assert_eq!(recover(&dir, &log), full);
    live.apply(3, &Cmd::Put(1, 999)); // index <= snapshot: skipped
    assert_eq!(live.applied, 600);
}

Complexity and constants

• Snapshot write: O(live state), not O(history). Write amplification = state size / interval; doubling the interval halves it and doubles worst-case replay.
• Recovery: O(state) load plus at most one interval of replay. Publishing: one file fsync, one rename, one directory fsync.

Efficiency

• Cost: measured here, Apple M4 Pro, macOS, single runs, 1M keys (16 MB snapshot): replay of 1M random-key puts into a BTreeMap about 390 ms (390 ns/entry); encode 21 ms; write without fsync 15-25 ms (640-1,100 MB/s), with sync_all 23-34 ms; read 3 ms; decode by per-key insert 154 ms, by bulk build from sorted pairs 12.5 ms. With 10M puts to 1,000 hot keys, replay took 213 ms but the snapshot was 16 KB and loaded in 73 µs. Bound: rebuild cost (load), flush latency (publish).
• Levers:
  • Copy-on-write capture (fork, persistent structures) — no write pause; fork itself stalls ms to ~1 s on big datasets (Redis docs) — state fits in memory.
  • Bulk-build or mmap-able snapshot format — decode 154 ms to 12.5 ms (measured above) — load dominates restart.
  • Larger interval — fewer snapshot writes, longer replay (etcd documents the memory trade-off) — restarts rare.
  • Incremental or hard-linked checkpoints — write only changed files (RocksDB checkpoints hard-link SST files) — state mostly immutable.
  • Chunked streaming install — constant memory on both ends — snapshots are GBs.
• Naive → standard → state of the art: write in place while stopped · pause = write time, torn file on crash; temp file + fsync + rename at a threshold · atomic, recovery bounded by interval; COW capture, incremental files, streamed install · no pause, cost proportional to change.

Implementation notes

• Snapshot at an apply boundary; with async apply use the applied index, not the commit index.
• Temp file in the same directory (rename across file systems is not atomic); delete leftover *.tmp at startup.
• Keep the previous snapshot until the new one is published; checksum files and fall back if the newest is bad.
• Serialize on its own thread over the COW view; rate-limit it so it does not starve log fsyncs on the same device.
• Install in chunks of a few MB, publish only when done.

Pitfalls

• Truncating the log before the snapshot is durable: a crash loses state with no way back.
• Non-determinism (HashMap order, wall clock, unseeded RNG, thread timing): snapshot plus suffix differs from full replay.
• Off by one between snapshot index and state: entry i applied twice or i+1 skipped.
• Dropping term and configuration: Raft needs both after an install.
• fork() under heavy writes can double memory.

Variants and alternatives

In production

• etcd: snapshot after --snapshot-count applied entries (default 100,000), then truncates old Raft entries; a follower behind the compacted index receives the leader's snapshot.
• ZooKeeper: snapshot plus transaction log; snapCount is randomized per server in [snapCount/2+1, snapCount] so the quorum does not snapshot together; the leader sends a full snapshot to followers missing too many proposals.
• Redis: RDB point-in-time snapshot by a forked child plus an AOF log; AOF rewrite builds a new base file in a temporary file.
• Game servers: world checkpoint plus input log for crash recovery, replay playback and lockstep late-join.
• Flink: asynchronous barrier snapshots for exactly-once recovery; event-sourced ledgers keep state plus an event tail.

Implementations

Sources

• Diego Ongaro, John Ousterhout, In Search of an Understandable Consensus Algorithm, USENIX ATC 2014, §7 log compaction. paper
• Redis, Persistence (RDB, AOF, fork behaviour). docs
• etcd, Maintenance (Raft log retention, --snapshot-count). docs
• Apache ZooKeeper, Administrator's Guide (snapCount). docs
• Hunt, Konar, Junqueira, Reed, ZooKeeper: Wait-free coordination for Internet-scale systems, USENIX ATC 2010. paper
• Carbone et al., Lightweight Asynchronous Snapshots for Distributed Dataflows, 2015. arXiv
• Chandy, Lamport, Distributed Snapshots: Determining Global States of a Distributed System, ACM TOCS 1985. paper