Chapter 58: Design Google Maps

Mapping platform serving 1B+ MAU with real-time navigation, traffic, and POI search

1. Requirements

Functional Requirements

Feature	Description	Priority
Map Rendering	Display interactive maps with zoom levels 0-22, pan, rotate	P0
Routing	Calculate optimal routes: driving, walking, transit, cycling	P0
Real-Time Traffic	Show live traffic conditions, congestion, incidents	P0
ETA Calculation	Predict arrival time using traffic + historical data + ML	P0
POI Search	Find businesses, landmarks, addresses with autocomplete	P0
Turn-by-Turn Navigation	Voice guidance, route re-calculation on deviation	P0
Street View	360-degree street-level imagery	P1
Offline Maps	Download regions for offline use	P1

Non-Functional Requirements

Requirement	Target	Rationale
Scale	1B+ monthly active users	Global service
Map Load Latency	<200ms for tiles, <500ms for search	Smooth pan/zoom experience
Routing Latency	<1s for typical routes, <3s for long-distance	Real-time navigation expectation
Traffic Update Frequency	30s-2min refresh	Near real-time accuracy
Availability	99.99%	Critical navigation service
Data Freshness	Road data <30 days, POI <7 days	Accuracy for new roads/businesses
Storage	10+ PB map tiles, 100+ TB road graph	Global coverage at high zoom

Scale Estimation

Metric	Value	Calculation
DAU	400M	40% of 1B MAU
Map Views/day	2B	400M × 5 sessions
Tile Requests/day	100B	2B views × 50 tiles/view
Tile QPS	1.16M	100B / 86400s
Route Requests/day	200M	400M × 0.5 routes
Route QPS	2.3K	200M / 86400s
Active Navigations	10M concurrent	Peak traffic hours
Traffic GPS Reports/sec	1M	10M active × 0.1 Hz

Interview Callout: Clarify routing modes (driving vs transit have different graphs), real-time vs offline requirements, and whether to design Street View. Focus on core navigation first.

2. High-Level Design

graph TB subgraph "Client Layer" Mobile["Mobile App
(iOS/Android)"] Web["Web App
(JavaScript)"] end subgraph "CDN Layer" CDN["Global CDN
(CloudFront/Akamai)"] end subgraph "API Gateway" Gateway["API Gateway
(Rate Limiting, Auth)"] end subgraph "Core Services" TileService["Tile Service
(Serve Pre-rendered Tiles)"] RoutingService["Routing Service
(A*, Contraction Hierarchies)"] TrafficService["Traffic Service
(Real-time Aggregation)"] GeocodingService["Geocoding Service
(Address ↔ Coordinates)"] POIService["POI Search Service
(Elasticsearch)"] NavigationService["Navigation Service
(Turn-by-Turn)"] end subgraph "Data Processing" TrafficAggregator["Traffic Aggregator
(Stream Processing)"] MapBuilder["Map Data Builder
(OSM, Satellite)"] TileGenerator["Tile Generator
(Batch Rendering)"] end subgraph "Storage" TileStorage["Tile Storage
(S3/GCS - 10+ PB)"] RoadGraph["Road Graph DB
(Graph DB - 100+ TB)"] TrafficDB["Traffic DB
(Time-series DB)"] POIDB["POI Database
(PostgreSQL + Search Index)"] end subgraph "Data Sources" GPSData["GPS Data
(Crowdsourced)"] MapData["Map Data
(OSM, Licensed)"] SatelliteData["Satellite Imagery"] end Mobile --> CDN Web --> CDN CDN --> Gateway Gateway --> TileService Gateway --> RoutingService Gateway --> TrafficService Gateway --> GeocodingService Gateway --> POIService Gateway --> NavigationService TileService --> TileStorage RoutingService --> RoadGraph RoutingService --> TrafficDB TrafficService --> TrafficDB GeocodingService --> RoadGraph POIService --> POIDB NavigationService --> RoutingService NavigationService --> TrafficService GPSData --> TrafficAggregator TrafficAggregator --> TrafficDB MapData --> MapBuilder SatelliteData --> MapBuilder MapBuilder --> RoadGraph MapBuilder --> TileGenerator TileGenerator --> TileStorage CDN -.->|Cache Tiles| TileStorage

Component Responsibilities

Component	Responsibility	Technology
Tile Service	Serve pre-rendered map tiles by zoom/x/y coordinates	Nginx, S3, CloudFront CDN
Routing Service	Compute optimal routes using Contraction Hierarchies + A*	C++, Graph DB (Neo4j/custom)
Traffic Service	Aggregate GPS data, compute segment speeds, serve traffic	Kafka, Flink, InfluxDB/TimescaleDB
Geocoding Service	Convert addresses to coordinates and vice versa	Elasticsearch, PostGIS
POI Search	Full-text search for businesses, landmarks with ranking	Elasticsearch with geo-spatial queries
Navigation Service	Real-time turn-by-turn, route re-calc on deviation	WebSocket, gRPC streaming
Tile Generator	Pre-render tiles at all zoom levels from map data	Mapnik, Spark batch processing
Traffic Aggregator	Stream processing of GPS points, segment speed calculation	Kafka + Flink

Interview Callout: Emphasize separation of tile serving (read-heavy, CDN-cached) from routing (compute-heavy, real-time). Discuss trade-offs between pre-computation and on-demand calculation.

3. Map Tile Rendering

Tile Pyramid Structure

Zoom Level	Tiles (4^z)	Coverage	Use Case
0	1	Entire world	Global view
5	1,024	Continent	Country-level zoom
10	1M	City region	City overview
15	1B	Neighborhood	Street-level navigation
18	68B	Building detail	High-detail zoom
22	17T	Sub-meter precision	Maximum detail (selective)

Vector Tiles vs Raster Tiles

Aspect	Raster Tiles (PNG/JPG)	Vector Tiles (PBF)
Format	Pre-rendered images (256×256 or 512×512 px)	Geometric data (points, lines, polygons) + metadata
Size	10-100 KB per tile	20-200 KB per tile (compressed)
Rendering	Server-side (pre-rendered)	Client-side (dynamic styling)
Quality	Pixelated on zoom, fixed style	Crisp at any zoom, dynamic themes
Interactivity	No metadata, image only	Rich metadata, queryable features
Storage	Higher (all styles pre-rendered)	Lower (single data, styled on client)
Use Case	Legacy, satellite imagery	Modern maps (Google Maps uses vector)

graph TB subgraph "Tile Generation Pipeline" MapData["Map Data
(OSM, Roads, POIs)"] StyleRules["Style Rules
(Colors, Fonts)"] TileGenerator["Tile Generator
(Mapnik/Tangram)"] VectorTiles["Vector Tiles
(PBF Format)"] TileStorage["Tile Storage
(S3/GCS)"] CDN["CDN
(CloudFront)"] Client["Client App
(Renders on GPU)"] end MapData --> TileGenerator StyleRules --> TileGenerator TileGenerator -->|Generate for z=0-22| VectorTiles VectorTiles --> TileStorage TileStorage --> CDN CDN -->|Fetch z/x/y.pbf| Client Client -->|Dynamic Styling| Rendered["Rendered Map"]

Tile Coordinate System

Parameter	Description	Example
z (zoom)	Zoom level (0-22)	z=15 (street level)
x (column)	Tile column (0 to 2^z - 1), West to East	x=5242 (longitude)
y (row)	Tile row (0 to 2^z - 1), North to South	y=12642 (latitude)
URL Pattern	https://tiles.example.com/{z}/{x}/{y}.pbf	/15/5242/12642.pbf

Tile Generation Strategy

Zoom Level	Strategy	Rationale
0-10	Pre-render all tiles	Small count (<1M), frequently accessed
11-15	Pre-render popular areas + on-demand	1B-33B tiles, selective coverage
16-22	On-demand + cache popular	Trillions of tiles, sparse access

Interview Callout: Discuss tile pyramid math (4^z growth), storage optimization (only pre-render high-traffic regions), and client-side rendering benefits (one vector tile, infinite styles).

4. Tile Serving

Tile Delivery Architecture

Layer	Component	Cache Hit Rate	Latency
L1	Client-side cache (IndexedDB, memory)	80-90%	<1ms
L2	Edge CDN (CloudFront, 200+ PoPs)	95%	10-50ms
L3	Regional CDN cache	98%	50-100ms
L4	Origin tile servers (Nginx + S3)	100%	100-200ms

Viewport Tile Loading

Strategy	Description	Impact
Lazy Loading	Only fetch tiles in current viewport + 1 tile buffer	Reduces initial load by 80%
Priority Queue	Center tiles load first, edges deferred	Perceived latency <200ms
Prefetching	Predict pan direction, prefetch next tiles	Smooth panning experience
Progressive Loading	Show lower zoom tile, upgrade to higher zoom	Instant feedback, then detail
Batch Requests	HTTP/2 multiplexing, request 10-20 tiles in parallel	Lower latency overhead

Caching Strategy

Cache Level	TTL	Eviction Policy	Size Limit
Client Memory	Session	LRU	500 MB
Client Disk (IndexedDB)	7 days	LRU + size-based	2 GB
CDN Edge	30 days	LRU + popularity	Unlimited
Origin Cache	90 days	Infinite (S3)	10+ PB

Tile Update Strategy

Update Type	Frequency	Invalidation
Road Network Changes	Weekly	Invalidate affected z/x/y tiles in CDN
POI Updates	Daily	Versioned tiles (clients request latest)
Style Changes	On-demand	No invalidation (client-side styling)
Satellite Imagery	Monthly-Quarterly	Versioned URL (v=202505)

Interview Callout: Discuss cache hierarchy depth, CDN PoP placement (near users), and handling cache invalidation when roads change. Mention HTTP/2 for parallel tile requests.

5. Road Network Graph

Graph Structure

Component	Representation	Attributes
Nodes	Intersections, endpoints, junctions	node_id, lat, lng, elevation, traffic_light
Edges (Directed)	Road segments between nodes	edge_id, from_node, to_node, distance, time, road_type, lanes, speed_limit, toll, restrictions
Edge Weights	Cost for traversal	distance (m), time (s), traffic_factor, historical_speed

Edge Types and Weights

Road Type	Speed Limit (avg)	Base Weight (time)	Traffic Impact
Highway	65-75 mph	Low (fast)	High (congestion-sensitive)
Arterial Road	35-45 mph	Medium	High
Residential Street	25 mph	Medium-High	Low
Pedestrian Path	3 mph (walking)	High	None

Weight Calculation Formula

Component	Formula	Description
Base Time	distance / speed_limit	Theoretical time without traffic
Traffic Factor	1.0 (green) to 3.0 (red)	Current congestion multiplier
Historical Factor	avg_speed(day, hour) / speed_limit	Typical slowdown for time-of-day
Final Weight	base_time × traffic_factor × historical_factor	Used in routing algorithm

Graph Partitioning

Strategy	Description	Benefit
Geographic Sharding	Partition graph by region (US-West, EU, Asia)	Localized routing stays within shard
Cross-Region Links	Border nodes replicated across shards	Long-distance routes span shards
Hierarchical Graph	Separate graphs for local roads vs highways	Long routes use highway graph only

Interview Callout: Emphasize directed edges (one-way streets), time-dependent weights (rush hour), and graph partitioning for global scale. Mention that routing servers load regional sub-graphs in memory.

6. Routing Algorithms

Algorithm Comparison

Algorithm	Time Complexity	Space	Pre-processing	Query Time	Use Case
Dijkstra	O((V+E) log V)	O(V)	None	Seconds	Academic, small graphs
A* (A-star)	O((V+E) log V)	O(V)	None	100-500ms	Moderate-distance routes
Bidirectional A*	O((V+E) log V)	O(V)	None	50-200ms	Improved A*
Contraction Hierarchies	O(E log V)	O(V+E)	Hours (offline)	1-10ms	Production (Google Maps)
Transit Network	O(E + T)	O(V+E+T)	Minutes	50-200ms	Public transit routing

Dijkstra's Algorithm

Aspect	Details
Approach	Explore all nodes in order of increasing distance from start
Data Structure	Priority queue (min-heap) of (node, distance) pairs
Optimality	Guaranteed shortest path (non-negative weights)
Problem	Explores in all directions, no goal awareness (slow)

A* Algorithm

Aspect	Details
Approach	Dijkstra + heuristic to guide search toward goal
Priority Function	f(n) = g(n) + h(n), where g=actual cost, h=heuristic estimate to goal
Heuristic (h)	Haversine distance (straight-line) or Manhattan distance
Optimality	Guaranteed shortest path if h is admissible (never overestimates)
Benefit	10-100x fewer nodes explored than Dijkstra

Contraction Hierarchies (CH)

Phase	Description	Time
Pre-processing	Contract nodes in order of importance (remove node, add shortcut edges)	Hours (offline)
Result	Hierarchical graph: low-importance (local roads) → high-importance (highways)	Stored in memory
Query	Bidirectional search up the hierarchy from start/end, meet in middle	1-10ms
Optimality	Guaranteed shortest path	-
Benefit	1000x faster than A* for long routes	-

graph TD subgraph "Contraction Hierarchies Concept" L1["Level 1: Highways
(High Importance)"] L2["Level 2: Arterial Roads
(Medium Importance)"] L3["Level 3: Local Roads
(Low Importance)"] Start["Start
(Local Road)"] End["End
(Local Road)"] Start -->|"Search Up"| L3 L3 --> L2 L2 --> L1 L1 -->|"Meet Point"| L1 L1 --> L2b["Level 2"] L2b --> L3b["Level 3"] L3b -->|"Search Down"| End end style L1 fill:#FFD700 style Start fill:#90EE90 style End fill:#FFB6C1

Route Alternatives

Strategy	Description
Fastest Route	Minimize time (considering traffic)
Shortest Route	Minimize distance (ignore traffic)
Avoid Tolls	Filter toll edges, re-route
Avoid Highways	Filter highway edges
Alternative Routes	Penalty-based search to find 2-3 diverse routes

Interview Callout: Start with Dijkstra/A*, then introduce Contraction Hierarchies as production optimization. Explain pre-processing trade-off (hours offline for milliseconds online). Mention how traffic updates invalidate pre-computed shortcuts.

7. Real-Time Traffic

Traffic Data Sources

Source	Coverage	Accuracy	Cost
Crowdsourced GPS (Google Maps users)	High (1B+ users)	High (real-time)	Free (user data)
Road Sensors (loop detectors)	Low (major highways only)	High	High (government)
Historical Data	Global	Medium (predictive)	Free (own data)
Incident Reports (accidents, construction)	Medium	High (event-based)	Free (user reports)

GPS Data Processing Pipeline

graph LR subgraph "Traffic Data Pipeline" GPSDevices["GPS Devices
(10M active users)"] Ingest["Kafka Ingestion
(1M msgs/sec)"] MapMatch["Map Matching
(Snap to road segments)"] Aggregate["Aggregation
(Segment speed calc)"] HistoricalDB["Historical DB
(TimescaleDB)"] RealtimeDB["Real-time Cache
(Redis)"] TrafficAPI["Traffic API
(Serve to clients)"] end GPSDevices -->|"GPS point (lat,lng,speed,timestamp)"| Ingest Ingest --> MapMatch MapMatch -->|"segment_id, speed"| Aggregate Aggregate --> RealtimeDB Aggregate --> HistoricalDB RealtimeDB --> TrafficAPI HistoricalDB --> TrafficAPI

Map Matching

Step	Description
1. GPS Point	Receive (lat, lng, speed, timestamp, device_id)
2. Spatial Query	Find candidate road segments within 50m radius
3. Match	Assign to most likely segment (direction, speed, history)
4. Output	(segment_id, speed, timestamp)

Segment Speed Aggregation

Metric	Calculation	Window
Real-Time Speed	Median speed of GPS points in segment (last 2 min)	2 min rolling
Historical Speed	Average speed for segment at (day_of_week, hour)	Past 30 days
Traffic Factor	real_time_speed / speed_limit	Real-time
Congestion Level	Green (>80% limit), Yellow (50-80%), Red (<50%)	Real-time

Traffic Data Fusion

Scenario	Strategy
High GPS Coverage	Use real-time GPS data (primary)
Low GPS Coverage	Fall back to historical average for time-of-day
Incident Detected	Override with incident-based slowdown (e.g., accident = 10 mph)
New Road	Use similar road type speed limits until data accumulates

Traffic Update Frequency

Client State	Update Frequency	Rationale
Active Navigation	30s	Re-route if faster path emerges
Map Viewing	2 min	Visual traffic layer update
Background	10 min	Maintain data freshness

Interview Callout: Emphasize crowdsourcing scale (millions of GPS pings/sec), map matching complexity, and trade-off between real-time updates (network cost) and accuracy. Mention anonymization/privacy of GPS data.

8. ETA Calculation

ETA Formula Components

Component	Weight	Source
Base Travel Time	50%	Sum of edge times (distance / speed_limit)
Real-Time Traffic	30%	Current segment speeds (last 2 min)
Historical Patterns	15%	Typical slowdown for time-of-day, day-of-week
ML Adjustment	5%	Model trained on actual vs predicted ETA (weather, events)

ETA Calculation Process

Step	Description	Example
1. Route Segments	Break route into road segments	50 segments, 25 km total
2. Segment Time (base)	distance / speed_limit	Segment 1: 0.5 km / 65 mph = 27s
3. Traffic Factor	Apply real-time speed adjustment	Current speed 40 mph → 27s × 1.6 = 43s
4. Historical Factor	Apply typical slowdown for time	Rush hour → 43s × 1.2 = 52s
5. Sum All Segments	Total time across route	52s + ... = 28 min
6. ML Adjustment	Apply learned correction	Model predicts +2 min → 30 min ETA

ETA Refinement During Navigation

Event	Action
Completed Segment	Remove from route, recalculate remaining time
Traffic Update (30s)	Refresh segment speeds, adjust ETA
Deviation from Route	Re-route, compute new ETA
Incident Detected Ahead	Increase ETA or offer re-route
Faster Route Available	Suggest re-route with new ETA

ML Model for ETA Adjustment

Feature	Impact
Weather (rain, snow)	+10-30% time
Special Events (concert, game)	+20-50% time near venue
Holidays	Variable (Thanksgiving = high traffic)
Driver Behavior	Personalized (aggressive vs cautious)

Interview Callout: Discuss multi-source fusion (real-time + historical + ML), dynamic ETA updates during navigation, and importance of accuracy (users trust ETA for planning). Mention ML model training on past predictions vs actuals.

9. Geocoding

Geocoding Types

Type	Input	Output	Use Case
Forward Geocoding	Address string	(lat, lng)	Search "1600 Amphitheatre Pkwy" → coordinates
Reverse Geocoding	(lat, lng)	Address string	User location → "123 Main St, City"
Autocomplete	Partial address	Ranked suggestions	"1600 Amp..." → "1600 Amphitheatre Pkwy"

Forward Geocoding Pipeline

Step	Description	Technology
1. Parse	Extract street, city, state, zip, country	NLP/regex
2. Normalize	Expand abbreviations (St → Street, NY → New York)	Lookup tables
3. Search	Query address database with fuzzy matching	Elasticsearch
4. Rank	Score by relevance, popularity, user location proximity	BM25 + geo-boost
5. Return	Top result(s) with (lat, lng, formatted_address)	JSON API

Reverse Geocoding

Step	Description
1. Spatial Query	Find nearest road segment to (lat, lng)
2. Address Lookup	Get address metadata for segment (street name, range)
3. Interpolate	Estimate street number based on position along segment
4. Fallback	If no road nearby, return nearest POI or neighborhood

Fuzzy Matching Strategies

Technique	Example	Purpose
Typo Tolerance	"1600 Ampitheater" → "1600 Amphitheatre"	Handle misspellings (Levenshtein distance)
Abbreviation Expansion	"St" → "Street", "Ave" → "Avenue"	Match variations
Synonym Matching	"Route 101" = "Highway 101"	Different names for same road
Geo-Contextualization	"Main St" → prioritize results near user location	Disambiguate common names

Geocoding Data Storage

Data Type	Storage	Size
Address Database	PostgreSQL + PostGIS (spatial index)	10+ TB
Search Index	Elasticsearch (inverted index + geo-spatial)	5 TB
POI Database	PostgreSQL + Elasticsearch	1 TB

Interview Callout: Discuss fuzzy matching necessity (typos, abbreviations), geo-contextualization (nearby results ranked higher), and reverse geocoding complexity (address interpolation). Mention caching popular searches.

10. Scalability

Tile CDN Scalability

Challenge	Solution	Impact
1M+ tile QPS	CDN with 200+ PoPs, 95%+ cache hit rate	Origin handles <50K QPS
10+ PB tile storage	S3/GCS with lifecycle policies (archive old tiles)	Cost-effective at scale
Tile updates (road changes)	Versioned tiles, CDN invalidation API	Propagates in minutes
Peak traffic (lunch, commute)	Auto-scaling CDN capacity	Handle 3x baseline

Routing Service Scalability

Challenge	Solution	Impact
2.3K route QPS	Horizontal scaling: 100+ routing servers	23 QPS per server (easy)
Graph too large for RAM	Regional sharding (US-West, EU, Asia)	Each server loads sub-graph
Long-distance routes	Contraction Hierarchies (1-10ms queries)	1000x faster than A*
Traffic invalidates shortcuts	Re-compute CH every 30 min (incremental)	Fresh traffic-aware hierarchy

Traffic Processing Scalability

Challenge	Solution	Impact
1M GPS reports/sec	Kafka with 100 partitions, Flink parallel processing	10K msgs/sec per partition
Map matching (CPU-heavy)	Distributed Flink workers, spatial index (R-tree)	Sub-millisecond lookup
Segment aggregation	Windowed aggregation (2 min tumbling window)	Continuous updates
Historical data (100+ TB)	TimescaleDB (time-series + compression)	10x compression

Graph Sharding Strategy

Region	Graph Size	Servers	Cross-Region Routing
US-West	10 GB	20	Border nodes shared with US-East
US-East	10 GB	20	Border nodes shared with US-West
Europe	15 GB	30	Border nodes with Asia, US-East
Asia	20 GB	40	Border nodes with Europe

POI Search Scalability

Challenge	Solution	Impact
100M POI records	Elasticsearch with 50 shards	2M POIs per shard
Geo-spatial queries	Geo-hash indexing + bounding box filter	<100ms query latency
Autocomplete (<50ms)	Prefix search + caching popular queries (Redis)	90% cache hit
Ranking (relevance)	BM25 + geo-boost + popularity score	Accurate results

Database Scalability Summary

Database	Purpose	Size	Scaling Strategy
Tile Storage (S3)	Map tiles	10+ PB	Object storage, CDN caching
Road Graph DB	Routing graph	100+ TB	Regional sharding, in-memory
Traffic DB (TimescaleDB)	Traffic data	100+ TB	Time-series partitioning, compression
POI DB (Elasticsearch)	POI search	1 TB	Horizontal sharding
Real-time Cache (Redis)	Traffic, popular queries	10 GB	Redis cluster, LRU eviction

Cost Optimization

Area	Strategy	Savings
Tile Storage	Compress tiles (vector PBF), archive low-zoom	50% reduction
Tile Serving	CDN caching (95% hit rate)	20x fewer origin requests
Routing	Pre-compute CH (10ms vs 500ms), fewer servers	50x efficiency
Traffic Data	Compress historical data (TimescaleDB), 30-day retention	10x compression

Interview Callout: Emphasize CDN for tile serving (massive QPS), Contraction Hierarchies for routing (pre-computation win), and regional graph sharding (fit in RAM). Discuss trade-offs between pre-computation cost and query latency.