Location Intelligence Retail Site Selection Automation

Invalidating Isochrone Caches on Traffic Updates

This page solves one exact problem: serving cached isochrones fast without serving stale ones after the underlying traffic or routing graph has changed.

Caching isochrones is close to mandatory once a portfolio grows — recomputing the same 15-minute contour on every dashboard load is wasteful, and the caching layer for repeated network queries exists precisely to avoid that. But a cache that never expires will happily hand back a contour computed against last month’s graph. When a new bridge opens, a highway segment closes, or the speed model is retuned, every catchment touching that change is now wrong, and downstream site scores silently drift. This page covers how to invalidate correctly: versioned keys, region-scoped purges, the TTL-versus-event trade-off, and how to stop a stampede when a whole region invalidates at once.

Prerequisites

Before running this task you need:

  • Python packages: redis for the cache client and shapely / geopandas to reason about the region geometry of an invalidation. Install with pip install redis shapely geopandas.
  • A running Redis (or compatible) instance reachable from the routing service, used as the shared cache tier.
  • A monotonic graph version. Every routing-graph build must emit an identifier that only increases — an OSM extract timestamp, a build number, or a content hash. Without it, versioned keys are impossible.
  • A way to know what changed. Event-based invalidation needs the bounding box or region id of the update. If the graph pipeline can only tell you “something rebuilt,” you are limited to whole-namespace invalidation.

Configuration and Execution Parameters

The core design choice is TTL versus event-based invalidation, and mature systems run both. A TTL is a safety net that bounds maximum staleness even when an event is missed; event-based invalidation gives immediate correctness when the graph changes. The other lever is invalidation scope — purging one key, a bounding box, or an entire graph version.

Parameter Typical value Effect
ttl_seconds 86400 (24 h) Upper bound on staleness if an invalidation event is missed
graph_version e.g. osm-2026w28 Namespaces every key so a new graph never collides with old contours
Key schema iso:{v}:{lon}:{lat}:{min}:{profile} Uniquely identifies one cached contour
Invalidation scope key · bbox · version Purge one contour, a region, or the whole prior graph
lock_ttl_seconds 30 Lifetime of the recompute lock that prevents a stampede
stale_grace_seconds 60 Window a stale value may be served while one worker recomputes
region_index Redis set per grid cell Maps a bbox to the keys that must be purged

The decisive design decision is putting graph_version in the key, not in a separate validity flag. When the version is part of the key, a graph refresh does not require touching any old entries at all — new requests simply miss on the new-version key and recompute, while old-version keys age out under their TTL. This turns the hardest case (a full graph rebuild) into a no-op invalidation. You only need active purging for the surgical case: a localized change where you want the region’s contours regenerated immediately rather than waiting for the version bump.

Versioned keys and the invalidation model

A cache key must encode every input that changes the contour. For an isochrone that is the origin, the time budget, the profile, and the graph the router traversed:

k=hash( lon, lat, minutes, profile, graph_version )k = \text{hash}\big(\,\text{lon},\ \text{lat},\ \text{minutes},\ \text{profile},\ \text{graph\_version}\,\big)

Any two requests agreeing on all five are genuinely interchangeable; a difference in any one must produce a different key. Staleness is then a strict statement about versions — a cached value is stale exactly when its embedded graph_version is older than the current one for the region it covers:

stale(k)  ⟺  v(k)<vcurrent(region(k))\text{stale}(k) \iff v(k) < v_{\text{current}}(\text{region}(k))

Region-scoped invalidation exploits the fact that a graph update rarely touches the whole network. A new interchange affects only contours whose geometry intersects its bounding box. If you maintain a reverse index from a coarse spatial grid cell to the set of keys whose origin (or contour) falls in that cell, an event carrying a bbox purges only the intersecting cells — leaving the other 99% of the cache warm.

Isochrone cache read path with versioned keys, stampede lock, and traffic-update invalidation A request builds a versioned key from lon, lat, minutes, profile and graph_version. On a cache hit the contour is returned immediately. On a miss, workers contend for a recompute lock: the lock winner computes the isochrone and writes it back with a TTL, while others briefly serve the stale value or wait. Separately, a traffic or graph update event carries a bounding box that purges only the intersecting region index cells, leaving the rest of the cache warm. Build versioned key lon·lat·min·profile·v Cache hit? hit Return contour no recompute miss Acquire lock? lost Serve stale or wait won Recompute + SETEX write back with TTL Traffic / graph update event carries bbox → region cells purge intersecting keys only or bump graph_version old keys age out via TTL

Annotated Implementation

The cache below builds versioned keys, indexes each key into a coarse grid cell for region-scoped purges, and guards recomputes with a per-key lock so a mass invalidation does not trigger a thundering herd. The isochrone computation itself is abstracted behind compute_fn, which would call the routing engine.

python
import json
import time
import hashlib
import redis
from shapely.geometry import box, Point

GRID = 0.25          # degrees per region-index cell (~25-28 km mid-latitude)
TTL = 86_400         # 24h safety-net expiry
LOCK_TTL = 30        # seconds a recompute may hold the lock
STALE_GRACE = 60     # seconds a stale value may be served during recompute


def _cell(lon, lat):
    # Coarse WGS84 grid cell id for the reverse index. This is an indexing
    # bucket, not a geometric measurement, so no projection is needed here.
    return f"{int(lon // GRID)}:{int(lat // GRID)}"


def _key(lon, lat, minutes, profile, graph_version):
    raw = f"{lon:.6f}:{lat:.6f}:{minutes}:{profile}:{graph_version}"
    digest = hashlib.sha256(raw.encode()).hexdigest()[:16]
    return f"iso:{graph_version}:{digest}"


class IsochroneCache:
    def __init__(self, client: redis.Redis):
        self.r = client

    def get_or_compute(self, lon, lat, minutes, profile,
                       graph_version, compute_fn):
        key = _key(lon, lat, minutes, profile, graph_version)
        cached = self.r.get(key)
        if cached is not None:
            return json.loads(cached)

        # Stampede protection: only the lock winner recomputes.
        lock_key = f"{key}:lock"
        got_lock = self.r.set(lock_key, "1", nx=True, ex=LOCK_TTL)
        if not got_lock:
            # Another worker is recomputing. Serve last-known-good if we have
            # it, else wait briefly for the winner to populate the key.
            stale = self.r.get(f"{key}:stale")
            if stale is not None:
                return json.loads(stale)
            time.sleep(0.2)
            fresh = self.r.get(key)
            return json.loads(fresh) if fresh else self.get_or_compute(
                lon, lat, minutes, profile, graph_version, compute_fn)

        try:
            geojson = compute_fn(lon, lat, minutes, profile)   # routing call
            payload = json.dumps(geojson)
            pipe = self.r.pipeline()
            pipe.setex(key, TTL, payload)
            pipe.setex(f"{key}:stale", TTL + STALE_GRACE, payload)
            # Register this key under its region cell for scoped invalidation.
            pipe.sadd(f"region:{_cell(lon, lat)}", key)
            pipe.execute()
            return geojson
        finally:
            self.r.delete(lock_key)

    def invalidate_bbox(self, min_lon, min_lat, max_lon, max_lat):
        """Purge only keys whose region cell intersects the update bbox."""
        # bbox is a WGS84 extent from the graph-update event; we iterate the
        # coarse cells it covers rather than scanning the whole keyspace.
        purged = 0
        lon = min_lon
        while lon <= max_lon:
            lat = min_lat
            while lat <= max_lat:
                cell = f"region:{_cell(lon, lat)}"
                keys = self.r.smembers(cell)
                if keys:
                    pipe = self.r.pipeline()
                    for k in keys:
                        pipe.delete(k)
                        pipe.delete(f"{k}:stale")
                    pipe.delete(cell)
                    pipe.execute()
                    purged += len(keys)
                lat += GRID
            lon += GRID
        return purged

Note the two-tier write: the live key expires at TTL, but a :stale shadow copy lives slightly longer, so a worker that loses the recompute lock can still return a recent contour instead of blocking. That is the difference between a cache miss costing one client a 200 ms wait versus every concurrent client stampeding the routing engine at once.

Failure Modes and Debugging

Symptom Cause Fix
Dashboards show old contours after a bridge opens No invalidation event fired; TTL not yet elapsed Wire the graph pipeline to emit a bbox event, or bump graph_version on every build.
Routing engine saturates at graph-refresh time Thundering herd — every key invalidated at once, all clients recompute Keep versioned keys so old entries age out lazily; reserve active purges for small bboxes; the recompute lock caps concurrency.
Redis memory grows without bound Keys written with no TTL, or region sets never trimmed Always SETEX, never SET, for contours; delete the region set when its cell is purged (done above).
invalidate_bbox purges nothing Event bbox in a different CRS than the WGS84 grid index Normalize the event extent to EPSG:4326 before indexing; the grid is defined in degrees.
Stale value served indefinitely :stale shadow outlives the real refresh cadence Keep STALE_GRACE small (tens of seconds); it is a stampede buffer, not a second cache tier.

The thundering-herd case deserves emphasis because it is where naive invalidation does the most damage. If a graph refresh flushes the entire cache, the next wave of traffic finds every key missing and every client calls the router simultaneously — the cache stops absorbing load exactly when load peaks. Versioned keys sidestep this by design: a new graph version means new keys, so the old cache is not flushed, it just stops being read and expires quietly in the background while the new version fills in on demand. This is the same lazy-migration discipline the Airflow idempotency workflow applies to the batch side — a refresh should be safe to run without invalidating work that is still correct.

Verification

Confirm the cache behaves before trusting it in front of the router:

  1. Hit/miss ratio. Instrument get outcomes and watch the ratio. A healthy steady state sits well above 90% hits; a sustained dip after a deploy means a key input changed and every request is missing.
  2. Version isolation. After bumping graph_version, assert a fresh request produces a different key and misses, while an old-version key still resolves until its TTL. The two must not collide.
  3. Region-scoped purge. After invalidate_bbox, assert keys inside the bbox are gone and keys outside it survive — the purge must be surgical, not global.
  4. Stale-key sweep. Periodically scan for entries whose embedded version is older than current for their region and confirm they are expiring, catching any key written without a TTL.
python
def audit_cache(cache: IsochroneCache, current_version: str):
    r = cache.r
    total = no_ttl = wrong_version = 0
    for k in r.scan_iter(match="iso:*"):
        if k.endswith(b":stale"):
            continue
        total += 1
        if r.ttl(k) < 0:                       # -1 = no expiry set
            no_ttl += 1
        # Version is the 2nd colon-delimited field of the key.
        if k.decode().split(":")[1] != current_version:
            wrong_version += 1
    assert no_ttl == 0, f"{no_ttl} keys have no TTL — unbounded growth risk"
    return {"total": total, "stale_version": wrong_version}

Run audit_cache on a schedule. A rising stale_version count is normal immediately after a graph bump (old keys draining) but must trend to zero within one TTL window; if it plateaus, an invalidation path is broken. A non-zero no_ttl is always a bug — it is the leak that eventually evicts hot keys under memory pressure and quietly destroys your hit rate.

← Back to Caching Strategies for Repeated Network Queries