Requirements and Scale
Functional: turn-by-turn navigation, ETA estimation, real-time traffic updates, points of interest search, route alternatives. Non-functional: 1B daily active users, 5M concurrent navigation sessions, ETA accuracy within 10% (P90), route recalculation in < 500ms on traffic change, map tile serving at < 50ms globally. The map data problem: road network graph has 100M+ nodes (intersections) and 200M+ edges (road segments). Cannot fit in single-machine memory for global routing. Must partition geographically.
Road Network Graph and Storage
Road network modeled as a directed weighted graph: nodes = intersections, edges = road segments. Edge attributes: distance, speed_limit, road_type (MOTORWAY/ARTERIAL/LOCAL), turn_restrictions, one_way flag. Partitioned by geographic region (H3 hexagons at resolution 4, ~2,000 partitions globally). Each partition fits in memory (~500MB). Cross-partition edges: border edges stored in both partitions with remote endpoint metadata. Storage: custom binary format for fast memory-mapped loading (not a general-purpose DB). Graph updates: map changes applied nightly in batch (new roads, speed limit changes). Real-time traffic weights applied as overlays on top of static graph.
Shortest Path: A* for Single Route
import heapq
def astar(graph: dict, start: int, end: int,
heuristic: callable) -> tuple[list[int], float]:
# graph[node] = [(neighbor, weight), ...]
# heuristic(node, end) = estimated remaining cost (haversine distance)
dist = {start: 0}
prev = {}
heap = [(heuristic(start, end), 0, start)] # (f, g, node)
while heap:
f, g, u = heapq.heappop(heap)
if u == end:
# Reconstruct path
path = []
while u in prev:
path.append(u); u = prev[u]
path.append(start)
return path[::-1], dist[end]
if g > dist.get(u, float('inf')):
continue # stale entry
for v, w in graph[u]:
new_g = g + w
if new_g float:
lat1, lng1 = get_coords(node)
lat2, lng2 = get_coords(end)
# Haversine formula returns km; convert to time estimate
dist_km = haversine(lat1, lng1, lat2, lng2)
max_speed = 130 # km/h motorway speed
return (dist_km / max_speed) * 3600 # secondsContraction Hierarchies for Fast Global Routing
A* on a 100M-node graph is too slow for long-distance routes. Contraction Hierarchies (CH) precompute shortcuts: node importance is ordered (local streets < arterials < highways). During preprocessing: iteratively contract least important nodes – add shortcut edges between neighbors to preserve shortest paths. Query time: bidirectional Dijkstra that only relaxes edges going "upward" in importance hierarchy. Result: query time of 10-100ms even on global road networks (vs minutes for plain Dijkstra). Google Maps and Waze use CH or similar techniques (Arc Flags, HL). Preprocessing is expensive (hours) but done offline. Live traffic changes are applied as time-dependent edge weights without full recomputation.
ETA and Real-Time Traffic
ETA components: (1) Route distance and speed limits (static). (2) Historical traffic patterns by time of day and day of week (ML model per road segment). (3) Live traffic events: accidents, road closures ingested from user reports + sensors + partner feeds. (4) Current congestion: speed readings aggregated from GPS traces of active navigation sessions. ETA model: predicted_travel_time = sum over route segments of (segment_length / predicted_speed). predicted_speed = f(speed_limit, historical_pattern, current_congestion). Live traffic propagation: when an accident is reported on segment X, increase edge weight for X. Recompute affected routes within a geographic radius. Push route update to active navigation sessions if new ETA differs by > 2 minutes or new route is > 5% faster.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does Google Maps compute the shortest route so quickly?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Plain Dijkstra on a 100M-node road graph takes minutes. Google Maps uses Contraction Hierarchies (CH): during preprocessing, nodes are ordered by "importance" (local streets are least important, highways most important). Less important nodes are iteratively contracted – their neighbors are connected by shortcut edges that preserve shortest paths. At query time, bidirectional Dijkstra only relaxes edges going "upward" in importance, dramatically reducing the search space. CH preprocessing takes hours but is done offline. Query time: milliseconds for continent-scale routing. Real-time traffic is applied as edge weight overlays without full recomputation.”}},{“@type”:”Question”,”name”:”What is A* and how does it improve on Dijkstra for routing?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A* is Dijkstra with a heuristic that guides the search toward the destination. Priority: f(n) = g(n) + h(n), where g(n) is the known cost from start to n, and h(n) is the estimated cost from n to the destination. For maps, h(n) is the haversine (straight-line) distance divided by the maximum possible speed – this is admissible (never overestimates) and consistent. A* explores fewer nodes than Dijkstra because it prioritizes nodes likely to be on the optimal path. For long-distance routing, A* alone is insufficient – Contraction Hierarchies are needed. A* is used for local routing (< 50km).”}},{“@type”:”Question”,”name”:”How do you model real-time traffic in a maps system?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”GPS traces from active navigation sessions provide current speed readings per road segment. Aggregate: for each segment, compute median speed from GPS traces in the last 5 minutes. Compare to the historical baseline for this time of day / day of week (precomputed). If current speed < 0.5 * historical: mark as congested, increase edge weight. External inputs: accident reports (user-submitted + partner feeds), road closures, construction. Traffic data applied as a time-dependent overlay on the static road graph – edge weight = f(distance, current_speed_estimate). Affected routes are recomputed when congestion changes materially (> 2 min ETA impact).”}},{“@type”:”Question”,”name”:”How are map tiles served at scale?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Map tiles are pre-rendered PNG or vector tiles at each zoom level (z/x/y coordinates). Tiles are static and rarely change (road changes happen nightly). Architecture: tiles stored in object storage (S3), served through CDN with very long TTLs (1 year for static tiles). CDN hit rate: 99%+ for popular areas. For satellite imagery: stored as JPEG tiles at multiple zoom levels. For vector tiles: binary format (Mapbox Vector Tile / MVT) containing road geometries and labels; client renders them dynamically for smooth zoom. Tile generation: nightly batch job generates all tiles from the updated road network data. Changed tiles are selectively invalidated in CDN cache.”}},{“@type”:”Question”,”name”:”How do you partition a global road network for distributed routing?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Partition using H3 hexagonal grid (or similar) at a coarse resolution (each cell ~500km wide). Each partition is a subgraph of the road network including all nodes and edges within the cell, plus border edges to adjacent cells. Each partition fits in memory (< 1GB). Routing within a partition: single-machine A* or Dijkstra. Cross-partition routing: hierarchical – first route on the highway layer (motorways and major arterials only, fits in one machine), then refine the first and last mile within the source and destination partitions. This two-level approach is used by commercial routing engines for global-scale routing.”}}]}
Uber system design interviews cover routing and ETA computation. Review maps design patterns for Uber interview: maps routing and ETA system design.
Lyft system design rounds include routing and navigation. See design patterns for Lyft interview: navigation and routing system design.
Snap system design covers location-based features. Review maps system design for Snap interview: location and maps system design.