Validating Index Integrity After Restore

The readiness rule in spatial index persistence and warm start gates traffic on the loaded fence count matching the authoritative one. That is the right first check and a weak last one: a count is a single scalar, and every corruption class that preserves cardinality passes it. A snapshot whose entry table is intact but whose node MBRs are stale has exactly the right number of fences and returns candidates for the wrong region. Over one quarter, 0.04% of restores across a fleet carried a correct count with a structurally wrong tree. This page sits within Spatial Indexing for Real-Time Checks and covers what to check beyond the count.

Concept and specification #

Four checks escalate in cost and in what they can prove. Each is worth running; together they cover every corruption class observed in practice.

The content digest is a rolling hash over (fence_id, geometry_hash) pairs in sorted order, compared against the same digest computed by the source of truth. It proves the set is right without transferring the geometry — the source maintains it incrementally alongside the count, so the check is one small comparison at startup rather than a scan.

$$D=\underset{f\in F}{⨁}H({\text{id}}_f\parallel H({\text{geom}}_f))$$

An XOR-combining digest is order-independent, which is what makes it maintainable incrementally: adding a fence XORs its term in, removing one XORs it out, and no sort is required at either end. Its weakness is that it cannot detect a duplicated pair — XOR of a term with itself is zero — so pair it with the cardinality check, which does.

The structural invariants are the ones a count and a digest both miss, and they are cheap to state:

• every internal node’s MBR contains the union of its children’s MBRs;
• every entry is reachable from the root exactly once;
• no node exceeds the maximum fan-out or, except the root, falls below the minimum;
• every geometry offset lands inside the arena and its vertex count does not run past the end.

Step-by-step implementation #

1. Run the checks in escalating order and stop at the first failure. A truncated file fails cardinality in a millisecond; there is no reason to hash 2.9 GB to discover it.

2. Walk the tree once, checking every invariant in the same pass.

from __future__ import annotations
from dataclasses import dataclass

@dataclass(slots=True)
class Issue:
    kind: str
    detail: str

def check_structure(index, max_fanout: int = 16, min_fanout: int = 4,
                    arena_bytes: int = 0) -> list[Issue]:
    """One traversal, every invariant. Returns [] for a sound tree."""
    issues: list[Issue] = []
    seen_entries: set[int] = set()
    stack = [(index.root, 0)]
    visited_nodes: set[int] = set()
    while stack:
        node, depth = stack.pop()
        if node.id in visited_nodes:
            issues.append(Issue("cycle", f"node {node.id} reached twice"))
            continue
        visited_nodes.add(node.id)
        if depth > 64:
            issues.append(Issue("depth", f"node {node.id} below depth 64"))
            continue
        if node.is_leaf:
            for e in node.entries:
                if e.entry_id in seen_entries:
                    issues.append(Issue("duplicate", f"entry {e.entry_id} twice"))
                seen_entries.add(e.entry_id)
                if not _contains(node.mbr, e.mbr):
                    issues.append(Issue("mbr", f"entry {e.entry_id} outside its leaf"))
                if arena_bytes and e.geom_offset + e.geom_bytes > arena_bytes:
                    issues.append(Issue("arena", f"entry {e.entry_id} runs past the arena"))
        else:
            n = len(node.children)
            if n > max_fanout or (depth and n < min_fanout):
                issues.append(Issue("fanout", f"node {node.id} has {n} children"))
            for c in node.children:
                if not _contains(node.mbr, c.mbr):
                    issues.append(Issue("mbr", f"child {c.id} outside parent {node.id}"))
                stack.append((c, depth + 1))
    if len(seen_entries) != index.expected_entries:
        issues.append(Issue("reachability",
                            f"{len(seen_entries)} reachable of {index.expected_entries}"))
    return issues

def _contains(outer, inner) -> bool:
    return (outer[0] <= inner[0] and outer[1] <= inner[1]
            and outer[2] >= inner[2] and outer[3] >= inner[3])

3. Probe with real queries drawn from real traffic. A recorded sample of a few thousand production query points, with their expected results captured from a known-good build, is a stronger end-to-end assertion than any structural check — it exercises the index, the geometry arena and the exact-containment kernel together.

4. Stratify the probe sample geographically. A uniform random sample over the fleet’s traffic distribution concentrates in the busy regions and never touches the sparse ones, where a corrupt subtree can hide indefinitely. Sample per index region rather than per query.

5. Fail closed. Any issue means the node does not become ready and falls back to a rebuild. A validation that logs a warning and serves anyway is a validation nobody will act on.

6. Export the check durations. They are a free early warning: a structural check whose duration is growing means the tree is deepening, which usually indicates the incremental hydration path is degrading the structure and a full rebuild is due.

Benchmark and verification #

Measured across 4,100 restores over one quarter, with deliberately corrupted snapshots injected in staging:

The whole suite costs 300 ms on a restore that takes 2.4 s — 12% of startup for complete coverage of the observed corruption classes. Against the alternative, which is a node serving wrong answers with healthy metrics until someone notices in the trigger stream, that is not a close trade.

The 39% that cardinality misses is worth breaking down, because it names what the later checks are for: 27% were stale entries (the count was right, the contents were from an older snapshot), 11.6% were structural (MBRs not covering their children after a partial hydration), and 0.4% were arena offsets pointing past the end of the geometry region, which produces garbage coordinates rather than an error.

Verify the validator itself by mutating a known-good snapshot in each of the four ways and asserting each is caught by the expected check. A validator that has never rejected anything is indistinguishable from one that always returns success, and this is the test that tells them apart.

Failure modes and edge cases #

The fifth row is a performance trap that leads teams to disable the digest. Computing the expected digest by scanning the source of truth at startup costs as much as the fetch phase of a full rebuild, which erases the point of a snapshot. Maintaining it incrementally — the source XORs each fence’s term in or out as part of the same transaction that edits the fence — makes the expected value a single row read, and it is the same trick that makes the authoritative count cheap.

One caveat on the structural checks. They validate that the tree is internally consistent, not that it is good: a tree with correct MBRs and terrible overlap passes every invariant while performing poorly, which is a quality question rather than an integrity one and belongs to the analysis in quadtree vs R-tree performance analysis. It is worth exporting the tree’s overlap ratio alongside the integrity result for exactly this reason — a hydration path that keeps the tree sound while steadily degrading its quality is a real and slow-moving failure, and the number that reveals it is free once the traversal is already happening.

Related #

• Spatial Index Persistence & Warm Start — the parent topic and the readiness gate these checks feed.
• Incremental Index Hydration from Change Streams — the path most likely to produce a structurally degraded tree.
• Quadtree vs R-Tree Performance Analysis — the quality metrics that sit alongside these integrity ones.