Design Google Maps

Three separable subsystems: rendering the map, finding a route, and **predicting an ETA**. Treat them separately — trying to answer as one system is what makes this question feel overwhelming.

Requirements

Functional

• Display a map at any location and zoom level.
• Navigate from A to B with turn-by-turn directions.
• ETA that accounts for live traffic; reroute when conditions change.
• Search for places.

Non-functional

• Map panning must feel instant.
• Routing under a second, for a continent-scale graph.
• Massive read skew — cities are queried far more than deserts.

1B users, 100M daily route requests ≈ 1,200 requests/second, higher at rush hour
Road network: ~100M road segments globally
Map tiles: 256×256 px, ~20 zoom levels → hundreds of billions of possible tiles

Map tiles

The map is not rendered per request. It is **pre-rendered into a pyramid of square tiles**, one set per zoom level, each tile addressed by (z, x, y).

zoom 0 → 1 tile covering the world
zoom 1 → 4 tiles          (2×2)
zoom 2 → 16 tiles         (4×4)
zoom z → 4^z tiles

Tiles are immutable static images (or vector tiles), so they are perfectly CDN-cacheable — which is why panning is instant. Only populated areas at high zoom are pre-rendered; the rest is generated on demand and cached. Vector tiles are increasingly preferred: the client renders them, which allows rotation, styling and label placement without new downloads.

Geospatial indexing

"What is near me" cannot use a plain B-tree, because two-dimensional proximity has no single sort order. The standard technique is to map 2-D space onto 1-D so ordinary indexes work:

• Geohash — recursively subdivide the world into a grid and encode the path as a

string. Shared prefix ≈ nearby. Simple and widely supported.

• S2 (Google) / H3 (Uber) — space-filling curves over a sphere; better locality and no

distortion near the poles.

• Quadtree — a tree subdivided by density, so dense cities get finer cells.

The catch worth naming: two points either side of a cell boundary can be metres apart with completely different prefixes, so a proximity search must query the target cell **and its neighbours**.

Routing

Dijkstra over 100M nodes takes far too long, so real systems precompute.

Graph partitioning. Split the road network into regions, precompute shortest paths

between region boundary nodes, and at query time route: origin → its boundary → (looked up) → destination's boundary → destination. Long routes touch a handful of regions instead of millions of nodes.

Contraction hierarchies. Rank nodes by importance and precompute shortcut edges that

skip unimportant ones. Queries then run a bidirectional search that only ever moves "upward" in the hierarchy — orders of magnitude faster than plain Dijkstra, at the cost of an expensive preprocessing step.

A\* with a great-circle-distance heuristic is the answer for the interactive case

without heavy preprocessing, and is worth naming as the baseline improvement over Dijkstra.

The road graph is directed and weighted by travel time, not distance — one-way streets, turn restrictions and speed limits all live in the edge model.

Live traffic

Phones report anonymised GPS traces
   → ingest (Kafka)
   → map-matching: snap noisy GPS points to road segments
   → aggregate speed per segment per time bucket
   → update edge weights in the routing graph
   → detect incidents from sudden slowdowns

Map-matching is the non-obvious step: raw GPS is accurate to metres and roads run parallel, so points must be snapped to the most probable road given the trajectory — typically with a hidden Markov model over candidate segments.

Traffic makes edge weights time-dependent, which breaks the assumption behind precomputed shortcuts. The practical resolution: precompute on a historical baseline, then apply live adjustments to the small number of segments in the candidate routes, and recompute periodically rather than continuously.

ETA

Not simply distance ÷ speed limit. It is a prediction over: current speeds per segment, historical speeds for this segment at this time of week, turn and traffic-light delays, weather, and the driver's own behaviour. The important structural point is that ETA must be computed for future arrival times at each segment — you will reach a segment 40 minutes from now, so the prediction must use the expected conditions then, not now. That is why this is a machine-learning problem rather than arithmetic.

Follow-ups to expect

• Rerouting — the client periodically re-requests; the server only proposes a change if

the saving exceeds a threshold, to avoid flapping.

• Multiple route options — k-shortest paths with a diversity constraint.
• Places search — a separate inverted index with geo-filtering, ranked by prominence

and distance.

• Offline maps — download tiles and a regional road graph for on-device routing.
• Privacy — GPS traces must be anonymised and aggregated; individual traces are

identifying.

• Map updates — road data changes; tiles and the routing graph are rebuilt on a

pipeline, not edited live.

Track this problem on the System Design sheet.