Maps is three separate systems: rendering is storage, routing is a graph, ETA is prediction, and the discipline is never letting one answer for another.
Two numbers that set the design
- Graph is small: all roads as junctions and segments fit in ~10.2 GB, the RAM of one box. No distributed shortest path.
- Search is slow: one long route by Dijkstra costs ~31 s CPU, ~150x over budget. Avoid the search entirely.
Sizing (back of the envelope)
- Planet constants: 40,000,000 m equator, 510,000,000 km² surface, 15,000,000 km² settled land.
- 1B DAU → ~4.2M concurrent navigators (Little’s Law: concurrency = rate × duration).
- Route requests: 7 per 30-min session → ~40,510/s peak (×2.5 peak multiplier).
- Probes: 1 fix/s, batched 10 per upload → 1.04M peak uploads/s, 10.4M peak fixes/s. Carry both at peak.
- Fix stream is not stored durably (worthless within a minute).
Tile pyramid: ship geometry, not pixels
- Level
z has 4^z tiles; bottom two levels are 15/16 of any pyramid. The top is free.
- Ground resolution =
40,000,000 / 2^z m wide. Zoom 14 ≈ 2.4 km; zoom 20 ≈ 38 m (0.15 m/pixel).
- A zoom-
z tile equals a geohash cell with z longitude bits (same subdivision keys cache and matcher).
| Approach | Stop at | Size | Note |
|---|
| Raster (pixels) | zoom 20 | 431 TB | 93.75% in bottom 2 levels |
| Vector (geometry) | zoom 14 | 526 GB | 819x smaller; client rasterizes |
- 819x =
4^6 fewer tiles (4,096) ÷ 5x bigger per vector tile. Cost is client CPU; keep raster for old devices and satellite imagery.
Routing: never run Dijkstra live
| Method | Nodes settled | Query | Cores at 40,510 QPS |
|---|
| Dijkstra | 61.8M | 30.9 s | 1,251,759 |
| A* (ellipse, 7.2x smaller) | 8.5M | 4.27 s | 172,978 |
| Contraction hierarchies | ~1,000 | 0.5 ms | 20 |
- Graph: 64M km road, 0.25 km segments → 256M segments, 512M directed edges, ~205M nodes (degree 2.5). Node 20 B + edge 12 B ≈ 10.2 GB. Density 13.65 nodes/km².
- A* ellipse gain (7.2x) is geometry, not code; straight-line is the largest admissible heuristic. Only escape: don’t search.
- Contraction hierarchies (CH): rank nodes by importance, contract least-important first (add shortcut only when the path through
v was the unique shortest), query bidirectionally moving upward only. ~18 core-hours preprocess; artifact grows to 12.7 GB (edge array replaced).
- CH catch: shortcuts are valid only for the metric they were built against. Traffic invalidates them; rebuild is the only fix, and 18 core-hours does not fit a 120-s window. CH alone is incompatible with live traffic.
Split topology from metric
- Topology = shape (which junctions connect), changes in weeks. Metric = seconds per edge, changes every ~2 min. Fusing them redoes the expensive thing at the cheap thing’s rate.
- Cell overlay: partition into ~4,096-node cells (~50,000 total), find boundary nodes (doorways), precompute a clique per cell (doorway-to-doorway shortest time inside). Query hops doorway-to-doorway, descends to roads only in origin/destination cells.
- Boundaries scale as
2 × sqrt(cell size) ≈ 128 doorways/cell. Overlay ≈ 813M edges ≈ 9.8 GB. Served artifact = 10.24 GB graph + 9.8 GB overlay = 20.0 GB (overlay sits on top, does not replace; 12.7 GB understates by 57%).
- Customization re-prices overlay edges: one bounded Dijkstra per boundary node inside its cell, all cells independent. Full pass ~13,100 core-s; only ~5% of cells change → ~655 core-s ≈ 10.2 s on 64 cores, inside the 120-s window. ~97.7x cheaper than a CH rebuild (4.9x structure × 20x incrementality).
- Trade: overlay query ~a few ms vs CH’s 0.5 ms (~10x slower, but 2.5% of a 200 ms p99). Worth it because updates run every 2 min.
ETA is a prediction, not a sum of edge times
- Summing edge times fails: turn/intersection costs live at junctions (left turn 20-40 s); speeds are conditional on time of week; error is asymmetric (late worse than early, so report above the mean).
- Historical profile is the primary signal; at most ~1.2% of segments have live data. Frame the model (objective, labels from probes, two-stage score, online serving with feature store), don’t build it.
- Consistency trap: the router’s metric and the ETA function must be the same function, or the returned route isn’t fastest under the number displayed. Fix: model produces the metric, or ETA = metric path cost + learned correction. Never two independent estimates.
Traffic loop that eats itself
- Fixes are not observations; only distinct vehicle-segment crossings count. ~30M obs/window vs 512M edges = 5.9% touched; require 5 vehicles → ~1.2% ceiling. Raising ping frequency changes nothing.
- Greedy router lags one 2-min window and flips everyone back and forth: 26.25 min vs 25.0 min for no router at all vs 21.7 min at equilibrium.
- Fix (structural): (1) split demand across
k near-optimal routes assigned randomly by spare capacity (why /v1/route returns a list); (2) damp updates p_next = (1-α)p + α·p_target, α=0.3, 0.7^n residual; (3) route each user selfishly (user equilibrium), never system-optimal (routes strangers onto slower paths).
Scaling and gotchas
- Data fits 20.0 GB, so every route/graph bottleneck is replication, never partitioning. Map matching (10.4M fixes/s) shards by geographic cell; it is embarrassingly parallel.
- Base tiles and traffic tiles are separate resources: base is immutable (CDN forever), traffic has a 2-min TTL. Merging drags the whole map to 2 min.
- Probe upload returns
202 before processing. Version graph + overlay as one artifact; never hot-swap one half.
- Every failure degrades to a worse answer, not none: stale metric still routes, missing live speed falls back to the historical profile.
Probes -> segment speeds -> routing metric -> routes returned -> probes
(control loop with users inside; split + damp to avoid oscillation)