Design Google Maps
"Maps" is the word that hides the trap. It is not one system — it is four, with almost nothing in common, glued together behind one app. The senior move is to refuse to design "Maps" and instead design the four workloads separately, because they have opposite read/write shapes.
Everything downstream follows from that split. A tile that was correct yesterday is still correct today, so we treat tiles like static assets and lean entirely on caching (lesson 06). A road graph changes monthly, not per-request, so we are allowed to spend hours of offline batch compute to make the online query cheap (DDIA Ch. 10). Traffic changes every few seconds, so it is a stream we layer on top of the graph rather than into it (DDIA Ch. 11). And the phone in a tunnel must still draw the map, so the client is a first-class cache, not an afterthought.
1. Clarify the contract
Treat the prompt as a product contract before a box diagram. The system must:
- Render the map at ~20 zoom levels, pan/zoom smoothly — serve tiles for any
(z, x, y)on screen. - Search places — text/geo lookup returning POIs (covered in depth by C22's geo index; here it is a satellite).
- Compute a route between two points and an ETA, fast enough to feel instant — sub-100ms server time is the bar.
- Reflect live traffic in ETAs and route choice, within seconds of the world changing.
- Degrade offline — a phone with a downloaded region must still render and (ideally) route.
And, just as important, what it need not do: tiles need no strong consistency (a tile a few hours stale is invisible to a user); routing need not return the provably-optimal path (a path within ~1% of optimal is indistinguishable to a driver); traffic ingestion need not be transactional (a single dropped GPS ping changes nothing). Naming these "don't need" items is what frees the design to be cheap where it can be.
2. Put numbers on the shape
Two calculations do all the architectural work. Everything else is a footnote to them.
Tile volume — why you cannot store, but can cache
The world is tiled with a quadtree: zoom level z divides the world into 4^z tiles (each level quarters the previous tile). Summing a full pyramid from z=0 to z=20:
∑z=020 4z = (421 − 1) / 3 ≈ 4.4·1012 / 3 ≈ 1.4 × 1012 tiles
That is ~1.4 trillion tiles. At, say, 20 KB per tile that is on the order of tens of petabytes per render style — and you have several styles (road, satellite, terrain) and several seasons. Storing every tile precomputed is enormous but, crucially, tractable as cold object storage; what you cannot do is serve it from a database on the request path. The saving grace is the access distribution: tile traffic is brutally skewed. Almost nobody requests z=20 over the open ocean. The hot set — populated areas at the zoom levels people actually browse — is a tiny fraction of the pyramid yet serves the overwhelming majority of requests. That single fact ("trillions stored, kilobytes-worth hot") is the entire reason a CDN works here, and it is the number you put on the table.
Routing — why plain Dijkstra is hopeless
A continental road network has on the order of 10^8 nodes (intersections) and a similar number of edges. Dijkstra explores nodes in expanding rings of distance from the origin; a coast-to-coast query touches a large fraction of the continent — potentially tens of millions of nodes — per request. At even 100 ns of work per node, that is 10^7 · 10^{-7} = 1 second of CPU per route, single-threaded, and you have millions of route requests per second. Plain Dijkstra is off by three to four orders of magnitude. The fix is not a faster Dijkstra; it is to not search the whole graph at runtime. Precomputation — contraction hierarchies (CH) — adds "shortcut" edges so a query only touches a thin upward-then-downward frontier, cutting query work by roughly 1000× and bringing continental routes into the sub-100ms range. We derive this in deep dive 2.
3. Define the surface area
Keep the API small and let it expose product operations, not internal layout. Note the verbs: tiles and search and routes are all GET (cacheable reads); only traffic is a write, and it is an async ingest, never a synchronous request.
| API / operation | Shape | Why it exists |
|---|---|---|
GET /tiles/{z}/{x}/{y}.{fmt} | Immutable blob, long Cache-Control | Render the map. CDN-served; origin almost never touched for hot tiles. |
GET /route?from=&to=&t= | Cacheable read, CH query | Compute path + ETA. t is the traffic-snapshot version so responses are reproducible. |
GET /places/search?q=&bbox= | Geo + text index | Find POIs. Geo-cell mechanics live in C22. |
POST /traffic/ingest (internal) | High-volume stream | GPS probe pings → segment speeds. Never on a user's request path. |
4. Model the data — four engines, on purpose
The data model is the architecture, and here the point is that the four datasets live in four different kinds of store, each chosen for its read/write shape. If you let one store try to hold all four, you have already lost.
| Dataset | Write rate | Read shape | Where it lives |
|---|---|---|---|
| Tiles | Rebuilt in batch (weeks/months) | Massive, skewed, immutable reads | Object store + CDN. DDIA Ch. 3 read-optimised, never updated in place. |
| Road graph + CH shortcuts | Rebuilt in batch (monthly) | Latency-critical graph queries | In-memory on routing servers; rebuilt offline, shipped as a versioned artifact. |
| Traffic overlay | Streaming, seconds | Keyed lookup by segment ID | Fast KV (Redis / in-memory map): segment_id → speed, ts. Sidecar to the graph. |
| Places / POI | Slow edits | Geo + text search | Geo-index (C22). Out of scope here beyond the API. |
The road graph and the traffic overlay deserve attention because they share an ID space but nothing else. The graph stores topology — edge(u,v) with a static base cost (length, speed limit, road class). The overlay stores only segment_id → current_speed. At query time the router reads the static cost and multiplies/adds the live penalty. The graph is the durable, slowly-rebuilt canonical truth; the overlay is volatile and disposable. Keeping them separate is the whole trick of deep dive 3.
5. Linearized design
Walk a request through each of the four subsystems; they barely interact, which is the point.
- 1. Build tiles (offline batch). A pipeline renders the base map into a
(z,x,y)tile pyramid and writes immutable objects to blob storage. This is a batch job (DDIA Ch. 10), run when source map data changes — never on the request path. - 2. Serve tiles (read path). The phone requests visible tiles; the CDN serves them from a PoP near the user. A miss falls back to an origin shield, then to object storage. Because tiles are immutable, cache TTLs are effectively infinite and invalidation is by URL version, not purge.
- 3. Build the routing graph (offline batch). Ingest road data → build the graph → run contraction-hierarchy preprocessing to add shortcut edges. Output is a versioned, read-only graph artifact loaded into memory on every routing server.
- 4. Ingest traffic (stream). Millions of GPS probes flow in, get map-matched to segments, aggregated into per-segment speeds, and written to the traffic KV with a timestamp. A bad or sparse feed is damped, not trusted blindly.
- 5. Compute a route (read path). The routing service runs a bidirectional CH query over the in-memory graph, reading live penalties from the traffic overlay for each edge it touches. Sub-100ms, no graph mutation.
- 6. Cache on the client. The phone caches rendered tiles and recent routes, and (for downloaded regions) a slice of the graph, so it degrades gracefully when the network drops.
6. Deep dives
Deep dive 1 — Tiles are immutable, read-optimised data
This is DDIA Ch. 3's core idea applied to images: data you never mutate in place is the easiest data in the world to scale, because every layer of the stack can cache it without a coherence protocol. A tile at (z,x,y) for a given style version is a value, not a record — given the key, the bytes are fixed forever. So we make the key carry a version (/v7/tiles/12/2045/1362.webp) and set effectively-infinite cache lifetimes. When the map is re-rendered, we don't invalidate — we bump v7→v8, and old URLs simply stop being requested. No purge storm, no cache stampede.
Raster vs vector is the one real choice here. Raster tiles (pre-rendered PNG/WebP) are trivial to cache and render but bake in the style — changing label language or dark mode means re-rendering. Vector tiles ship geometry and let the client draw, enabling client-side restyling, rotation, and smooth zoom, at the cost of a heavier client and a tile that is still the same cache-friendly immutable blob. Modern Maps is vector; the immutability argument is identical either way. Connect this back to lesson 06: the trillion-tile pyramid is only servable because the access distribution is so skewed that the hot set fits in CDN RAM. The numbers from §2 are what make "just put a CDN in front" a serious answer rather than a hand-wave.
Deep dive 2 — Routing needs precomputation, not runtime Dijkstra
This is the sharpest part of the case, so derive it. Plain Dijkstra from your house to a city 3000 km away expands a roughly circular frontier that grows until it engulfs the destination — touching a large fraction of the continent's 10^8 nodes. A* with a straight-line heuristic helps (it stretches the frontier toward the goal) but in the worst case still explores millions of nodes. Neither survives a millions-QPS production load.
The structural insight is that long routes nearly always funnel onto a small number of important roads (highways). Contraction hierarchies exploit this with an offline preprocessing pass: order nodes by "importance," then "contract" them one at a time from least to most important, inserting a shortcut edge whenever removing a node would otherwise break a shortest path. The result is a layered graph where a query only ever needs to move upward in importance from the source, upward from the target, and meet in the middle — a bidirectional search that touches a few hundred to a few thousand nodes instead of millions. That is the ~1000× we put in the KPI grid: from ~1 s of CPU down to well under 100 ms.
The cost of CH is exactly the cost we said we could afford: an expensive offline batch build (hours over the continental graph) in exchange for a cheap online query. This is the batch/serving split of DDIA Ch. 10 made concrete — precompute a derived structure so the request path is trivial. The graph artifact is versioned and immutable for the life of a deploy, which is also why routing servers can hold it in RAM and shard by geography without coordination (lesson 07). Edge cases — turn restrictions, road closures, vehicle profiles — are handled by building per-profile graphs or by edge flags the query respects, not by abandoning CH.
Deep dive 3 — Traffic is an overlay, never a graph mutation
The tempting design is to write live speeds into the edge weights of the routing graph. It is wrong, and saying why is a senior signal. The CH artifact is precomputed and immutable — its shortcuts encode shortest paths under the base weights. Mutating edge weights would invalidate the shortcuts (a shortcut that was optimal at free-flow speed may not be under congestion), forcing a re-preprocess, which takes hours. You cannot re-run a multi-hour batch job every few seconds.
So traffic lives as a separate overlay: a fast KV map segment_id → (speed, timestamp) updated by the stream. At query time, when the CH search relaxes an edge it reads the static base cost and applies the live penalty as a multiplier. Updates are then O(1) and reversible — a new speed is one KV write; if a feed goes bad you simply stop reading it and fall back to base weights, instantly and safely. This is the DDIA Ch. 11 streaming view sitting beside the DDIA Ch. 10 batch artifact: the canonical truth is rebuilt slowly and in bulk; the volatile signal is layered on at read time. (Production CH variants like "customizable contraction hierarchies" go further, allowing fast metric-only recustomization without re-ordering nodes — but the principle is the same: keep the topology stable, vary the weights cheaply.)
The honesty note: traffic-aware routing weakens CH's guarantee slightly, since the precomputed hierarchy assumed base weights. In practice the hierarchy of important roads is stable under congestion (a highway is still a highway when it's slow), so the approximation is excellent — and "approximately optimal" is exactly what §1 said we are allowed to be.
7. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Raster vs vector tiles | simple CDN serving, light client | style baked in; re-render to change | basic / embedded maps |
| CH precompute vs runtime Dijkstra | ~1000× faster queries, sub-100ms | hours of offline build; rebuild on map change | always, at continental scale |
| Traffic overlay vs weight mutation | O(1) reversible updates, stable CH | slightly approximate optimality | any live-traffic system |
| Fresh traffic vs stable route | better ETA | route churn / re-route flapping | active navigation mode |
| Client cache vs server freshness | offline + instant pan/zoom | stale map / stale traffic | mobile, intermittent network |
The sharpest trade-off is the third row, because it is the one most candidates get wrong. Putting live traffic into the edge weights sounds like the clean, single-source-of-truth design — but it couples a per-second signal to a per-month artifact and forces you to re-run an hours-long preprocessing job at streaming cadence, which is impossible. The overlay decouples the two clocks: the graph changes on map-update time, the overlay changes on traffic time, and the query joins them at read time. That decoupling is the difference between a system that ships and one that melts.
8. Failure modes
| Failure | Mitigation |
|---|---|
| Tile hot spot (viral location, big event) | CDN + origin shielding; immutable URLs make caching trivial; hot set is tiny so PoP RAM absorbs it. |
| Bad / sparse traffic feed | Validate, clamp, and damp live speeds; on anomaly, drop the overlay and fall back to base weights — reversible because it's a separate store. |
| Routing service overload / outage | Serve cached routes for popular commutes; degrade to base-weight (no-traffic) routing; shed load (lesson 13). |
| Map / graph update breaks clients | Version tile schemas and graph artifacts; serve old version until clients migrate; never mutate in place. |
| Client offline | Downloaded region: client renders cached tiles and routes over a local graph slice; sync when network returns. |
9. Interview Q&A
- Why don't you run plain Dijkstra over the road graph, and what precomputation makes continental routing sub-100ms? (senior answer) A continental graph has ~10⁸ nodes; Dijkstra expands a frontier that engulfs a large fraction of the continent — roughly a second of single-threaded CPU per long route, hopeless at millions of QPS. The fix isn't a faster search, it's to not search the whole graph: contraction hierarchies precompute shortcut edges offline so a bidirectional query climbs from source and destination onto a small "spine" of important roads and meets in the middle, touching hundreds of nodes instead of millions — about a 1000× cut, into the sub-100ms range. It's the batch/serving split: pay hours offline to make the online query trivial.
- How do you store and serve a trillion tiles? (senior answer) You don't serve them from a database — you precompute them as immutable blobs in object storage and front them with a CDN. The full z=0..20 pyramid is ~1.4 × 10¹² tiles, but the access distribution is brutally skewed: the hot set (populated areas, common zooms) is a tiny fraction yet serves nearly all traffic, so it fits in PoP RAM. Immutability means cache TTLs are effectively infinite and "updates" are version bumps in the URL, not purges.
- Why not just write live traffic into the graph's edge weights? (senior answer) Because the CH artifact's shortcuts are precomputed under base weights; mutating weights invalidates them and forces an hours-long re-preprocess — at streaming cadence that's impossible. Traffic lives as a separate overlay KV (segment→speed) read at query time and applied as a penalty. Updates are O(1) and reversible: a bad feed is dropped instantly with a fallback to base weights. It's a Ch. 11 stream layered beside a Ch. 10 batch artifact.
- Doesn't traffic-aware routing break CH's optimality? (senior answer) Slightly — the hierarchy was built assuming base weights. But the importance hierarchy of roads is stable under congestion (a slow highway is still a highway), so the result stays within a fraction of optimal, which is indistinguishable to a driver. Production uses customizable CH to recustomize metrics cheaply without re-ordering nodes when needed.
- Raster or vector tiles? (senior answer) Both are immutable, cache-friendly blobs. Raster is trivial to render but bakes in style, so dark mode / language / rotation need a re-render. Vector ships geometry and restyles client-side at the cost of a heavier client. Modern Maps is vector; the caching story is identical.
- How does the client work offline? (senior answer) Treat the client as a first-class cache: it stores rendered/vector tiles and recent routes, and for downloaded regions a slice of the routing graph, so it renders and even routes with no network. It syncs traffic and map versions opportunistically when connectivity returns. This is why "degrade offline" was an explicit contract item, not an afterthought.
- What's the consistency requirement across the four subsystems? (senior answer) Deliberately weak everywhere. Tiles tolerate hours of staleness; routes need only approximate optimality; a single dropped GPS probe is invisible; traffic just needs to be seconds-fresh. Naming "what doesn't need strong consistency" is what lets each subsystem pick the cheap, cache-and-stream-friendly design.
- How do you shard the routing service? (senior answer) The graph artifact is read-only and versioned, so you can replicate it freely and shard by geography, holding regional graphs in RAM with overlap at boundaries for cross-region routes (lesson 07). No write coordination is needed because nothing mutates online — the only "writes" are the periodic artifact swaps.
Related foundation lessons
Read alongside: lesson 06 (caching) — the skewed tile distribution is exactly why a CDN turns a trillion-tile pyramid into a tiny hot set; lesson 14 (optimisation) — CH is the canonical "precompute a derived structure to make the request path trivial" move; lesson 07 (partitioning) — the read-only graph artifact shards by geography with no write coordination; lesson 13 (fault tolerance) — overlay fallback and route caching are graceful-degradation patterns. Cross-link with C22 (geospatial indexes), which owns the geo-cell / quadtree mechanics that the place-search path and tile addressing both rely on — this case treats geo cells as a known primitive and focuses on the four-workload split instead.