RouteMatching

Scheduling OSM Extract Refreshes for Routing Engines

A routing graph decays. Not quickly and not visibly, but a map that was current in January will, by autumn, be missing a new distribution park’s access road, still routing through a street that was pedestrianised in March, and unaware of two roundabouts. The traces that touch those places match slightly worse each month, and because the decay is gradual nobody attributes it to the map.

The remedy is a scheduled refresh — and the thing that makes a scheduled refresh safe rather than risky is the gate in front of promotion. This page builds the job around map data and graph preparation: download, verify, clip, overlay, build, test against real traces, promote atomically, and keep the previous graph where a rollback is one command.

Compatibility and Configuration Requirements

Requirement Value Notes
Scheduler Anything with retries and alerting The job is idempotent; the scheduler only needs to not silence failures
Disk Room for three graph versions Current, candidate, previous
Sample traces 2 000–5 000 recent traces, all depots The gate is only as representative as its sample
Promotion mechanism Symlink swap or config reload Must be atomic; a partial swap is worse than a stale graph
Alert channel Somewhere a human reads A gate that fails silently is a gate that does nothing

The Refresh Job

from __future__ import annotations

import hashlib
import pathlib
import subprocess

GRAPHS = pathlib.Path("/srv/routing/graphs")
LIVE = pathlib.Path("/srv/routing/live")          # symlink to a directory under GRAPHS


def verify_download(pbf: pathlib.Path, expected_sha256: str, min_bytes: int) -> str:
    """Refuse a truncated or unexpected extract before anything else touches it."""
    if pbf.stat().st_size < min_bytes:
        raise RuntimeError(f"{pbf} is {pbf.stat().st_size} bytes — expected at least {min_bytes}")
    digest = hashlib.sha256(pbf.read_bytes()).hexdigest()
    if digest != expected_sha256:
        raise RuntimeError(f"checksum mismatch for {pbf}")
    stamp = subprocess.run(
        ["osmium", "fileinfo", "-e", "-g", "data.timestamp.last.out", str(pbf)],
        capture_output=True, text=True, check=True,
    ).stdout.strip()
    return stamp


def build_candidate(pbf: pathlib.Path, stamp: str) -> pathlib.Path:
    """Clip, overlay and build into a directory named for the data timestamp."""
    out = GRAPHS / f"graph-{stamp[:10]}"
    out.mkdir(parents=True, exist_ok=True)
    subprocess.run(["./clip.sh", str(pbf), "operating_area.geojson", str(out / "region.osm.pbf")], check=True)
    subprocess.run(["osmium", "apply-changes", str(out / "region.osm.pbf"), "fleet-overlay.osc",
                    "--overwrite", "--output", str(out / "region-overlaid.osm.pbf")], check=True)
    subprocess.run(["./build-graph.sh", str(out)], check=True)
    (out / "SOURCE_SHA256").write_text(hashlib.sha256(pbf.read_bytes()).hexdigest())
    (out / "OSM_TIMESTAMP").write_text(stamp)
    return out


def promote(candidate: pathlib.Path) -> None:
    """Atomic swap: create a new symlink and rename it over the old one."""
    tmp = LIVE.with_suffix(".new")
    if tmp.exists() or tmp.is_symlink():
        tmp.unlink()
    tmp.symlink_to(candidate)
    tmp.replace(LIVE)          # rename is atomic on the same filesystem

The replace on the last line is the whole promotion mechanism. A symlink removed and recreated leaves a window — usually milliseconds, occasionally longer under load — during which the path does not exist, and any request that arrives in that window fails. Renaming over the old link has no such window.

Download, build, gate, promote — and keep the last one A refresh runs download and verification, then clip, overlay and build into a versioned directory, then a fitness gate against recent traces. Only on passing does a symlink swap make the candidate live. The previous graph stays on disk so a rollback is a second symlink swap. The gate is the only thing between a bad extract and production download + checksum clip + overlay + build fitness gate 3 000 recent traces match rate ≥ current − 1 pt pass fail symlink swap alert, keep current A failed gate is not an outage: the current graph keeps serving and a human looks at the candidate in the morning. Three graph directories on disk — previous, current, candidate — make rollback a symlink swap rather than a rebuild. Name directories for the OSM data timestamp, not the build date; two builds of the same data should collide. Record the promoted version in the matched output so a dispute can be reproduced against the right map.

The Fitness Gate

The gate answers one question: does the candidate graph match real traces at least as well as the graph currently serving? Everything else — file sizes, way counts, build success — is a precondition, not evidence.

def fitness(candidate: pathlib.Path, current: pathlib.Path, traces, tolerance_pts: float = 1.0) -> dict:
    new_rate = match_rate(candidate, traces)
    old_rate = match_rate(current, traces)
    delta_pts = (new_rate - old_rate) * 100
    verdict = "promote" if delta_pts >= -tolerance_pts else "hold"
    return {"new": new_rate, "current": old_rate, "delta_pts": delta_pts, "verdict": verdict}

Use yesterday’s traces, not a frozen benchmark. A benchmark set assembled once stops representing the fleet within a few months — new depots, new vehicle classes, new operating areas — and a gate that no longer represents the workload will cheerfully approve the change that breaks it.

Set the tolerance to one point, not zero. Match rate moves slightly between any two graphs because road geometry genuinely changes. A zero-tolerance gate blocks every promotion and gets disabled within a month, which is worse than a gate set slightly loose.

Alert on an improvement too, above a threshold. A candidate that gains four points of match rate is not good news; it usually means the current graph has been broken for a while and nobody noticed.

Execution and Tuning Guidelines

Build nightly, promote weekly. Building often keeps the pipeline exercised and surfaces upstream breakage the day it happens. Promoting often gives the gate too little signal and creates a long list of graph versions that matched output must reference. Decoupling the two costs nothing.

Make the job idempotent on the data timestamp. If the upstream extract has not changed since the last run, the job should notice and exit. Naming graph directories after the OSM data timestamp gives this for free, because a rebuild of unchanged data collides with a directory that already exists.

Keep the previous graph for at least as long as disputes can reach back. Two versions is the operational minimum for rollback. If matched distances reach invoices, keep months.

Run the gate against the engine you actually serve. Building an OSRM graph and gating it with a Valhalla matcher tests neither. It sounds obvious and it happens, usually when the gate is written by whoever owns the analytics rather than whoever owns the engine.

Eleven weeks of gated promotions Match rate on the weekly sample across eleven candidate graphs. Most weeks move by under half a point. In week six the candidate fell three points and was held, which turned out to be a truncated upstream extract. In week nine a candidate gained four points, revealing that the previous graph had been missing a rebuilt junction. Candidate match rate against the live graph, weekly sample live graph −1 pt tolerance held +4 pts — investigate w1 w11 Week six was a truncated download that every other check passed — the file was valid, just short. Week nine's gain came from a junction rebuilt in OSM months earlier, which the live graph had never seen. Both of those are findings. A gate that only blocks regressions surfaces half of what it could.

Common Pitfalls Specific to This Technique

Promoting inside the batch window. Swapping the graph while a nightly matching run is in flight means one batch is matched against two maps. Schedule promotion for a quiet window, and have the batch record which graph it used rather than assuming.

Letting the candidate build overwrite the live graph directory. Building in place removes the rollback and turns a bad extract into an outage. Build into a new directory, always.

Gating on build success alone. A graph that builds perfectly from a truncated extract is the exact failure the gate exists to catch, and it is invisible to every check that does not involve matching a real trace.

Rolling Back

A rollback is the reason the previous graph is on disk, and it should be boring enough that nobody hesitates to use it at two in the morning.

#!/usr/bin/env bash
set -euo pipefail
PREV=$(cat /srv/routing/PREVIOUS_VERSION)
ln -sfn "/srv/routing/graphs/${PREV}" /srv/routing/live.new
mv -Tf /srv/routing/live.new /srv/routing/live
systemctl reload osrm-routed
echo "rolled back to ${PREV}"

Three properties make it usable. It takes one argument or none — the previous version is recorded, not remembered. It is atomic, using the same rename that promotion uses. And it reloads rather than restarts, so in-flight requests finish rather than failing.

Test the rollback on a schedule. A rollback path exercised only during incidents is one that will be found broken during an incident; running it monthly against a staging instance costs minutes and converts a hope into a fact.

What a rollback does not fix

Output already produced against the bad graph stays wrong. That is what the version stamp is for: a query on graph_version identifies every affected trace, and re-matching them is a bounded job rather than a full reprocess. Without the stamp the only safe response is to re-match everything since the promotion, which for a fleet is days of compute.

Record the rollback itself as an event with a reason. Over a year the reasons form a short list — truncated extract, upstream schema change, a profile edit that was not meant to ship — and each entry is a candidate for a new precondition check in the refresh job. A rollback that produces a new check is a rollback that will not be needed for the same reason twice.

Two graphs, briefly

There is a window during a promotion where a long-running batch may hold the old graph open while new requests get the new one. That is usually fine and occasionally not: a batch that matches half its traces against each map produces a dataset with two version stamps, which is correct but surprises anybody aggregating it. Either promote outside the batch window, or have the batch resolve the graph once at start-up and hold it for the whole run.

A bad promotion, contained A graph is promoted at 02:00 and the fitness gate's tolerance lets a regression through. Match rate drops, the alert fires at 06:40, the rollback takes ninety seconds, and the version stamp identifies the four hours of output that need re-matching rather than requiring a full reprocess. A regression that got past the gate The candidate lost 0.8 points on the weekly sample — inside the 1-point tolerance, so it promoted. The loss was concentrated in one depot, where it was closer to six points. 02:00 promote 06:40 alert 06:41 rolled back 4 h 40 m of output stamped with the bad version a bounded re-match, not a full reprocess The rollback restores service in ninety seconds; the version stamp is what makes the cleanup finite. Every rollback reason should become a precondition check, so the same cause cannot produce a second one.

Related

Up to section Map Data and Graph Preparation for Fleet Routing Related Clipping OSM Extracts to a Fleet Operating Area with osmium Related Adding Truck Restrictions to an OSM Extract for Routing Related Pinning Map Versions for Reproducible Fleet Matching