Copy-on-Write Snapshots for Lock-Free Fence Reads

The read path of a geofence evaluator runs 25,000 times a second and the write path runs forty. Any synchronisation that charges the read path for the write path’s existence is paying the wrong side: a reader-writer lock costs 41 ns per acquisition uncontended, which is 2.7% of a 1.5 µs lookup, and several microseconds when a writer holds it — long enough that a fence edit becomes visible in the evaluation latency histogram. Copy-on-write moves the entire cost onto the writer. This page sits under async index updates without locking within Spatial Indexing for Real-Time Checks.

Concept and specification #

The structure is one immutable snapshot object referenced by one mutable pointer. Readers dereference the pointer once, work entirely against the object they obtained, and never synchronise. A writer builds a new snapshot incorporating its changes and publishes it by assigning the pointer, which in CPython is a single bytecode and therefore atomic with respect to other threads.

Two properties make this correct without any lock. Publication is atomic, so no reader ever observes a partially built snapshot. And readers hold a strong reference for the duration of their work, so the old snapshot survives exactly as long as someone is using it and is collected when the last reader finishes — reference counting doing the job that epoch-based reclamation does in languages without it.

The last row is the property most easily overlooked. Fine-grained locking is cheap per node and does not give a reader a consistent view of the whole index: between descending into one subtree and reading the next, a writer can change both, and the query can miss a fence that was present throughout. A snapshot gives point-in-time consistency for free, which for a containment query — a negative assertion over the whole fence set — is not a nicety.

The cost is memory. A naive implementation copies the entire index per write, doubling peak memory. Structural sharing fixes this: only the nodes on the path from the root to the changed leaf are rebuilt, and every other subtree is shared by reference between the old and new snapshots.

$$\text{nodes rebuilt per edit}=O({\log }_{B}n)\text{against}O(n)\text{ for a full copy}$$

At $n=1.2$ M and a branching factor of 16, that is roughly five nodes per edit rather than 1.2 million — the difference between a technique that is theoretically nice and one that is deployable.

Step-by-step implementation #

1. Make the snapshot genuinely immutable. Anything a reader can mutate destroys the guarantee. Freeze the geometry arrays, use tuples rather than lists for node children, and never expose a mutable view.

from __future__ import annotations
from dataclasses import dataclass

@dataclass(frozen=True, slots=True)
class Node:
    mbr: tuple[float, float, float, float]
    children: tuple["Node", ...] = ()
    entries: tuple[tuple[str, tuple[float, float, float, float]], ...] = ()

@dataclass(frozen=True, slots=True)
class Snapshot:
    root: Node
    version: int
    watermark_ns: int
    count: int

class FenceIndex:
    """One mutable reference to an immutable snapshot. Readers never lock."""

    __slots__ = ("_snapshot",)

    def __init__(self, snapshot: Snapshot) -> None:
        self._snapshot = snapshot

    def read(self) -> Snapshot:
        return self._snapshot          # one atomic load; hold it for the query

    def publish(self, snapshot: Snapshot) -> None:
        self._snapshot = snapshot      # one atomic store; readers see old or new

2. Read the reference exactly once per query. Re-reading mid-query reintroduces the inconsistency the snapshot exists to prevent — the second read can see a newer snapshot and the query’s two halves then describe different worlds.

def evaluate(index: FenceIndex, x: float, y: float) -> list[str]:
    snap = index.read()                # ONE read; everything below uses `snap`
    hits = []
    for fence_id, mbr in _descend(snap.root, x, y):
        if _exact_contains(fence_id, x, y):
            hits.append(fence_id)
    return hits

3. Rebuild only the changed path. A writer descends to the affected leaf, rebuilds it, and rebuilds each ancestor with the new child substituted — every sibling subtree is shared by reference.

def with_entry(node: Node, path: list[int], leaf: Node) -> Node:
    """Rebuild the spine to `leaf`, sharing every untouched subtree."""
    if not path:
        return leaf
    i, rest = path[0], path[1:]
    child = with_entry(node.children[i], rest, leaf)
    kids = node.children[:i] + (child,) + node.children[i + 1:]
    return Node(mbr=_union(k.mbr for k in kids), children=kids)

4. Batch writes. Publishing per edit means one spine rebuild per edit and a version churn readers pay for in cache locality. Accumulate edits for a short window — 50–200 ms — and publish once, which at 40 edits/sec means one publication per batch of about eight.

5. Keep the write off the event loop. Building a snapshot is pure CPU and can take milliseconds for a large batch. Build it in a thread — the work releases the interpreter lock inside the geometry library — and publish from the loop, following the offload rules in async Python execution patterns for spatial math.

6. Bound the number of live snapshots. A long-running query holds an old snapshot alive; a leaked reference holds it forever. Export the count of distinct live versions and alert above a small number — it is the only symptom of a reference leak before memory growth becomes obvious.

Benchmark and verification #

Measured at 25k reads/sec and 40 writes/sec against 1.2M polygons:

The read P99 column is the result that matters: the lock’s tail is 27× its median because a reader that arrives while a writer holds the lock waits for the whole write, while copy-on-write’s tail is 1.3× its median because nothing ever waits. The fine-grained row shows the trade people expect to be free — a better tail than the coarse lock, at the cost of the consistency guarantee, which for containment queries is not a trade worth making.

Structural sharing is what makes the technique practical: 1.4 ms per write against 890 ms for a full copy, and 7.1 GB peak against 13.4 GB. The remaining 0.3 GB over the lock’s steady state is the transient double-referencing of rebuilt spines, and it is bounded by batch size rather than by index size.

Verify consistency with a concurrent property test: run readers issuing queries whose expected answers are known while a writer applies and reverts a fence in a loop, and assert every reader’s result set matches either the pre-edit or the post-edit expectation and never a mixture. That test fails immediately against fine-grained locking and passes against a correct snapshot implementation, which is exactly the discrimination it exists to make.

Failure modes and edge cases #

The mutable-object case is subtle enough to name precisely. A Snapshot that is frozen but whose leaf entries hold a NumPy array of coordinates is not immutable, because a writer holding that array can modify it in place and the change is visible to every reader already inside a query. Either copy the array when it changes — it is one leaf’s worth — or mark it read-only with arr.setflags(write=False), which makes the violation an exception rather than a silent corruption.

One structural note about where this sits. Copy-on-write publication is the mechanism the warm-start hydration path uses to promote a caught-up index, and the mechanism the fence-edit path uses for ordinary updates. Having one publication primitive for both is worth insisting on: a system with two ways to make a new index visible has two sets of consistency bugs, and the second is always the one nobody tested.

Related #

• Async Index Updates Without Locking — the parent topic and the wider mutation-boundary model.
• Thread-Safe Spatial Index Updates in Python — what the interpreter does and does not guarantee about the atomic store.
• Incremental Index Hydration from Change Streams — the other writer that publishes through this primitive.