Invalidating Tile Caches After an OSM Diff

Take the change file your replication pipeline just applied and end up with a map that is current everywhere — including in caches you do not control — without regenerating a continent.

Prerequisites

Conceptual minimum

Invalidation has two halves that are easy to conflate and must not be.

Re-rendering makes the archive correct. It takes the dirty set, generates those tiles from current data, and writes them back. Until it completes, the archive still holds old tiles, so purging before re-rendering simply refills every cache with stale content.

Purging makes the caches consistent with the archive. It must run after re-rendering, must reach every layer, and must be idempotent, because a purge that partially fails has to be safe to repeat.

The expansion rules that produce the dirty set are worth restating because they are where correctness lives. A change at the deepest zoom dirties the tile containing it, the eight tiles around it — because each retains buffer geometry from its neighbours — and the entire ancestor chain up to zoom 0. Ancestors matter because a low-zoom tile shows a generalized version of the same feature; skipping them leaves a map that is right zoomed in and wrong zoomed out.

The order of operations after a change file is applied Four stages in strict order. The expand stage takes the raw touched tiles and adds neighbours at the deepest zoom and the full ancestor chain at every lower zoom. The render stage regenerates every tile in the expanded set from current data. The swap stage writes the new tiles into the archive atomically so no partially updated state is ever served. The purge stage issues invalidations to each cache layer, ordered from the layer nearest the origin outward, so a refill cannot repopulate an outer cache from a stale inner one. Render before purge, and purge inward to outward expand neighbours and ancestors cheap over-approximation render from current data archive becomes correct swap atomic write-back never a partial state purge origin then edge idempotent by design Purging before rendering refills every cache with the stale tiles it was supposed to remove, which is the classic ordering bug.
The ordering is the whole design: each stage is only safe once the one before it has finished.

Runnable solution

python 
from __future__ import annotations

import logging
from collections.abc import Iterable, Iterator
from dataclasses import dataclass

import requests

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.tiles.invalidate")

MAXZOOM = 14
PURGE_BATCH = 500


@dataclass(frozen=True, order=True)
class Tile:
    z: int
    x: int
    y: int

    def parent(self) -> "Tile | None":
        return None if self.z == 0 else Tile(self.z - 1, self.x // 2, self.y // 2)

    def neighbours(self) -> Iterator["Tile"]:
        span = 1 << self.z
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                if dx == 0 and dy == 0:
                    continue
                nx, ny = self.x + dx, self.y + dy
                if 0 <= nx < span and 0 <= ny < span:
                    yield Tile(self.z, nx, ny)

    def url(self, base: str, version: str) -> str:
        return f"{base}/{version}/{self.z}/{self.x}/{self.y}.mvt"

    def tag(self) -> str:
        """A coarse purge tag: every tile shares one with its zoom-6 ancestor."""
        shift = max(0, self.z - 6)
        return f"z6-{self.x >> shift}-{self.y >> shift}"


def expand(touched: Iterable[Tile]) -> set[Tile]:
    """Add buffer neighbours at the deepest zoom, then every ancestor."""
    dirty: set[Tile] = set()
    for tile in touched:
        if tile.z != MAXZOOM:
            raise ValueError("expand expects tiles at the deepest zoom")
        dirty.add(tile)
        dirty.update(tile.neighbours())

    # Walk up level by level; each level is a quarter the size of the one below.
    level = {t for t in dirty}
    while level:
        parents = {p for t in level if (p := t.parent()) is not None}
        dirty |= parents
        level = parents
    logger.info("expanded %d touched tile(s) to %d dirty tile(s)",
                len(set(touched)), len(dirty))
    return dirty


def render_and_swap(dirty: set[Tile], render, archive) -> None:
    """Regenerate every dirty tile, then write them back in one transaction."""
    rendered: list[tuple[Tile, bytes]] = []
    for tile in sorted(dirty):
        rendered.append((tile, render(tile)))
    archive.write_batch(rendered)          # atomic: all tiles land or none do
    logger.info("re-rendered and swapped %d tile(s)", len(rendered))


def purge(dirty: set[Tile], base: str, version: str,
          origin_purge_url: str, edge_purge_url: str, token: str) -> None:
    """Purge inner caches first so an outer refill cannot pull a stale copy."""
    headers = {"Authorization": f"Bearer {token}"}

    urls = [t.url(base, version) for t in sorted(dirty)]
    for i in range(0, len(urls), PURGE_BATCH):
        batch = urls[i:i + PURGE_BATCH]
        response = requests.post(origin_purge_url, json={"urls": batch},
                                 headers=headers, timeout=60)
        response.raise_for_status()
    logger.info("purged %d URL(s) from the origin cache", len(urls))

    # Tag-based purge at the edge: far fewer requests than enumerating URLs.
    tags = sorted({t.tag() for t in dirty})
    for i in range(0, len(tags), PURGE_BATCH):
        batch = tags[i:i + PURGE_BATCH]
        response = requests.post(edge_purge_url, json={"tags": batch},
                                 headers=headers, timeout=60)
        response.raise_for_status()
    logger.info("purged %d tag(s) from the edge network", len(tags))


def invalidate(touched: Iterable[Tile], render, archive, **purge_args) -> None:
    dirty = expand(touched)
    render_and_swap(dirty, render, archive)   # archive correct BEFORE purging
    purge(dirty, **purge_args)


if __name__ == "__main__":
    logger.info("feed `touched` from the dirty-tile computation over the .osc")

Step-by-step walkthrough

  1. Insist the input is at the deepest zoom. The expansion assumes it, and a mixed-zoom input silently produces an incomplete dirty set. Failing loudly is better than a map that is quietly wrong at some levels.
  2. Add neighbours before ancestors. A neighbour’s own ancestors must be dirty too, so expanding in the other order misses them.
  3. Walk ancestors level by level. Each level is a quarter the size of the one below, so the whole chain adds roughly a third to the set — cheap, and the alternative is a permanently stale low-zoom map.
  4. Render everything before writing anything. Collecting the rendered tiles first and writing them in one batch means the archive never holds a mixture of old and new tiles from the same change.
  5. Purge after the swap. Purging first evicts correct-but-old tiles and immediately refills every cache with them again from an archive that has not been updated yet.
  6. Purge inward to outward. The origin cache is purged before the edge, so an edge refill triggered by a reader pulls from an already-correct origin.
  7. Use tags at the edge. A coarse tag shared by every tile under one zoom-6 ancestor turns hundreds of thousands of URL purges into a few hundred tag purges, which stays well inside rate limits.
  8. Keep purges idempotent. Batches can be retried safely, which matters because a partial failure is the normal case at this volume.
Purge request counts for one change file, by purge strategy Four strategies compared on the number of purge API requests needed for a single minutely change file. Purging each URL individually needs one request per tile, in the thousands. Batching URLs five hundred at a time reduces it to a handful of requests. Purging by coarse tag reduces it further, because many tiles share one tag. Purging the entire cache is a single request but evicts everything, destroying a hit ratio that took hours to build. Four strategies, and the cheapest one is the worst One request per URL about 1,520 Batched URLs about 4 By coarse tag about 2 Purge everything 1, and ruinous The last strategy evicts a cache that took hours to warm, so the next hour of traffic lands on the origin instead of the edge.
Tag purges win because many tiles under one coarse ancestor change together, which is exactly how edits cluster.
Three invalidation mistakes and the symptom each produces for a reader Three panels. Skipping ancestor expansion leaves low zoom tiles permanently behind, so the map is correct when zoomed in and progressively more stale as the reader zooms out. Purging before rendering evicts correct-but-old tiles and immediately refills every cache from an archive that has not been updated, leaving the caches unchanged and the hit ratio damaged. Purging the entire cache makes the map correct at once but evicts hours of warmed entries, sending the next hour of traffic to the origin. Three mistakes, three very different symptoms No ancestors Symptom: stale at low zoom Correct when zoomed in Worsens as you zoom out Hard to attribute to a cause Fix: walk the whole chain Purge before render Symptom: nothing changes Caches refill from the archive Archive not updated yet Hit ratio damaged for nothing Fix: render, swap, then purge Purge everything Symptom: map is correct But origin load spikes Hours of warming lost Latency rises for everyone Fix: purge only the dirty set Only the second mistake leaves the map wrong; the other two are correct maps bought at a cost somebody else pays.
That is why invalidation bugs survive review: two of the three produce a map that looks entirely fine.

Verification

  • A changed feature is visible at every zoom. Check the edited area at the deepest zoom and at zoom 8; both must reflect the change.
  • The dirty count is proportional to the change. A minutely diff producing a dirty set in the millions means the expansion is wrong, not that the diff was large.
  • No partial state is ever served. Request tiles continuously during a swap; every response must be either wholly old or wholly new.
  • Purges are idempotent. Re-run the same purge batch; it must succeed and change nothing.
  • Cache hit ratio recovers quickly. A dip after invalidation is expected; a sustained drop means the purge is far broader than the change.

Common errors and fixes

Symptom Root cause One-line fix
Low zooms permanently stale Ancestors not included Walk the full ancestor chain of every touched tile
Seams beside edited features Neighbours not included Add the eight neighbours at the deepest zoom
Stale tiles immediately after a purge Purge ran before re-rendering Render and swap first, purge second
Edge serves old tiles after an origin purge Purge order reversed Purge the origin before the edge
Purge API rate limited One request per tile URL Batch URLs, and prefer coarse tags at the edge
Hit ratio collapses after every update Whole-cache purge used Purge only the dirty set
Readers still see old tiles Browser cache with a long lifetime Put a version token in the tile URL

Specification reference

A tile at zoom level \(z\) with coordinates \((x, y)\) has as its parent the tile at zoom \(z-1\) with coordinates \((\lfloor x/2 \rfloor, \lfloor y/2 \rfloor)\), and the ancestor chain continues to zoom 0. Because generalized representations of a feature appear in every ancestor tile, a change affecting one tile affects its whole chain. See the Slippy map tilenames documentation for the addressing scheme and the coordinate arithmetic.

Frequently Asked Questions

Why must re-rendering happen before purging?

Because a purge evicts a cached tile and the next reader request refills it from the archive. If the archive has not been updated yet, the refill pulls exactly the stale tile the purge was meant to remove, and the caches end up in the same state they started in — except that the hit ratio has been damaged for nothing. Rendering first, then purging, is the only ordering that converges.

How far up do I need to invalidate?

All the way to zoom 0. It sounds expensive and is not: each level contributes a quarter as many tiles as the one below, so the entire ancestor chain adds roughly a third to the dirty set. Stopping partway produces a map that is correct when zoomed in and progressively more stale as the reader zooms out, which is both confusing and hard to attribute to a cause.

Should I purge by URL or by tag?

By tag at the edge, where the volume is high and rate limits bite, and by URL at the origin, where the layer is closer and the set is smaller. A coarse tag shared by every tile under a common low-zoom ancestor collapses hundreds of thousands of URLs into a handful of tags. The cost is precision — a tag purge evicts some tiles that did not change — which is a good trade because edits cluster geographically anyway.

Is purging the whole cache ever acceptable?

Only after a change that genuinely affects every tile, such as a schema or style change that regenerated the whole set. For an ordinary data update it destroys a hit ratio that took hours of traffic to build, and the following hour of requests lands on the origin instead of the edge. The cost of that is usually far larger than the cost of computing a precise dirty set.

Up one level: Serving & Invalidating OSM Tiles.