system design · system-design
Design Google Maps (Tiles + Routing)
Geospatial DB, map tile serving, routing with Dijkstra/A*, real-time traffic, Street View tile pyramid.
Theory
Explanation
Intuition first, formal definition second. Skim the bullets if you already know this; read the prose if you don't.
Two products in one: render a map (tiles) and compute a route. Tiles are a pre-rendered pyramid keyed by (z, x, y), static-ish, heavily cached. Routing is a graph search over road network, accelerated by precomputed contraction hierarchies and live traffic overlays.
Tile service: world divided into Mercator-projected quadtree, levels z=0..22. Each tile is 256×256 PNG/vector. CDN-cached aggressively. Routing service: road graph stored as edge list with weights = travel time. Precompute contraction hierarchies offline; A* online over the contracted graph runs in ms instead of seconds. Live traffic: vehicle probes report speed; aggregator updates edge weights per ~1min. Geospatial index (S2 cells or H3) for proximity queries (nearby restaurants).
When to use
Mapping, routing, fleet dispatch (Uber, food delivery), logistics.
When not to
Static maps with no routing, just CDN.
flowchart LR Client([Client]) --> Tile[Tile Service] Tile --> CDN[Tile CDN] CDN --> Store[(Tile Store · z/x/y)] Client --> Route[Routing Service] Route --> CH[(Contracted Road Graph)] Route --> Traffic[(Live Traffic Overlay)] Probes[Vehicle Probes] --> Aggr[Speed Aggregator] Aggr --> Traffic Client --> Geo[Geo Search · S2/H3] Geo --> POI[(POI Index)]
Key insights
- Tile pyramid trades storage for compute, pre-render once, serve forever.
- Vector tiles are smaller + restyleable client-side; raster tiles simpler.
- Contraction hierarchies precompute shortcuts; online query is O(sqrt(n)) effectively.
- Live traffic is overlay on static graph, multiply edge weights, don't rebuild graph.
- S2 cells (Google) or H3 (Uber) give hierarchical geo indexing that survives at scale.