The whole design, in writing
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.
Why this piece earns its place
The assumption hiding in “tiles rarely change” is worth saying out loud, because the day a road opens, a tile that edges have been happily serving for years is wrong. I wouldn’t reach for a purge: purging a planet of caches is slow, and a purge that half-lands leaves tiles from two different renders butted up against each other, which on screen looks like the map has torn along a seam. I’d put the render version in the tile path instead, so every tile stays immutable forever, a re-render publishes new paths rather than overwriting old ones, and a client that picks a version at session start sees one self-consistent world all the way through. The second assumption is that you can materialize every tile at every zoom. You can’t — the grid subdivides with each level and most of it is ocean, desert and farmland nobody will ever look at. Pre-render the zooms and the places that actually get traffic, generate the long tail on first request, and let the edge cache it like any other tile.
- 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.
Why this piece earns its place
What this model leaves out is the part that produces embarrassing directions. Nodes and edges express “this road meets that one,” but a route isn’t really a sequence of edges — it’s a sequence of manoeuvres, and a lot of the cost lives in the manoeuvre rather than in the road. Turning left across oncoming traffic at a signal costs far more than continuing straight through the same intersection, and some of those turns are simply illegal, or illegal at certain hours. A plain node-and-edge graph has nowhere to put that: the cost of reaching a node is the same no matter which way you leave it. So in practice you either hang a turn table off each node — a cost for every in-edge/out-edge pair, with a forbidden marker for the restrictions — or you flip to an edge-based graph, where segments become the nodes and turns become the edges, which buys you more nodes but makes turns first-class. Skip it and the router will confidently send someone across three lanes they legally cannot cross.
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.
Why this piece earns its place
The heuristic is the knob here, and the first thing to get right is that it has to be in the same currency as the edge weights. If edges are weighted by travel time, a straight-line distance isn’t comparable to them at all — you divide that distance by the fastest speed anywhere on the network to turn it into a lower bound on time. That conversion is exactly what keeps the heuristic admissible, never overestimating, which is the property that lets A* still return the best route rather than merely a good one. And the divisor is the lever. Use the true network maximum and the bound is safe but weak: on city streets the estimate sits far under the real travel time, the search barely narrows, and you’ve paid for A* while getting close to Dijkstra. Scale the heuristic up and the explored frontier tightens sharply and queries get much faster, but the guarantee is gone and the route returned can be slightly worse than optimal. That’s a trade some production systems take deliberately; what matters is knowing which side you’re on rather than landing there by accident.
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.
Why this piece earns its place
What this bakes in is that the weights were already known when the shortcuts were built. Every shortcut stands for a chain of real segments at a cost frozen at contraction time, so anything that changes the cost underneath one makes that shortcut lie — and it lies quietly, because the query still returns a path and the path still looks plausible. That drives a rule I’d hold to: never express a change as an edit to the graph. A closed road is tempting to simply delete, and deleting it leaves every shortcut built over it intact and still advertising a route through a road that isn’t there. Closures go in as weights — make the segment expensive enough that nothing sane routes over it — so the structure stays valid and only numbers move. Which points at the real split: treat the topology work, the contraction order and the shortcut set, as the expensive thing you rebuild rarely, and keep the costs as a thin layer over it you can recompute cheaply and often. A genuinely new road does need the heavy rebuild, and that runs region by region on its own schedule.
- 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.
Why this piece earns its place
Two things bite once the traffic layer starts closing the loop on itself. The first is that routing around a jam is an intervention, not an observation. Re-weight a blocked arterial and every router in the area produces the same answer in the same minute, so the quiet residential street that was the detour fills up, your own pings duly report it slowing, and you’ve manufactured the next jam — and possibly sent a wall of through-traffic past a school. The defense is to stop treating each request as independent: damp how fast weights are allowed to swing, spread drivers across several plausible alternatives instead of piling everyone onto the single best one, and cap how much load the network will push onto small residential roads whatever the graph says. The second is coverage. A live speed is only as good as the number of distinct devices that produced it, and a quiet road can be swung by one delivery van idling at the kerb. So I’d hold a minimum-sample floor per segment and fall back to that road’s historical profile for the time of day below it, rather than publishing a confident speed built from almost nothing.
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.
Why this piece earns its place
Geocoding hands back a coordinate, and routing needs a position on the graph. Those aren’t the same thing, and the gap between them is where a surprising share of bad directions comes from. A place’s coordinate is usually its centroid, and a centroid sits in the middle of a building, a park or a car park — somewhere with no road under it at all. Snapping it to the nearest segment by raw distance is where it goes wrong: the closest line to a shop on a divided road is often the carriageway running the other way, or the trunk road rather than the service road beside it, and the router then computes a perfectly optimal route to a point the driver cannot actually stop at without carrying on to the next turnaround. So the places index should store an access point, not just a centroid — the entrance, snapped to a specific edge and a direction of travel, checked against one-ways — and routing should take that as the endpoint. Reverse geocoding has the mirror problem, which is why a GPS trace gets map-matched onto the graph rather than snapped to whatever is nearest.
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.
Why this piece earns its place
Partitioning by geography is right, and it concentrates the entire cost of the design into one place: the routes that cross a boundary. A naive cross-region query wants both regions in memory at once, which is exactly what partitioning was supposed to avoid, and long routes are the queries you least want to be slow. So the boundary has to become a first-class object rather than an accident of where you drew the lines. Each region publishes its border nodes; you precompute the costs between the borders of neighbouring regions — a small table, because a region has far fewer border nodes than interior ones — and a crossing query becomes local-to-border, a lookup across, then border-to-local. That makes the cut cheap, and usefully makes it a thing you can refresh on its own cadence. The other thing I’d watch is that geography is a shard key with wildly uneven load: an equal-area grid gives you one cell that is a dense city and its neighbour that is farmland. Cut regions by query volume instead, and accept small dense ones where the traffic actually is.
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.