Designing Google Maps Routing: Contraction Hierarchies, Tiles, and ETA

The road network of the planet is a graph with roughly half a billion edges. Textbook Dijkstra explores it in O(E log V) — seconds of CPU and most of the graph visited for one cross-country query. Google Maps answers in tens of milliseconds, under millions of QPS, with traffic factored in. The gap between those two numbers is not hardware; it is one of the cleanest examples in industry of trading preprocessing for query time, and it makes a wonderful senior interview because the naive answer is a real algorithm that is still four orders of magnitude too slow.

Requirements

Route between any two points with live traffic, under 100ms server time; ETAs that hold up; alternative routes; map rendering for a billion devices; graph updates (closures, new roads) without global recompute.

The routing core: contraction hierarchies

The insight all fast-routing techniques share: real road networks have hierarchy. Long routes spend their middle on highways; no optimal NYC→LA route wanders through a Kansas subdivision. Contraction hierarchies (CH) formalize this:

Preprocessing: order nodes by "importance" (roughly: how much through-traffic needs them). Remove ("contract") nodes from least to most important; whenever removing node v would break a shortest path u→v→w, insert a shortcut edge u→w with the combined weight. The output is the original graph + a few hundred million shortcuts + the importance ordering.

Query: bidirectional Dijkstra — forward from source, backward from target — but each direction only relaxes edges going upward in importance. Both searches climb to the highway layer and meet; the touched region is a few hundred nodes instead of a hundred million.

naive Dijkstra:     visits ~10^7-10^8 nodes   ~seconds
CH query:           visits ~10^2-10^3 nodes    ~0.1-1ms
CH preprocessing:   hours over the full graph  (done offline, shipped as data)

Shortcuts unpack recursively into real edges when you need the turn-by-turn polyline — stored as a simple expansion table. The economics to say out loud: preprocessing hours are paid once per graph version; query milliseconds are paid billions of times a day. Any knob that moves cost from query-time to preprocess-time wins.

Traffic breaks it — and the fix

CH bakes edge weights into its shortcuts; live traffic changes weights every minute. Re-running hours of preprocessing per minute is absurd. The production answer is customizable route planning (CRP / microsoft's and google's variants): split preprocessing into a topology phase (slow, rare — the road graph changes weekly) and a metric customization phase (fast, minutes — recompute shortcut weights from current traffic over the fixed topology). Multiple metrics coexist: fastest-now, no-tolls, truck-legal, cycling — same topology, different customizations.

The graph is partitioned into regions (nested cells); customization recomputes per-cell overlay weights, so a traffic update touches its cell, not the planet. Partitioning also shards the whole serving problem: routing servers hold the overlay graph in RAM (it fits — the overlay is small), sharded and replicated per region-pair traffic.

ETA: a prediction, not a sum

Adding current edge times gives "ETA if traffic froze the moment you left" — wrong for any trip longer than 20 minutes, because you traverse edge 300 an hour from now, under future traffic. Real ETA is time-dependent routing: edge weights are functions of arrival-time-at-edge, built from historical patterns (Tuesday 5pm on this segment) blended with live conditions decaying into the prediction (today's accident matters at +10min, barely at +90min). Modern stacks (DeepMind×Maps) learn segment-sequence speeds with GNNs, but the systems shape is unchanged: a prediction service feeding weights into the routing core, with the feedback loop closed by the drivers themselves — every phone navigating is reporting speeds, so ETAs are trained on the fleet's own outcomes.

That loop has a second-order effect worth naming: routing shifts traffic (send everyone down the "empty" side street and it isn't), so live weights + rerouting form a feedback system — one more reason alternatives are computed and load is implicitly spread.

Tiles: the other half of the product

Rendering is its own pipeline: the world pre-cut into tiles (zoom 0 = Earth, each zoom quadruples; z/x/y addressing), generated per zoom with aggressive generalization (a city at z=5 is a dot). Modern maps ship vector tiles — geometry + attributes, styled client-side — ~5x smaller than raster, restyleable (dark mode, nav mode) without new data, and rotatable. Tiles are immutable blobs with content-hashed URLs behind a CDN — the textbook static-content story (cache hierarchy, hot tiles like downtown Manhattan pinned in edge memory), which is why this half of the system is architecturally boring and the interviewer will steer you back to routing.

Interview probe	Answer sketch
Why not Dijkstra + cache popular routes?	Route space is quadratic in locations; cache hit rate ~0 — precompute structure, not answers
Road closure at 2pm?	Metric customization re-run for the affected cells (minutes); topology rebuild only for real graph edits
A* with straight-line heuristic?	Correct but weak — distance underestimates time badly on real networks; landmark heuristics (ALT) are the respectable middle answer
Offline navigation?	Ship per-region graph + CH data to the device; same algorithm, smaller graph

The pattern to keep: when queries are astronomically frequent and the underlying data changes slowly-and-partially, split the world into what changes (weights, per-cell) and what doesn't (topology, global) — and precompute the expensive structure on the slow-changing part. That decomposition, not the algorithm's name, is what the interview is testing.