Concepts / State, data structures and algorithms inside objects / Snapshots and versioning

Snapshots and versioning

Keeping history cheaply: copies, diffs and persistent structures.

Low-level design conceptState, data structures and algorithms inside objects2 Nov 2026

01The intuition

The problem it solves

A drawing app has an undo button. The first version keeps history by copying the entire canvas, a list of 10,000 shapes, before every change.

import copy

class Canvas:
    def __init__(self) -> None:
        self.shapes: list[dict] = []
        self.history: list[list[dict]] = []

    def add(self, shape: dict) -> None:
        self.history.append(copy.deepcopy(self.shapes))   # whole copy, every time
        self.shapes.append(shape)

    def undo(self) -> None:
        self.shapes = self.history.pop()

Count the cost: after 1,000 edits on a 10,000-shape canvas the history holds 10 million shape copies, and each edit paid a 10,000-element copy to add one shape. The same shape of problem appears in a document with versions, a database with transactions, and a map that must answer "what was the value at time t". History is needed; copying everything is not.

Build it one piece at a time

Step one: record the change, not the state. An undo log stores what was done so it can be reversed; for add, that is "remove the last shape". Memory per edit becomes constant.

class Canvas:
    def __init__(self) -> None:
        self.shapes: list[dict] = []
        self.undo_log: list[tuple[str, dict]] = []

    def add(self, shape: dict) -> None:
        self.shapes.append(shape)
        self.undo_log.append(("add", shape))

    def undo(self) -> None:
        op, shape = self.undo_log.pop()
        if op == "add":
            self.shapes.remove(shape)

Step two: a log answers undo but not "show me version 37". Give every change a version number and keep, per key, a list of (version, value) pairs. Reading at a version is a binary search for the last pair at or before it. This is what a time-based key-value store is.

import bisect

class VersionedMap:
    def __init__(self) -> None:
        self.version = 0
        self.hist: dict[str, list[tuple[int, object]]] = {}

    def put(self, key: str, value: object) -> int:
        self.version += 1
        self.hist.setdefault(key, []).append((self.version, value))
        return self.version

    def get(self, key: str, at: int | None = None) -> object:
        pairs = self.hist.get(key, [])
        if at is None:
            at = self.version
        i = bisect.bisect_right(pairs, (at, chr(0x10FFFF))) - 1
        if i < 0:
            raise KeyError(key)
        return pairs[i][1]

Step three: a snapshot that is cheap to take and safe to read while writes continue. Copy-on-write does it: a snapshot is just the current version number, and a writer never modifies an old pair, it appends a new one. Readers holding version 37 see exactly the state at 37 no matter what happens later. For whole structures, the same idea becomes a persistent tree where a write copies only the path from root to the changed node.

class VersionedMap(VersionedMap):   # continued
    def snapshot(self) -> int:
        return self.version            # O(1): nothing is copied

    def rollback(self, to: int) -> None:
        for key, pairs in self.hist.items():
            while pairs and pairs[-1][0] > to:
                pairs.pop()
        self.version = to

History for one key after three puts, and what three reads return:

Callhist["colour"]version
put(colour, red)[(1, red)]1
put(size, 3)[(1, red)]2
put(colour, blue)[(1, red), (3, blue)]3
get(colour, at=2)red (last pair at or before 2)
get(colour)blue
get(colour, at=0)KeyError

Why it works

The invariant is that each key's list is sorted by version and that a version, once assigned, is never rewritten. Sorted-by-construction is what makes the binary search valid, and never-rewritten is what makes a snapshot free: anyone holding version v can be sure that the pairs at or below v are permanent. Rollback is the one operation that breaks the second half, which is why it is a separate, explicit method rather than something a put can do.

Where it breaks: unbounded growth. A key written a million times keeps a million pairs, so a real system compacts history older than the oldest live snapshot. The other trap is the sentinel in the bisect: searching for (at, something larger than any value) relies on values being comparable, so a production version searches a separate list of versions.

full copies: n edits × s shapes memory. Log or versions: n entries. Snapshot: O(1) with copy-on-write, O(s) with a deep copy

The trade-off you must say out loud

An undo log is smallest but only walks backwards; versioned values answer any point in time at the cost of a binary search; persistent structures give O(1) snapshots of whole trees at the cost of path copying on every write. Say which question the problem actually asks (undo, read-at-time, or isolated snapshot) and pick the cheapest one that answers it. The follow-up that usually comes next is garbage: how old versions are dropped, and who decides that nobody still needs them.

Where it shows up in the 100 Google problems

02Used in these problems