Design Google Maps
Design a mapping and navigation service like Google Maps with features like map rendering, directions, and real-time traffic.
Use hierarchical tile-based rendering, graph algorithms for routing, and crowdsourced data for real-time traffic.
How would you structure the road network graph?
Think about map tile caching strategies
Consider real-time traffic data ingestion
functional
- •Map display
- •Search places
- •Directions
- •Real-time traffic
- •Street view
- •Offline maps
non functional
- •Fast map loading
- •Accurate ETA
- •Global coverage
- •Low bandwidth usage
graph
edges
Road segments with weights (distance, time, traffic)
nodes
Intersections
algorithm
Modified A* or Contraction Hierarchies
optimizations
- •Precomputed shortcuts
- •Hierarchical decomposition
- •Bidirectional search
prediction
ML models combining current + historical
processing
Real-time stream processing with Kafka + Flink
data sources
- •GPS from mobile apps
- •Road sensors
- •Historical patterns
offline
Download region tiles + routing graph subset
eta accuracy
Segment-level traffic prediction, consider turns
places search
Geospatial index + text search hybrid
tile system
levels
22 zoom levels, each 4x previous tiles
delivery
CDN with aggressive caching
description
Pre-rendered tiles at multiple zoom levels
vector tiles
pros
- •Smaller size
- •Dynamic styling
- •Smooth zoom
description
Send raw data, render on client