Interview Setup
Interview Prompt
Design a map rendering and navigation system like Google Maps. Users can pan and zoom interactive maps, search points of interest, compute driving directions with live traffic, and receive turn-by-turn guidance while driving.
Clarifying Questions (ask before designing)
| Question | Why it matters |
|---|---|
| Vector tiles or pre-rendered raster tiles? | Vector MVT tiles at ~10 KB per tile vs 20 to 50 KB raster tiles drastically changes CDN egress economics at 2M requests per second. |
| How fresh must traffic data be for routing? | Sub-minute traffic updates require Flink stream aggregation and Customizable Route Planning rather than static contraction hierarchies alone. |
| Is offline navigation in scope? | Offline navigation shifts storage to client devices and requires downloadable vector region packages rather than online-only tile serving. |
| What is the peak concurrent navigation session count? | 50M active sessions creates a continuous reroute and ETA push workload that is distinct from map tile viewing QPS. |
Scope
In scope
- Vector tile pyramid and CDN delivery
- Geocoding and place search
- Route planning with live traffic weights
- Turn-by-turn navigation and rerouting
- GPS telemetry ingestion and map matching
- Traffic aggregation for edge speed updates
Out of scope (state explicitly)
- Ride dispatch and driver matching systems
- Raw map data collection and OSM ingestion pipelines
- Street View imagery capture
Functional Requirements
Scope the problem carefully across tile rendering, routing, and real-time traffic telemetry. Key capabilities include map tile delivery via CDN, turn-by-turn route planning, and ETA calculations, while confirming the scope of live traffic integration.
In the room: avoid designing the entirety of Google Maps; focus deeply on either tiles, routing, or real-time traffic.
- Interactive Map Rendering: Render smooth, zoomable, pannable vector maps with satellite and live traffic overlays.
- Geocoding & Reverse Geocoding: Translate human-readable street addresses into geographic coordinates and vice versa.
- Multi-Modal Route Planning: Compute optimal travel paths across driving, walking, cycling, and public transit modes.
- Turn-by-Turn Navigation: Provide real-time maneuvers, voice prompts, and lane guidance as drivers progress.
- Live Traffic & Dynamic Rerouting: Ingest crowd-sourced vehicle telemetry to detect congestion and compute alternate paths. Related problems include the ETA Calculation Service and Real-Time Vehicle Tracking.
- Place Search & POI Discovery: Query points of interest by business name, category, and spatial proximity.
- Accurate ETA Prediction: Estimate arrival times factoring in live segment speeds, intersection delays, and road classifications.
- Offline Map Packs: Support pre-downloaded regional packs for basic offline search, rendering, and routing.
- Incident Reporting: Allow motorists to submit real-time reports of road hazards, accidents, and speed cameras.
Non-Functional Requirements
Map tiles must load in under 200 ms and route planning must complete within 1 second for metropolitan areas.
- Low Latency: Interactive vector tiles must render in under 200 ms, while route planning queries return in under 1 second.
- High Availability: Achieve 99.99% availability, because navigation outages while driving create severe safety and liability issues.
- Massive Scalability: Support 300M DAU, 2M tile requests per second, and 50M concurrent active navigation sessions.
- High Accuracy: Routes must strictly obey legal driving maneuvers, one-way streets, and turn restrictions, keeping ETAs within ±10% of actual trip duration.
- Data Freshness: Traffic telemetry must aggregate and refresh every 30 to 60 seconds.
- Bandwidth Efficiency: Minimize mobile cellular data usage by leveraging compressed Vector protobuf tiles rather than heavy raster images. Explore CDN and Edge Delivery for edge caching patterns.
- Global Coverage: Provide worldwide geographic data, handling localized address schemas and international road regulations.
Capacity Estimations
Tile pyramid storage and routing graph size for your coverage area drive CDN and server memory. At 2M tile requests/sec, CDN hit ratio is the headline metric, because a 1% miss rate can overwhelm origin capacity. Run zoom-level math before sizing SSD edge caches.
| Metric | Calculation | Value |
|---|---|---|
| DAU | 300 Million | |
| Map tile requests / sec | Multiple tiles per pan/zoom | ~2 Million |
| Route calculation requests / sec | 100K | |
| Active navigation sessions | Concurrently active | 50 Million |
| Traffic data points / sec | GPS telemetries sent every 5s | 10 Million |
| Map data total size (raw) | Vector roads, points of interest | ~20 TB |
| Tile cache (all zoom levels) | Pre-rendered + cached vector | ~500 TB |
| Road graph (global) | Nodes and edges representation | ~2B nodes, ~5B edges |
I/O Estimations: 1. Map tile bandwidth: - 2M tile requests/sec x 10 KB avg vector tile size = 20 GB/s egress bandwidth (handled by CDNs). 2. Traffic telemetry data ingest: - 10M GPS updates/sec x 100 bytes/update = 1 GB/s ingress. Kafka handles this with dynamic partitioning.
Architecture Diagram
Map serving splits into three paths: tile pyramids behind CDN (2M+ RPS at pan/zoom), routing on a preprocessed road graph (Contraction Hierarchies for sub-second queries), and optional live traffic overlay from a Kafka, Flink, and Redis pipeline. Pick one path to go deep, because interviewers rarely expect all three fully designed.
Vector MVT tiles compress better than raster and scale with zoom; routing loads a regional CH graph (~300 GB in-memory per metro) and applies traffic edge weights from Redis before returning an encoded polyline.
Component Deep Dives
1. Map Tile System: Pyramids and Vector Formats
Start with the tile pyramid and CDN edge caching hierarchy before explaining routing graphs and pathfinding algorithms.
The world map is represented as a tile pyramid. Zoom Level 0 covers the entire planet in one 256x256 px tile. Each subsequent zoom level quadruples the number of tiles (2z x 2z grid). Zoom 18 street-level contains ~69 billion tiles.
Vector Tiles vs Raster Tiles:
| Aspect | Raster Tiles (Traditional) | Vector Tiles (Modern) ⭐ |
|---|---|---|
| Data Content | Pre-rendered static PNG/JPEG images | Raw geometric coordinates (roads, buildings, labels) |
| Client Effort | Low (displays pre-drawn pixels) | High (WebGL client GPU rendering) |
| Dynamic Rotation | Poor (blurry/pixelated text) | Flawless (vectors re-align instantly) |
| Styling / Themes | Requires full server-side re-render | Instant (client stylesheet swap) |
| Network Size | ~20 to 50 KB per tile | ~5 to 15 KB per tile (Google Protobuf MVT) |
| Offline Feasibility | Extremely bulky (hundreds of GBs) | Highly viable (highly compressed geometries) |
2. Routing Engine: Algorithms and Customizations
The road network is modeled as a weighted directed graph (~2B nodes, ~5B edges). Since a standard Dijkstra search would take minutes for continental paths, optimized variations are deployed:
- Contraction Hierarchies (CH): A pre-processing step that eliminates lower-importance minor nodes (cul-de-sacs, residential alleys) and inserts shortcut edges. Bidirectional Dijkstra searches UP the hierarchy from both origin and destination, yielding sub-millisecond continental searches. However, CH handles real-time traffic updates poorly due to long pre-processing recalculation times.
- Customizable Route Planning (CRP): Divides the global road network graph into nested geometric cells. Pre-computes boundary-to-boundary clique paths within each partition. When live traffic changes edge speeds, only affected cells are re-evaluated, keeping queries exceptionally fast.
- ALT (A*, Landmarks, Triangle Inequality): Uses pre-selected landmark nodes to bound heuristics, offering a flexible middle-ground that easily supports live weight updates.
3. Traffic Service: Real-Time Map Matching (HMM)
Telemetric GPS coordinates sent by mobile clients are inherently noisy (±10m drift). Snapping these coordinates to the road graph requires the Hidden Markov Model (HMM).
If a driver travels near an elevated freeway overpass and a parallel minor service road below, a simple closest-segment metric might snap them to the service road. An HMM considers the sequence of past transitions. If the vehicle registers speeds of 100 km/h, the transition matrix dictates that they must be on the highway. Flink aggregates segment speeds in 60s windows.
4. Navigation Service: Maneuvers and Rerouting
The initial route is computed server-side due to complete access to historical and live traffic data. The client monitors progression locally (allowing offline guidance). If the GPS coordinates deviate > 50m from the planned path, a local routing fallback triggers immediate rerouting, while asynchronously updating the server for optimal traffic adjustments.
Event Bus Design (Kafka)
Traffic telemetry and incident reports publish to partitioned Kafka topics, driving stream aggregation in Flink and edge speed updates in Redis.
Topics:
traffic-telemetry: partition key: device_id (GPS pings from navigation clients)
incident-reports: partition key: road_segment_id
Partitions: 128; Retention: 24 hours; RF=3
Producer events:
traffic-telemetry: { device_id, lat, lng, speed_mps, heading, timestamp }
incident-reports: { segment_id, type, severity, reporter_id, timestamp }
Consumer groups:
1. traffic-flink: HMM map-match -> aggregate speed per segment -> Redis traffic:{segment_id}
2. tile-regenerator: trigger traffic overlay tile regen every 60s
3. routing-updater: push congestion weights to Contraction Hierarchies index
Read path: Routing Service reads Redis segment speeds for real-time edge weights.
DLQ: traffic-telemetry-dlq, alerting when Flink lag exceeds 90 seconds.API Design
Map and Navigation Endpoints
The API exposes vector tile fetching, forward and reverse geocoding, and multi-modal route planning.
Get Vector Map Tiles
GET /api/v1/tiles/{z}/{x}/{y}.mvt
Headers:
Accept: application/vnd.mapbox-vector-tile
Cache-Control: public, max-age=86400
Response:
Binary Protobuf (MVT vector tile payload)Geocoding (Address to Coordinates)
GET /api/v1/geocode?address=1600+Amphitheatre+Parkway+Mountain+View
Response: 200 OK
{
"results": [{
"formatted_address": "1600 Amphitheatre Pkwy, Mountain View, CA 94043",
"geometry": { "lat": 37.4220, "lng": -122.0841 },
"place_id": "ChIJj61dQgK6j4AR4GeTYWZsKWw"
}]
}Get Route Path
POST /api/v1/routes
{
"origin": { "lat": 37.7749, "lng": -122.4194 },
"destination": { "lat": 37.3382, "lng": -121.8863 },
"mode": "driving",
"avoid_tolls": true
}
Response: 200 OK
{
"routes": [{
"route_id": "r-9921",
"distance_meters": 72400,
"duration_seconds": 3420,
"duration_in_traffic_seconds": 4200,
"encoded_polyline": "_p~iF~ps|U_ulLnnqC_mqNvxq`@",
"maneuvers": [
{
"instruction": "Turn left onto Market St",
"distance_meters": 800,
"duration_seconds": 120
}
]
}]
}Common Error Responses
Structured error responses for unroutable origin-destination pairs, invalid bounding boxes, and rate limiting.
400 Bad Request: invalid input, missing required fields, or malformed JSON payload 401 Unauthorized: missing or invalid authentication token or API key 403 Forbidden: authenticated caller lacks required permissions for this resource 404 Not Found: requested resource ID does not exist 409 Conflict: duplicate write or version conflict, retry with a unique idempotency key 422 Unprocessable Entity: syntactically valid request failed semantic business validation 429 Too Many Requests: rate limit quota exceeded, client should honor Retry-After header 500 Internal Error: unexpected server failure, retry safely with an idempotency key 503 Service Unavailable: downstream dependency is unavailable or overloaded, retry with exponential backoff
Data Model
PostgreSQL + PostGIS Schema (Road Graph Source of Truth)
-- Road segments model edges
CREATE TABLE road_segments (
segment_id BIGINT PRIMARY KEY,
start_node_id BIGINT NOT NULL,
end_node_id BIGINT NOT NULL,
road_name TEXT,
road_class VARCHAR(30),
length_meters FLOAT,
speed_limit_kmh INT,
one_way BOOLEAN DEFAULT FALSE,
toll BOOLEAN DEFAULT FALSE,
geometry GEOMETRY(LineString, 4326),
country_code CHAR(2)
);
CREATE INDEX idx_road_segments_geom ON road_segments USING GIST(geometry);
-- Nodes represent junctions
CREATE TABLE road_nodes (
node_id BIGINT PRIMARY KEY,
lat DECIMAL(10,7),
lng DECIMAL(10,7),
geometry GEOMETRY(Point, 4326)
);
CREATE INDEX idx_road_nodes_geom ON road_nodes USING GIST(geometry);Redis Transient Caching Structure
# Segment Congestion speeds (stale in 120s)
Key: traffic:{segment_id} -> Hash { avg_speed, congestion_level, updated_at }
# Popular geocoding locations (stale in 24 hours)
Key: geocode:{address_hash} -> JSON { lat, lng, formatted_address }Routing Engine In-Memory Graph Memory Cost
To maintain sub-millisecond route checks, the entire global road graph is hosted in RAM across region shards:
- Nodes: 2 Billion x 16 Bytes (ID, coordinates, level) = 32 GB.
- Edges: 5 Billion x 32 Bytes (from, to, weight, attributes) = 160 GB.
- CH Shortcuts: ~3 Billion x 32 Bytes = 96 GB.
- Total Memory Footprint: ~288 GB (sharded into 20 global region servers of ~50-150 GB each). For distribution details, see Sharding and Partitioning.
Fault Tolerance
| Scenario Concern | System Solution Design |
|---|---|
| Tile Service Ingestion Failure | CDNs absorb > 95% of traffic. Underlying render servers are decoupled via origin shields to prevent thundering herd. |
| Routing Server Crash | Routing microservices are completely stateless. Replicas partition graph data and use health check ALB failovers. |
| Live Traffic Outage | If Flink streaming fails, fall back to historical speeds mapped to the specific weekday and hour of the day. |
| GPS Connection Drop (e.g. Tunnel) | Client-side dead reckoning tracks movement using internal accelerometer and gyroscope heading sensors. |
| Cross-Region Routing Splice |
|
Tunnel Outage Recovery Protocol
When a user enters a prolonged signal dead-zone (e.g., driving through a 5-minute mountain tunnel):
- The mobile client holds the pre-computed maneuvers and route polyline in local memory.
- The GPS receiver tracks coordinate changes without cellular connectivity.
- Guidance calculations run on the client, updating ETA locally and triggering voice warnings.
- Once connection returns, buffered coordinates are sent back to Flink to refine dynamic traffic segments.
Additional Considerations
1. Polyline Delta Compression
Sending raw arrays of floats for a long route (e.g. 5,000 lat/lng coordinates from SF to LA) would consume ~200 KB. Google's Encoded Polyline Algorithm uses delta compression (only encoding small variations from the previous point) and base64-like character sets. This reduces the route coordinates footprint to ~15 KB (a 13x reduction), saving massive mobile data.
2. Offline Map Bounding-Box Downloads
When a user downloads an offline city pack (e.g., "San Francisco" region):
- Vector Tiles: Pre-fetched zoom 0 to 16 MVT blocks for the bounding box (~500 MB).
- Local Graph: Highly simplified local road graph with contraction hierarchies (~140 MB).
- POI Search: Local SQLite-indexed places directory containing categories (~50 MB).
- Total Weight: ~700 MB. Delivers full search and navigation offline, pulling delta updates weekly.
Interview Walkthrough
- 25-minute pacing strategy
Prioritize vector tile pyramids and Contraction Hierarchies before delving into offline package synchronization.
- Separate tile serving from routing engines with distinct performance profiles (5 min)
- Serve vector MVT tile bundles cached at the CDN edge for client-side GPU rendering (6 min)
- Preprocess road networks with Contraction Hierarchies for sub-millisecond continental searches (5 min)
- Compress route polylines using delta encoding algorithms (5 min)
- Support offline city packs with localized SQLite POI stores and tile bounding boxes (4 min)
- Separate tile serving (CDN-cached vector MVT pyramids) from routing (graph-based pathfinding), because they have different latency and storage profiles.
- Serve map tiles as vector MVT bundles at zoom levels 0 to 18, cached at the CDN edge so clients render locally to conserve bandwidth compared to raster PNGs.
- Preprocess road networks with Contraction Hierarchies offline so A* queries on mobile complete in <50ms on a simplified local graph.
- Compress route polylines with Google's encoded polyline algorithm: 5000 coordinates shrink from ~200 KB to ~15 KB (a 13x reduction).
- Support offline city packs: pre-fetch zoom 0 to 16 tiles, simplified road graphs, and local POI SQLite databases (~700 MB per city).
- Apply tile cache invalidation by versioning tile sets, pushing delta updates weekly rather than re-downloading full packs.
- Quantify tile storage: global coverage across zoom 0 to 18 comprises billions of tiles, so only pre-render and cache tiles within the active viewport and immediate buffer.
- On mobile, downsample GPS to ~1 Hz while moving and pause updates when stationary to save battery without degrading turn-by-turn guidance.
- Common pitfall: serving raster PNG tiles at high zoom levels, because storage and bandwidth scale exponentially and mobile rendering becomes sluggish.
Engineering Trade-offs
Architectural Trade-offs
Map rendering architectures balance vector vs raster tile formats, offline storage burdens against connectivity, and pre-computed static hierarchies against dynamic traffic routing.
1. Map Tile Pre-Rendering vs On-Demand
Pre-rendering all 70B street-level tiles would require ~700 TB of storage and weeks of compute. Any minor map correction (e.g., updating a park layout) would require costly re-rendering. The system chooses a hybrid approach: pre-render global zoom levels 0 to 12 and highly popular metropolitan centers (covering 90% of views). Everything else is rendered on-demand and cached with dynamic TTL invalidation tags.
2. In-Memory Routing vs SQL pgRouting
Using SQL extensions like pgRouting is simple but performs disk-bound calculations, bottlenecking under load. Creating a specialized C++ in-memory routing service (like OSRM or Valhalla) requires massive sharded RAM clusters (~288 GB), but guarantees sub-millisecond continental queries, fully justifying the infrastructure cost.
Review
How helpful was this walkthrough?
Click a star to rate. We actively use this feedback to refine and update our system design content.
Discussion
Share your thoughts, ask questions, or help others.