51. Walkthrough: Design Google Maps Routing & Navigation

Step 0 — Clarify the business goal

🎤 Candidate: For navigation, the outcomes are ETA accuracy and route quality, which drive trust and daily use. For the business, they also feed local ads and ride-hailing and delivery partners through APIs. Shall I focus on driving directions with live traffic, plus how tiles are served?

🧑‍💼 Interviewer: Yes. Driving routes with live traffic, global scale.

Step 1–2 — Requirements

Step 3 — Estimates

Road graph (world): order of 10^8-10^9 nodes/edges → tens of GB in compact form → fits in RAM per server
  → replicate the whole graph per routing server; no cross-server graph traversal
Plain Dijkstra on a continental graph explores millions of nodes → seconds → too slow
Routing QPS: e.g. 100M route requests/day + reroutes → ~2-5k QPS avg, more at commute peaks
Traffic probes: tens of millions of phones sending speed samples → aggregated per road segment per minute

Step 5 — High-level architecture

 Map data (sources, edits, imagery-derived) ─▶ map build pipeline ─▶ versioned road graph
     ├─▶ preprocessing: partition graph into cells (multi-level) / build contraction hierarchy
     └─▶ vector tile generation per zoom level ─▶ object store ─▶ CDN (tiles are static, cacheable)
 Phones (opt-in) ─location/speed probes─▶ ingestion ─▶ map matching (snap to road segments)
     ─▶ streaming aggregation: speed per segment per minute (anonymized, k-anonymity thresholds)
     ─▶ traffic metric publisher (every ~1 min) ─▶ routing servers (update edge weights)
 Client ─route request─▶ Routing front end ─▶ routing server (graph + current metric in RAM)
     ─▶ fast query on preprocessed graph ─▶ ETA model (ML correction using history + live)
     ─▶ alternatives ─▶ response (polyline + steps + ETA)
 Navigation session: client follows route; server (or client) re-checks periodically and on deviation

Step 6 — Deep dives

1. Why preprocessing: Contraction Hierarchies (CH) add "shortcut" edges so queries explore only a tiny upward search from each end (milliseconds instead of seconds). But CH preprocessing depends on the edge weights, so live traffic would require re-contracting. Customizable Route Planning (CRP), from Microsoft Research and used in Bing Maps, separates a metric-independent partition (done once) from a fast customization step that applies new weights (traffic) in seconds. This is the key insight to state: separate topology preprocessing from metric updates. OSRM (open source) implements both CH and a multi-level Dijkstra (MLD) variant.
2. Traffic pipeline: map matching of noisy GPS (§36), outlier removal, per-segment speed aggregation, a minimum number of contributors per segment for privacy, and fusion with historical speed profiles (by time of week) where live data is sparse.
3. ETA: a graph route gives a base travel time. ML corrects it with learned effects (turns, signals, time of day). DeepMind and Google described graph neural networks improving ETA accuracy in Google Maps (2020).
4. Tiles: vector tiles per zoom level (z0–z20) mean the client renders styling, so one tile set serves many themes. They're immutable per map version, so they're cacheable forever at the CDN with versioned URLs.

Step 7 — Failure modes & corner cases