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). The platform must ingest billions of live GPS telemetry pings from active devices, continuously reconstruct planetary traffic congestion overlays via streaming analytics, serve zoomable vector map tiles with sub-20ms edge latency, and calculate optimal driving routes across hundreds of millions of road segments in under 25 milliseconds.

At a glance:

Functional Requirements

1. Hierarchical Vector Map Tile Rendering: Serve zoomable vector map tiles across zoom levels 0 through 21 using standard Web Mercator Slippy Map conventions ($Z/X/Y$ coordinates) via Mapbox Vector Tile (MVT/PBF) format with sub-20ms edge latency.
2. Shortest-Path Driving Directions (GetDirections): Calculate optimal driving routes between origin and destination coordinates, accounting for complex turn restrictions, one-way streets, bridge weight limits, highway preferences, and dynamic real-time traffic speeds.
3. Accurate Estimated Time of Arrival (ETA): Continuously estimate arrival times by fusing historical segment velocity profiles, real-time telemetry speed observations, and traffic light delays.
4. Dynamic Proactive Re-Routing: Monitor active in-flight navigation sessions and automatically push real-time detour recommendations via WebSockets/APNs when unexpected incidents, accidents, or gridlocks arise along the remaining route.
5. Live GPS Map Matching (Viterbi HMM): Snap noisy mobile GPS coordinates ($5\text{--}15\text{m}$ error radius) to the most mathematically probable physical road network segments using Hidden Markov Models.

Non-Functional Requirements (SLAs & SLOs)

• Ultra-Low Latency:
  • Map Tile Rendering (CloudFront CDN Edge): $P99 < 20\text{ ms}$.
  • Driving Route Calculation (Sub-continental): $P95 < 15\text{ ms}$, $P99 < 25\text{ ms}$.
  • Real-Time Traffic Velocity Update Pipeline: Telemetry ping to live routing weight delta $< 30\text{ seconds}$.
• Planetary Availability: $99.999\%$ uptime SLA for core navigation and directions APIs ($< 5.26\text{ minutes}$ unscheduled downtime per calendar year).
• Scale: Support $1,000,000,000\text{ DAU}$, $20,000,000$ concurrent navigation sessions, $50\text{M daily route calculations}$, and $1\text{ Billion tile requests/day}$.
• Data Durability & Offline Support: Route polylines and turn-by-turn guidance steps cached locally on mobile devices; clients must navigate through tunnels and dead zones without connection drops via inertial dead reckoning.

---

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

Road Network Graph Sizing (Planetary Graph Memory)

The global drivable road network consists of intersections (vertices) and road segments (directed edges):

• Global Intersections (Vertices $V$): $\approx 100,000,000\text{ nodes}$ ($100\text{M intersections}$).
• Global Directed Road Segments (Edges $E$): $\approx 300,000,000\text{ directed edges}$ ($300\text{M segments}$).
• Compact In-Memory Forward-Star Graph Structs & Cache Line Alignment: In standard object-oriented graphs (std::vector<std::vector<Edge*>>), traversing adjacent edges triggers pointer chasing across disjoint heap allocations, generating continuous CPU L1/L2/L3 cache misses ($\approx 60\text{--}100\text{ ns}$ DRAM stall per miss). We pack the graph into a flat Forward-Star (Compressed Sparse Row) representation aligned to 64-byte CPU cache lines:
  1. Vertex Struct (16 bytes): lat (float32, 4B), lon (float32, 4B), first_edge_offset (uint32, 4B), ch_rank (uint32, 4B) $= 16\text{ bytes}$. There is no stored node_id: after Hilbert renumbering (item 4) the node's id is its array index, which is what makes the layout compact. The CH rank has to live here because the query (Section 6.3) compares ranks on every edge relaxation.
  2. Directed Edge Struct (16 bytes aligned): target_node_id (uint32, 4B), distance_meters (uint32, 4B), base_traversal_time_ms (uint16, 2B), flags_and_turn_restrictions (uint16, 2B), live_speed_multiplier (uint8, 1B), road_class (uint8, 1B), padding (2B) = 16 bytes.
  3. L1 Cache Line Density: Exactly $4\text{ edges}$ occupy a single $64\text{-byte}$ CPU cache line. When relaxing edges from vertex $u$, a single memory bus fetch loads up to 4 contiguous candidate edges directly into L1 CPU cache.
  4. Spatial Locality via Hilbert Curve Renumbering: Intersections are renumbered along a 2D Hilbert Space-Filling Curve. Geographically adjacent intersections occupy adjacent indices in RAM, maximizing L2/L3 hardware prefetcher hit rates during graph traversal.
• Raw Graph Memory Footprint: $\text{Memory}_{\text{nodes}} = 100 \times 10^6 \times 16\text{ bytes} = 1.6\text{ GB}$ $\text{Memory}_{\text{edges}} = 300 \times 10^6 \times 16\text{ bytes} = 4.8\text{ GB}$ $\text{Memory}_{\text{raw}} = 1.6\text{ GB} + 4.8\text{ GB} = \mathbf{6.4\text{ GB RAM}}$
• Contraction Hierarchies (CH) Shortcuts Overhead ($+35\%$ shortcut edges): $\text{Memory}_{\text{shortcuts}} = (300 \times 10^6 \times 0.35) \times 16\text{ bytes} \approx 1.68\text{ GB}$ $\text{Total Planetary CH Graph RAM} \approx 6.4\text{ GB} + 1.68\text{ GB} + 1.5\text{ GB (Heuristics)} \approx \mathbf{9.6\text{ GB RAM}}$
• Crucial Architectural Conclusion: The entire planetary road graph fits comfortably inside the L3 cache / RAM of a single modern compute-optimized EC2 instance (c6in.4xlarge with 32 GiB RAM and 50 Gbps network), completely eliminating distributed network RPCs during shortest-path graph search.

Telemetry Ingestion & Real-Time Traffic Volume

• Active In-Flight Drivers: $20,000,000\text{ drivers}$ streaming GPS telemetry.
• Broadcast Frequency: 1 ping every 5 seconds ($0.2\text{ pings/sec/driver}$).
• Global Telemetry Ingestion QPS: $\text{QPS}_{\text{telemetry}} = \frac{20 \times 10^6\text{ drivers}}{5\text{ seconds}} = \mathbf{4,000,000\text{ pings/sec}} \quad (\text{Peak: } \mathbf{6,000,000\text{ pings/sec}})$
• Telemetry Ingestion Bandwidth:
  • Encoded binary Protobuf ping: driver_id (16B), lat (8B), lon (8B), speed_mps (2B), bearing (2B), timestamp (8B), accuracy (2B) $\approx 46\text{ bytes}$ (with transport envelope $\approx 100\text{ bytes}$). $\text{Bandwidth}_{\text{in}} = 4,000,000\text{ pings/sec} \times 100\text{ bytes} = 400\text{ MB/sec} = \mathbf{3.2\text{ Gbps}}$

Map Tile Traffic & Edge CDN Caching

• Daily Tile Requests: $1,000,000,000\text{ tile requests/day}$ ($1\text{ Billion}$).
• Average Tile Request QPS: $\text{QPS}_{\text{tile, avg}} = \frac{1 \times 10^9}{86,400} \approx \mathbf{11,574\text{ QPS}} \quad (\text{Peak: } \mathbf{50,000\text{ QPS}})$
• Average Vector Tile Size (MVT Protobuf): $\approx 25\text{ KB}$ (compressed).
• Edge Cache Hit Ratio (Amazon CloudFront): $99.2\%$.
• Origin S3 Tile Read QPS: $\text{QPS}_{\text{S3 origin}} = 50,000\text{ QPS} \times (1 - 0.992) = \mathbf{400\text{ QPS}}$
• CDN Peak Egress Bandwidth: $\text{Bandwidth}_{\text{CDN egress}} = 50,000\text{ QPS} \times 25\text{ KB} = 1.25\text{ GB/sec} = \mathbf{10.0\text{ Gbps}}$

Directions & Routing Throughput

• Daily Completed Routes: $50,000,000\text{ route calculations/day}$.
• Average Routing QPS: $\text{QPS}_{\text{routes, avg}} = \frac{50 \times 10^6}{86,400} \approx \mathbf{578.7\text{ QPS}}$
• Peak Routing QPS ($10\times$ rush-hour spike + dynamic reroutes): $\text{QPS}_{\text{routes, peak}} \approx \mathbf{5,787\text{ QPS}} \quad (\text{dimensioned for } \mathbf{10,000\text{ QPS}})$

---

3. AWS-First High-Level Architecture

The platform is decoupled into three specialized subsystems: 1) Vector Map Tile Edge CDN, 2) Telemetry Ingestion & Stream Processing Pipeline, and 3) In-Memory Shortest-Path Routing & Rerouting Engine.

Synthesizing vector architecture diagram...

The platform is three subsystems that share only the edge. In the "Hierarchical Map Tile Subsystem" panel, a weekly batch job builds vector tiles from OpenStreetMap into S3, and CloudFront serves over 99% of tile requests from cache, so map display costs almost nothing at the origin. In the "GPS Telemetry & Live Traffic Pipeline" panel, about 4M GPS pings per second flow through the NLB and ingest fleet into Kinesis; Flink first snaps each noisy ping to the road it is really on (Viterbi map matching), then averages speeds per road segment over 5 minutes into Redis. In the "In-Memory Shortest-Path Routing Engine" panel, route requests hit servers holding the road graph in memory as contraction hierarchies, updated with live speeds every minute; active trips are stored in DynamoDB, and when a road on a trip closes, a Lambda pushes a detour to the driver. Precompute what is static (tiles, hierarchy), stream what changes (speeds), and combine them only at query time.

Data Flow Walkthrough

1. Map Tile Discovery: When a user pans or zooms, the client computes required Mercator tile coordinates $(z, x, y)$ and queries CloudFront: GET /v1/tiles/14/4823/6120.pbf. Over $99.2\%$ of requests hit CloudFront's distributed SSD edge caches ($< 15\text{ ms}$). Edge misses read directly from Amazon S3. The mobile device's Metal/Vulkan GPU shaders render vectors, 3D buildings, and labels locally.
2. Telemetry Ingestion: Active mobile devices emit binary GPS pings every 5 seconds to AWS NLB over persistent TCP/TLS connections. The ECS Ingestion fleet aggregates pings with the Kinesis Producer Library (many pings per Kinesis record) and writes to an Amazon Kinesis Data Stream of $\approx 500$ shards. Shard math: a shard accepts $1{,}000$ records/sec or $1\text{ MB/sec}$, whichever binds first. Without aggregation, $4\text{M pings/sec}$ would need $4{,}000$ shards; with aggregation the byte limit binds instead, $400\text{ MB/sec} \div 1\text{ MB/sec} = 400$ shards, provisioned as 500 for burst headroom.
3. Map Matching via HMM: An Apache Flink application reads the raw GPS stream and executes a Viterbi Hidden Markov Model to eliminate GPS jitter ($5\text{--}15\text{m}$) and snap points to directed physical road segments.
4. Traffic Speed Calculation: Flink aggregates vehicle speeds across 5-minute tumbling windows per road segment, comparing observed velocities to posted speed limits. Speed overrides are published to an ElastiCache Redis Cluster.
5. Route Calculation: When a rider requests directions (POST /v1/navigation/routes), the API Gateway invokes the EC2 Routing Fleet. The routing engine runs an in-memory Bidirectional Contraction Hierarchy (CH) upward search across the global graph, incorporating dynamic live speed metrics from Redis. The optimal path, turn instructions, and polyline are returned in $< 20\text{ ms}$.
6. Dynamic Rerouting: If a severe traffic jam or bridge closure occurs, Flink emits a segment alert. The Reroute Trigger service scans active navigation sessions in DynamoDB whose remaining polyline traverses the blocked segment, recalculates alternative routes, and pushes proactive detour notifications to drivers.

Core Request Tracing Execution Walkthrough

---

4. API Interface Design & Wire Protocols

1. Calculate Optimal Driving Route (POST /v1/navigation/routes)

Calculates optimal routes between origin and destination coordinates with dynamic traffic penalties.

Request Headers & Payload

httpCopy
POST /v1/navigation/routes HTTP/1.1
Host: routes.navigation.platform.aws.internal
Authorization: Bearer jwt_nav_usr_7718293041
Content-Type: application/json
X-Correlation-ID: corr_nav_01J8N6K3P4V9QZ2W8M1Y7R4X

jsonCopy
{
  "origin": {
    "latitude": 37.774929,
    "longitude": -122.419416
  },
  "destination": {
    "latitude": 37.338208,
    "longitude": -121.886329
  },
  "travel_mode": "DRIVING",
  "routing_preference": "FASTEST_WITH_TRAFFIC",
  "avoid_options": ["TOLLS", "FERRIES"],
  "departure_time_epoch_ms": 1767225600000,
  "alternatives_count": 2
}

Response: 200 OK

jsonCopy
{
  "routes": [
    {
      "route_id": "rt_fastest_sf_sanjose_101",
      "summary": "via US-101 S",
      "distance_meters": 77840,
      "duration_seconds": 3120,
      "typical_duration_seconds": 2700,
      "delay_seconds": 420,
      "congestion_level": "MODERATE",
      "encoded_polyline": "u{~nFjk`uVv]fYtXo\\rUqV...",
      "bounds": {
        "northeast": { "lat": 37.7751, "lon": -121.8859 },
        "southwest": { "lat": 37.3380, "lon": -122.4201 }
      },
      "legs": [
        {
          "step_index": 0,
          "instruction": "Head southeast on Market St toward 10th St",
          "distance_meters": 450,
          "duration_seconds": 65,
          "maneuver": "DEPART"
        },
        {
          "step_index": 1,
          "instruction": "Merge onto US-101 S via the ramp to San Jose",
          "distance_meters": 72400,
          "duration_seconds": 2850,
          "maneuver": "MERGE_HIGHWAY"
        }
      ]
    }
  ],
  "session_token": "sess_nav_88192a0e_sf_sj",
  "computation_latency_ms": 11.4
}

2. Fetch Mapbox Vector Tile (GET /v1/map/tiles/{z}/{x}/{y}.pbf)

Delivers a compressed binary protocol buffer containing vector geometry for Slippy Map coordinate $(z, x, y)$.

httpCopy
GET /v1/map/tiles/14/2624/6332.pbf HTTP/1.1
Host: tiles.platform.aws.internal
If-None-Match: "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
Accept-Encoding: gzip, br

• Status: 200 OK (or 304 Not Modified)
• Content-Type: application/x-protobuf
• Content-Encoding: gzip
• Cache-Control: public, max-age=604800, immutable (7-day edge cache)

3. High-Frequency Telemetry Ingestion Ping (Protobuf over UDP/TCP)

protobufCopy
syntax = "proto3";
package navigation.telemetry;

message GpsPingBatch {
  string device_id = 1;
  int64 batch_timestamp_ms = 2;
  repeated GpsPing pings = 3;
}

message GpsPing {
  double latitude = 1;
  double longitude = 2;
  float speed_mps = 3;
  float bearing_degrees = 4;
  int64 timestamp_epoch_ms = 5;
  float horizontal_accuracy_meters = 6;
  bool is_navigating = 7;
}

---

5. Data Models & Storage Architecture

Database Selection Justification

1. In-Memory Forward-Star Graph (EC2 RAM): Static and shortcut edge graphs are loaded directly into bare-metal memory structures. Pointer-based adjacency lists in C++ or Rust eliminate serialization overhead and enable memory lookups in nanoseconds.
2. Amazon ElastiCache Redis 7 Cluster: Stores ephemeral, rolling 5-minute dynamic speed overrides for each directed road segment (speed:edge:<edge_id>).
3. Amazon S3 Standard + CloudFront: Serves pre-rendered vector map tiles (.pbf). S3 offers $99.999999999\%$ (11 9s) durability and near-infinite horizontal GET concurrency.
4. Amazon DynamoDB: Maintains active navigation session states, polyline coordinates, and driver route tracking coordinates for dynamic rerouting.

1. In-Memory Graph Memory Layout (Forward-Star Format)

textCopy
================================================================================
                    FORWARD-STAR COMPACT ROAD GRAPH IN RAM
================================================================================
Node Array (Length |V| = 100M):
Index (NodeID) | Latitude (4B) | Longitude (4B) | First Edge Offset (4B) | Node Rank (4B)
--------------------------------------------------------------------------------
0              | 37.77492      | -122.41941     | 0                      | 1204
1              | 37.77510      | -122.41890     | 4                      | 8940210
...            | ...           | ...            | ...                    | ...

Edge Array (Length |E| + |Shortcuts| = 405M):
Edge Index     | Target NodeID | Length (m)     | FreeFlow Speed (km/h)  | Flags / Restrictions
--------------------------------------------------------------------------------
0              | 1             | 120            | 45                     | ONE_WAY_FORWARD
1              | 4             | 85             | 30                     | NO_LEFT_TURN
2              | 902           | 240            | 50                     | TOLL_ROAD
3              | 18            | 410            | 100                    | CH_SHORTCUT_EDGE
================================================================================

2. S3 Vector Tile Directory Structure

Pre-compiled Mapbox Vector Tiles are stored hierarchically following Web Mercator Quadkeys:

textCopy
s3://planetary-map-tiles-production/
  v2026_09/
    streets/
      0/0/0.pbf              # Global Zoom Level 0
      1/0/0.pbf, 1/1/0.pbf   # Zoom Level 1
      ...
      14/2624/6332.pbf       # Zoom Level 14 (Street-level resolution)
      21/1048576/894012.pbf  # Zoom Level 21 (Building footprint resolution)

3. Active Navigation Session Table (Amazon DynamoDB)

• Table Name: ActiveNavigationSessions
• Billing Mode: On-Demand with auto-scaling

---