Design Google Maps
Tiles, routing, geospatial index, real-time traffic, and global CDN delivery.
Interview tip Split map tiles (static CDN) from dynamic routing (graph search). Mention quadtree/geohash, A*/Dijkstra on contracted graphs, and traffic-weighted edges.
① Functional requirements
- Display map tiles at zoom levels
- Search places by name or category
- Compute driving route A → B
- ETA with live traffic
- Turn-by-turn navigation updates
- Save favorite places
② Non-functional requirements
- Route p99 < 500ms for metro areas
- Tile load < 100ms via CDN
- Global availability 99.99%
- Traffic data refreshed every 1–2 minutes
- Offline map packs for mobile
③ Back-of-the-envelope scale
Assumptions
- Tile pyramid: zoom 0–20 → billions of tiles, mostly static CDN
- Routing graph: continental graph contracted to GB-scale in memory
- 10K route QPS → GPU/CPU farm for path search
- Traffic: 100M road segments updated per minute
④ High-level architecture
Google Maps
Mobile / web clients
CDN (map tiles)
Places API + search
Routing service (graph)
Traffic ingestion pipeline
Geospatial index DB
Tiles immutable — aggressive CDN cache. Routing uses preprocessed hierarchical graph (highways first). Traffic overlays edge weights.
⑤ Data flow & execution path
Route request path
① Snap A,B to graph→② Load traffic weights→③ Bidirectional search→④ Polyline encode→⑤ Return ETA + steps
Tile path: CDN cache hit → no origin
Place search: geospatial index + text search
Navigation: periodic reroute on traffic delta
Mobile offline: bundled tile region packs
Separate static tile delivery from compute-heavy routing. Mention contraction hierarchies for interview depth.
⑥ API & interfaces
| Endpoint / flow | Purpose | Notes |
|---|---|---|
| GET /tiles/{z}/{x}/{y} | Map tile | CDN cached |
| GET /places/search | Place search | lat,lng + query |
| POST /routes | Compute route | mode=driving|walking |
| GET /routes/{id}/traffic | Reroute hint | WebSocket for nav |
⑦ Data model & storage
Road graph: nodes, edges, speed limits. Tiles: z/x/y PNG/vector. Place: name, lat, lng, categories. Traffic: edge_id → speed_factor.
| Store | What | Why |
|---|---|---|
| CDN + S3 | Map tiles | Immutable static |
| In-memory graph | Routing | Preprocessed CH index |
| PostGIS / S2 | Place index | Geo queries |
| Redis | Traffic overlay | TTL 2 min |
⑧ Deep dive — core components
Contraction hierarchies
Preprocess graph offline to add shortcut edges. Query runs bidirectional search on hierarchy — ms on continental graphs vs seconds on raw Dijkstra.
Tile pyramid
Web Mercator grid. Parent tile covers 4 children. Vector tiles reduce bandwidth vs raster. CDN cache keyed by tile URL forever (immutable version in path).
⑨ Trade-offs & alternatives
| Decision | Option A | Option B | Pick when |
|---|---|---|---|
| Routing | CH preprocess | Live Dijkstra | CH fast query; heavy preprocess on map updates |
| Tiles | Vector | Raster | Vector smaller + style client; raster simpler |
| Traffic | Probe fusion | Fixed historical | Live traffic better ETA; fallback patterns |
| Search | Geo first | Text first | Geo bias when lat/lng known |
⑩ 45-minute interview script
- 0–5 min: Map + route + search
- 5–12 min: Tile CDN vs routing compute
- 12–22 min: Routing graph + traffic
- 22–32 min: Place search geospatial
- 32–40 min: Navigation reroute
⑪ Likely follow-up questions
| Question | Short answer |
|---|---|
| Multi-modal transit? | Layered graphs per mode; transfer edges at stations; longer compute budget |
| Map update pipeline? | Probe + government feeds → traffic service; weekly graph rebuild for road changes |
| Privacy on location history? | On-device storage option; server TTL; aggregate analytics only |
⑫ Revision checklist
- Tile CDN pyramid
- Road graph storage
- Contraction hierarchies
- Traffic-weighted edges
- Place geospatial index
- Route polyline encoding
- Reroute on traffic
- Offline region packs