Design Google Maps

Map tiles, place search, turn-by-turn routing with live traffic, and ETAs for a billion users.

Difficulty: hard. Patterns: geospatial, routing, graphs, cdn. Reported at Google, Uber, Lyft, DoorDash, Apple.

Study shows every answer; Practice hides them until you have produced your own.

Functional requirements

• Render the map at any zoom level. Pan and zoom smoothly on web and mobile, online and with a cached offline area.
• Search for places and addresses. Autocomplete as you type, biased to the viewport and the user's location.
• Compute a route between two points. Driving first; walking and transit as variants. Return the path, distance and ETA.
• Turn-by-turn navigation. Follow the user's GPS, announce manoeuvres, re-route when they deviate.
• Live traffic and traffic-aware ETAs. Traffic derived from anonymised location pings of navigating users.
• Show nearby places (POIs). Restaurants, fuel, parking near a point or along a route.
• Out of scope. Street View imagery, business reviews, satellite imagery pipeline, and map data acquisition (we assume the road graph exists).

Non-functional requirements

• Scale (1 B MAU · 50 M concurrent navigating). Tile serving is the read-heavy part; navigation is the write-heavy part (location pings).
• Tile latency (p95 < 100 ms). Tiles are what the user perceives as "the map is slow". Must come from a CDN edge.
• Route latency (p95 < 500 ms for 1 000 km). Naive Dijkstra over a continent takes seconds. Needs a preprocessed graph.
• ETA accuracy (within 10 % for 90 % of trips). Accuracy is a product metric; drives the traffic pipeline freshness requirement.
• Traffic freshness (< 2 min from ping to routing). A jam that started 10 minutes ago must already affect ETAs.
• Availability (99.99 %). Degrade gracefully: stale tiles and static routes are better than errors.
• Privacy. Location pings are anonymised, aggregated, and never joined back to a user for traffic purposes.
• Bandwidth. Mobile users on poor networks. Vector tiles, aggressive caching, delta updates.

Back-of-envelope estimates

• Tile requests per second: ~2 M. 1 B MAU, ~10 % daily = 100 M DAU. Each session loads ~50 tiles, 2 sessions a day: 100 M × 100 = 10 B/day ÷ 86 400 ≈ 115 k/s average, peak 5× ≈ 600 k/s… but each pan/zoom fetches a 3×3 to 5×5 grid, so budget ~2 M/s at the CDN edge. Origin sees under 1 % of that.
• Tile storage: ~100 TB (vector). Web Mercator zoom 0–20 has 4^20 ≈ 10^12 tiles at the deepest level, but most are ocean or empty. Real data ~ 100 TB as vector tiles across all zooms, several PB if raster. Pre-render zooms 0–14, render 15–20 on demand and cache.
• Road graph size: ~500 M edges. Global road network: ~ 100 M nodes, ~ 500 M edges (intersections and segments), ~50 GB with geometry. Fits in memory on a handful of large machines per region; must be sharded or partitioned for parallel queries.
• Location pings per second: ~10 M. 50 M concurrent navigating × one ping every 5 s = 10 M pings/s. This is the single biggest stream in the system and it is write-only. Each ping ~100 B → 1 GB/s ingest.
• Route requests per second: ~50 k. 100 M DAU, ~20 % navigate daily, ~2 routes each plus re-routes: 40 M × 3 = 120 M/day ≈ 1.4 k/s average; peak ~10×, plus autocomplete-triggered previews. Budget ~50 k/s. Each is CPU heavy, so this sizes the routing fleet.
• Routing server CPU: ~500 servers. A contraction-hierarchy query costs ~1–5 ms of CPU. 50 k/s × 5 ms = 250 CPU-seconds per second → ~250 cores busy, so ~500 servers across regions with headroom and graph replication.
• Autocomplete queries per second: ~300 k. Each search types ~6 characters; ~1 query per keystroke after debounce: 100 M DAU × 2 searches × 6 = 1.2 B/day ≈ 14 k/s average, peak 20× = ~300 k/s. Must be served from an in-memory prefix index.

Components

• Maps client (vector renderer · GPS): Web or mobile app. Renders vector tiles on the GPU, caches tiles on disk, tracks GPS at 1 Hz, and does local map-matching and manoeuvre announcement during navigation so short network gaps do not break guidance.
• CDN edge (tiles · static): Serves tiles and static assets from hundreds of edge locations. Cache key is (layer, z, x, y, version). Hit rate above 99 % because popular areas at popular zooms are a tiny fraction of the tile space.
• API gateway (auth · rate limit · geo-route): Terminates TLS, authenticates API keys and user sessions, rate limits, and routes to the nearest regional deployment of each service. Stateless.
• Tile service: Origin for the CDN. Serves pre-rendered vector tiles for low zooms from object storage and renders high-zoom tiles on demand from the geo database, then caches them. Handles tile versioning when map data updates.
• Place search (prefix index + geo bias): Autocomplete and full search. In-memory prefix tries per region, results scored by text match, popularity, and distance to the viewport or user. Backed by the places index for full queries.
• Routing service (contraction hierarchies): Answers shortest-path queries in milliseconds using a preprocessed road graph (contraction hierarchies or customisable route planning). Holds the graph in memory, sharded by region with cross-border stitching. Applies live traffic weights.
• Navigation service (session state): Owns an active navigation session: current route, progress, next manoeuvre. Receives location pings, map-matches them to the road graph, detects deviation, and requests a re-route. Forwards anonymised pings to the traffic pipeline.
• Geo database (PostGIS / spatial index): Source of truth for map features: roads, buildings, boundaries, POIs, with geometry. Spatially indexed (R-tree / geohash). Read by the tile renderer and the places index builder; written by the map data pipeline.
• Places index (Elasticsearch · geo_point): Searchable POIs and addresses with names, aliases, categories, popularity and location. Sharded by geographic region so a viewport-biased query hits one or two shards.
• Road graph store (preprocessed CH graph): The compiled routing graph: nodes, edges, base weights, and the contraction hierarchy shortcuts. Rebuilt when map data changes (weekly) and loaded into routing servers at startup. Stored in object storage as versioned binary blobs.
• Traffic pipeline (stream processing): Consumes anonymised location pings, map-matches them to road segments, aggregates speed per segment per minute, and publishes current segment speeds plus predicted speeds by time of day. The output is a compact weight overlay for the routing graph.
• Ping stream (Kafka · keyed by geo cell): Durable stream of location pings, partitioned by coarse geo cell so a consumer sees all pings for an area. 10 M/s makes this one of the largest topics in the company; retention is short (hours).
• Traffic store (Redis · segment → speed): Current speed per road segment, refreshed every minute, plus historical speed profiles. Routing servers pull deltas every 30–60 s and apply them as edge weight overrides without rebuilding the hierarchy.
• Tile storage (object storage): Pre-rendered vector tiles for zooms 0–14 and cached on-demand tiles for deeper zooms. Versioned by map release so CDN keys change atomically on a data update.

User flows

1. Pan and zoom the map. The path that must be fast for everyone. Almost every request is answered at the CDN edge; the origin only sees cache misses and on-demand renders.
2. Search for a place with autocomplete. One query per keystroke at hundreds of thousands per second, answered in tens of milliseconds, biased toward where the user is looking.
3. Compute a route with live traffic. Continental shortest path in under half a second, with edge weights that reflect traffic from two minutes ago.
4. Turn-by-turn navigation and re-routing. The client does the per-second work locally; the server tracks the session, detects deviations, and re-routes without the user noticing.
5. Live traffic: from pings to ETAs. Ten million pings a second become a speed per road segment per minute, and routing picks it up within two minutes.

Deep dives

1. Vector tiles vs raster tiles. Why ship geometry to the client instead of rendered images?
2. Routing: why not Dijkstra?. Textbook shortest path over 500 million edges takes seconds. How do you get to milliseconds and still respect live traffic?
3. Spatial indexing: geohash, S2, quadtree, R-tree. How do you find the roads in a tile, the places near a point, or the segment a ping belongs to, fast?
4. Traffic from crowdsourced pings. How do you turn ten million noisy location pings a second into trustworthy per-segment speeds, without building a surveillance system?
5. Navigation: what runs on the phone vs the server. The phone has the GPS and the screen; the server has the graph and the traffic. Where does each piece of work belong?
6. ETA prediction. An ETA is a forecast, not a sum. What goes into it and how do you make it accurate?