Scope the requirements
The first thing I'd do is split this into its three real sub-systems — map rendering, routing/ETA, and location ingestion — because they have wildly different shapes: one is static content at CDN scale, one is CPU-bound graph search, one is a write-heavy firehose. Designing them as one system is the failure mode.
Functional — what it must do
- Render the map: serve tiles at ~21 zoom levels as the user pans and zooms.
- Navigation: given origin and destination, return a route with turn-by-turn directions.
- ETA computation that reflects live traffic, refreshed continuously during navigation.
- Re-route when the user misses a turn or traffic makes a better route available.
- Devices report GPS positions during navigation — this feeds the traffic signal.
- Explicitly cut: place search and reviews (that's the proximity-service question), multi-stop trips, offline maps — offered back as extensions.
Non-functional — the numbers that shape the design
- Accuracy over latency for routes: a wrong route is worse than a route 200 ms late. Routing responses in under ~1 s.
- Tile loading must feel instant while panning — CDN cache hits, tens of ms.
- 99.99% availability — people navigate motorway junctions with this.
- Scale: 1B DAU; location ingestion at millions of writes per second.
- Battery and data efficiency on mobile: batch GPS pings, never one HTTP request per point.
I'll design three loosely-coupled systems: tiles are precomputed static content behind a CDN, routing is graph search over a partitioned road network, and location ingestion is a Kafka firehose whose consumers turn GPS points into live traffic. The only place they meet is that traffic re-weights the routing graph's edges.
Back-of-envelope estimates
Two of these numbers are the biggest most candidates will ever say out loud, which is why the interviewer asks — they want to see you handle petabytes and millions of QPS without either panicking or hand-waving.
| Quantity | Estimate | How you got there |
|---|---|---|
| Tiles at zoom 21 | ~4.4 trillion | The world at max zoom in 256px tiles. × 100 KB each ≈ 440 PB raw. |
| Tile storage, real | ~100 PB | ~90% of Earth is ocean or empty — ~50 PB; all coarser zoom levels add ~⅓; round up. Object storage + CDN, never a database. |
| Location writes | ~3M/s, peak 5M/s | 1B users × ~35 min navigation/week × 1 GPS point/s, batched every 15 s. The single scariest number in the design. |
| Navigation requests | ~thousands/s | ~1B route requests/week ÷ 604,800 s. Tiny QPS — the cost is CPU per request, not I/O. |
| Road graph size | ~tens of TB | Billions of road segments with geometry and metadata, partitioned into routing tiles loaded on demand. |
| CDN egress | ~60 GB/s | 5M concurrent users × ~200 KB/s of tiles while panning — this is why the CDN is load-bearing, not an optimisation. |
The asymmetry is the insight: routing is thousands of QPS but expensive per request, location ingest is millions of QPS but each write is trivial, and tiles are petabytes that never change after a build. Three different systems — and none of them should share a datastore.
Sketch the API
Three surfaces matching the three systems. The tile URL design is the quietly clever bit: the client computes which tiles it needs, so there's no server in that loop at all.
- Batching location updates is a requirement, not a nicety: one HTTP request per GPS point would mean 60M requests/s and a dead phone battery. Buffer 15-30 s on device, send one compressed batch, drop frequency when stationary. This one decision cuts ingest QPS by ~15×.
- Tile URLs are deterministic and immutable per build version, which makes CDN caching nearly perfect — a new map build publishes under a new version prefix rather than invalidating trillions of objects.
Data model
Four datasets, and the discipline is keeping them apart — especially the two geographic ones: display tiles and the routing graph describe the same streets but are different data with different pipelines.
No single database wins here and I'd say so explicitly: object storage plus CDN for both kinds of tiles, Cassandra for the location firehose because it's an append-heavy time series with no cross-user queries, and Redis for geocoding lookups. The relational itch has almost nothing to scratch — user profiles. If the interviewer asks where Postgres goes, the honest answer is: nowhere load-bearing.
High-level design
Three request paths that barely touch: tiles go client-to-CDN, navigation goes to a routing service that reads the road graph, and location batches pour into Kafka where consumers distil them into the live traffic that re-weights the graph.
- Map rendering: the app computes tile IDs from the viewport and zoom, fetches them from the CDN — an app server is never involved; misses fall through to the tile store in S3.
- Navigation:
GET /v1/navhits the navigation service → the route planner runs A* over hierarchical routing tiles (local roads → arterials → motorways) → the ETA service prices each candidate using live plus historical segment speeds → a ranker applies preferences (avoid tolls) → top routes return in well under a second. - During navigation the phone buffers GPS points and POSTs a batch every 15 s → the location service acks immediately and drops the batch onto Kafka — nothing downstream is on the request path.
- Stream consumers do the real work: map-match points to road segments, compute live speeds, update
traffic_segments, and push re-weighted edge costs into the routing tiles; a separate consumer sinks raw history to Cassandra. - If a segment on the user's active route degrades past a threshold, the navigation session re-runs routing and pushes the new route and ETA over the persistent connection.
Deep dives — where the interview is won
Routing at scale: hierarchy makes the graph small, precomputation makes it fast
Dijkstra over a flat world graph with billions of edges is hopeless — a cross-country query would touch hundreds of millions of nodes. The production answer has two parts. First, partition the graph into routing tiles (geohash-addressed chunks with explicit boundary connections) so a routing server only loads the neighbourhoods a query passes through — a brief nod to geo-indexing, which the proximity-service question covers in depth. Second, make the graph hierarchical: roughly three layers — local streets, arterials, motorways. A 500 km route spends its middle 490 km purely in the motorway layer, touching local tiles only near the endpoints, which cuts the search space by orders of magnitude.
On top of that sit precomputation techniques worth naming: contraction hierarchies add shortcut edges so common long-haul segments collapse to single hops, and A* with landmarks gives tighter distance bounds than the raw heuristic. The trade this buys: queries drop from seconds to milliseconds, paid for by hours of preprocessing whenever the base map changes — which is fine, because road topology changes slowly. Live traffic changes fast, but it only re-weights existing edges; it never restructures the hierarchy.
ETA is a prediction problem, not a measurement problem
The naive ETA sums current segment speeds along the route — wrong for any trip over ~15 minutes, because you'll reach the motorway in 40 minutes, and what matters is its speed then, not now. So ETA blends two signals per segment: a historical profile (speed by time-of-day and day-of-week) and live speeds derived from the location firehose, feeding a model that predicts each segment's cost at your projected arrival time at that segment. That's also the honest place to say "ML model" in this interview — it genuinely is one, and its features are exactly the pipeline outputs already in the design.
Getting live speeds from raw GPS requires map-matching: points are noisy (urban canyons reflect signals, tunnels drop them) and must be snapped to road segments — a parallel road ambiguity classically resolved with a hidden Markov model over candidate segments. Then re-routing closes the loop: the navigation session tracks the active route's segments, and when the traffic pipeline degrades one past a threshold, routing re-runs and the client gets a push. Threshold-triggered, not periodic — re-running A* every few seconds per driver would waste the CPU the estimates said was the scarce resource.
Tiles are a build pipeline plus a CDN — keep app servers out of it
All ~100 PB of tiles are precomputed offline from map source data, at every zoom level, and published to object storage. Zoom levels are literally precomputed aggregation: each zoom-N tile summarises four zoom-N+1 tiles, so panning at any altitude costs the same few hundred KB. Clients compute tile IDs themselves from the viewport, so the serving path is client → CDN → (miss) → S3, with cache hit rates in the high 90s because the tile grid is identical for everyone. At ~60 GB/s of egress, the CDN isn't an optimisation — it is the serving system.
The modern refinement is vector tiles (.mvt) over raster PNGs: geometry and labels instead of pixels, styled on-device. They're smaller, one tile set serves every visual style including dark mode and rotated labels, and they enable smooth zoom interpolation. The cost is client CPU/GPU for rendering, which current phones absorb easily. Raster remains the fallback for very low-end devices and static embeds.
Surviving 3M location writes a second by making ingest do almost nothing
The ingest tier's whole job is to accept a batch, ack, and append to Kafka — no validation beyond schema, no synchronous DB write, no fan-out. Stateless ingest nodes behind the load balancer scale linearly, and Kafka partitioned by user_id (or geohash region for the traffic consumers) absorbs the firehose as sequential disk writes, which is exactly what Kafka is for. Every expensive step — map-matching, speed aggregation, history persistence — happens in consumers that can lag seconds behind without any user noticing.
This is also the availability story: if Cassandra is slow or the traffic pipeline is down, ingestion doesn't care — the stream buffers and consumers catch up. Traffic data degrades gracefully to historical profiles, and navigation keeps working with slightly staler ETAs. The one thing I'd protect jealously is Kafka itself: regional clusters, so a device talks to its nearest region and no GPS point crosses an ocean before being acked.
Follow-ups you should expect
How do you snap noisy GPS traces to actual roads?
Raster or vector tiles?
How does re-routing work when I miss a turn?
How would you support offline maps?
Where does the privacy story bite?
Where candidates lose the room
- Running shortest-path over one flat world graph — the hierarchy and tiling is the routing answer; without it nothing else matters.
- Storing tiles in a relational database or serving them through app servers — it's static content at 100 PB; object storage and CDN or you've missed the point.
- One HTTP request per GPS point — 60M QPS of self-inflicted load and a dead battery; batching is the first thing to say about ingestion.
- Conflating display tiles with the routing graph — same streets, different datasets, different pipelines; blending them signals you haven't thought about either.
- Computing ETA from current speeds only — a 45-minute trip needs predicted segment speeds at arrival time, which is why historical profiles and the stream pipeline exist.