Courses › System Design › Question Breakdowns

Design Google Maps

Vector tiles on a CDN, contraction hierarchies, live traffic from probes, ETA and re-routing.

Design a maps and navigation service like Google Maps: users view a map anywhere in the world, search for places, get the fastest route between two points with an ETA that reflects live traffic, and are re-routed while driving. It's a question about serving map tiles, shortest paths on a continental road graph, live traffic from location probes and ETA.

Requirements

Functional

  • Users can view and pan/zoom the map anywhere in the world
  • Users can get directions between two points (driving; mention walking/transit as variants) with an ETA
  • ETAs and routes reflect live traffic
  • During navigation, users get turn-by-turn guidance and are re-routed if they leave the route or traffic changes

Out of scope: place search (see Design Yelp (Nearby Places)), Street View, building the base map from imagery, reviews.

Non-functional

  • Scale: ~1B monthly users; ~100k route requests/second at peak; ~10M concurrent navigating devices
  • Fast: map tiles render instantly while panning; routes in < 1 second
  • Accurate ETAs (within a few minutes for long trips)
  • Highly available; the map must work with weak connectivity (and offline for downloaded areas)

[!TIP] Split it into three systems Maps is really three products that share a road graph: tiles (read-only, CDN problem), routing (graph algorithm problem) and traffic (stream processing problem). Say so up front and take them one at a time; trying to design them as one service is how candidates run out of time.

Capacity estimates

Core Entities

  • Road segment — edge between two intersections: geometry, length, speed limit, road class, turn restrictions
  • Tile — (zoom, x, y), vector data for that square
  • Route — origin, destination, list of segments, distance, ETA
  • Location probe — device (anonymized), lat/lng, speed, heading, timestamp
  • Traffic speed — segment, current speed, updated at

API

GET /v1/tiles/{z}/{x}/{y}.mvt                → vector tile (CDN-cached)

GET /v1/routes?from=40.74,-73.99&to=40.69,-73.98&mode=drive&alternatives=2
→ { "routes": [{ "polyline": "...", "distanceM": 7400, "etaSec": 1260, "steps": [...] }] }

POST /v1/navigation/{sessionId}/locations   { lat, lng, speed, heading, t }
→ { "onRoute": true, "etaSec": 1180, "reroute": null }

High-Level Design

user = client "Maps App" @0,1
cdn = cache "CDN\n(vector tiles)" @1,0
tiles = blob "Tile Store" @2,0
route = service "Routing Service\n(graph in memory)" @1,1
graph = store "Road Graph +\nPreprocessed Shortcuts" @2,1
nav = service "Navigation Service" @1,2
probes = queue "Location Probes\n(Kafka)" @2,2
traffic = service "Traffic Aggregator" @3,2
speeds = cache "Live Segment Speeds" @3,1
user -> cdn : tiles
cdn -> tiles : miss
user -> route : directions
route -> graph
route -> speeds : edge weights
user -> nav : location updates
nav -> probes
probes -> traffic
traffic -> speeds
nav -> route : re-route
  • Tiles: pre-generated offline from map data and served from a CDN; the app fetches only tiles in the viewport (plus a margin).
  • Routing: the routing service holds the road graph in memory (sharded by region) with precomputed shortcuts, and uses live speeds as edge weights.
  • Traffic: navigating devices send location probes; a stream job map-matches them to road segments and computes current speed per segment.
  • Navigation: the navigation service tracks each session, updates the ETA and asks for a re-route when the user goes off route or traffic changes.

Deep Dives

1. Map tiles

  • The world is cut into a quadtree of tiles: zoom 0 is one tile; each zoom level splits every tile into 4. Tiles are addressed (z, x, y) — perfectly cacheable keys.
  • Vector tiles (geometry + labels, rendered on the device) are far smaller than raster images, scale smoothly between zooms and allow rotation and dark mode without re-rendering on the server.
  • Tiles change rarely: regenerate affected tiles in a batch pipeline when map data changes, and give them long CDN TTLs with versioned URLs.
  • Offline maps: download all tiles + the routing graph for a region as a bundle.

2. Shortest paths at continental scale

Dijkstra on a 1B-node graph explores millions of nodes for a long trip — seconds per query. A\* with a straight-line heuristic helps, but not enough. Production engines preprocess the graph:

Contraction hierarchies are the classic answer. Their weakness is that shortcuts are computed for fixed weights, and traffic changes weights constantly. Customizable route planning (CRP) splits preprocessing into a slow topology phase (rarely) and a fast customization phase (seconds) that recomputes cell shortcuts with new traffic weights — which is why it's used for live-traffic routing.

3. Live traffic from probes

[Navigating devices] -> {Kafka} -> [Map matching] -> [Per-segment speed windows] -> (Live speed store)
  • Map matching: a GPS point is noisy; snap the trace to the most likely sequence of road segments (an HMM / Viterbi over candidate segments).
  • Aggregation: per segment, keep a sliding window (e.g. last 5 minutes) of observed speeds; publish the median when there are enough probes.
  • Sparse data: fall back to historical speeds for that segment, hour of week; blend live and historical by confidence.
  • Privacy: probes are anonymized, sampled, and trimmed at trip start/end.

4. ETA

The basic ETA is the sum of each segment's expected travel time at the time you'll reach it — live speed for the next few minutes, transitioning to historical/predicted speed later in the trip — plus turn and intersection penalties. Production systems then correct this with an ML model trained on actual trip durations.

5. Navigation and re-routing

  • The app follows the route locally (turn-by-turn works with weak connectivity) and sends location every few seconds.
  • The server checks off-route (distance from the route polyline) and periodically re-computes the ETA. If a faster route appears (traffic jam ahead), it pushes an alternative.
  • 10M sessions × an update every 5s is ~2M messages/s: shard sessions by session ID and keep their state in memory.

6. Sharding the graph

A route between two cities in the same region is served by that region's graph shard. Long, cross-region trips use a boundary/overlay graph of shortcut edges between region borders: route to the border inside region A, across the overlay, and to the destination inside region B.

What's expected at each level

  • Mid-level: a tiled map served from a CDN, a graph-based route search, and traffic as an input to edge weights.
  • Senior: why plain Dijkstra is too slow, preprocessing with contraction hierarchies, the probe → map matching → segment speed pipeline, ETA from segment times.
  • Staff: reconciling fast queries with changing weights (CRP-style customization), cross-region routing on an overlay graph, historical/live blending, navigation session scale and offline support.