Design Google Maps
Design Maps: serve map tiles from a CDN, route over a road graph with Dijkstra/A* and contraction hierarchies, compute ETA from live traffic ingestion, and geocode addresses — anchored on partitioning a continent-sized road graph so routing stays fast.
Ask for directions across a country and a textbook says “run Dijkstra”. Try it on a real road graph — tens of millions of intersections, hundreds of millions of road segments — and a single query explores half the continent before it finds the destination, taking seconds per request when you need milliseconds at planetary QPS. Maps is really three hard systems wearing one app: a tile service that paints the world, a routing engine that answers “fastest path” faster than brute force allows, and a traffic pipeline that keeps the answer honest as roads jam. The unifying trick across all three is precomputation: do the continent-scale work once, offline, so each live query touches only a sliver of it.
After this lesson you’ll understand why “just run Dijkstra” fails at planetary scale, how offline precomputation makes real-time routing possible, and why traffic data must be separated from the graph structure to avoid rebuilding the whole thing every minute.
Requirements
- Functional: render the map (pan/zoom), find the fastest route between two points, show an ETA that reflects current traffic, and turn an address into coordinates (geocoding) and back.
- Non-functional: very read-heavy and globally distributed; tiles and routes are requested everywhere at once. Tiles are near-static and must be fast (served from the edge). Routing must be low-latency despite a graph far too large to search naively. ETAs must track reality, so traffic ingestion is a continuous, high-volume stream.
The through-line is that almost nothing can be computed from scratch per request at this scale. The base map changes rarely, the road graph changes slowly, and traffic changes fast but is shared across all users on a road — so the design is dominated by what you precompute and where you cache it.
Estimation
The map is a pyramid of tiles: at zoom level z the world is a 2^z × 2^z grid of 256-pixel images. That is 1 tile at z0, 4 at z1, and roughly 4^z at level z — so the full pyramid to z20 is hundreds of billions of tiles, terabytes to petabytes of mostly-static imagery. They are written once (per map refresh) and read billions of times: a textbook CDN workload. Routing is the opposite extreme — small data (a country’s road graph fits in memory, single-digit GB) but expensive computation, where a naive search visits millions of nodes. So the two halves of Maps stress completely different resources: tiles stress storage and edge bandwidth, routing stresses CPU and clever algorithms.
High-level design
Tiles flow from object storage through a CDN to the client. A route request goes to a routing service holding the preprocessed road graph; it consults the latest traffic weights and returns a path. Geocoding is its own service translating text to coordinates.
The deep dives that matter are how routing escapes brute-force search, and how traffic re-weights the graph without invalidating the precomputation.
Deep dive
Tiles and the CDN
A tile is addressed by (z, x, y) — zoom level and grid coordinates — so the client computes exactly which tiles its viewport needs and requests them by name. Because a tile’s content is identical for every user and changes only on a map refresh, it is the ideal CDN object: precompute the pyramid into object storage, front it with a CDN, and serve from the edge POP nearest the user. Cache keys are immutable per map version, so invalidation is rare and a version bump rotates everything cleanly. Vector tiles (geometry plus styling, rendered on the client) push this further: smaller payloads, restyleable without re-rendering server-side, and crisp at any zoom. The point is that the entire base-map experience is a static-content distribution problem, fully separate from the dynamic routing engine.
Routing: why plain Dijkstra loses
Dijkstra and A* are correct but explore too much. Dijkstra fans out in all directions until it reaches the target; on a continental graph that is millions of node expansions per query. A* with a straight-line heuristic helps but still explores a wide cone. At Maps’ QPS, neither is affordable. The production answer is preprocessing: spend hours offline transforming the graph so that online queries are cheap.
Contraction hierarchies (CH) are the canonical technique. Rank every node by importance, then “contract” them from least to most important: removing a node, add shortcut edges between its neighbors that preserve shortest-path distances. After contraction, a query runs a bidirectional search that only ever moves upward in the hierarchy — from the source up to important highway-like nodes, and from the target up to meet it. Long routes ride a handful of high-level shortcuts (think: get onto the motorway, stay on it, exit near the destination) instead of crawling through every local street. The result is queries that touch thousands of nodes instead of millions — orders of magnitude faster, while still returning the exact shortest path.
▸Why this works
Why does contracting nodes into shortcuts make queries faster without changing the answer? Because most of a long trip is spent on a few major roads, and a query repeatedly re-derives that obvious fact. A shortcut edge bakes in “the cheapest way from this on-ramp to that off-ramp is already known to cost X” so the search never re-explores the streets between them. The hierarchy guarantees a property: for any shortest path there exists an equivalent path that first only goes “up” in importance and then only “down”, so a search that refuses to descend until the two frontiers meet can ignore the vast low-level interior. You trade preprocessing time and extra shortcut edges (more memory) for query speed — exactly the precomputation bargain that runs through all of Maps. CH is also why a road closure is awkward: it can invalidate shortcuts, so traffic that changes edge weights needs a scheme that does not force a full recontraction.
Traffic, ETA, and re-weighting
A route is only as good as its edge weights, and real travel time depends on live traffic. Maps ingests a continuous stream of anonymized GPS probes from phones in motion, aggregates speed per road segment, and updates each edge’s current travel-time weight. ETA is then the sum of (possibly traffic-adjusted) edge times along the chosen path, often refined by a model that accounts for time-of-day patterns and historical curves, not just the instantaneous snapshot. The architectural tension is that pure contraction hierarchies bake edge weights into the shortcuts, so changing weights for traffic would demand re-running the expensive contraction. Production systems separate the slow-changing graph structure (preprocessed rarely) from the fast-changing weights (updated continuously), using techniques in the customizable-route-planning family that let live traffic re-weight edges without rebuilding the whole hierarchy. The lesson: partition your precomputation along its rate of change.
Bottlenecks & tradeoffs
The first hard problem is graph partitioning. A continental road graph does not shard cleanly: split it into regions and the routes that cross a boundary need careful stitching at the cut edges (boundary nodes), and a bad partition puts hot, frequently-crossed highways on a seam. Good partitions cut along natural low-traffic boundaries to minimize cross-shard routes — the same “minimize what crosses the boundary” instinct as cell design in the proximity lesson, now applied to a graph cut. The second is the precompute-vs-freshness tension: heavier preprocessing makes queries faster but makes updates (a new road, a closure, a traffic spike) harder to fold in, which is why structure and weights are kept on separate update cadences. The third is the two-workload split: tiles want a fat global CDN and almost no compute; routing wants beefy CPU near the graph and almost no bandwidth — so you scale and even locate them independently rather than as one tier.
A team builds continental routing with plain Dijkstra. It's correct but each query takes seconds because it expands millions of nodes. What preprocessing makes queries touch only thousands of nodes while still returning the exact shortest path?
Maps uses contraction hierarchies, which bake edge weights into shortcuts. Now you must update travel times every minute from live traffic. What's the right architecture?
The unifying technique across tiles, routing, and ETA is _______: do the continent-scale work once, offline — bake the tile pyramid, contract the road graph into shortcuts — so each live request touches only a small slice of the result rather than recomputing from scratch.
- 01Why are map tiles a CDN problem, and how are they addressed and cached?
- 02Why does plain Dijkstra fail for continental routing, and how do contraction hierarchies fix it?
- 03How does live traffic feed ETA without forcing a full re-contraction, and what's the partitioning challenge?
Maps is three systems in one app, unified by precomputation. Tiles are a static-content CDN problem: the world is a pyramid of (z, x, y)-addressed 256-pixel images, precomputed into object storage and served from the edge, with immutable per-version cache keys. Routing cannot use plain Dijkstra at planetary scale — it expands millions of nodes — so the graph is preprocessed into contraction hierarchies: nodes ranked by importance and contracted with distance-preserving shortcut edges, letting a bidirectional query move only upward and touch thousands of nodes while still returning the exact shortest path. Traffic is a continuous GPS-probe stream that re-weights edges for ETA, and because contraction bakes weights into shortcuts, the design separates slow-changing structure from fast-changing weights so live traffic does not force a re-contraction. The recurring hard problems are graph partitioning (cut along natural low-traffic boundaries to minimize cross-shard routes), the precompute-vs-freshness tension (heavier preprocessing means harder updates), and the two-workload split (tiles want a CDN; routing wants CPU) scaled independently. Now when you see a routing problem in a design review — slow queries, stale ETAs, or a re-indexing job that runs for hours — you’ll know to ask: is the graph structure separated from the weights, and is the work that can be done offline actually done offline?
Practice
Start at the top. Tasks go easiest → hardest: recall a fact, apply it to a case, then a senior-level stretch. Open one, attempt it, then reveal.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.