Google Maps — System Design · Engineering Playbook

Step 1 — Clarify Requirements#

Functional

Serve map tiles (vector or raster) at multiple zoom levels.
Compute the shortest / fastest route between two points on a road network.
Estimate arrival time accounting for current traffic.
Ingest real-time location pings from millions of phones to feed traffic.
Out of scope here: business listings (/system-design/proximity-service-yelp), Street View, indoor navigation.

Non-functional

99.99% availability.
p99 tile fetch under 100 ms; p99 route computation under 500 ms.
1 B MAU; ~10 B route requests/day; ~500 M concurrent location pings during peaks.
Road graph updates daily; traffic updates every minute.

Step 2 — Capacity Estimation#

Tile QPS: a single map view loads ~10 tiles. 1 B MAU × 5 sessions/day × 20 pans = 100 B tile fetches/day = 1.2 M tile fetches/sec average, 5 M peak. Most served from CDN.
Route QPS: 10 B/day = 120 K route requests/sec average, 500 K/sec peak.
Tile storage: world tiled at 20 zoom levels. At zoom 20, ~10^12 tiles; in practice we store only tiles with content (~10^11 tiles × 50 KB each ≈ 5 PB of tiles globally, cacheable indefinitely since the underlying data changes slowly).
Road graph: ~10^8 road segments globally, ~10^9 nodes. Compressed graph ~50 GB in memory per region; full world ~500 GB.
Live traffic pings: 500 M concurrent at 30-second intervals = 17 M pings/sec. After aggregation by road segment, the live-traffic state is only a few GB.

Tile serving is a CDN problem; routing is an in-memory graph problem; traffic is a streaming aggregation problem. Three nearly orthogonal sub-systems.

Step 3 — System Interface#

GET   /tiles/:z/:x/:y.pbf            (vector tile; zoom z, tile coords x,y)
GET   /tiles/:z/:x/:y.png            (raster fallback)

POST  /route
      { origin: {lat,lng}, destination: {lat,lng}, mode: 'car'|'walk'|'bike'|'transit' }
      → { polyline, distance_m, duration_s, steps: [...] }

POST  /traffic/ping
      { device_id, lat, lng, speed, heading, ts }

GET   /eta?origin&destination       (route + duration only, cheaper than full route)

Tiles are served as pre-rendered immutable artifacts with long Cache-Control (a tile changes only when the road network changes). Route requests must be online and dynamic.

Step 4 — High-Level Design#

                                        ┌── tile CDN (planet-scale edge cache) ─→ client
                                        │
client ──→ LB ──→ API gateway ──┬── /tiles ──→ tile origin (object store of pre-rendered tiles)
                                │
                                ├── /route ──→ routing service ──┬→ pre-built road graph (in-memory)
                                │                                ├→ contraction-hierarchies index
                                │                                └→ live traffic overlay
                                │
                                └── /traffic/ping ──→ Kafka ──→ traffic aggregator ──→ live traffic store

   Offline: map data + OSM-style sources → tile renderer → tile store
                                        → graph builder → routing index (CH/CRP)

The routing index is the secret sauce. A naive Dijkstra on a continental road network is 100 ms-1 s; production routing needs 10-50 ms, which requires precomputed shortcuts (contraction hierarchies, customizable route planning, or hub labels).

Step 5 — Data Model#

Tiles (object store, key = z/x/y.pbf):

key: tiles/14/8746/5374.pbf       (vector tile, MapboxVT format)
value: compressed protobuf of all features (roads, buildings, labels) intersecting the tile bbox

Tile versioning: each tile carries a version. Old versions stay cached until TTL expiry; clients fetch new versions when a region updates.

Road graph (binary, memory-mapped on routing servers):

struct Node { id, lat, lng, edges: [edge_id] }
struct Edge { id, from_node, to_node, length_m, speed_limit, road_class }

Plus precomputed contraction-hierarchy shortcuts so most shortest paths skip directly to high-level edges (highways) without exploring side streets.

Live traffic (Redis, sharded by region):

key: traffic:{region}:{segment_id} → { speed_kph, flow, updated_at }

This gets merged in at routing time: each edge’s cost = length / current_speed.

Step 6 — Detailed Design#

Tile rendering pipeline#

Map data (OpenStreetMap-ish sources + Google’s proprietary data + commercial feeds) is ingested into a feature database. A renderer reads features within a tile’s bbox and produces:

tiles/0/0/0      → whole world, one tile (low detail)
tiles/1/0/0..1   → quartered
...
tiles/20/...     → ~50 cm/pixel street-level

Tile rendering is fully offline. A continent re-rendering takes hours; only changed tiles need re-rendering (detected by feature-change diffs against the previous build). New tiles get pushed to the CDN with a new version.

Vector tiles are preferred over raster: smaller (~30 KB vs 100 KB), client-side styled (dark mode, labels in user language), and zoom-fluid (one tile renders at multiple sub-zooms).

Routing: contraction hierarchies#

Plain Dijkstra is too slow for cross-continental routes. Production systems use contraction hierarchies (CH) or similar:

Preprocessing (offline, hours): rank nodes by “importance”; replace each removed node with a shortcut edge through it. Result: a hierarchy where high-rank nodes (highway interchanges) form a thin top layer.
Query (online, ms): bidirectional search from origin and destination, only going “up” the hierarchy. Meets in the middle near the top, total visited nodes ~100-1000 even for 1000+ km routes.

Contraction Hierarchies (CH) — fast queries (10-50 ms), expensive preprocessing (hours). Hard to incorporate live traffic — the shortcut weights depend on the static cost function.

Customizable Route Planning (CRP) — designed for live traffic. Two-level structure where the upper level can be re-weighted in seconds when traffic changes. Slightly slower queries than CH but flexible. Used by production Google Maps.

CRP is the modern choice: the road graph is partitioned into cells; cell-boundary shortcut weights are recomputed in O(seconds) when traffic updates arrive.

ETA prediction#

Naive ETA = route_distance / speed_limit. Real ETA accounts for:

Current traffic on each segment (live overlay).
Historical traffic for the day-of-week / hour-of-day pattern.
ML-predicted slowdowns (a model trained on past trips with similar conditions).

The ML model is consulted as a per-edge multiplier: expected_speed = predicted_factor × free-flow_speed. Inference is cheap because the route is at most a few thousand edges; batched as one tensor request.

Live traffic ingestion#

phone GPS ping ── Kafka topic 'pings' (partitioned by region)
                       │
                       ▼
            map-matching service ── matches (lat,lng) to road segment + direction
                       │
                       ▼
            traffic aggregator ── per-segment rolling-window speed estimate
                       │
                       ▼
            redis: traffic:{region}:{segment_id} = { speed, samples, ts }

Map-matching is non-trivial: a ping at a freeway overpass might be on either the freeway or the surface road below. The matcher uses bearing, recent trajectory, and road geometry to disambiguate.

Aggregation uses a windowed median over ~30 seconds — robust against single-vehicle outliers (a phone in a stopped car at a red light shouldn’t drag the segment’s reported speed to zero if the rest of traffic flows freely).

Privacy#

Pings are sampled and anonymized (per-ping device ID is rotated, location is fuzzed at the start and end of each session). Individual driver paths cannot be reconstructed from the aggregated traffic.

Step 7 — Evaluation & Trade-offs#

Bottleneck #1: tile rendering pipeline keeping up with the world. When OSM has a large import (say, Africa road data refresh), the renderer must re-render millions of tiles. The cost is dominated by I/O and CPU; a fleet of thousands of renderer workers keeps it bounded. The CDN absorbs the impact on clients — old versions stay served until new versions propagate.

Bottleneck #2: routing memory. The continental road graph is ~50-100 GB. A single routing server hosts one or two regions in memory; cross-region routes (NY to LA) require a cross-region query path, typically by partitioning at the country / region border with handoff edges.

Bottleneck #3: live traffic latency. From “a phone slows down” to “the route avoids that segment” takes ~30-60 seconds. Faster than that requires sub-second windowing, which trades stability for responsiveness. For most usecases, 30s is fine; for incidents (an accident closing a freeway), the system relies on explicit reports (Waze-style) in addition to passive inference.

Alternative I’d push back on: serving routes by computing Dijkstra on demand. Naive and pedagogical, but production routing is unrecognizable from the textbook version — the preprocessed index is what makes 10 ms queries possible. Anyone who proposes “just run Dijkstra” hasn’t sized a real graph.

What breaks first at 10× scale: the map-matching service. Pings are heavy (location, time, sensor data) and map-matching is CPU-intensive. Already a major cost at present scale; at 10×, expect to need on-device map-matching (the phone does the work, sends segment IDs instead of raw GPS).

Companies this resembles#

Google Maps, Apple Maps, Mapbox, HERE, TomTom, Waze (traffic-first variant). Cousins include OpenStreetMap (data layer only; routing is third-party).

Proximity Service (Yelp) — different problem on the same geo substrate.
Uber — depends on this design’s routing and ETA primitives.
Content Delivery Network — backbone of tile delivery.
Distributed Cache — used for live traffic state.