System Design: Designing Google Maps

Designing a navigation system like Google Maps or Waze involves managing massive amounts of geographic data and performing complex graph calculations (Pathfinding) in real-time.

1. Core Requirements

• Map Rendering: Displaying the map at various zoom levels.
• Routing: Finding the shortest/fastest path between two points.
• ETA: Estimating arrival time based on distance and traffic.
• Real-time Traffic: Updating routes based on accidents or congestion.

2. Modeling the World: Road Networks

The world is modeled as a massive Directed Weighted Graph.

• Nodes: Intersections or dead-ends.
• Edges: Road segments connecting nodes.
• Weights: Distance or travel time (impacted by speed limits and traffic).

3. Pathfinding Algorithms at Scale

A simple Dijkstra or A* algorithm works for a small city, but running it on a graph with billions of nodes (global map) is too slow.

Optimization: Hierarchical Routing

Google Maps uses a tiered approach:

1. Local Roads: Only searched for the start and end points of a trip.
2. Arterial Roads: Connecting neighborhoods.
3. Highways: Used for long-distance travel.

• The Logic: You only calculate the full Dijkstra for the local parts, then jump onto a pre-computed "Highway Graph" for the majority of the trip.

Optimization: Contraction Hierarchies

A technique that "contracts" unimportant nodes (like a quiet street corner) and replaces them with "shortcuts." This reduces the number of nodes the search algorithm needs to visit by several orders of magnitude.

4. Calculating ETA (Real-time Traffic)

ETA is not just distance / speed_limit. It requires real-time data ingestion.

• Data Source: Millions of mobile devices sending GPS pings (Apache Kafka).
• Processing: A stream processing engine (Apache Flink) aggregates these pings into "Speed segments."
• Storage: These segments are stored in a fast Time-Series Database to track historical patterns (e.g., "Monday mornings are slow on Route 101").

5. Storage and Serving

• Map Tiles: Pre-rendered image tiles or vector data stored in a Geo-redundant BLOB store (S3) and served via CDN.
• Graph Data: Custom in-memory graph databases optimized for fast traversal.

6. Global Scalability

The map is partitioned into Geospatial Shards (cells). When a user moves, their device fetches tiles and graph data for neighboring cells.

Summary

The engineering behind Google Maps is a masterclass in Graph Optimization. By combining hierarchical routing with real-time streaming data, you can navigate a user through the entire world with sub-second pathfinding and remarkably accurate ETAs.