Design the core of a maps product: render map tiles, compute routes between points with turn-by-turn directions and ETA that accounts for traffic, and update location during navigation.

• Road graph: ~1B nodes/edges worldwide; with contraction hierarchies preprocessing, in-memory per continent ≈ tens of GB — fits on big machines, partitioned by region.
• Tiles: 21 zoom levels; ~4^21 tiles at max zoom is impractical to precompute → precompute z0–z14, render/cache deeper on demand; CDN handles delivery.
• Location pings during navigation: 100M sessions × 1 ping/5 s over avg 30 min ≈ 36B/day ≈ 400k/s → stream to a traffic pipeline.
• Route requests: 100M/day ≈ 1.2k/s average; peaks 10k/s.

GET  /v1/tiles/{z}/{x}/{y}.pbf            (vector tiles, CDN-cached)
GET  /v1/route?from=lat,lng&to=lat,lng&mode=driving&departAt=  → { legs[], steps[], distanceM, durationS, polyline }
POST /v1/navigation/{sessionId}/location   { lat, lng, speed, heading, ts }  → { rerouted?: route }
GET  /v1/eta?from&to                       (lightweight)
GET  /v1/search?q=&near=                   (places)

road_graph   nodes(id, lat, lng), edges(id, from, to, length_m, speed_limit, road_class, restrictions, geometry)
ch_index     precomputed shortcuts/levels for contraction hierarchies, per region
traffic      edge_id → current_speed (Redis, TTL minutes) ; historical speed profiles by (edge, weekday, 15-min bucket)
tiles        object storage / tile cache keyed by (z,x,y, style_version)
places       search index (see proximity service)

1. Map data pipeline: ingest OSM/vendor data → build the road graph → validate → publish versioned graph snapshots and pre-rendered vector tiles (z0–14) to object storage + CDN.
2. Tile service: CDN → tile cache → on-demand renderer for deep zooms; clients render vector tiles locally.
3. Routing service: per-region servers hold the graph + contraction hierarchies (or CRP) in memory; a query = bidirectional Dijkstra on the CH, returning a path in ms even for 1,000 km. Edge weights = time using live traffic where fresh, historical profile otherwise. Cross-region routes stitch via border nodes.
4. Traffic service: ingests navigation pings (Kafka), map-matches them to edges (HMM map matching), aggregates speeds per edge per minute, and publishes current speeds; historical profiles computed offline.
5. Navigation service: keeps the session's route; on each ping, checks distance from the route; if off-route beyond a threshold, requests a reroute; sends the next instruction.
6. Places search uses the proximity/search design.

Contraction hierarchies: preprocess by contracting unimportant nodes and adding shortcut edges; queries become tiny bidirectional searches. Trade-off: preprocessing takes hours and live traffic changes weights → use customisable CH/CRP where metric customisation takes seconds.

Map matching: raw GPS is noisy; an HMM over candidate edges with transition probabilities from road distance yields the true path.

ETA: sum of edge travel times using time-dependent speeds (departure time matters); ML correction models on top for turn delays, signals.

Alternatives: penalise the found path's edges and re-run, or plateau method; ensure alternatives are meaningfully different.

Privacy: pings anonymised, sessions rotated, aggregated before storage.

• Traffic service down: routing falls back to historical profiles; ETAs less accurate but available.
• Regional routing server loss: replicas per region; cross-region stitch continues.
• Bad map data release: versioned snapshots; canary a region; instant rollback.
• GPS loss in tunnels: dead reckoning on the client; server tolerates gaps.