Google Maps

Design a simplified Google Maps. Google Maps has 1B DAU, 99% world coverage, 25M location updates daily. Focus on: location update, navigation (including ETA), and map rendering. Primary devices: mobile phones.

Step 1 of 4: Understand the problem and establish design scope #

Goal: lock in features, constraints, and scale.

Key features #

1. User location update
2. Navigation service (including ETA)
3. Map rendering

Scope notes: support driving, walking, bus modes. Multi-stop directions out of scope. Traffic conditions important for accurate ETA. Road data: TBs of raw data from external sources.

Non-functional requirements:

1. Accuracy: no wrong directions
2. Smooth navigation: smooth map rendering on client
3. Data and battery: minimal data/energy usage on mobile
4. General scalability and availability

Map 101 #

1. Positioning: latitude (north/south), longitude (east/west)

2. Map projection: 3D globe → 2D plane. Google Maps uses Web Mercator (modified Mercator)

3. Geocoding: address → lat/lng (e.g. "1600 Amphitheatre Parkway, Mountain View, CA" → 37.423021, -122.083739). Reverse geocoding: lat/lng → address. Uses interpolation from GIS data
4. Geohashing: encodes a geographic area into a short string. Recursively divides grids into sub-grids. Used for map tiling in this design

5. Map rendering: the world is broken into tiles (256×256 px PNGs at different zoom levels). Client downloads only the relevant tiles for its viewport + zoom level and stitches them together
6. Road data processing for navigation: routing algorithms (Dijkstra/A* variants) operate on graphs (intersections = nodes, roads = edges). World graph too large → break into routing tiles (binary files of road data per grid). Three hierarchical levels: local roads, arterial roads, major highways. Higher-level tiles cover larger areas with fewer details. Tiles reference connected tiles at the same/different zoom levels

Back-of-the-envelope estimation #

Storage (map tiles):

1. Zoom level 21: ~4.4 trillion tiles × 100KB = 440 PB raw
2. ~90% is ocean/desert/mountain → highly compressible → reduce 80-90% → ~50 PB at highest zoom
3. Each lower zoom = 4× fewer tiles. Total: 50 + 50/4 + 50/16 + ... = ~67 PB. Rough estimate: ~100 PB for all zoom levels

Server throughput:

1. Navigation: 1B DAU × 5 trips/week ÷ 7 ÷ 10⁵ = ~7,200 QPS (avg). Peak: ~36,000 QPS (5×)
2. Location updates: 5B nav minutes/day × 60 = 300B requests/day = 3M QPS (every 1s). Batched every 15s → 200,000 QPS (avg). Peak: ~1M QPS

Step 2 of 4: Propose high-level design and get buy-in #

Goal: agree on the three services and the tile-based map pipeline.

Figure 7: High-level design

Location service #

Clients send location updates every X seconds (configurable). Batched: record every 1s, send batch every 15s → reduces traffic. Uses:

1. HTTP with keep-alive
2. POST /v1/locations with a JSON-encoded array of (lat, lng, timestamp) tuples
3. Database: Cassandra (high write volume, scalable) + Kafka for stream processing

Navigation service #

Finds a reasonably fast route A→B. Accuracy critical, can tolerate some latency.

• GET /v1/nav?origin=...&destination=...
• Returns: distance, duration, start/end location, polyline, HTML instructions, travel mode

Map rendering #

Pre-generated static map tiles (option 2): not dynamically generated. Each tile at a zoom level covers a fixed geohash grid. Served via CDN from the nearest POP.

Data usage: at 30km/h, 200m×200m tiles (100KB each), 25 tiles per 1km² = 2.5MB data → 75MB/hour or 1.25MB/minute.

CDN traffic: 5B nav minutes/day × 1.25MB/min = 6.25B MB/day = ~62,500 MB/sec through CDN. With 200 POPs → a few hundred MB/sec each.

Tile URL construction: client converts lat/lng + zoom → geohash → URL (e.g. https://cdn.map-provider.com/tiles/9q9heb.png). Alternative: map tile service as intermediary for operational flexibility (avoid hardcoding geohash logic in clients).

Step 3 of 4: Design deep dive #

Goal: data model, then each service: with the adaptive ETA trick.

Data model #

Routing tiles:

1. Raw road data (TBs) → offline routing tile processing service → routing tiles at 3 resolutions
2. Stored as adjacency lists serialized to binary files in object storage (S3), organized by geohash
3. Aggressively cached on the routing service. DB not needed

User location data (Cassandra):

Partition key: user_id. Clustering key: timestamp. Efficient time-range queries per user. Prioritizes availability over consistency (CAP: AP).

Geocoding database: Redis key-value store: place → lat/lng. Frequent reads, infrequent writes.

Precomputed map images: stored on CDN backed by cloud storage (S3). Precomputed at 21 zoom levels.

Services #

Location service:

Location data logged to Kafka. Downstream consumers:

1. Live traffic service → updates the live traffic DB
2. Routing tile processing service → detects new/closed roads, updates routing tiles in object storage
3. Other services tap the stream for various purposes

Map rendering:

21 zoom levels. Level 0: 1 tile (256×256, entire world). Each increment: 4× tiles, 4× pixels.

Vector optimization: send vector info (paths, polygons) instead of raster PNGs. Better compression, smoother zooming (no pixelation). Client draws from vectors via WebGL.

Navigation service:

1. Geocoding service: resolves address → lat/lng. Uses key-value DB (Redis)
2. Route planner service: orchestrates pathfinding
3. Shortest-path service: A* variant against routing tiles in object storage:
   • Convert origin/destination lat/lng → geohashes → load start/end routing tiles
   • Traverse the graph, load neighboring tiles on demand from object storage (or local cache)
   • Can switch to higher-level tiles (highways) through cross-resolution references
   • Continue until the best routes are found

4. ETA service: ML-based prediction using current traffic + historical data. Predicts traffic 10-20 min ahead
5. Ranker service: filters routes by user preferences (avoid tolls, avoid freeways), ranks fastest to slowest, returns top-k
6. Updater services: consume the Kafka location stream. Traffic update service → live traffic DB. Routing tile processing service → updated routing tiles

Adaptive ETA and rerouting #

Naive approach: store user → [routing tiles] mapping. Traffic incident on tile s₂ → scan all rows to find affected users. O(n × m): too slow.

Improved: store user → [current tile, parent tile, grandparent tile]. Check only the largest tile in each row. Fast filtering.

Delivery protocol: WebSocket preferred over mobile push (limited payload, no web support) and long polling. Bi-directional communication supports last-mile delivery. SSE also viable.

Figure 21: Final design

Step 4 of 4: Wrap up #

What we designed:

1. Location update (Cassandra + Kafka)
2. ETA/route planning (A* with routing tiles + ML ETA)
3. Map rendering (precomputed tiles + CDN + vectors)
4. Adaptive ETA uses hierarchical tile tracking

Potential expansion: multi-stop navigation for enterprise (e.g. delivery services).