Design Google Maps & Distributed Routing Engine

1. Problem Statement & Scope Clarification

System Mission

Design a planetary-scale digital mapping, shortest-path navigation, and real-time dynamic traffic routing platform (similar to Google Maps, Apple Maps, and Waze) capable of rendering high-definition vector map tiles globally, ingesting billions of live GPS telemetry pings, and calculating optimal driving routes across hundreds of millions of road segments in under 100 milliseconds.

Functional Requirements

1. Vector Map Tile Rendering: Serve zoomable vector map tiles (Zoom 0 to 21) based on standard Slippy Map / Quadkey conventions with sub-20ms edge latency.
2. Shortest-Path Driving Directions (GetDirections): Compute optimal routes considering turn restrictions, one-way streets, road hierarchies, and real-time traffic congestion.
3. Accurate Estimated Time of Arrival (ETA): Predict travel durations incorporating live telemetry speed profiles and historical traffic patterns.
4. Real-Time Dynamic Re-Routing: Push proactive detour alerts to in-flight drivers when accidents or unexpected congestion arise along their active route.
5. Live GPS Map Matching: Snap noisy client GPS coordinates to physical road network segments using Hidden Markov Models (HMM).

Non-Functional Requirements (SLAs & SLOs)

• Ultra-Low Latency:
  • Map Tile Rendering (Edge CDN): $P99 < 20\text{ ms}$.
  • Long-Distance Cross-Country Routing: $P99 < 100\text{ ms}$.
• High Availability: $99.999\%$ uptime SLA for navigation and directions.
• Scale: Support $500,000,000\text{ Daily Active Users (DAU)}$, $50\text{M daily route calculations}$, and $1\text{ Billion tile requests/day}$.

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Road Network Graph Sizing

• Global Intersections (Vertices $V$): $\approx 100,000,000\text{ nodes}$ ($100\text{M intersections}$).
• Global Road Segments (Edges $E$): $\approx 300,000,000\text{ directed edges}$ ($300\text{M segments}$).
• Vertex Struct Size: node_id (8B), lat (4B float), lon (4B float), edges_offset (4B) $\approx 20\text{ bytes}$.
• Edge Struct Size: target_node (8B), distance_meters (4B), speed_limit (2B), live_weight (2B), flags (4B) $\approx 20\text{ bytes}$.
• Total Graph Memory Footprint: $\text{Graph Memory} = (100\text{M} \times 20\text{B}) + (300\text{M} \times 20\text{B}) = 2.0\text{ GB} + 6.0\text{ GB} = \mathbf{8.0\text{ GB RAM}}$
• Adding Contraction Hierarchy shortcut edges ($+20\%$) yields $\approx \mathbf{9.6\text{ GB RAM}}$, allowing the entire planetary road graph to fit in the RAM / L3 cache of a single EC2 instance.

Telemetry Ingestion & Tile Traffic

• Active Navigation Devices: $20,000,000\text{ active drivers}$ emitting GPS pings every 5 seconds.
• GPS Ingest QPS: $\text{GPS Telemetry QPS} = \frac{20,000,000\text{ drivers}}{5\text{ seconds}} = \mathbf{4,000,000\text{ pings/sec}}$
• Map Tile Egress QPS: Peak $50,000\text{ tile requests/sec}$ ($99.2\%$ cached at edge CDN).

3. High-Level Architecture & AWS Component Mapping

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

4. Shortest Path Graph Algorithms: Dijkstra vs Contraction Hierarchies

1. The Shortest-Path Complexity Evolution

2. Contraction Hierarchies (CH) Mechanics

1. Offline Preprocessing Phase: Order all road network nodes by importance (e.g. residential alleyways = lowest, interstate highways = highest). Iteratively "contract" nodes from lowest to highest, adding shortcut edges to preserve shortest distances between remaining neighbors.
2. Bidirectional Upward Query Phase: Run forward Dijkstra from Origin and backward Dijkstra from Destination, strictly traversing edges that lead to nodes of higher rank. The search spaces meet at a peak node in $< 10\text{ ms}$ after exploring only hundreds of nodes.

textCopy
Query Space:
Origin (Residential) ---> Minor Arterial ---> Highway Peak Node <--- Highway <--- Destination
(Search explores ONLY upward hierarchy, ignoring millions of irrelevant side streets)

5. Live GPS Map-Matching with Hidden Markov Models (HMM)

Raw GPS coordinates have a $5 - 15\text{ meter}$ error radius, frequently jumping onto parallel service roads or buildings. The engine snaps noisy points to physical road segments using Viterbi HMM Algorithms:

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...