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.
How to read this: We add one piece at a time, problem then fix, and the diagram grows. Hit Begin.
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.
Design decision: 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?
The call: Pre-render the map into z/x/y tiles served from a CDN. — 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."
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.
Precompute + cache: Tiling turns “render the world” into “fetch a few static images near the viewport”. Immutable, edge-cached tiles make map browsing fast and cheap globally.
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.
Design decision: Directions aren’t about images — they’re about connectivity. What structure do you compute routes over?
The call: A weighted graph: intersections = nodes, segments = edges. — 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.
The map is a weighted graph: Separating the visual tiles from the routing graph is key: one is for looking, the other for computing. Edge weights encode reality — distance, speed limits, legal turns.
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.
Design decision: Find the lowest-cost path in a graph with hundreds of millions of edges. Plain Dijkstra crawls outward everywhere. Better?
The call: A*: Dijkstra guided by a straight-line-distance heuristic. — 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.
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.
A* = Dijkstra + heuristic: The heuristic prunes the search toward the goal. For road networks where “as the crow flies” underestimates real distance, A* finds the optimal route while touching a fraction of the graph.
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.
Design decision: Even A* is too slow for continental routes at millions of queries/sec. How do you get millisecond long-distance routes?
The call: Precompute shortcuts with contraction hierarchies (offline). — 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.
Trade build time for query time: Heavy offline preprocessing builds shortcut edges; online queries ride them. Long-distance routing becomes a few hops at the top of a hierarchy — the offline/online split again.
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.
Design decision: The shortest route by distance isn’t fastest in a jam, and you need CURRENT speeds on every road. Where do they come from?
The call: Aggregate anonymized GPS pings from phones in motion. — 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.
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.
Crowdsourced ground truth: Every moving user is a sensor. Aggregating their motion into per-segment speeds turns the user base itself into the real-time traffic layer that powers honest ETAs and re-routing.
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.
Design decision: Users type "Eiffel Tower" or "221B Baker St", but the router and tiles need coordinates. How do you bridge them?
The call: A Geocoding service: address/place ↔ coordinates, via a places index. — 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.
The text ↔ space bridge: Geocoding plus place search is its own retrieval problem — autocomplete, ranking by relevance and distance — feeding clean coordinates into routing and map display.
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.
Partition space, cache aggressively: Geography is a natural shard key: most routes are local to a region. Edge-cached tiles plus regionally partitioned graphs let the system scale to a planet of users.
You did it
You just designed Google Maps.
- 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.