Architecture Blueprint

Design Google Maps / Turn-by-Turn Navigation

Real-time navigation and routing engine computing shortest paths across continental road networks using Contraction Hierarchies, Google S2 spatial indexing, and live traffic congestion telemetry.

1. System Requirements

Functional

Calculate point-to-point driving, walking, and transit routes with turn-by-turn navigation instructions.
Ingest real-time GPS telemetry from active drivers to dynamically adjust road segment speeds.
Perform dynamic rerouting when traffic congestion, accidents, or road closures occur mid-trip.

Non-Functional / SLA

Sub-80ms route computation latency across continental road network graphs.
High GPS telemetry ingestion capability (500,000+ pings/sec) with minimal battery drain on client devices.
High availability (99.999%) for critical driver routing and emergency turn-by-turn dispatch.

2. Scale & Resource Estimates

Throughput: 1 Billion Active Users. 100 Million daily routing calculations. 500,000 GPS telemetry pings/sec.

Storage & RAM: Global road graph: 200 Million intersections (nodes) and 500 Million road segments (edges) = ~40 GB in-memory graph.

3. System API Endpoints

GET /api/v1/navigation/route?origin=40.7128,-74.0060&dest=40.7580,-73.9855&mode=driving
Response (200 OK):
{
  "route_id": "rt-88201",
  "eta_seconds": 1380,
  "distance_meters": 7820,
  "polyline": "a~l~FjkblOnq@...",
  "steps": [
    { "instruction": "Head north on Broadway", "distance_meters": 450, "duration_sec": 80 }
  ]
}

POST /api/v1/telemetry/location
Request: { driver_id: "drv-9912", lat: 40.7128, lng: -74.0060, speed_mps: 12.4, timestamp: 1783709000 }
Response: { status: "ack" }

4. Database Schema Design

Table: road_segments (PostgreSQL PostGIS)
- segment_id (BIGINT - Primary Key)
- start_node_id (BIGINT)
- end_node_id (BIGINT)
- length_meters (NUMERIC(8,2))
- speed_limit_kmh (INTEGER)
- current_speed_kmh (INTEGER)
- geom (GEOMETRY(LineString, 4326))

Redis Spatial Index (Google S2 Geometry):
- S2 Cell Token: s2:cell:{cell_id_level_13}
- Value: Set of segment_ids overlapping the geographic cell

Table: live_traffic_stats (ClickHouse / TimescaleDB)
- segment_id (BIGINT)
- timestamp_minute (TIMESTAMP)
- average_speed_kmh (FLOAT)
- vehicle_count (INTEGER)

5. Interactive High-Level Architecture

graph TD Client["Driver Mobile App"] -->|GPS Pings 1Hz| IngestService["Location Telemetry Ingestion"] IngestService --> KafkaLoc[("Kafka GPS Telemetry Stream")] KafkaLoc --> FlinkSpeed["Apache Flink Speed & Traffic Aggregator"] FlinkSpeed --> S2Index[("Google S2 Geometry Segment Cache: Redis")] Client -->|Route Request| RouterService["Route Computation Service"] RouterService --> S2Index RouterService --> CHGraph[("Contraction Hierarchies Graph: RAM")] RouterService --> Directions["Turn-by-Turn Dynamic Path"] Client -->|Fetch Map Tiles| MapCDN["Vector Map Tile CDN PoPs"]

6. Scalability Deep Dive & Bottlenecks

Standard Dijkstra or A* shortest path algorithms on a global graph of 500 Million edges take 3-10 seconds per query—unacceptable for interactive maps. Google Maps utilizes Contraction Hierarchies (CH). During offline preprocessing, nodes are contracted in order of relative importance (local residential alleys first, major interstate highways last), and 'shortcut edges' are pre-calculated. At query time, bidirectional search traverses only upward edges in the hierarchy, computing optimal routes across thousands of miles in under 5 milliseconds. Live traffic speeds update edge weights in memory.

7. Production Scaling Strategies

Contraction Hierarchies Precomputation: Pre-contract continental graphs into hierarchical shortcut networks. Query time scales with O(log N) rather than O(N log N), dropping routing compute from seconds to <5ms.

Google S2 Geometry Hierarchical Indexing: Map Earth onto a cube projected to 6 spheres with 30 hierarchical levels. Road segments and GPS pings are indexed into 64-bit integer S2 cell tokens, turning 2D spatial queries into fast 1D range lookups in B-Trees.

Real-Time Speed Aggregation via Flink: Ingest 500K GPS pings/sec into Apache Flink. Compute a 2-minute rolling average speed for every road segment. Discrepancies between current speed and speed limits immediately flag traffic jams.

Vector Map Tile CDN Caching: Rather than raster PNG images, serve vector protobuf tiles containing geometry coordinates. Vector tiles are 80% smaller, client-renderable at any zoom factor, and cached indefinitely on global CDNs.

Dynamic Mid-Trip Rerouting: The mobile navigation SDK periodically queries a lightweight route check endpoint every 60 seconds with current coordinates. If ahead segments experience severe congestion (>5 min delay), the system prompts an automated detour.

Map Matching Kalman Filter: Raw smartphone GPS drift (5-15m error) is corrected using Hidden Markov Models (HMM) and Kalman filters, snapping raw coordinates accurately to the true topological road network.

8. Runnable Production Starter Code

Scaffold

System Design Architectures