Checkpoint and restart

Deep dive

How it works

Parts:

• Quiesce point — a consistent moment: step boundary, barrier, frozen process tree or coordinated cut.
• Serializer — app-level (own format), user-space library (DMTCP), or kernel-assisted (CRIU reads /proc, injects helper code via ptrace).
• Atomic writer — temp file, fsync, rename (atomic-file-replacement), checksum inside.
• Generation store — newest N files; older ones deleted only after a newer one is complete.
• Loader — newest generation that verifies; rebuilds state, resumes.
• Interval policy — fixed, or from the Young/Daly formula.

1. At the quiesce point capture state: arrays, counters, RNG and input-position state. CRIU stops the tree with PTRACE_SEIZE or the freezer cgroup, reads maps, fds and sockets (TCP via TCP_REPAIR), and dumps pages from inside the target.
2. Optionally resume at once and write in the background: copy-on-write fork (copy-on-write-fork) or a staged copy plus async upload.
3. Write tmp, fsync, rename, fsync the directory (fsync-and-direct-io); delete generations beyond N.
4. After a crash take the newest file whose magic, length and checksum verify.
5. Restore state, re-create what is not serialisable (connections, device contexts), continue from the saved step.
6. Distributed: all ranks save the same logical step, or use markers (Chandy-Lamport snapshots); uncoordinated saves can force a rollback chain (domino effect).

 compute ─► step k ─► [quiesce] ─► serialize ─► tmp ─fsync─► rename ─► ckpt-k
    ▲                                                                  │ keep N
    └──────── crash ─► load newest valid (checksum) ◄──────────────────┘
 failure at step k+j  ⇒  lost work = j steps (at most one interval)

Code

Std-only Rust: xorshift64 RNG state, CRC-32 trailer, temp+fsync+rename, 2 generations. main crashes at step 137, resumes, asserts a bit-identical result, and asserts that a truncated and a bit-flipped newest file are rejected for the previous generation. Run: cargo run --release -- /tmp/dir.

use std::{fs::{self, File}, io::Write, path::Path, time::Instant};

const MAGIC: &[u8; 8] = b"CKPT0001";
const fn crc_table() -> [u32; 256] {
    let (mut t, mut i) = ([0u32; 256], 0);
    while i < 256 {
        let (mut c, mut k) = (i as u32, 0);
        while k < 8 { c = if c & 1 != 0 { 0xEDB8_8320 ^ (c >> 1) } else { c >> 1 }; k += 1; }
        t[i] = c; i += 1;
    }
    t
}
static TABLE: [u32; 256] = crc_table();
fn crc32(b: &[u8]) -> u32 {
    !b.iter().fold(!0u32, |c, &x| TABLE[((c ^ x as u32) & 0xFF) as usize] ^ (c >> 8))
}

/// Everything the computation needs to continue: counter, RNG state, accumulator, bulk data.
#[derive(Clone, PartialEq, Debug)]
struct State { step: u64, rng: u64, acc: u64, data: Vec<u64> }

impl State {
    fn advance(&mut self) { // deterministic given the state: xorshift64 drives all choices
        for _ in 0..1_000_000 {
            self.rng ^= self.rng << 13; self.rng ^= self.rng >> 7; self.rng ^= self.rng << 17;
            let i = (self.rng % self.data.len() as u64) as usize;
            self.data[i] = self.data[i].wrapping_mul(31).wrapping_add(self.rng);
        }
        self.acc = self.acc.rotate_left(5) ^ self.rng;
        self.step += 1;
    }
    fn encode(&self) -> Vec<u8> {
        let mut b = MAGIC.to_vec();
        for v in [self.step, self.rng, self.acc, self.data.len() as u64] { b.extend(v.to_le_bytes()); }
        for v in &self.data { b.extend(v.to_le_bytes()); }
        let c = crc32(&b);
        b.extend(c.to_le_bytes()); // trailer: CRC over header + payload
        b
    }
    fn decode(b: &[u8]) -> Option<State> {
        if b.len() < 44 || &b[..8] != MAGIC { return None; }
        let (body, tail) = b.split_at(b.len() - 4);
        if crc32(body) != u32::from_le_bytes(tail.try_into().ok()?) { return None; }
        let w = |i: usize| u64::from_le_bytes(body[8 + 8 * i..16 + 8 * i].try_into().unwrap());
        let n = w(3) as usize;
        if body.len() != 40 + 8 * n { return None; } // header length must match payload
        Some(State { step: w(0), rng: w(1), acc: w(2), data: (0..n).map(|i| w(4 + i)).collect() })
    }
}

fn save(dir: &Path, s: &State, keep: usize) -> std::io::Result<()> {
    let tmp = dir.join("ckpt.tmp"); // same directory, same file system: rename is atomic
    let mut f = File::create(&tmp)?;
    f.write_all(&s.encode())?;
    f.sync_all()?; // data durable BEFORE the name appears
    fs::rename(&tmp, dir.join(format!("ckpt-{:010}.bin", s.step)))?;
    File::open(dir)?.sync_all()?; // make the rename itself durable
    let mut names = list(dir);
    while names.len() > keep { fs::remove_file(dir.join(names.remove(0)))?; } // keep N generations
    Ok(())
}
fn list(dir: &Path) -> Vec<String> {
    let mut v: Vec<String> = fs::read_dir(dir).unwrap().filter_map(|e| e.ok())
        .map(|e| e.file_name().to_string_lossy().into_owned())
        .filter(|n| n.starts_with("ckpt-") && n.ends_with(".bin")).collect();
    v.sort(); // zero-padded step numbers sort by age
    v
}
fn load_latest(dir: &Path) -> Option<State> {
    list(dir).iter().rev().find_map(|n| State::decode(&fs::read(dir.join(n)).ok()?))
}
fn run(dir: &Path, s: &mut State, until: u64, every: u64) {
    while s.step < until {
        s.advance();
        if every > 0 && s.step % every == 0 { save(dir, s, 2).unwrap(); }
    }
}

fn main() {
    let base = Path::new(&std::env::args().nth(1).unwrap()).to_path_buf();
    let fresh = || State { step: 0, rng: 0x9E37_79B9_7F4A_7C15, acc: 0, data: vec![1; 1 << 20] }; // 8 MiB
    let (total, every) = (300, 25);
    let mut reference = fresh();
    run(&base, &mut reference, total, 0); // uninterrupted run, no checkpoints

    let dir = base.join("a"); fs::create_dir_all(&dir).unwrap();
    let mut victim = fresh();
    run(&dir, &mut victim, 137, every); // "crash" at step 137: in-memory state is lost
    drop(victim);
    let mut s = load_latest(&dir).expect("checkpoint");
    assert_eq!(s.step, 125); // resumed from the last checkpoint, not step 137
    run(&dir, &mut s, total, every);
    assert_eq!(s, reference); // bit-identical incl. RNG and accumulator

    // torn newest generation: truncate it; flip a byte in another copy
    let newest = dir.join(list(&dir).pop().unwrap());
    let good = fs::read(&newest).unwrap();
    fs::write(&newest, &good[..good.len() / 2]).unwrap();
    assert_eq!(load_latest(&dir).unwrap().step, 275); // previous generation used
    let mut bad = good.clone(); bad[1000] ^= 1;
    fs::write(&newest, &bad).unwrap();
    assert_eq!(load_latest(&dir).unwrap().step, 275);
    let mut s = load_latest(&dir).unwrap();
    run(&dir, &mut s, total, every);
    assert_eq!(s, reference);

    for every in [0, 100, 10] { // overhead
        let d = base.join(format!("t{every}")); fs::create_dir_all(&d).unwrap();
        let (mut s, t0) = (fresh(), Instant::now());
        run(&d, &mut s, 300, every);
        println!("every={every:3} total={:?}", t0.elapsed());
    }
    println!("ok");
}

Complexity and constants

• Checkpoint cost grows with state size S: S / bandwidth plus one durable flush. Expected lost work per failure is about T/2.
• Overhead per unit time ≈ C/T + T/(2M) (first-order model), minimised at T = sqrt(2*C*M), where overhead = sqrt(2C/M). Example (arithmetic, not measured): C = 60 s, M = 24 h gives T ≈ 3,220 s, overhead ≈ 3.7 %.
• Young: T ≈ sqrt(2 * Ts * Tf) (save time, mean time to failure). Daly's first-order form T = sqrt(2*C*(M+R)) - C (R = restart time) is reported valid while (T+C)/M < 1/2; his 2006 paper adds a perturbation series (see the paper).
• Measured on this Mac (Apple M4 Pro, macOS 27.0.1): an 8 MiB state saves in ≈ 30 ms; ≈ 16 ms of that is the byte-at-a-time table CRC-32, the rest encode, write, F_FULLFSYNC (sync_all), rename, directory sync. One compute step ≈ 1.7 ms.

Efficiency

• Cost: one 8 MiB application checkpoint takes ≈ 30 ms (measured on this Mac (Apple M4 Pro): 20 saves, two runs, 29.8 and 30.5 ms). 300 steps with no checkpoint: 0.50-0.52 s; with a checkpoint every 100 steps: 0.59-0.64 s (+14 % to +24 %); every 10 steps: 1.39-1.55 s (2.7-3x) (5 runs, measured on this Mac (Apple M4 Pro)). Bound: storage durability latency and bandwidth, plus checksum and copy time.
• Levers:
  • hardware or sliced CRC (CRC32C) — the checksum was over half of the measured save — large states
  • fork-based snapshot — parent only forks, never does disk I/O (Redis docs) — big in-memory state
  • incremental dirty-page checkpoints — write only changed pages (CRIU --track-mem, dirty-page tracking) — slowly changing state
  • async staging and upload — compute resumes after the local copy (PyTorch DCP async_save) — slow or remote storage
  • Young/Daly interval — balances save cost against lost work — failures roughly Poisson
• Naive → standard → state of the art:
  • stop everything, write one file in place · lost on torn write; stall = full write time
  • temp+fsync+rename, checksum, N generations, interval from Young/Daly · stall = serialize + flush
  • fork/staged async write, incremental or sharded parallel save with resharding on load · stall = snapshot cost only

Implementation notes

• Temp file in the same directory (rename is atomic only within one file system); fsync the file before, the directory after.
• Header with magic, version, length; trailer checksum over everything: catches truncation and bit rot.
• Save RNG, step, input offset, optimizer state and schedules, not only weights.
• Zero-padded step in the name makes lexical order age order.
• PyTorch DCP: every rank writes its shards in parallel (at least one file per rank); load-time resharding allows a different cluster topology.
• CRIU needs privileges and refuses some resources (devices, tasks with a debugger attached; see its "What cannot be checkpointed" page).

Pitfalls

• Torn checkpoint: in-place write or rename before fsync; only checksum plus generations survive it.
• Missing RNG, data position or optimizer state: the run resumes but diverges (the code asserts equality).
• Saving mid-step captures an inconsistent cut.
• Uncoordinated checkpoints of communicating processes can roll back repeatedly (Elnozahy et al. survey).
• Non-serialisable state: GPU contexts, open sockets, wall-clock time, PIDs. Re-create on restore.
• Interval too short saturates storage; too long loses hours. Re-estimate M from real failures.
• Deleting the old generation before the new one is synced.

Variants and alternatives

In production

• Redis RDB: a forked child writes a temporary file and replaces the old one.
• CRIU in Docker, Podman, LXC/Incus and Kubernetes; DMTCP in HPC (MPI, SLURM).
• PyTorch Distributed Checkpoint and Orbax for training state.
• Android: the OS may destroy a backgrounded app process, so apps save UI state for relaunch (mobile-background-execution).
• Emulator and game save states, database snapshots, long scientific pipelines.

Implementations

Sources

• J. W. Young, A first order approximation to the optimum checkpoint interval, Communications of the ACM 17(9), 1974. paper
• J. T. Daly, A higher order estimate of the optimum checkpoint interval for restart dumps, Future Generation Computer Systems 22(3), 2006. paper
• E. N. Elnozahy, L. Alvisi, Y.-M. Wang, D. B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys 34(3), 2002. paper
• K. M. Chandy, L. Lamport, Distributed snapshots, ACM TOCS 3(1), 1985. paper
• CRIU docs: Checkpoint/Restore, Incremental dumps · DMTCP: project page
• Redis persistence · PyTorch Distributed Checkpoint · Android: Save UI states