Snapshotting R-Tree State for Fast Restarts

The reason a rebuild takes ninety seconds is that it constructs 1.2 million Python objects from 1.2 million blobs of WKB. A snapshot that avoids the construction avoids nearly all of the ninety seconds; a snapshot that merely avoids the fetch saves thirty. This page sits under spatial index persistence and warm start within Spatial Indexing for Real-Time Checks, and it covers the file layout that makes a restore a memory map rather than a deserialisation, and the three safety mechanisms without which that layout is dangerous.

Concept and specification #

The file has four regions and the order matters, because a reader validates before it trusts:

Everything is offset-addressed rather than pointer-addressed, which is the property that makes the file mappable at any base address. A node’s children are byte offsets from the start of the node region; an entry’s geometry is a byte offset and a vertex count into the arena. Nothing in the file contains a machine address, so mmap at whatever address the kernel chooses is immediately usable.

The header carries the three safety mechanisms:

$$\text{trustworthy}⟺\text{magic ok};\wedge ;\text{version}=V_{\text{code}};\wedge ;\text{checksum ok}$$

The magic catches a wrong file. The version catches the dangerous case — a file written by a build whose node layout differed, which would otherwise be read as though it were the current layout, producing plausible garbage rather than an error. The checksum catches truncation and corruption, which matter because a snapshot is often written to object storage and downloaded.

Checksumming 2.9 GB costs about 1.1 s with a hardware-accelerated CRC32C, which is longer than the mmap itself. The workable compromise is to checksum the header, node and entry regions eagerly — 134 MB, 60 ms — and the geometry arena lazily, verifying each 2 MB block the first time it is faulted. That keeps startup fast while still catching corruption before it produces a wrong answer.

Step-by-step implementation #

1. Write the header last, and write the file atomically. A reader must never see a header that promises regions the writer has not finished. Write to a temporary path, fsync, write the header, fsync again, then rename — rename is atomic within a filesystem, so a reader sees either the old complete file or the new one.

from __future__ import annotations
import mmap, os, struct, zlib
from dataclasses import dataclass

MAGIC = b"RTGFENCE"
FORMAT_VERSION = 7          # bump on ANY layout change, without exception
HEADER = struct.Struct("<8sIIQQQQI")   # magic, version, page, n_nodes,
                                       # n_entries, arena_bytes, watermark, crc

@dataclass(slots=True, frozen=True)
class SnapshotHeader:
    version: int
    page_size: int
    n_nodes: int
    n_entries: int
    arena_bytes: int
    watermark_ns: int
    crc: int

def write_snapshot(path: str, nodes: bytes, entries: bytes, arena: bytes,
                   watermark_ns: int, page_size: int = 4096) -> None:
    tmp = path + ".tmp"
    crc = zlib.crc32(nodes)
    crc = zlib.crc32(entries, crc)
    with open(tmp, "wb") as fh:
        fh.write(b"\0" * HEADER.size)          # reserve, fill in last
        fh.write(nodes)
        fh.write(entries)
        fh.write(arena)
        fh.flush()
        os.fsync(fh.fileno())
        fh.seek(0)
        fh.write(HEADER.pack(MAGIC, FORMAT_VERSION, page_size, len(nodes),
                             len(entries), len(arena), watermark_ns, crc))
        fh.flush()
        os.fsync(fh.fileno())
    os.replace(tmp, path)                       # atomic within a filesystem

def open_snapshot(path: str) -> tuple[mmap.mmap, SnapshotHeader]:
    fh = open(path, "rb")
    raw = fh.read(HEADER.size)
    magic, ver, page, n_nodes, n_entries, arena, wm, crc = HEADER.unpack(raw)
    if magic != MAGIC:
        raise ValueError("not a fence snapshot")
    if ver != FORMAT_VERSION:
        raise ValueError(f"snapshot format {ver}, this build reads {FORMAT_VERSION}")
    mm = mmap.mmap(fh.fileno(), 0, access=mmap.ACCESS_READ)
    body = mm[HEADER.size:HEADER.size + n_nodes + n_entries]
    if zlib.crc32(body) != crc:
        mm.close()
        raise ValueError("snapshot checksum mismatch")
    return mm, SnapshotHeader(ver, page, n_nodes, n_entries, arena, wm, crc)

2. Bump the version on every layout change, mechanically. Not “when it seems significant” — a field widened from 32 to 64 bits, a reordered struct, a different coordinate encoding all invalidate every existing file. Derive the version from a hash of the struct definitions if the discipline is hard to maintain by hand.

3. Always have a rebuild fallback, and exercise it. Every failure path above raises, and the caller’s response must be to rebuild from the source of truth rather than to exit. A version stamp with no fallback turns a routine deploy into an outage.

4. Record the change-stream watermark in the header, written in the same atomic operation as the contents. A watermark stored separately can disagree with the file, and a snapshot claiming to include edits it does not is worse than one that claims less than it has.

5. Align regions to the page size. A node region starting mid-page means every node access faults a page shared with the header, and the arena’s lazy faulting behaviour becomes unpredictable. Pad each region to a page boundary; the waste is kilobytes.

6. Warm the internal nodes deliberately. madvise(MADV_WILLNEED) over the node region only — 46 MB of 2.9 GB — pulls the branch structure into memory without the leaves, cutting the post-ready P99 ramp from 140 ms to 9 ms as the parent topic measures.

Benchmark and verification #

Measured on 1.2M polygons, 96 vertices mean, on NVMe:

The last two rows separate two things that are easy to conflate. “Restore to first query” is when the process can answer at all; “restore to steady P99” is when it answers at production latency. Without the node warm, the index is queryable in 0.4 s but spends the next second and a half faulting branch pages under live traffic, so its P99 during that window is an order of magnitude high. The warm costs 60 ms and removes the ramp — a good trade, and one that only shows up if the metric is measured after readiness rather than at it.

Write time matters more than it first appears, because the snapshot cadence has to be frequent enough to keep catch-up short. At 6.4 s per full write, a 60 s cadence spends 11% of a core continuously, which is why incremental snapshots — writing only the pages that changed — are the usual production arrangement, with a full write on a slower schedule.

Verify with a deliberate corruption test in CI: truncate the file, flip a byte in the node region, and write a file with the version decremented. Each must raise and each must trigger a rebuild rather than a crash or, worse, a successful load. This test is the one that justifies the header, and a codebase without it will eventually ship a layout change that reads old snapshots as current ones.

Failure modes and edge cases #

The last row is the design constraint that everything else follows from, and it is easy to violate accidentally in a language with real pointers or in a serialisation library that preserves object identity. The test is simple: a file that can be mapped twice, at two addresses, in the same process, and produce identical query results from both mappings is offset-addressed; one that cannot, is not.

One operational caveat about mmap that surprises teams the first time: resident memory after a restore is small and grows as queries fault pages in, so a node that has just restored looks like it is leaking memory for its first few minutes. It is not — it is populating its working set — and the plateau is the working set rather than the file size, typically well under half of it because most fences are never queried in a given hour. Alert on the plateau, not on the growth.

Related #

• Spatial Index Persistence & Warm Start — the parent topic and the readiness rule that makes any restore safe.
• Incremental Index Hydration from Change Streams — replaying from the watermark this header records.
• Optimizing R-Tree Bulk Loads for Real-Time Ingestion — the packing step whose output this file stores.