Incremental Index Hydration from Change Streams

A snapshot is a photograph of a moving subject. Between the moment it was taken and the moment a node finishes loading it, fences have been created, edited and deleted, and the node’s index is wrong by exactly those edits. Closing that gap is the catch-up phase, and it is the step that decides whether snapshot-based warm start is actually faster than rebuilding: at a naive 1,400 edits/sec, a one-hour-old snapshot takes 103 seconds to catch up, which is longer than the 94-second rebuild it was supposed to replace. This page sits under spatial index persistence and warm start within Spatial Indexing for Real-Time Checks.

Concept and specification #

Catch-up replays a change stream from the snapshot’s watermark to the current head. Three guarantees are required and they are not all free.

Per-fence ordering. Edits to one fence must be applied in the order they occurred, or a create-then-delete pair applied backwards leaves a deleted fence in the index forever. Ordering across fences is unnecessary, which is what allows the parallelism the throughput depends on — the same argument as the partition key choice makes for triggers, applied to state.

Idempotency. A change stream redelivers, so applying an edit twice must leave the same state as applying it once. An upsert keyed by fence id is naturally idempotent; a “translate this fence 5 m north” delta is not, and delta-encoded change streams are therefore unusable for hydration without a sequence check.

Completeness. The stream must be known to start at or before the watermark. A stream whose retention has expired past the watermark cannot close the gap at all, and the correct response is to abandon the snapshot and rebuild rather than to hydrate into a hole.

$$t_{\text{catchup}}=\frac{{\lambda }_{\text{edits}}\cdot A_{\text{snapshot}}}{r_{\text{apply}}},A_{\text{crossover}}=\frac{r_{\text{apply}}\cdot t_{\text{rebuild}}}{{\lambda }_{\text{edits}}}$$

The crossover age is the snapshot age past which rebuilding is faster, and it is the number the snapshot cadence should be set from. Raising $r_{\text{apply}}$ moves it out proportionally, which is why the throughput work below matters as much as the cadence.

Step-by-step implementation #

1. Coalesce before applying. A fence edited fifteen times during the snapshot’s age needs its final state applied once, not fifteen times. Collapsing the batch by fence id, keeping the last edit per fence, is the single largest win available and it is pure bookkeeping.

from __future__ import annotations
from dataclasses import dataclass

@dataclass(slots=True, frozen=True)
class Edit:
    fence_id: str
    seq: int            # per-fence monotonic sequence from the source
    op: str             # "upsert" | "delete"
    payload: bytes | None

def coalesce(batch: list[Edit]) -> list[Edit]:
    """Keep only the highest-sequence edit per fence. A fence edited fifteen
    times during the snapshot's age needs its final state applied once."""
    latest: dict[str, Edit] = {}
    for e in batch:
        prev = latest.get(e.fence_id)
        if prev is None or e.seq > prev.seq:
            latest[e.fence_id] = e
    return list(latest.values())

2. Apply as a bulk mutation, not as individual inserts. An R-tree that rebalances after every insert does $O(n\log n)$ of structural work for a batch that could be applied as one bulk update. Defer the rebalance to the end of the batch, following the bulk-load discipline in optimizing R-tree bulk loads for real-time ingestion.

3. Parallelise across fence-id ranges, never within one. Hashing fence ids into $k$ ranges and applying each range on its own worker preserves per-fence order for free while giving near-linear speedup — the index’s per-range subtrees do not interact until the final merge.

4. Track the watermark as the minimum across workers. With parallel application the node is caught up only to the slowest range. Publishing the maximum instead is the bug that lets a node declare readiness while one range is still behind.

def catchup_watermark(per_range: dict[int, int]) -> int:
    """Caught up to the SLOWEST range, never the fastest."""
    return min(per_range.values()) if per_range else 0

5. Verify the sequence is contiguous per fence. A gap means the stream lost an edit — retention expiry, a producer bug, a topic misconfiguration — and hydrating past a gap produces an index that is wrong in a way no later check detects. Abandon the snapshot and rebuild.

6. Apply against a shadow, promote atomically. Hydrating the live index means queries see a partially applied batch. Build the updated structure alongside and swap it in with the copy-on-write promotion described in async index updates without locking, so readers move from one consistent state to the next.

Benchmark and verification #

Measured hydrating a 60-second-old snapshot on a fleet taking 40 fence edits/sec, and a 60-minute-old one for comparison:

The coalescing column explains most of the improvement on the older snapshot: 62% of edits in an hour’s window are superseded by a later edit to the same fence, so applying them is pure waste. That figure is a property of how fences are edited — an operator adjusting a zone saves repeatedly — and it rises with snapshot age, which is why coalescing helps the stale case disproportionately.

The peak-memory column is the cost. Parallel hydration into a shadow structure holds the old index, the new one and the pending batches simultaneously, peaking 19% above steady state — well inside a typical container’s headroom, but worth sizing for, since being OOM-killed during hydration produces the crash loop described in the parent topic.

Verify with a three-way comparison: hydrate from a snapshot, rebuild from the source of truth, and assert the two indexes answer identically over a large sample of query points. That test catches ordering bugs, coalescing bugs and gap-handling bugs at once, and it is worth running in CI against a recorded change stream rather than only in staging.

Failure modes and edge cases #

The last row is the one that turns a warm start into a silent correctness failure if it is not checked. If the change stream’s retention is six hours and a node boots from a snapshot eight hours old, the stream simply has no records covering the first two hours, and a hydration loop that starts from “the earliest available offset” will happily replay what it can and declare success. Comparing the stream’s earliest available offset against the snapshot’s watermark before starting is two API calls and converts an undetectable wrong index into an ordinary rebuild.

One subtlety about coalescing is worth naming because it can be wrong in an audit context. Collapsing fifteen edits into one means the index never observes the intermediate states — which is correct for the index and wrong if anything downstream needs the history of a fence. Keep coalescing to the hydration path, where only the final state matters, and leave the change stream itself uncollapsed for whatever consumes it for audit purposes.

Related #

• Spatial Index Persistence & Warm Start — the parent topic and the crossover-age formula this optimises.
• Snapshotting R-Tree State for Fast Restarts — where the watermark this replay starts from is recorded.
• Validating Index Integrity After Restore — the check that confirms hydration produced the right index.