Google Maps

Overview

Google Maps is the world’s most used mapping and navigation service, serving 1B+ monthly active users with real-time directions, place search, street view, and traffic information. Its architecture combines massive precomputed graph data (road networks, transit schedules), real-time sensor data (traffic from billions of Android phones), geospatial indexing for point-of-interest search, and a tile-based rendering system for map display. The system processes billions of routing requests daily while maintaining a continuously updated model of the world’s roads and places.

Scale

Requirements

High-Level Architecture

Loading diagram...

Key Components

Data Model

Loading diagram...

Routing with Contraction Hierarchies

Google Maps computes billions of routes daily. Running Dijkstra’s algorithm on a raw road graph with billions of edges would be far too slow. Instead, it uses Contraction Hierarchies (CH).

Preprocessing: The road graph is contracted offline by iteratively removing less important nodes and adding shortcut edges. A node on a residential street is contracted early, adding a shortcut between its neighbors. Major highway intersections are contracted last. This creates a hierarchical structure.

Query: At query time, a bidirectional search runs from origin and destination simultaneously, only exploring edges that go “up” the hierarchy. This drastically reduces the search space — a continental route that would explore millions of nodes with Dijkstra’s touches only thousands with CH.

Real-time traffic: The edge weights in the CH are updated continuously based on traffic data. When traffic changes, only the affected shortcuts need recomputation. Google uses a variant called Customizable Contraction Hierarchies that separates the topology (which shortcuts exist) from the metrics (edge weights), allowing weight updates without full reprocessing.

Multi-modal: For transit routing, a separate algorithm (RAPTOR or CSA) handles schedule-based queries, combined with walking segments from the road graph.

Loading diagram...

S2 Geometry and Spatial Indexing

Google Maps uses the S2 Geometry Library for all geospatial indexing and partitioning.

S2 cells: S2 projects the Earth’s surface onto the faces of a cube, then subdivides each face into a quadtree of cells. Each cell has a unique 64-bit ID. Cells at level 30 are ~1 cm², while level 12 cells are ~3.3 km² — covering the range from global to street-level precision.

Spatial indexing: Every place, road segment, and map feature is assigned to one or more S2 cells. Searching for “restaurants near me” becomes a cell-range query — find all S2 cells within a radius, then look up all places in those cells.

Map tiling: Map tiles are aligned to S2 cell boundaries. This means tile rendering, spatial queries, and data partitioning all use the same coordinate system, simplifying the architecture.

Coverage unions: S2 can represent arbitrary regions as a union of cells at different levels. This is used for features like “notify me when this area has less traffic” or defining offline map download regions.

Real-time Traffic from Crowdsourced Data

Google Maps’ traffic data comes primarily from anonymized location signals from Android phones and Waze users.

Data collection: When a user has location services enabled, their phone periodically reports anonymized speed and location data. This creates billions of “probe” data points per day across the world’s road network.

Aggregation: Probe data is aggregated per road segment in near real-time (<2 minutes). The system computes the median speed on each segment, compares it to the free-flow speed, and classifies congestion (green/yellow/red).

Privacy: Individual probe data is never stored with user identity. Data is aggregated with differential privacy guarantees — a road segment must have a minimum number of probes before traffic is reported, and k-anonymity ensures no individual’s route is reconstructable.

Prediction: Beyond current traffic, Google Maps predicts future traffic using historical patterns (e.g., rush hour on this highway every weekday) combined with real-time trends. The ETA displayed for a route accounts for predicted traffic conditions along the entire path, not just current conditions.

Incident detection: Sudden speed drops on a segment trigger automatic incident detection. Combined with Waze user reports, this feeds into route recalculation for affected users.

Architectural Tradeoffs

# Learn From a Google Maps-like System

You are an expert software architect and teacher. I want to learn from a Google Maps-inspired system design (Real-time navigation and geospatial search for billions of users) without pretending this is the exact private production architecture.

Use the following reference as a learning model. Keep assumptions visible, avoid unsupported scale claims, and explain the engineering forces behind each design choice.

---

## System Design Reference
import { Mermaid, Scale, ComponentList, ComponentCard, Requirements, Tradeoff } from '@/components/mdx';

## Overview

Google Maps is the world's most used mapping and navigation service, serving 1B+ monthly active users with real-time directions, place search, street view, and traffic information. Its architecture combines massive precomputed graph data (road networks, transit schedules), real-time sensor data (traffic from billions of Android phones), geospatial indexing for point-of-interest search, and a tile-based rendering system for map display. The system processes billions of routing requests daily while maintaining a continuously updated model of the world's roads and places.

## Scale

<Scale items={{
  "Monthly active users": "1B+",
  "Countries covered": "220+",
  "Road data": "1B+ km of roads",
  "Places in database": "250M+",
}} />

## Requirements

<Requirements
  functional={[
    'Map rendering with vector tiles at multiple zoom levels',
    'Turn-by-turn navigation for driving, walking, cycling, transit',
    'Place search and discovery',
    'Real-time traffic and ETA updates',
    'Street View imagery',
    'Offline maps for areas without connectivity',
    'Location sharing and timeline',
  ]}
  nonFunctional={[
    'Route computation in \<200ms for most queries',
    'Real-time traffic updates with \<2 minute freshness',
    'Map tile delivery in \<100ms from edge',
    'Global coverage including offline areas',
    'Accuracy — route ETAs within 5% of actual',
    ...

[Full prompt copied to clipboard]