Design Maps and Navigation
HardSystem design · Geospatial Routing · Google
Design a maps and navigation service: place search, map tiles, routing with live traffic, turn-by-turn guidance and offline maps. Scale: a continental road graph of hundreds of millions of segments, 50K route requests/s with p99 under 200ms, and traffic refreshed every 1 to 2 minutes from client traces. Cover tile serving, why plain Dijkstra fails and how preprocessing (contraction hierarchies, customizable route planning) works with changing traffic, map matching, rerouting, and instruction generation.
Requirements
- Tiles are static, versioned and CDN cached; routing is dynamic and separate
- Routing preprocesses the graph topology offline and recomputes weights quickly from live speeds
- Match noisy GPS traces to road segments and use them to estimate traffic
- Rerouting is conservative, and instructions and offline data let guidance continue without connectivity