System Design: Designing Google Maps (Navigation and ETA)

Designing a navigation system like Google Maps or Waze is one of the most intellectually challenging problems in software engineering. Calculate the optimal route between two points on opposite sides of a continent in less than a second requires traversing a graph containing hundreds of millions of nodes and edges, all while factoring in real-time traffic speeds, road closures, and live detours.

This case study analyzes the architecture of a global real-time navigation and ETA service, detailing road network graphing, hierarchical pathfinding optimizations, geospatial sharding, and real-time speed stream ingestion.

1. Requirements & Core Constraints

To build a high-performance navigation system, we must define functional expectations and scale requirements.

Functional Constraints

• Map Navigation and Route Generation: Users must receive the fastest and shortest paths between starting and ending coordinates, with options for transit mode (driving, walking, biking).
• Accurate ETA Calculation: Estimate arrival time with precision, adjusting for current traffic conditions dynamically.
• Dynamic Re-routing: Detect driver deviations or ahead-of-route accidents and generate detours in under $3\text{ seconds}$.
• Live Traffic Aggregation: Continuously ingest location streams from driving users to calculate current road segment speeds.

Non-Functional SLAs

• Global Low Latency: Pathfinding queries must return results within $\le 200\text{ms}$ (p99) for standard intra-city navigation.
• Massive Ingestion Capacity: Ingest millions of location pings per second from active navigation clients worldwide without dropping telemetry data.
• High Read Scale: Support hundreds of thousands of concurrent active navigation sessions displaying real-time ETAs.
• High Data Freshness: Traffic updates and road status changes must propagate to the routing engine within $\le 30\text{ seconds}$.

Back-of-the-Envelope Estimation

1. Ingestion Scale (Telemetry)

• Active Navigation Users: $50,000,000$ (50 Million) active drivers at peak globally.
• Telemetry Frequency: Each client transmits their GPS location (latitude, longitude, speed, heading) once every 10 seconds.
• Ingestion QPS: $$\text{Telemetry QPS} = \frac{50,000,000 \text{ clients}}{10 \text{ seconds}} = 5,000,000 \text{ events/sec}$$
• Data Payload Size: Each location telemetry ping is roughly $100\text{ bytes}$: $$\text{Ingress Bandwidth} = 5,000,000 \text{ events/sec} \times 100 \text{ bytes} = 500 \text{ MB/s} \approx 4 \text{ Gbps}$$

2. Graph Size Sizing (Global Road Network)

• Global Intersections (Nodes): Assume $300,000,000$ (300 Million) road intersections globally.
• Global Road Segments (Edges): Assume $400,000,000$ (400 Million) road segments (each intersection connects to roughly 1.3 roads).
• Node Memory Size: Each node stores a 64-bit ID, 64-bit latitude, and 64-bit longitude ($24\text{ bytes}$): $$\text{Nodes Memory} = 300,000,000 \times 24 \text{ bytes} = 7.2 \text{ GB}$$
• Edge Memory Size: Each edge stores start node ID, end node ID, speed limit, road segment distance, and traffic congestion factor ($40\text{ bytes}$): $$\text{Edges Memory} = 400,000,000 \times 40 \text{ bytes} = 16 \text{ GB}$$
• Total In-Memory Graph footprint: $\approx 23.2 \text{ GB}$ (easily fits inside standard RAM, but search optimization is still critical to avoid scanning millions of nodes per query).

2. API Design & Core Contracts

The navigation service exposes public APIs for route queries and internal ingestion contracts for active telemetry.

1. Request Route Navigation

POST /api/v1/navigation/route Invoked by the mobile app to load available routes and calculate the initial ETA.

Request Headers:

Content-Type: application/json
Accept: application/json

Request Payload:

{
  "start_location": {
    "latitude": 37.7749,
    "longitude": -122.4194
  },
  "destination_location": {
    "latitude": 37.3382,
    "longitude": -121.8863
  },
  "travel_mode": "driving",
  "avoid_tolls": false
}

Response Payload (200 OK):

{
  "route_id": "rt_88f9a2c3",
  "distance_meters": 78200,
  "eta_seconds": 3240,
  "polylines": "s{~fFvb|g@`@dA{C...",
  "waypoints": [
    {
      "name": "US-101 S",
      "distance_meters": 75000,
      "duration_seconds": 3000
    }
  ]
}

2. Client GPS Telemetry Event (Ingestion Stream)

POST /api/v1/telemetry/pings Dispatched in batches by the client SDK every 10 seconds to feed the traffic engine.

Request Payload:

{
  "client_id": "usr_99f8e7d6c5",
  "device_timestamp": 1782236500000,
  "pings": [
    {
      "latitude": 37.77492,
      "longitude": -122.41945,
      "speed_mps": 14.2,
      "bearing_degrees": 180.5
    }
  ]
}

Response (202 Accepted): The tracking server acknowledges the request in under 5ms, offloading the event payload to Kafka.

3. High-Level Design (HLD)

The architecture leverages a streaming telemetry ingestion pipeline to keep graph edge weights highly accurate, coupled with an optimized query tier for route pathfinding.

graph TD
    %% User Inputs
    UserClient[Mobile Client App] -->|1. Route Request| APIGateway[API Gateway]
    UserClient -->|1. Live GPS Pings| TelemetryFleet[Telemetry Ingest Fleet]

    %% Telemetry Stream Ingestion
    subgraph TelemetryPath["Telemetry Stream Pipeline"]
        TelemetryFleet -->|2. Ingest Stream| KafkaCluster[("Apache Kafka Telemetry Topic")]
        KafkaCluster -->|3. Consume Pings| FlinkCluster["Apache Flink Map-Matcher Engine"]
        FlinkCluster <-->|4. Query Road Grid| GeoDB[("Geospatial Database (PostGIS)")]
        FlinkCluster -->|5. Publish Speeds| SpeedBroker[("Kafka Speed Events")]
        SpeedBroker -->|6. Write Updates| TrafficService["Live Traffic Predictor Service"]
    end

    %% Pathfinding and Routing Tier
    subgraph QueryPath["Route Resolution Query Tier"]
        APIGateway -->|7. Route Query| RoutingEngine["Graph Routing Engine Fleet"]
        RoutingEngine <-->|8. Load precomputed shortcuts| CacheGraph[("In-Memory Graph Cache")]
        TrafficService -->|9. Apply dynamic weights| RoutingEngine
        RoutingEngine -->|10. Return Directions| APIGateway
    end

    classDef database fill:#0d3b66,stroke:#f4d35e,stroke-width:2px,color:#fff;
    classDef cluster fill:#2e0f38,stroke:#f4d35e,stroke-width:2px,color:#fff;
    classDef client fill:#3d5a80,stroke:#293241,stroke-width:2px,color:#fff;
    
    class GeoDB,CacheGraph database;
    class APIGateway,TelemetryFleet,KafkaCluster,FlinkCluster,SpeedBroker,TrafficService,RoutingEngine cluster;
    class UserClient client;

End-to-End Architectural Workflows

1. Ingesting Live Telemetry and Computing Traffic Speed

1. GPS Ping Submission: The mobile device sends location telemetry to the Telemetry Ingest Fleet.
2. Buffer Stream writing: The stateless servers parse the payload and write it immediately to Apache Kafka partitioned by client_id to distribute the massive scale.
3. Map Matching in Flink: Apache Flink consumes the GPS stream. Because GPS pings have a slight accuracy drift, Flink executes a Hidden Markov Model (HMM) algorithm, querying the Geospatial Database (PostGIS) to snap the raw coordinates to the correct physical road segment.
4. Velocity Analysis: Flink aggregates mapped pings per road segment over a 30-second sliding window to calculate the average traffic speed.
5. Dynamic Weight Updates: Calculated segment speeds are emitted to a second Kafka topic and consumed by the Traffic Predictor Service, which updates the live edge weight table in memory.

2. Querying Routes and Pathfinding

1. Route Calculation: When a user inputs a destination, the request hits the API Gateway and routes to the Graph Routing Engine Fleet.
2. Precomputed Shortcut Lookup: The engine retrieves the static road network graph from the In-Memory Graph Cache (utilizing precomputed shortcuts from Contraction Hierarchies).
3. Applying Real-Time Weightings: The engine queries the Traffic Predictor Service to overlay real-time speeds onto the active path segments.
4. Running Search Algorithm: The engine executes a Bidirectional Dijkstra search using precomputed Contraction Hierarchies to return the optimal path in under $200\text{ms}$.

4. Low-Level Design (LLD) & Data Models

Database Selection Rationale

Graph navigation requires databases optimized for spatial relationships and fast read-only access.

SQL Database Schema (Road Segment Metadata)

-- Intersection Nodes Registry
CREATE TABLE map_intersections (
    node_id BIGINT PRIMARY KEY,
    latitude DECIMAL(9, 6) NOT NULL,
    longitude DECIMAL(9, 6) NOT NULL,
    geohash VARCHAR(12) NOT NULL -- Spatial index partition key
);

CREATE INDEX idx_map_intersections_geohash ON map_intersections(geohash);

-- Road Segment Edges Registry
CREATE TABLE road_segments (
    segment_id BIGINT PRIMARY KEY,
    start_node_id BIGINT REFERENCES map_intersections(node_id),
    end_node_id BIGINT REFERENCES map_intersections(node_id),
    distance_meters DECIMAL(8, 2) NOT NULL,
    speed_limit_mps DECIMAL(4, 1) NOT NULL,
    one_way BOOLEAN DEFAULT FALSE,
    surface_type VARCHAR(32),
    polyline_geometry GEOMETRY(LineString, 4326) -- PostGIS Spatial Line type
);

-- Spatial index for rapid location-to-edge mapping queries
CREATE INDEX idx_road_segments_spatial ON road_segments USING GIST(polyline_geometry);

5. Pathfinding Algorithms at Scale

Calculating a route across a continent on a raw graph containing hundreds of millions of nodes using a standard algorithm is far too slow for production. We must employ structural graph optimization techniques.

1. Traditional Pathfinding Limits: Dijkstra vs. A* Search

• Dijkstra: Dijkstra expands in all directions equally, forming a huge circular search boundary. This guarantees finding the absolute shortest path, but visits millions of unnecessary nodes.
• A* Search: A* uses a distance heuristic (e.g., straight-line Euclidean distance to target) to guide the search forward, significantly reducing the node expansion size. However, it can still search many unproductive side streets if blocked by natural barriers (e.g., rivers, mountains).

2. Contraction Hierarchies (The Production Gold Standard)

Contraction Hierarchies speed up pathfinding queries by precomputing shortcut edges for transit roads, bypassing minor streets during long-distance searches.

• Preprocessing Step: We rank nodes based on their importance (e.g., highway exits are highly important, dead-end neighborhood corners are low importance). Nodes are "contracted" one by one in ascending order of importance. When a node is contracted, we add "shortcut edges" between its neighbors if that node was part of the shortest path between them.
• Query Step: The routing engine runs a Bidirectional Dijkstra Search. The forward search from the source node and the backward search from the target node only traverse edges that lead to nodes of higher importance. This reduces the search space from 100 Million nodes to less than 1,000, yielding sub-100ms response times.

graph TD
    subgraph Preprocessing_Tier["1. Offline Precomputation"]
        A[Local Corner Node] -->|Contracted| B[Shortcut Edge added]
    end
    
    subgraph Query_Tier["2. Online Query Resolution"]
        Source[Source: Home] -->|Traverse Upward| HighwayExit[Highway Node]
        HighwayExit -->|Follow Shortcut Edge| DestExit[Destination Exit]
        DestExit -->|Traverse Downward| Target[Target: Work]
    end

Compilable Java Bidirectional Dijkstra Routing Engine

Below is a complete, production-grade Java class implementing a Bidirectional Dijkstra algorithm on an adjacency graph list:

package com.codesprintpro.navigation.routing;

import java.io.Serializable;
import java.util.*;

public class BidirectionalDijkstra {

    public static class Edge implements Serializable {
        public final int targetNodeId;
        public final double travelTimeSeconds;

        public Edge(int targetNodeId, double travelTimeSeconds) {
            this.targetNodeId = targetNodeId;
            this.travelTimeSeconds = travelTimeSeconds;
        }
    }

    public static class RoutingGraph {
        public final Map<Integer, List<Edge>> forwardAdjacencyList = new HashMap<>();
        public final Map<Integer, List<Edge>> backwardAdjacencyList = new HashMap<>();

        public void addEdge(int from, int to, double cost) {
            forwardAdjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(to, cost));
            backwardAdjacencyList.computeIfAbsent(to, k -> new ArrayList<>()).add(new Edge(from, cost));
        }
    }

    public static class SearchResult {
        public final double shortestCost;
        public final int meetingNodeId;

        public SearchResult(double shortestCost, int meetingNodeId) {
            this.shortestCost = shortestCost;
            this.meetingNodeId = meetingNodeId;
        }
    }

    public static SearchResult findRoute(RoutingGraph graph, int startNode, int endNode) {
        // Priority queues for bidirectional search
        PriorityQueue<NodeDistance> forwardQueue = new PriorityQueue<>(Comparator.comparingDouble(n -> n.distance));
        PriorityQueue<NodeDistance> backwardQueue = new PriorityQueue<>(Comparator.comparingDouble(n -> n.distance));

        // Distance trackers
        Map<Integer, Double> forwardDistances = new HashMap<>();
        Map<Integer, Double> backwardDistances = new HashMap<>();

        forwardDistances.put(startNode, 0.0);
        backwardDistances.put(endNode, 0.0);

        forwardQueue.add(new NodeDistance(startNode, 0.0));
        backwardQueue.add(new NodeDistance(endNode, 0.0));

        Set<Integer> forwardVisited = new HashSet<>();
        Set<Integer> backwardVisited = new HashSet<>();

        double bestDistance = Double.MAX_VALUE;
        int meetingNode = -1;

        while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
            // Forward step
            if (!forwardQueue.isEmpty()) {
                NodeDistance curr = forwardQueue.poll();
                int u = curr.nodeId;
                if (!forwardVisited.contains(u)) {
                    forwardVisited.add(u);

                    // Check overlap
                    if (backwardDistances.containsKey(u)) {
                        double total = forwardDistances.get(u) + backwardDistances.get(u);
                        if (total < bestDistance) {
                            bestDistance = total;
                            meetingNode = u;
                        }
                    }

                    for (Edge edge : graph.forwardAdjacencyList.getOrDefault(u, Collections.emptyList())) {
                        int v = edge.targetNodeId;
                        double cost = edge.travelTimeSeconds;
                        double nextDist = forwardDistances.get(u) + cost;
                        if (nextDist < forwardDistances.getOrDefault(v, Double.MAX_VALUE)) {
                            forwardDistances.put(v, nextDist);
                            forwardQueue.add(new NodeDistance(v, nextDist));
                        }
                    }
                }
            }

            // Backward step
            if (!backwardQueue.isEmpty()) {
                NodeDistance curr = backwardQueue.poll();
                int u = curr.nodeId;
                if (!backwardVisited.contains(u)) {
                    backwardVisited.add(u);

                    // Check overlap
                    if (forwardDistances.containsKey(u)) {
                        double total = forwardDistances.get(u) + backwardDistances.get(u);
                        if (total < bestDistance) {
                            bestDistance = total;
                            meetingNode = u;
                        }
                    }

                    for (Edge edge : graph.backwardAdjacencyList.getOrDefault(u, Collections.emptyList())) {
                        int v = edge.targetNodeId;
                        double cost = edge.travelTimeSeconds;
                        double nextDist = backwardDistances.get(u) + cost;
                        if (nextDist < backwardDistances.getOrDefault(v, Double.MAX_VALUE)) {
                            backwardDistances.put(v, nextDist);
                            backwardQueue.add(new NodeDistance(v, nextDist));
                        }
                    }
                }
            }
        }

        return new SearchResult(bestDistance == Double.MAX_VALUE ? -1.0 : bestDistance, meetingNode);
    }

    private static class NodeDistance {
        final int nodeId;
        final double distance;

        NodeDistance(int nodeId, double distance) {
            this.nodeId = nodeId;
            this.distance = distance;
        }
    }
}

6. Scaling Challenges & System Bottlenecks

Operating a real-time navigation graph under massive load introduces severe bottlenecks. Here is how we mitigate them:

1. Ingestion Bottlenecks during Real-Time Traffic Anomalies

• The Bottleneck: When an accident occurs on a major highway, thousands of drivers slow down or stop simultaneously. This triggers a sudden flood of location pings, saturating the telemetry ingestion fleet and causing a write bottleneck.
• The Mitigation: Dynamic Ingestion Throttle & Adaptive Frequency. The client SDK is designed to adjust its transmission frequency dynamically based on the user's velocity.
  • If the user is moving at high speed ($> 50 \text{ mph}$), location pings are sent every 10 seconds.
  • If the vehicle is stationary or crawling in slow traffic ($< 5 \text{ mph}$), the ping interval is throttled down to 30 seconds.
  • This adaptive throttling reduces total ingestion write workloads by over $60%$ during major traffic pileups, protecting the stream pipeline.

2. Spatial Grid Sharding and Cross-Cell Paths

• The Bottleneck: Graph structures cannot be easily partitioned across separate databases without breaking edge traversals that span partitions. If we shard maps by state or country boundaries, calculating a cross-country route requires traversing across multiple independent nodes, causing slow database read overhead.
• The Mitigation: Geohash Spatial Sharding & Boundary Nodes.
  • We divide the global map into a hierarchical grid utilizing Geohash cells.
  • Nodes and edges are stored in local, isolated shards corresponding to their Geohash cells.
  • To support cross-cell searches, we define Boundary Intersection Nodes that link adjacent cells. These boundary links are pre-cached, allowing the routing engine to jump between cells without executing global scans.

7. Technical Trade-offs & Consistency Models

1. Offline Precomputation vs. Live Update Latency

8. Resilience & Failure Scenarios

1. Regional Graph In-Memory Cache Failures

The routing engine relies on a massive in-memory graph cache to calculate routes. If a cache host suffers a hardware failure, it loses its graph segment, which can lead to pathfinding failures.

• Recovery Protocol: We deploy graph caches in redundant clusters using RocksDB as a local persistent storage backing on SSDs. If a node crashes, a standby node takes over the partition instantly. Rather than rebuilding the graph segment in memory from PostgreSQL (which would take minutes), the node reads directly from its local RocksDB store, recovering in under 5 seconds.

2. Dynamic Traffic Service Isolation

If the Live Traffic Predictor Service fails or becomes isolated due to a network partition, the routing engine cannot retrieve real-time speeds, risking outdated directions.

• Recovery Protocol: The routing engine is designed with a graceful fallback system. If the live traffic service becomes unavailable, the engine falls back to historical average speed profiles mapped by day-of-week and time-of-day. This historical data is pre-cached on the routing hosts, allowing navigation to continue uninterrupted during a traffic system outage.

9. Candidate Verbal Script (Interview Guide)

Below is an exhaustive, verbatim transcript showing how a Staff Engineer candidate navigates the design of a real-time navigation and ETA system:

Interviewer: "How would you design a system like Google Maps that can calculate optimal routes and accurate ETAs for millions of active drivers?"

Candidate: "I will architect a real-time navigation system that separates map data precomputation from dynamic traffic overlaying, utilizing a Hierarchical Routing Architecture.

To handle our physical scale, the global road network is modeled as a directed weighted graph. Intersections are nodes and road segments are edges, with weights representing travel time.

Because standard Dijkstra search is too slow to traverse a graph with 300 million nodes in real-time, we precompute Contraction Hierarchies offline to add shortcut edges between major highway exits. This reduces our active search space by several orders of magnitude.

At runtime, the Graph Routing Engine runs a bidirectional Dijkstra search across this optimized skeleton. It overlays real-time speeds by querying the Traffic Predictor Service, which processes location telemetry from active drivers in real-time."

Interviewer: "How do you calculate real-time speeds? With 50 million drivers sending GPS pings, how do you handle the massive write and process load?"

Candidate: "We decouple ingestion from processing using a streaming pipeline:

1. At Ingestion: Mobile clients write GPS telemetry to stateless servers, which buffer payloads into Apache Kafka partitioned by client_id to distribute the load.
2. At Processing: We use Apache Flink to consume the stream. Flink runs map-matching algorithms asynchronously to snap raw coordinates to physical road segments using spatial indexes.
3. At Aggregation: Flink aggregates vehicle speeds per segment in 30-second sliding windows. The calculated speeds are sent to the traffic service, which updates the active graph weights in memory in under 30 seconds."