Snapshots, backup and restore

intermediateCommon atAnthropicOpenAIStripeGoogleRead firstVersioning and point-in-time queriesHash mapsPractise in the Sandbox →

A snapshot freezes the current state so later writes can’t change it. Three designs: a full copy (O(n) per snapshot, trivially correct), copy-on-write (share everything, copy a piece only when it’s about to be written), and version stamps (snapshot = bump a counter, O(1); reads at an old snapshot binary-search each item’s history). Pick by asking how often you snapshot, how much changes between snapshots, and how often you read or restore old ones.

The idea in plain words

Photocopying a whole binder before every edit works, but it’s slow and fills the shelf. Most edits touch one page.

• Full copy: photocopy the binder. Simple and independent: the copy never needs the original again.
• Copy-on-write (COW): the snapshot is a second table of contents pointing at the same pages. Nothing is copied yet. When you’re about to scribble on a page that a snapshot also points at, you copy just that page first and point your own table of contents at the copy.
• Version stamps: write the snapshot number on every change instead (“as of snapshot 3, this cell is 7”). Taking a snapshot is just “start writing snapshot 4 now”. Reading snapshot 3 means finding, for each cell, its last change stamped 3 or earlier. That’s versioning with a counter instead of a clock.

Real systems use all three. fork() in Unix and file systems like ZFS and Btrfs use copy-on-write. Databases use version stamps (MVCC). Backups to another machine are full copies, often followed by incremental ones.

See it

Write to a few cells, take a snapshot, write again. Watch the costs split: full copy pays at snapshot time, copy-on-write pays on the first write to each shared page, version stamps pay a little on every write and more on restore. Take several snapshots with few writes between them, then many writes with few snapshots, and compare the memory bars.

Three ways to snapshot the same 16 cells

sandbox

cell write cell 5write randomsnapshot↺

3074

1852

9630

7418

live data: 16 cells, grouped into 4 pages

full copy0 snaps

no snapshots yet

copy-on-write pages4 pages stored

live3074p01852p19630p27418p3

version-stamped cellsepoch 0

each cell has one version (epoch 0). Snapshot, then write.

cells stored (memory)

full copy

16

copy-on-write

20

version-stamped

16

work so far: snapshot / write / restore

full copy0 / 0 / 0copy-on-write0 / 0 / 0version-stamped0 / 0 / 0

Units: cells or pointers copied, plus search probes. COW memory counts 4 cells per stored page plus 4 pointers per table.

page shared by 2+ tablespage owned by one tablepage just cloned or written

Take a snapshot, then write to a few cells. Watch which strategy pays, and when.

When to reach for it

The problem says…	Likely design
“back up the data; restore replaces everything” (rare backups)	Full copy. Correct and simple. Deep-copy the nested parts.
“snapshot returns a version number; read as of version v”	Version stamps per item + binary search.
“taking a snapshot must not copy the data”	Version stamps, or copy-on-write. Not a full copy.
“memory proportional to the number of changes”	Version stamps: one entry per change, not per item per snapshot.
“nested transactions that can be rolled back”	A stack of change logs (an undo log per level) rather than a copy per level. See undo / redo.
“restore keeps the TTL that was left at backup time”	Store remaining time (deadline − backup time), re-add it at restore time. See TTL.

How it works

1. Decide what a snapshot must answer: a full restore, reads of single items at an old snapshot, or both. Restores favor copies; old reads favor version stamps.
2. Full copy: deep-copy everything that is mutable. A shallow copy of a map of lists shares the lists, so later writes leak into the “backup”.
3. Copy-on-write: split data into pieces (pages, nodes, sub-maps). A snapshot copies the pointers and marks every piece shared. Before writing a shared piece, clone it and repoint the live table.
4. Version stamps: keep a global epoch counter. Every write records (epoch, value) on that item (replacing the entry if it already has one for this epoch). snapshot() returns the epoch and increments it. A read at snapshot s is a floor search for the last entry with epoch ≤ s.
5. Restore from any of them by producing the old state, then decide what happens to newer snapshots: kept (a branch), or discarded (time travel).

Step 3, on an int array split into four-cell pages:

Python

paged_array.py

PAGE = 4  # cells per page


class PagedArray:
    """An int array split into pages. Snapshots share pages until someone writes."""

    def __init__(self, n: int) -> None:
        self.pages: list[list[int]] = [[0] * PAGE for _ in range((n + PAGE - 1) // PAGE)]
        self.shared: list[bool] = [False] * len(self.pages)  # does a snapshot also hold page p?
        self.snaps: list[list[list[int]]] = []

    def snapshot(self) -> int:
        self.snaps.append(list(self.pages))  # 1. copy the page *pointers* only: O(n / PAGE)
        self.shared = [True] * len(self.pages)  # 2. every live page is now shared
        return len(self.snaps) - 1

    def set(self, i: int, v: int) -> None:
        p = i // PAGE
        if self.shared[p]:  # 3. copy-on-write: clone just this page, once
            self.pages[p] = list(self.pages[p])
            self.shared[p] = False
        self.pages[p][i % PAGE] = v  # 4. now the write can't leak into a snapshot

    def get(self, i: int, snap: int | None = None) -> int:
        pages = self.pages if snap is None else self.snaps[snap]
        return pages[i // PAGE][i % PAGE]


if __name__ == "__main__":
    a = PagedArray(16)
    a.set(5, 50)
    s0 = a.snapshot()
    a.set(5, 51)  # clones page 1 only
    a.set(6, 60)  # page 1 is private now: no second clone
    assert a.get(5) == 51 and a.get(5, s0) == 50 and a.get(6, s0) == 0
    assert a.pages[0] is a.snaps[s0][0]  # untouched pages are still shared
    assert a.pages[1] is not a.snaps[s0][1]
    print("ok")

TypeScript

paged_array.ts

import assert from "node:assert/strict";

const PAGE = 4; // cells per page

/** An int array split into pages. Snapshots share pages until someone writes. */
class PagedArray {
  pages: number[][];
  private shared: boolean[]; // does a snapshot also hold page p?
  readonly snaps: number[][][] = [];

  constructor(n: number) {
    this.pages = Array.from({ length: Math.ceil(n / PAGE) }, () => new Array<number>(PAGE).fill(0));
    this.shared = this.pages.map(() => false);
  }

  snapshot(): number {
    this.snaps.push([...this.pages]); // 1. copy the page *pointers* only: O(n / PAGE)
    this.shared.fill(true); // 2. every live page is now shared
    return this.snaps.length - 1;
  }

  set(i: number, v: number): void {
    const p = Math.floor(i / PAGE);
    if (this.shared[p]) { // 3. copy-on-write: clone just this page, once
      this.pages[p] = [...this.pages[p]];
      this.shared[p] = false;
    }
    this.pages[p][i % PAGE] = v; // 4. now the write can't leak into a snapshot
  }

  get(i: number, snap?: number): number {
    const pages = snap === undefined ? this.pages : this.snaps[snap];
    return pages[Math.floor(i / PAGE)][i % PAGE];
  }
}

const a = new PagedArray(16);
a.set(5, 50);
const s0 = a.snapshot();
a.set(5, 51); // clones page 1 only
a.set(6, 60); // page 1 is private now: no second clone
assert.equal(a.get(5), 51);
assert.equal(a.get(5, s0), 50);
assert.equal(a.get(6, s0), 0);
assert.equal(a.pages[0], a.snaps[s0][0]); // untouched pages are still shared (same object)
assert.notEqual(a.pages[1], a.snaps[s0][1]);
console.log("ok");

C#

paged_array.cs

var a = new PagedArray(16);
a.Set(5, 50);
int s0 = a.Snapshot();
a.Set(5, 51); // clones page 1 only
a.Set(6, 60); // page 1 is private now: no second clone
if (a.Get(5) != 51 || a.Get(5, s0) != 50 || a.Get(6, s0) != 0) throw new Exception("snapshot leaked");
if (!a.SharesPageWith(s0, 0) || a.SharesPageWith(s0, 1)) throw new Exception("sharing is wrong");
Console.WriteLine("ok");

// An int array split into pages. Snapshots share pages until someone writes.
class PagedArray
{
    const int Page = 4; // cells per page
    readonly int[][] pages;
    readonly bool[] shared; // does a snapshot also hold page p?
    readonly List<int[][]> snaps = [];

    public PagedArray(int n)
    {
        pages = new int[(n + Page - 1) / Page][];
        for (int p = 0; p < pages.Length; p++) pages[p] = new int[Page];
        shared = new bool[pages.Length];
    }

    public int Snapshot()
    {
        snaps.Add((int[][])pages.Clone()); // 1. copy the page *pointers* only: O(n / Page)
        Array.Fill(shared, true);           // 2. every live page is now shared
        return snaps.Count - 1;
    }

    public void Set(int i, int v)
    {
        int p = i / Page;
        if (shared[p]) { pages[p] = (int[])pages[p].Clone(); shared[p] = false; } // 3. clone once
        pages[p][i % Page] = v; // 4. now the write can't leak into a snapshot
    }

    public int Get(int i, int? snap = null) => (snap is int s ? snaps[s] : pages)[i / Page][i % Page];
    public bool SharesPageWith(int snap, int page) => ReferenceEquals(pages[page], snaps[snap][page]);
}

And step 2’s trap, which catches people in every language:

Python

shallow_vs_deep.py

import copy

# A playlist library: name -> list of track ids.
library: dict[str, list[int]] = {"focus": [1, 2], "run": [3]}

shallow = dict(library)  # 1. copies the outer dict only
deep = copy.deepcopy(library)  # 2. copies every nested list too
manual = {k: list(v) for k, v in library.items()}  # 3. one level deeper by hand (enough here)

library["focus"].append(9)  # mutate an inner list
library["new"] = []  # add a top-level key

if __name__ == "__main__":
    assert shallow["focus"] == [1, 2, 9]  # leaked: same inner list object
    assert "new" not in shallow  # but top-level changes did not leak
    assert deep["focus"] == [1, 2] and manual["focus"] == [1, 2]
    print("ok")

TypeScript

shallow_vs_deep.ts

import assert from "node:assert/strict";

// A playlist library: name -> list of track ids.
const library = new Map<string, number[]>([["focus", [1, 2]], ["run", [3]]]);

const shallow = new Map(library); // 1. copies the outer map only
const deep = structuredClone(library); // 2. copies every nested array too (Maps supported)
const manual = new Map([...library].map(([k, v]) => [k, [...v]] as const)); // 3. one level by hand

library.get("focus")!.push(9); // mutate an inner array
library.set("new", []); // add a top-level key

assert.deepEqual(shallow.get("focus"), [1, 2, 9]); // leaked: same inner array object
assert.equal(shallow.has("new"), false); // but top-level changes did not leak
assert.deepEqual(deep.get("focus"), [1, 2]);
assert.deepEqual(manual.get("focus"), [1, 2]);
console.log("ok");

C#

shallow_vs_deep.cs

// A playlist library: name -> list of track ids.
var library = new Dictionary<string, List<int>> { ["focus"] = [1, 2], ["run"] = [3] };

var shallow = new Dictionary<string, List<int>>(library); // 1. copies the outer dictionary only
var manual = library.ToDictionary(kv => kv.Key, kv => new List<int>(kv.Value)); // 2. copy each list
// 3. .NET has no general deep-copy; copy each nesting level yourself, or use immutable types.

library["focus"].Add(9); // mutate an inner list
library["new"] = [];    // add a top-level key

if (!shallow["focus"].SequenceEqual([1, 2, 9])) throw new Exception("expected the leak");
if (shallow.ContainsKey("new")) throw new Exception("top-level change should not leak");
if (!manual["focus"].SequenceEqual([1, 2])) throw new Exception("manual copy should be isolated");
Console.WriteLine("ok");

Immutable data makes snapshots free

If values are never mutated in place (strings, tuples, frozen records, persistent collections), then a “snapshot” can simply keep a reference to the current value. Clojure’s and Immutable.js’s persistent maps, and .NET’s System.Collections.Immutable, are copy-on-write trees: an update copies only the O(log n) nodes on the path to the change and shares the rest.

What it costs

With n items, s snapshots, c changed items between snapshots, and page size B:

	Snapshot	Write	Read old snapshot	Restore	Memory
Full copy	O(n)	O(1)	O(1)	O(n)	O(n · s)
Copy-on-write pages	O(n / B) pointers	O(B) on first write per shared page, else O(1)	O(1)	O(n / B)	O(n + pages touched · B)
Persistent tree	O(1)	O(log n)	O(log n)	O(1)	O(n + changes · log n)
Version stamps	O(1)	O(1) amortized	O(log h) per item (h = its history)	O(n log h)	O(n + total changes)

The pattern: you either pay when you snapshot (full copy), when you first write after one (copy-on-write), or when you read the past (version stamps). If snapshots are frequent and old reads rare, stamps win. If restores are frequent and the data is small, full copies win on simplicity.

Variations you’ll meet

• Incremental backup. Store only what changed since the last backup, plus a pointer to it. Restore = last full backup + replay of increments.
• Snapshot isolation. A database transaction reads from a snapshot taken at its start, while others keep writing. That’s version stamps (MVCC) at scale.
• Redis BGSAVE. The server forks; the child writes the dataset to disk while the parent keeps serving. The operating system’s copy-on-write pages make the fork nearly instant.
• Checkpoint + log. Periodically write a full snapshot to disk, and log every change since. Recovery = load checkpoint, replay log. Most databases and stream processors do this.
• Per-entity backups. “Back up this user’s files” is a full copy of one slice of the data, keyed by owner. Mind what happens on restore if names now collide with other owners’ data.

Pitfalls

• Shallow copies. The single most common bug. Copying a map of lists, or a list of objects, shares the inner pieces.
• Snapshotting derived indexes inconsistently. If you keep a secondary index or a counter, restore must rebuild or restore it too. Otherwise the index points at data that no longer exists.
• Time-relative data. A backup of “expires in 30 s” restored an hour later is wrong either way unless you define it. Store absolute deadlines, or remaining time, deliberately.
• Version stamp off-by-one. Is a write after snapshot() returns 3 part of snapshot 3 or 4? Write the rule down: “snapshot() returns the current epoch, then increments it; writes are stamped with the current epoch.”
• Unbounded history. Every strategy needs a way to release old snapshots: drop the snapshot table (COW), drop backups, or compact versions older than the oldest live snapshot.

In the interview

• Ask: “How often are snapshots taken compared to writes? Do we read old snapshots, restore them, or both? Can old snapshots be deleted? Is it the whole store or one user’s slice?”
• Start simple out loud: “A deep copy per snapshot is O(n) and obviously correct. If snapshots are frequent, I’d switch to version stamps so a snapshot is O(1) and memory grows with changes, not with size.”
• Name the invariant: “Once taken, a snapshot never changes: no write after it may be visible through it.” Then test exactly that: snapshot, write, read the snapshot.
• Expect follow-ups: memory limits, deleting old snapshots, restoring with TTLs, and “what if restore must be atomic while other writes are happening?”

Check yourself

Check yourself

pick one

You take 1,000 snapshots of a 1,000,000-item store, with about 10 items changed between snapshots. Roughly how much memory does each strategy use, in items stored?

AFull copy ~1,000,000; version stamps ~1,000,000,000BFull copy ~1,000,000,000; version stamps ~1,010,000CBoth ~1,010,000DBoth ~1,000,000,000

Check yourself

pick one

With copy-on-write pages, you take a snapshot and then write to the same page 50 times. How many times is that page copied?

A0B1C50DOnce per snapshot that exists

Check yourself

pick one

backup = dict(store) where store maps user → list of file names. A user then deletes a file from their list. What does the backup show?

AThe file is still there: the backup is a copyBThe file is gone too: the inner list is sharedCIt depends on the Python version

Practice on your own

These are classic exercises, not gym questions:

• An array with set(i, v), snap() → id and get(i, snap_id), where snap() is O(1).
• A persistent (immutable) binary search tree where insert returns a new root and shares untouched subtrees. Count nodes copied per insert.
• A document store with checkpoint() and rollback() implemented with an undo log instead of copies. Compare memory with full copies.
• An incremental backup tool: full backup on day 1, then daily diffs. Implement restore to any day.

Go deeper

• Python copy module docs: shallow vs deep copies and __deepcopy__.
• MDN, structuredClone(): what JS deep copy supports (Maps, Sets, Dates; not functions or class prototypes).
• Chris Okasaki, Purely Functional Data Structures (1998): path copying and persistent structures.
• Redis docs, “Persistence”: RDB snapshots via fork and copy-on-write, plus the append-only log.

Related

Versioning and point-in-time queriesVersion stamps are per-item histories.

Undo / redo and command patternMementos are snapshots; commands are deltas.

Memory efficiencyWhat the copies really cost.

Secondary indexesDerived data that must be restored too.