Routing Spatial Queries by Bounding-Box Locality

Header-based routing answers “which domain”, and for many spatial requests that is not enough: a query bounded to a region should reach the replica nearest that region’s data, not whichever replica the load balancer picked. Bounding-box locality routing adds that second decision — resolve the extent to a spatial partition, then prefer the replica holding it — turning cross-region reads into local ones. This guide implements it without introducing the non-determinism that makes routing undebuggable. It extends the routing model in Cross-Domain Routing Strategies within Federated Ownership & Routing Architecture, and it composes with Header-Based Routing for Spatial Domains.

Prerequisites

Requirement Value / Assumption Notes
Tools The gateway with a request-time extension point, python3 ≥ 3.11 The mapping must be cheap and side-effect free
Partitioning Domain data partitioned by a spatial key, replicas aligned to it Locality is meaningless without it
CRS convention Request bbox declared in EPSG:4326 A bbox in another CRS resolves to the wrong partition
Residency Residency evaluated before locality Locality must never override a lawful-region constraint
Environment PARTITION_MAP, GATEWAY_ENV Exported before running

Step-by-Step Implementation

1. Build a static, cheap extent-to-partition map

The mapping runs on every request, so it must be a lookup rather than a query. A precomputed grid is enough and is trivially deterministic.

python
# locality.py — extent to partition, with no I/O on the request path.
import math

GRID_DEG = 5.0     # coarse cells; the map stays small enough to hold in memory


def cells_for_bbox(bbox: tuple[float, float, float, float]) -> set[str]:
    """Every grid cell a bbox touches. Coarse deliberately: the goal is to pick a
    replica, not to plan a query, and a fine grid makes the map large for no gain."""
    minx, miny, maxx, maxy = bbox
    cells = set()
    x = math.floor(minx / GRID_DEG) * GRID_DEG
    while x <= maxx:
        y = math.floor(miny / GRID_DEG) * GRID_DEG
        while y <= maxy:
            cells.add(f"{int(x)}:{int(y)}")
            y += GRID_DEG
        x += GRID_DEG
    return cells


def preferred_replicas(bbox, partition_map: dict, replicas: dict) -> list[str]:
    """Replicas holding the partitions this bbox touches, most-covering first.
    Deterministic: same bbox and same map always give the same ordering."""
    partitions = {p for c in cells_for_bbox(bbox) for p in partition_map.get(c, ())}
    scored = [
        (len(partitions & set(held)), name)
        for name, held in replicas.items()
    ]
    # Sort by coverage descending, then by name — never by a random tiebreak, or
    # two identical requests take different paths and nothing is reproducible.
    scored.sort(key=lambda s: (-s[0], s[1]))
    return [name for score, name in scored if score > 0]

Verify the mapping is deterministic and fast enough for the hot path:

bash
python3 - <<'PY'
import locality, timeit
m = {"−5:50": ("eu-west",), "0:50": ("eu-west", "eu-central")}
r = {"eu-west": ("eu-west",), "eu-central": ("eu-central",)}
bbox = (-1, 50, 1, 52)
a = locality.preferred_replicas(bbox, m, r)
b = locality.preferred_replicas(bbox, m, r)
assert a == b, "non-deterministic ordering"
print(a, f"{timeit.timeit(lambda: locality.preferred_replicas(bbox, m, r), number=10000)/10000*1e6:.1f} µs")
PY

2. Apply locality after residency, never before

Locality is an optimisation; residency is a constraint. Evaluating them in the wrong order produces a fast, unlawful route.

python
# route.py — the ordering that keeps locality safe.
def select_backend(request, product, replicas) -> str:
    # 1. Residency eliminates unlawful replicas outright. Non-negotiable.
    lawful = [r for r in replicas if r.region in product.allowed_regions]
    if not lawful:
        raise Unroutable("451: no replica in a permitted region")

    # 2. Health removes replicas that cannot serve, whatever their locality.
    healthy = [r for r in lawful if r.healthy]
    if not healthy:
        raise Unroutable("503: no healthy replica in a permitted region")

    # 3. Locality orders what remains. An optimisation, applied last.
    if request.bbox:
        preferred = preferred_replicas(request.bbox, PARTITION_MAP,
                                       {r.name: r.partitions for r in healthy})
        for name in preferred:
            return name

    # 4. No bbox, or no replica holds the partition: ordinary load balancing.
    return least_loaded(healthy).name

Residency, then health, then locality — an ordering that cannot be rearrangedBackend selection evaluates three filters in a fixed order. Residency eliminates replicas outside the product permitted regions, which is a constraint rather than a preference. Health removes replicas that cannot serve. Locality then orders what remains by how much of the requested extent each replica holds. Two of the filters drop onto rails: no lawful replica returns 451 and no healthy lawful replica returns 503. Applying locality first would produce a fast, unlawful route, which is why the ordering is load-bearing rather than stylistic.1 · Residencylawful regions only2 · Healthcan it serve3 · Localityholds the partitionBackend chosendeterministiclawfulhealthypreferred451 no lawful replica503 none healthyRefused, not mis-routedlocality never overrides residency

Verify residency wins when the two disagree — the test that matters:

bash
curl -sS -o /dev/null -D - \
  -H "x-spatial-domain: cadastre" \
  -H "x-spatial-bbox: -1,50,1,52" \
  "https://api.internal/collections/parcels/items" \
  | grep -iE '^(x-served-by|x-served-region):'
# Must be a region in the product's allowed set, even where a nearer one exists.

3. Make the decision explainable offline

A routing decision that cannot be reproduced without live state is a routing decision nobody can debug.

Why the tiebreak must be deterministic rather than load-basedFour properties compared between a deterministic tiebreak — coverage, then replica name — and a random or load-based one. The deterministic form sends identical requests to the same replica every time, can be reproduced offline from the map and the request alone, and makes a routing question answerable with one command. The load-based form varies per request, cannot be reproduced without live cluster state, and turns every routing question into log archaeology.DeterministicLoad-basedIdentical requestssame replicavariesReproducible offlineyesnoDebugging a routeone commandlog archaeologyCache localityimprovesunchanged

bash
# Same inputs, same answer, no cluster required.
gateway-cli explain-route \
  --domain cadastre --product parcels \
  --bbox " -1,50,1,52" --crs EPSG:4326 \
  --partition-map "$PARTITION_MAP" --replicas /tmp/replicas.json
# residency: eu-west, eu-central permitted; us-east excluded
# health:    eu-west healthy, eu-central healthy
# locality:  eu-west covers 2/2 partitions -> selected

4. Measure whether locality is actually paying

bash
# Cross-region read share should fall after enabling locality. If it does not, the
# partition map does not match how data is actually replicated.
curl -sS "$PROM/api/v1/query" --data-urlencode \
  'query=sum(rate(backend_requests_total{cross_region="true"}[30m]))
         / sum(rate(backend_requests_total[30m]))' | jq -r '.data.result[0].value[1]'

Cross-region read share before and after locality routingFour measurements of the share of backend reads crossing a region boundary, against a ten percent target. Before locality routing, 47 percent of reads cross a region. With locality and partition-aligned replicas, that falls to about 6 percent. With locality enabled but replicas holding everything rather than partitions, it stays at 47 — locality has nothing to prefer and the lookup is pure overhead. With a stale partition map it sits at 31, degrading gracefully rather than breaking.before locality47%locality, partitioned6%working as intendedlocality, stale map31%degrades gracefullylocality, unpartitioned47%nothing to prefertarget

Configuration Reference

Parameter Value Effect
GRID_DEG 5.0 Coarse cells keep the map memory-resident
Evaluation order Residency → health → locality Locality must never override a constraint
Tiebreak Coverage, then name Never random; identical requests must route identically
Fallback Ordinary load balancing A bbox with no matching partition is not an error
Request bbox CRS EPSG:4326, declared Another CRS resolves to the wrong cells
Map source Precomputed, deployed with the table No I/O on the request path

Common Failure Modes & Fixes

Two identical requests reach different replicas. Root cause: a random or load-based tiebreak inside the locality step. Fix: sort deterministically; locality decides preference, and load balancing only applies when locality expresses none.

Cross-region reads do not fall after enabling it. Root cause: the partition map does not reflect actual replication — usually because replicas hold everything rather than partitions. Fix: locality is only meaningful with partition-aligned replicas; without them, disable it rather than paying the lookup for nothing.

A request is routed to a lawful-but-distant replica. Root cause: correct behaviour when the near replica is outside the permitted region. Fix: none; this is residency winning, which is the required ordering.

Latency improves for most requests and worsens for some. Root cause: locality is concentrating load on the replica holding a popular partition. Fix: cap the share locality may direct to one replica, falling back to load balancing above it.

A bbox in the wrong CRS routes oddly. Root cause: EPSG:3857 coordinates interpreted as degrees resolve to a cell far from the intended region. Fix: require the CRS header and reject a bbox whose values fall outside the declared CRS’s domain.

FAQ

Is this not just data locality by another name?

It is, applied at the routing layer rather than inside the storage engine — and that placement is what makes it useful in a federated estate. A database can only optimise locality within itself; the routing plane sits above several domains, each with its own replication topology, and is the only component positioned to choose between them. The trade is that the routing plane needs a map of where partitions live, which is why the map is precomputed and deployed alongside the route table rather than queried live.

How coarse should the grid be?

Coarse enough that the map fits comfortably in memory and never needs a lookup off-box. Five-degree cells over a global estate produce a few thousand entries, which is trivial; half-degree cells produce hundreds of thousands and buy almost nothing, because the decision being made is “which replica” and replicas hold large regions. The grid only needs to be fine enough to distinguish replicas, not to describe the data.

What happens for a query with no bounding box?

It falls through to ordinary load balancing, which is correct. A request without a spatial bound has no locality to exploit, and inventing one — from the caller’s region, say — would route by who is asking rather than by what is being asked for. That is a different optimisation with different trade-offs, and conflating the two makes both harder to reason about.

Does locality routing interact with caching?

Yes, and usually favourably: directing requests for a region to a consistent replica improves that replica’s cache hit ratio for the same reason it improves data locality. The caution is the concentration failure above — locality plus caching can make one replica very hot for a popular region, at which point the cap on locality’s share becomes load-bearing rather than theoretical.

How often should the partition map be regenerated?

Whenever replication topology changes, and on a slow schedule otherwise. The map is a description of where partitions live, so it goes stale when a replica is added, removed, or rebalanced — and a stale map does not break routing, it merely stops helping, because a preferred replica that no longer holds the partition falls through to ordinary load balancing. That graceful degradation is deliberate: it means a forgotten regeneration costs some locality rather than causing an outage. Deploying the map alongside the route table, which is already regenerated on every registry change, keeps the two in step without a separate process to remember.

Related in Cross-Domain Routing Strategies