Google Maps: scope, scale and map tiles

The prompt: "Design Google Maps."

Attempt it for 45 minutes before reading. This is the largest system in Part III (Sections 12–20) and the only one where the core algorithm is genuinely hard — so the most useful thing you can do in those 45 minutes is find out where your own understanding of shortest-path search runs out.

This lesson does the groundwork: scoping a prompt that contains at least five products, sizing the system, and designing the part users actually look at — map tiles. The routing engine, where the hard algorithm lives, is the subject of Google Maps: routing, live traffic, navigation and follow-ups.

Why this one is different

Every other system in this part is an assembly problem: pick the right storage, the right caching, the right fan-out, and connect them well. Maps has all of that and a computational core that ordinary engineering cannot rescue. The routing engine shows that the textbook shortest-path algorithm is roughly four orders of magnitude too slow for a continental route, and no amount of caching or sharding fixes it. The fix is a different algorithm.

That makes scoping unusually important. "Design Google Maps" contains at least five products, and attempting all of them produces a shallow answer to each.

The five questions

1. Which features are in scope? The candidates: viewing the map, searching for a place, routing from A to B, estimating arrival time, turn-by-turn navigation, and live traffic. Propose a scope out loud: map tiles, routing, ETA with live traffic, and navigation as a session. Place search is the problem of Section 18 (Proximity Service) and can be excluded by reference.

2. Which travel modes? Driving alone is one weighted graph. Adding walking and cycling adds more graphs with different rules. Adding public transport adds a timetable problem that is not a weighted-graph problem at all — Follow-ups explains why. Scope to driving, and name the others as extensions.

3. Is real-time traffic in scope? Say yes and mean it, because it is what makes the problem interesting: live traffic turns static edge weights into a continuously updating stream, and that breaks the fastest routing techniques. The routing engine confronts that directly.

4. Are offline maps required? Offline changes the client from a thin renderer into a device holding map data and a routing engine. It is a real requirement for a global product and a follow-up in this design.

5. What scale, and where are the users? Global, which makes tile serving a content delivery network problem and makes the routing graph too large for one machine.

Requirements and scale

Functional: render a map at any location and zoom level; compute a route between two points for a chosen mode; estimate arrival time using current and predicted traffic; guide a user turn by turn, rerouting when they deviate; ingest traffic observations from devices.

Non-functional: a route returned in under 500 ms at the 99th percentile, because it sits in front of a waiting user; tiles delivered fast enough that panning feels continuous; navigation resilient to losing connectivity mid-route; and a client battery cost low enough for an hour of driving.

The numbers

Invented figures for a global mapping product. A day is 100,000 seconds (see Rounding aggressively and staying fast).

Routing load:

200M ÷ 100,000 s = 2,000 route requests/s average, ~6,000/s at peak

That rate is modest by the standards of this course — Section 13 (Design a News Feed System) was doing 90,000 feed reads per second. What makes it hard is the cost of a single request, which The routing engine quantifies.

Location updates during navigation:

50M sessions × 30 min × 60 s = 90 billion potential position fixes/day at 1 Hz

90B ÷ 100,000 s = 900,000 positions/s

That is the largest ingest number in the system. Reduce it on the client: batch 15 seconds of fixes into one upload and the request rate falls to 60,000/s while still carrying 900,000 positions per second. Batching is the cheapest fix available and it also saves radio wake-ups, which is battery.

Tile bandwidth:

100M sessions × 50 tiles × 30 KB (a vector tile) = 150 TB/day

150 TB ÷ 100,000 s = 1.5 GB/s ≈ 12 Gbps average, and 3× that at peak

With raster tiles at ~100 KB each the same traffic is roughly 40 Gbps. Either way it is content delivery network traffic, not origin traffic — and the raster-versus-vector difference being a 3× bandwidth factor is itself an argument for vector, developed below.

Map data volume

The road network of the world, as a routing graph, is on the order of hundreds of millions of nodes and edges. Stored compactly — an edge as a pair of node references, a length, a category, and a travel-time weight, at roughly 20 to 30 bytes — a planet-scale graph is in the range of tens of gigabytes per metric.

The conclusion that matters: the graph is too large for one machine's memory at full detail, which is why The routing engine ends at partitioned graphs, and small enough that a region fits comfortably — which is why offline packs are feasible.

Map tiles and rendering

Before the algorithms, the part users actually look at. It is the most straightforwardly solved component in the design, and getting it wrong wastes the time routing needs.

Why tiles

Rendering a map means drawing roads, labels, water, and buildings for an arbitrary rectangle at an arbitrary zoom. Doing that on demand per user is expensive and, worse, produces a different image for every request — nothing caches.

Tiles fix both. Divide the world into a fixed grid of square images at each zoom level, addressed by (zoom, x, y). Every user viewing the same area at the same zoom requests the same tiles, so tiles cache perfectly at every layer: browser, edge, and origin.

The pyramid

Zoom level 0 is one tile covering the world. Each level quarters every tile of the level above.

At 20 KB per tile, rendering the complete pyramid to zoom 20 would be on the order of tens of petabytes — and pointless, because the overwhelming majority of those tiles are open ocean, desert, or empty land that nobody ever requests.

The practical answer is threefold: pre-render low zooms completely (they are cheap and universally requested), pre-render high zooms only where there is data and demand, and render the rest on demand on first request, then cache it. The tile server becomes a cache with a renderer behind it for misses.

Raster versus vector tiles

Raster tiles are pre-rendered images. The server does the drawing; the client pastes squares together. Simple, works on any device, and predictable to serve.

Vector tiles contain geometry and attributes — road lines, polygon boundaries, place labels — and the client draws them using a style it holds locally.

The label-language row is the decisive one for a global product. With raster tiles, supporting 40 languages means 40 renderings of every tile in the pyramid. With vector tiles, the labels are attributes and the client chooses — one tile set serves every language, every theme, and every rotation.

Recommend vector tiles as the default, with a raster fallback for constrained clients. The bandwidth saving is real but secondary; the reason is that vector tiles decouple content from presentation, which turns a combinatorial explosion of tile sets into one.

Serving

Tiles are immutable for a given map data version, so cache lifetimes can be long and invalidation is handled by versioning the URL path rather than purging caches. Push them onto a content delivery network and the origin sees only misses and newly rendered high zooms.