System Design Lab›System Design Questions›Design Google Maps
Design Google Maps
HardSearchgeolocationroutingcdnsearchreal-time🔵 Google
Question Overview
Design a maps and navigation service like Google Maps covering map display, place search, routing, and live traffic. The key challenges are serving billions of map tiles through CDNs, answering shortest-path queries on a continental road graph in milliseconds, and turning location pings into accurate ETAs.…
Sign up to see the full question and AI interviewer
Requirements
- Map display at every zoom level using cached vector tiles rendered on the client
- Place and address search, autocomplete, and reverse geocoding
- Fastest-route computation with alternatives in under 200 ms at p99
- ETAs that combine live traffic with historical time-of-day speeds
- Turn-by-turn navigation that reroutes when the user deviates or traffic changes
- Location data anonymized and aggregated before it feeds traffic estimates
Back-of-the-envelope numbers
- Tile pyramid: zoom z has 4^z tiles, so z14 ≈ 268M and z18 ≈ 68.7B (≈ 92B across z0-z18), so pre-build vector tiles only to z14 and overzoom
- Tile storage: ~30% of z14 tiles hold data ≈ 80M × ~30 KB ≈ 2.4 TB; all lower zooms add ~1/3 more (4^14 ÷ 3 tiles) ≈ 3.2 TB
- Tile requests: 100M DAU × 5 sessions × 30 tiles = 15B/day ÷ 86,400 ≈ 174K/s, ~520K/s at 3× peak; a 95% CDN hit rate leaves ~26K/s at origin
- Tile bandwidth: 520K/s × 30 KB ≈ 15.6 GB/s ≈ 125 Gbps at peak, served almost entirely from CDN edges
- Location pings: 50M sessions × 20 min = 1B session-minutes ÷ 1,440 ≈ 694K concurrent navigators, ~2M at peak → ~400K pings/s; 12B pings/day ≈ 1.2 TB
- Routing: 200M requests/day ÷ 86,400 ≈ 2.3K/s, ~7K/s at peak; contraction hierarchy queries take about a millisecond versus seconds for plain Dijkstra on a continent
- Road graph: 500M nodes × 16 bytes + 1.2B edges × 12 bytes ≈ 22 GB; shortcuts roughly double the edges → ~37 GB, fitting one large server
Key components
- Map data pipeline: merges imagery, surveys, authoritative feeds, and user reports into versioned releases of the road graph, place database, and tile sets
- Tile service and CDN: vector tiles addressed by z/x/y with versioned, immutable URLs and long cache TTLs; clients apply styles and labels locally
- Place search and geocoding: address parsing plus a text index over names, combined with an S2 or geohash spatial index to rank by relevance and distance
- Routing engine: contraction hierarchies or customizable route planning (CRP) with bidirectional search over precomputed shortcuts, partitioned by region with an overlay graph
- Traffic pipeline: pings stream through a log, are map-matched to road segments with an HMM, and aggregated into per-segment speeds every minute
- ETA service: live speeds for the next segments, historical time-of-day profiles for later ones, and an ML model trained on completed trips to correct bias
- Navigation session: the client map-matches locally and detects off-route deviations, while the server periodically re-evaluates the route and pushes a faster one
Common mistakes
- Running plain Dijkstra or A* over the raw continental graph per request, which explores millions of nodes and takes seconds
- Pre-rendering raster tiles for every zoom level worldwide instead of vector tiles with client-side overzoom and CDN caching
- Re-running full contraction hierarchy preprocessing on every traffic update instead of a customizable scheme (CCH or CRP) that swaps edge weights quickly
- Using raw GPS points as road positions without map matching, so noise snaps cars onto parallel streets and corrupts segment speeds
- Computing ETA from speed limits or only current traffic, ignoring how traffic will change over the course of a long trip
- Keeping identifiable location traces indefinitely instead of anonymizing, aggregating, and expiring raw pings
Likely follow-ups
- How would you support offline maps and navigation for an entire city on a phone?
- How would you detect a new road closure within minutes using only location pings?
- How would you predict the ETA for a trip departing tomorrow at 8 AM?
- How would you add public transit routing, where edge costs depend on timetables?
- How do you avoid rerouting every driver onto the same side street and creating a new jam?
- How do you release a new map version without mismatched tiles, search results, and routes?
No community solutions yet
Be the first to publish your solution
Practice ‘Design Google Maps’ with an AI Interviewer
Get scored feedback on your diagram, scalability approach, and trade-offs. Free while we grow — up to 3 full interviews a day.