The whole design, in writing
Learn system design by building a mapping and navigation service like Google Maps step by step. An interactive guide covering map tiles and CDN delivery, the road graph, shortest-path routing with A* and contraction hierarchies, traffic-aware ETAs, geocoding, and scaling.
Every step of the build above, written out: the problem each piece solves, the option that was taken and the ones that were not, the numbers, and how it fails in production.
The big idea
What is Google Maps?
Render the whole world as a smooth, zoomable map, and compute the fastest route between any two points — accounting for live traffic — in well under a second, for billions of users. Two very different problems live here: drawing the map and routing over it.
Pre-render the map into cacheable tiles served from the edge, and model roads as a graph you run shortest-path search over. Make routing fast with precomputation, fold in live traffic for ETAs, and add geocoding to connect names to places.
What the new pieces do
- Userclient
- Pans and zooms the map, searches places, and asks for directions with a live ETA — all expected to feel instant while moving.
Step 1 · Draw the world
Map tiles
You can’t send the entire planet’s map to a phone, nor re-render it per request. Yet panning and zooming must feel instant at every zoom level, everywhere.
You can’t send the planet’s map to a phone or re-render it per request. How do you make pan/zoom feel instant everywhere?
Rendering on demand for billions of pans/zooms is enormously expensive and barely cacheable since every viewport differs. Precompute reusable pieces instead.
Small tiles addressed by zoom/x/y let the client fetch only what’s in view; tiles rarely change, so they edge-cache beautifully and load fast worldwide. "Render the world" becomes "fetch a few static images."
The planet’s map data is far too large to download to a phone, and would be stale immediately. The client should request just the tiles in its viewport, rendered ahead of time.
Pre-render the map into tiles — small square images (or vector tiles) addressed by zoom / x / y. The client requests only the tiles in view; a Tile Service serves them from a CDN-fronted store. Since tiles rarely change, they cache beautifully.
- z/x/ytile address
- CDNedge cached
- viewportonly fetched
What the new pieces do
- Maps APIbackend
- Routes the three core requests: map tiles to render, route computations, and place/address lookups. The front door to every map feature.
- Tile Servicecache
- Serves the little square images (or vector tiles) that tile together into the map, addressed by zoom level and x/y grid coordinates.
- Tile Store + CDNstore
- Pre-rendered tiles in cheap storage, served from a CDN. Tiles change rarely, so they cache at the edge and load fast worldwide.
Step 2 · Roads as math
The road graph
Directions aren’t about images — they’re about connectivity. To compute a route you need a structure that captures which roads connect to which, and how “costly” each segment is.
Directions aren’t about images — they’re about connectivity. What structure do you compute routes over?
Tiles are pixels for looking at, not connectivity for computing over — you can’t route on images. Drawing and routing are different problems needing different structures.
A flat list of roads doesn’t capture which connects to which, turn restrictions, or costs — everything routing needs. You need explicit connectivity with weights.
Nodes are intersections, edges are road segments weighted by length and typical speed (plus one-ways and turn restrictions). Routing becomes shortest-path over this graph — separate from the visual tiles.
Model the map as a graph: intersections are nodes, road segments are edges weighted by length and typical speed (plus one-ways and turn restrictions). Routing becomes a shortest-path problem over this graph.
What the new pieces do
- Road Graphstore
- The map as a graph: intersections are nodes, road segments are weighted edges (by length/speed). All routing is graph search over this.
Step 3 · Find the way
Shortest-path routing
Given start and end nodes, you need the lowest-cost path through a graph with hundreds of millions of edges — and a plain Dijkstra exploration would crawl outward over an enormous area.
Find the lowest-cost path in a graph with hundreds of millions of edges. Plain Dijkstra crawls outward everywhere. Better?
Enumerating all paths is exponential — infeasible on a continental graph. You need a guided search that provably finds the optimum without exploring everything.
The heuristic (as-the-crow-flies distance to the goal) steers the search toward the destination instead of expanding in all directions — far fewer nodes explored, same optimal path.
Pure greedy best-first isn’t optimal — it can charge toward the goal down a dead-end or slow road. A* combines goal-direction WITH actual cost-so-far to stay optimal.
A Routing Engine runs A*: Dijkstra guided by a heuristic (straight-line distance to the goal) so the search heads toward the destination instead of expanding in all directions. Far fewer nodes explored, same optimal path.
What the new pieces do
- Routing Engineservice
- Computes the best route between two points over the road graph, accounting for road types, turn restrictions and, later, live traffic.
Back of the envelope
- A* = Dijkstra + heuristic
- straight-line distance to the goal
- heuristic steers toward destination
- a fraction of the nodes explored
- admissible ⇒ still optimal
- never overestimates real distance
Step 4 · Make it instant
Precompute for speed
Even A* is too slow for continental routes at query time, and you serve millions of route requests per second. Exploring the raw graph on every request simply won’t hit sub-second latency.
Even A* is too slow for continental routes at millions of queries/sec. How do you get millisecond long-distance routes?
More machines lower cost-per-query but each continental A* is still slow — you can’t parallelize one path search enough for sub-second. Do less work per query, not more hardware.
There are astronomically many origin-destination pairs — precomputing all routes is impossible to store. You precompute reusable shortcuts, not full answers.
Heavy offline preprocessing builds "highway" shortcut edges; online queries hop over them, skipping most local roads. Long routes become a few hops at the top of a hierarchy — milliseconds. The offline/online split again.
Precompute shortcuts with contraction hierarchies (or highway/transit hierarchies): collapse the graph so long routes hop over precomputed “highways” instead of every local road. Queries then run in milliseconds by skipping most of the graph.
- offlineshortcuts built
- msroute query
- continentalin real time
Back of the envelope
- offline: build shortcut "highways"
- heavy preprocessing, done once
- online: a few hops at the top
- skip most local roads
- continental route ⇒ ms
- trade build time for query time
Step 5 · Account for traffic
Live ETAs
The shortest route by distance isn’t the fastest in a jam, and a static ETA is wrong the moment congestion changes. You need to know current speeds on every road.
The shortest route by distance isn’t fastest in a jam, and you need CURRENT speeds on every road. Where do they come from?
Physical sensors on every road on earth are impossibly expensive and sparse. You already have hundreds of millions of moving sensors — the users’ phones.
Every moving user is a sensor; aggregating anonymized location pings gives live speed per segment. The ETA service weights routes by these (plus historical patterns), and routing re-weights edges to avoid jams.
Time-of-day priors help (and are a fallback), but can’t see today’s accident or event-driven jam. Real ETAs need live ground truth, which the crowd of moving users provides.
Phones stream anonymized Location Pings; aggregating them gives live Traffic Data — current speed per segment. The ETA Service weights the route by these speeds (and historical patterns) to estimate arrival, and routing re-weights edges to avoid jams.
What the new pieces do
- ETA Serviceservice
- Turns a route into a time estimate using live and historical speeds per segment, so the ETA reflects actual conditions, not just distance.
- Traffic Datastore
- Current speed per road segment, aggregated from millions of anonymized GPS pings. Feeds both ETAs and re-routing around jams.
- Location Pingsbus
- A firehose of anonymized location updates from phones in motion. Aggregated into live traffic speeds that keep ETAs and routes honest.
Back of the envelope
- every moving phone = a sensor
- 100Ms of anonymized pings
- aggregate ⇒ live speed / segment
- real-time ground truth
- re-weight edges ⇒ avoid jams
- fastest, not just shortest
Step 6 · Names to places
Geocoding
Users type “Eiffel Tower” or “221B Baker St”, not latitude/longitude. The router and map need coordinates, and search results need human-readable addresses back.
Users type "Eiffel Tower" or "221B Baker St", but the router and tiles need coordinates. How do you bridge them?
Forcing coordinates is hostile to users who think in names and addresses. The system must translate human input into coordinates, not push that burden onto people.
Graph nodes are intersections, not a searchable place/address index — and addresses don’t map cleanly to nodes. Place lookup is its own retrieval problem with ranking and autocomplete.
Geocoding (and reverse geocoding) translates names/addresses to lat-lng and back, backed by a places index with autocomplete and relevance/distance ranking — feeding clean coordinates into routing and the map.
A Geocoding service translates addresses and place names into coordinates (and reverse-geocodes coordinates into addresses), backed by a places index. It’s the bridge between what users type and what the graph and tiles understand.
What the new pieces do
- Geocodingservice
- Translates a typed address or place name into coordinates (and back), so “coffee near me” becomes points the map and router can use.
Step 7 · Scale the planet
The sharp edges
Billions of tile and route requests, a graph too big for one machine, and traffic that shifts by the minute. No single server holds the world or serves that load.
Lean on the CDN for tiles (most requests never hit your origin), partition the road graph by region with cross-region links for long routes, and continuously update edge weights from the traffic stream. Cache popular routes and precomputed hierarchies per region.
You did it
You just designed Google Maps.
Everything you assembled, in order
- Pre-rendered z/x/y map tiles served from a CDN make browsing instant.
- Roads modeled as a weighted graph of intersections and segments.
- A* routing (Dijkstra + heuristic) finds optimal paths efficiently.
- Contraction hierarchies precompute shortcuts for millisecond long-distance routes.
- Crowdsourced GPS pings aggregate into live traffic for honest ETAs and re-routing.
- Geocoding bridges typed addresses/places to coordinates and back.
- CDN tiles plus region-partitioned graphs scale to billions of requests.