Map Tile Serving & Distribution for AV Fleets

A validated HD map is an artefact on a build server; a served HD map is a system with a latency budget, a cache policy and a failure mode when the link drops. This stage sits at the end of the HD mapping architecture and spatial data standards pipeline, immediately after HD map version control signs a release, and its constraints come from the vehicle rather than from the map: a tile must be fetched, decoded and stitched before the planner reaches the area it describes, the resident set must stay inside a hard memory ceiling, and a vehicle that cannot reach the server must degrade to the last known-good map rather than to no map.

The naive design — one large regional file, downloaded at depot — fails on all three counts. It cannot deliver a lane closure surveyed this morning, it holds far more of the map resident than the planner will ever consult, and the first time the vehicle drives outside the downloaded region it has nothing at all.

The serving path, drawn from the signed release down to the tile the planner reads:

Distribution Model Comparison #

Four models cover essentially every fleet in service. The choice is decided by how often the map changes and how reliable the vehicle's link is, not by engineering taste.

Delta pull is the default and the rest of this page implements it: it keeps transfer proportional to the semantic change, exactly as content-addressed map tile deltas computes them, and it degrades to whole-tile pull automatically the first time a vehicle asks for a tile it has never held.

Push on release is layered on top rather than replacing it — a safety-relevant change is announced, and vehicles that hear the announcement pull the delta immediately instead of at their next scheduled poll.

Stage-by-Stage Implementation #

Stage 1 — Cut the release into addressable tiles #

The constraint: a tile boundary must never split a lane feature in a way that requires both tiles to be present in order to interpret either. Features that cross a boundary are stored whole in the tile containing their midpoint and referenced by identifier from the neighbour, which is the same ownership rule joining lane attributes across map tiles applies at the seam.

import numpy as np

def quadkey(lon: float, lat: float, level: int) -> str:
    """Bing-style quadkey for a WGS84 point at the given zoom level."""
    sin_lat = np.sin(np.radians(lat))
    x = (lon + 180.0) / 360.0
    y = 0.5 - np.log((1 + sin_lat) / (1 - sin_lat)) / (4 * np.pi)
    n = 1 << level
    tx, ty = min(int(x * n), n - 1), min(int(y * n), n - 1)

    digits = []
    for i in range(level, 0, -1):
        bit = 1 << (i - 1)
        d = 0
        if tx & bit:
            d += 1
        if ty & bit:
            d += 2
        digits.append(str(d))
    return "".join(digits)

At level 15 a quadkey cell is roughly 1 km on a side at mid-latitudes and shrinks toward the poles; pick the level from the metric size you want at your operating latitude rather than assuming the equatorial figure. Expected output: a string such as "120210233012133", which is also the storage path — tiles/1/2/0/2/.../tile.bin — so a prefix query selects a whole region.

Stage 2 — Address every tile by content, not by version number #

The constraint: a vehicle must be able to establish what it is missing with one small request, and it must be able to verify what it received without trusting the transport. Both fall out of addressing tiles by digest.

import hashlib

def tile_digest(feature_digests: list[str]) -> str:
    """Merkle root over a tile's canonically sorted feature digests."""
    h = hashlib.sha256()
    for d in sorted(feature_digests):
        h.update(bytes.fromhex(d))
    return h.hexdigest()


def missing_tiles(held: dict[str, str], target: dict[str, str]) -> list[str]:
    """Quadkeys whose digest differs from — or is absent in — what the vehicle holds."""
    return sorted(k for k, d in target.items() if held.get(k) != d)

held is the vehicle's tile-to-digest map, a few tens of kilobytes for a city; target is the release manifest. The comparison is set arithmetic on hashes, so its cost is independent of tile size and a vehicle that is already current transfers nothing beyond the manifest.

Why the manifest exchange is cheap enough to run on every poll:

Stage 3 — Stream the selected tiles under a latency budget #

The constraint: the first usable lane record must reach the decoder well before the whole tile has transferred, and a slow client must be able to slow the server rather than drop the connection. A server-streaming RPC gives both.

import grpc

def stream_tiles(stub, quadkeys: list[str], deadline_s: float = 0.2):
    """Yield decoded tile chunks as they arrive, honouring a hard deadline."""
    request = TileRequest(quadkeys=quadkeys, encoding="protobuf")
    try:
        for chunk in stub.StreamTiles(request, timeout=deadline_s):
            yield chunk.quadkey, chunk.payload, chunk.is_final
    except grpc.RpcError as exc:
        if exc.code() is grpc.StatusCode.DEADLINE_EXCEEDED:
            return              # keep the cached map; retry on the next poll
        raise

The deadline is on the whole call, so a partially delivered tile is discarded rather than admitted: a half-tile is worse than a stale tile because it looks complete to the planner. Chunk boundaries fall on feature boundaries, so is_final is the only signal the cache needs to promote a tile from staging to resident.

Stage 4 — Admit tiles under a hard ceiling #

The constraint: the resident tile set is bounded and the bound is expressed in tiles, so it survives a change in feature density. Admission and eviction are one operation — a tile is admitted only if something can be evicted for it, and the eviction ranking is the predicted-trajectory distance used by managing map tile boundaries in ROS2.

def admit(cache: dict, quadkey: str, payload: bytes,
          rank: dict[str, float], max_tiles: int = 9) -> bool:
    """Insert a tile, evicting the furthest-from-trajectory tile if needed."""
    if quadkey in cache:
        cache[quadkey] = payload
        return True
    while len(cache) >= max_tiles:
        victim = max(cache, key=lambda k: rank.get(k, float("inf")))
        if rank.get(victim, float("inf")) <= rank.get(quadkey, float("inf")):
            return False        # everything resident is more useful than this
        del cache[victim]
    cache[quadkey] = payload
    return True

Returning False rather than evicting something more useful is deliberate: a prefetch for a route the vehicle has already diverged from must not displace the tile it is currently driving on.

Validation & QC Automation #

Every gate here runs against a served endpoint, not against the build output, because the defects this stage introduces are transport and cache defects.

def assert_serving_contract(client, manifest: dict[str, str]) -> None:
    for quadkey, digest in manifest.items():
        payload = client.fetch(quadkey)
        assert tile_digest(feature_digests_of(payload)) == digest, \
            f"{quadkey}: served bytes do not match the manifest digest"

    resident = client.cache_state()
    assert len(resident) <= 9, f"cache ceiling breached: {len(resident)} tiles"
    assert client.p95_latency_ms() <= 200, "tile fetch p95 over the 200 ms budget"
    assert client.offline_read_ok(), "no last known-good map when the link is down"

The enforced thresholds: served digest equals the manifest digest for every tile; resident tile count never exceeds the ceiling under a simulated route with three detours; fetch p95 ≤200 ms on the reference link profile; and a link-down test that returns a complete map from cache rather than an error. Wire the whole function into the release pipeline so a change to the serving layer cannot ship without exercising all four.

Edge Cases & Failure Patterns #

A vehicle holds a tile the release no longer contains. The manifest is authoritative for presence as well as content: any resident quadkey absent from the manifest is evicted, not retained. Retaining it produces a vehicle driving on geometry that has been deliberately withdrawn.

Two vehicles at different map versions meet at a boundary. Nothing needs to be done — each is internally consistent, and consistency between vehicles is a fleet-management question, not a map one. What must not happen is one vehicle holding tiles from two versions, which the atomic manifest swap prevents.

A CDN caches a tile past its release. Tile paths include the content digest, so a changed tile is a different URL and the stale object is simply never requested again. Never serve a tile from a mutable path.

The link is fast but the decoder is slow. The 200 ms budget covers transfer and decode. Profile the decode of a dense urban tile before trusting a transfer-only measurement — on lane-dense tiles decode routinely dominates.

A partial tile is admitted after a deadline. Guard admission on is_final and stage the payload outside the resident map until it arrives. A truncated tile presents as a region with no lanes, which the planner reads as impassable rather than as missing.

Why the re-cut is incremental. A release that edits one junction has no business re-cutting a region:

Performance & Scale Notes #

Serving is cheap to scale horizontally because it is stateless — the only per-vehicle state is the held-digest map, and that lives on the vehicle. A single origin behind a CDN serves a national fleet, since tiles are immutable and cacheable forever at the edge once addressed by digest.

The expensive part is the cut in stage 1, which is re-run per release over the whole region. Cut only the tiles whose feature set changed: a release that edits one junction re-cuts one tile, and the manifest for every other tile carries forward unchanged. On a 40 000-tile region this turns a 6-hour re-cut into a 20-second one.

Onboard, the dominant cost is decode. Keep tiles in a format the vehicle can memory-map rather than parse — the same argument made for tile geometry in the ROS2 boundary guide — and the resident-set ceiling becomes a page-cache concern rather than a heap one.

FAQ #

What tile size should an HD map use? #

Size the tile so that one tile plus its immediate neighbours covers the planning horizon with room to prefetch, and so that a single tile decodes inside the frame budget. For urban HD maps that lands between 250 m and 1 km on a side: smaller tiles mean more index overhead and more boundary stitching, larger tiles mean a longer stall the first time a vehicle enters an uncached area. Measure the decode time of a representative tile before fixing the number, because decode cost scales with lane density rather than with area.

Should tiles be indexed by quadkey or by H3? #

Quadkeys give a strict hierarchy, so a parent prefix selects all its children and range queries over a sorted key space are trivial — which makes them a natural fit for object storage and CDN paths. H3 gives cells with uniform neighbour distance, which makes ring queries around a pose exact rather than approximate. Fleets that serve tiles over HTTP normally use quadkeys for the storage layout and compute H3 rings onboard for the prefetch set, using each index for what it is good at rather than choosing one.

How large should the onboard tile cache be? #

Derive it from the planning horizon and the route uncertainty, not from the free space on the device. A cache holding the active tile, every tile the predicted trajectory crosses within the horizon, and one ring beyond that is enough; anything more is holding data the vehicle will not use before it is evicted anyway. Express the ceiling in tiles rather than bytes so the policy survives a change in tile density, and enforce it with a hard limit so a routing detour cannot grow the resident set without bound.

Why stream tiles rather than downloading them as files? #

A streaming transport lets the vehicle begin decoding the first lane records before the last byte of the tile has arrived, which turns a 200 ms transfer into a 200 ms pipeline rather than a 200 ms stall followed by a decode. It also gives per-message flow control, so a vehicle on a weak link applies backpressure to the server instead of timing out and retrying a whole tile. The cost is a more complex client and a server that must be able to resume a partial tile.

Related #

• Tiling HD Maps with Quadkeys and H3 — choosing a level and cutting features on boundaries without splitting them.
• Streaming Map Tiles to Vehicles over gRPC — the transport, its deadline handling and its resume path.
• Prefetching and Evicting Map Tiles Onboard — the cache policy that keeps the resident set bounded.
• HD Map Version Control — the release this stage distributes.
• Map Format Interoperability: OpenDRIVE, Lanelet2 & NDS.Live — what the served payload is encoded as.

Up one level: HD Mapping Architecture & Spatial Data Standards — the pipeline whose signed output this stage delivers to the fleet.