System Design Case Study
Maps and navigation
7:41 AM before a commute: Google Maps zooms the city, searches for work, and paints Directions. The map paints instantly, a blue route appears, and an updates as traffic shifts: all while millions of phones quietly contribute GPS.
Maps is several systems cooperating: for display, / places for search, for paths, and for live ETAs, without tracking individuals.
Open Maps → navigate
CDN serves z/x/y squares as you pan.
Address or POI → coordinates.
Road graph + shortcuts → polyline.
Historical + live traffic weights.
Try it: tiles, routing, and location updates
Map tiles are CDN-heavy. Routing is a compute path over a road graph; driver location updates are a separate write stream.
- Client
- Tile CDN
- Routing service
- Graph shard
- Location stream
- Tile hits
- 0
- Route computes
- 0
- Mode
- tiles
- Path hop
- 0
Tiles
CDN0 tile requests.
Routing
CPU0 route computes.
Freshness
trafficLive traffic overlays update faster than base map tiles.
Load tiles, compute a route, or publish a location update on separate paths.
What actually happens
The viewport requests (raster or ) from edge caches. Searching "coffee near me" hits geospatial indexes via and POI search.
runs on a weighted road graph. Production systems use (or similar preprocessing) so regional routes finish under a second. sums segment times from historical patterns plus live .
Live traffic starts as GPS pings, runs , then aggregates by segment with privacy thresholds. If the stream lags past the freshness SLO, routes should use historical weights and show a stale badge, not fake live data.
How to choose the maps building blocks
1. Raster or vector tiles? Raster is simple and CDN-friendly; are smaller and restylable when clients can render.
2. Can Dijkstra finish in time? For city-to-city routes on 100M nodes, say (or A* only for smaller graphs).
3. Fresh traffic vs privacy? Publish only after K devices; keep raw pings short-lived.
Simple rule of thumb
Treat maps as four products in one jacket: tiles, search, routing, traffic. Optimize each path separately, then join them at the client.
In simple terms: paint the map fast, find the place, compute a honest route, and update ETA without tracking people.
Case-study upgrade
Maps and Navigation Math
Maps combine mostly static tile serving with dynamic routing, place search, and live traffic ingestion.
Assumptions and formulas
- Daily users: 100M. Tile requests/session: 10. Sessions/user/day: 5.
- GPS traffic pings are high-volume and feed segment speed aggregation.
- Routing CPU depends on graph size, traffic freshness, and route complexity.
Concrete math
- Tile requests: 100M x 10 x 5 = 5B/day = 57.9K QPS average; peak can exceed 500K QPS.
- Route requests: 100M/day = 1.16K QPS average; peak can be 5K to 20K QPS.
- GPS pings: 50M/min = 833K/sec. At 100 bytes/ping, ingress is about 83 MB/sec before overhead.
- Traffic updates: 10M segments x 32 bytes/minute = 320 MB/minute, about 460 GB/day raw if dense.
- Route CPU: 5K QPS x 50 ms CPU = 250 CPU cores before headroom.
Design decisions forced by numbers
- Serve tiles from caches and CDN; keep routing and traffic updates as dynamic paths.
- Map-match GPS pings into road segments before updating routing edge weights.
- Use offline graph preprocessing and regional graph partitions.
Scaling to millions
- At 1M users: cached tiles, basic routing, and place search are enough.
- At 10M users: add traffic streams, regional route workers, and tile cache warming.
- At 100M+ users: add graph partitioning, offline map packages, sparse traffic updates, and degraded stale routes.
Readable flow
Interview follow-ups to expect
- Which data is static and cacheable, and which data is live?
- How stale can traffic be before routes become bad?
- How do offline maps change storage and sync design?
Operational readiness checklist
After the math, explain how this capacity plan is measured, protected, launched, and evolved.
Observability
- Attach each capacity estimate to a dashboard metric: p99 latency, queue age, cache hit rate, shard skew, error rate, and freshness lag.
- Alert on rate-of-change and saturation, not only hard failures; backlogs and hot keys usually warn before an outage.
Security and abuse
- Budget for auth checks, rate limits, quota isolation, audit logging, privacy filters, and abuse-review side paths.
- Separate trusted internal events from user-controlled input so retries and backfills cannot bypass policy checks.
Degraded modes
- Define the fallback when a dependency is slow: stale cache, partial results, read-only mode, delayed async work, or admission control.
- Protect the invariant first; reduce freshness, personalization, or analytics quality before risking duplicate or corrupt state.
Testing and rollout
- Test average, peak, and hot-object traffic; include retry storms, cold caches, lagging workers, and regional dependency loss.
- Use canaries, shadow reads, dual-write validation, feature flags, and explicit rollback criteria for risky path changes.
Rollout, backfill, and runbooks
- Make migrations and backfills idempotent, resumable, rate-limited, and visible through progress and error metrics.
- Write the runbook before launch: owner, dashboards, paging thresholds, mitigation switches, replay steps, and repair commands.
10x evolution
- For maps and navigation math, state which number forces the next move: cache memory, shard count, write amplification, queue lag, egress, or failover reserve.
- Add the next layer only when the metric forces it: sharding, regional reads, async replay, hot-key isolation, or stricter backpressure.
Scope you should nail down
Product surface
- Map rendering: display map tiles at multiple zoom levels
- Navigation: turn-by-turn directions
- Routing: shortest/fastest path
- Real-time traffic: traffic flow, incidents
- ETA prediction
- Location search: address, POI, coordinates
- Nearby places: restaurants, gas stations, etc.
Scale targets
- 1B users
- Route computation <1 second
- Map tiles load <200ms
- Real-time traffic updates
- Offline maps support
Capacity estimation
Tile requests: 100M+ users × 10 tiles/session ≈ 1B+ tile requests/day
Road graph: ~100M nodes, edges. ~50 GB compressed
POI database: billions of places
Tile QPS: 100M daily users × 5 sessions/day × 10 tiles/session = 5B tile requests/day; 5B / 86,400 ≈ 57.9K QPS average, with 500K+ QPS peak.
Route QPS: 100M route requests/day / 86,400 ≈ 1.16K QPS average; commute peaks can be 5K-20K QPS.
GPS ingress: 50M pings/min / 60 ≈ 833K pings/sec; at 100 bytes/ping, ingress is about 83MB/sec before protocol overhead.
Traffic aggregates: 10M road segments × 32 bytes/update = 320MB per full minute, or about 460GB/day raw if every segment updates each minute.
Route compute: 5K QPS × 50ms CPU/query = 250 CPU cores before redundancy, retries, and headroom.
Offline packages: 10M monthly downloads × 300MB average region = 3PB/month egress before delta updates and caching.
3. 🔌 System API
getRoute(origin, destination, mode?)origin, destination: { lat, lng } or place_id. mode: driving | walking | transit | bicycling. Returns: polyline, steps, ETA, distance
searchPlaces(query, location?, radius?)Geocoding, reverse geocoding, POI search. Returns Place[]
getMapTiles(zoom, x, y)Returns tile URLs for given zoom level and tile coordinates
getTraffic(bounds)Returns traffic flow data for visible map bounds
4. 🗺️ Map Tile System
Pre-Rendered Tiles
A tile pyramid divides the world into a grid at each zoom level. Zoom zero has one tile; each additional level divides a tile into four, giving 4^z possible tiles at level z. A z/x/y address identifies a tile without a database lookup. At zoom 20 alone the full world would contain more than a trillion possible tiles, so do not assume every tile at every level is pre-rendered and retained. Generate or store useful coverage selectively and cache tiles according to demand.
Raster Tiles
Pre-rendered PNG/WebP images. Fast to serve, Content Delivery Network (CDN). Large storage. Fixed style.
Vector Tiles
Send geometry + style; client renders. Smaller size, dynamic styling. Client needs GPU.
5. 🧭 Navigation & Routing
Road Network Graph
Represent legal movement through the road network as a directed graph. Edges carry distance and estimated travel time; one-way restrictions remove illegal directions. Turn restrictions need additional state, because reaching an intersection from one road can permit different exits than reaching it from another. A routing graph may therefore represent road segments as states or explicitly encode turns. Walking, driving, and cycling use different access rules and weights even on the same geographic map.
Dijkstra
Dijkstra’s algorithm repeatedly settles the unsettled state with the smallest known travel cost and relaxes its outgoing edges. With nonnegative weights, the destination cost is optimal once it is settled. A binary-heap implementation has a typical O((V + E) log V) bound. It provides a clear correctness baseline, but exploring a large fraction of a continental road graph for every request is often too expensive.
A*
A* adds an estimate of the remaining travel cost to the cost already spent, directing exploration toward the destination. To preserve shortest-path guarantees, the heuristic must be a valid lower bound; straight-line distance needs conversion to a lower-bound travel time when edge weights are seconds. A heuristic that overestimates can skip the best route. Performance depends on heuristic quality and graph structure, so it is not automatically the best choice for every long route.
Contraction Hierarchies
Contraction hierarchies move work into preprocessing: remove less important graph states while adding shortcuts that preserve shortest-path distances between the remaining states. A query then searches a much smaller hierarchy and expands shortcuts back into actual roads. This trades extra build time and storage for faster queries. Dynamic traffic complicates the trade-off because shortcuts depend on weights; use an update-capable preprocessing method or rebuild/customize affected structures instead of assuming old shortcuts remain valid.
6. ⏱️ ETA Prediction
Begin with estimated traversal time for each road segment at the time the vehicle is expected to enter it. Historical speeds by weekday and time provide a baseline; recent traffic, incidents, weather, and route-specific patterns adjust that baseline. Travel time is distance divided by speed only when that speed is representative, so intersections, turns, and stop delays also matter.
For a simple example, three segments estimated at two, three, and four minutes yield a nine-minute route before additional turn delays. The third segment is reached about five minutes in the future, so using its current speed may be less accurate than predicting its speed at arrival. Measure ETA error over completed trips by city, transport mode, and horizon rather than treating one global average as sufficient.
7. 🚦 Real-Time Traffic
Data Pipeline
- Aggregate GPS data from millions of users
- Map GPS to road segments (map matching)
- Calculate segment speed (avg, median)
- Traffic flow model: free flow vs congested
- Incident detection: accidents, construction
Storage
Time-series DB for segment speeds. Update every 1–5 min. Stream processing (stream log, Flink) for real-time aggregation.
8. 🏗️ Architecture
9. 🔍 Location Search
Geocoding
- Address → lat/lng (geocoding)
- lat/lng → address (reverse geocoding)
- POI search: "coffee near me", "gas station"
search index
Geospatial queries: geo_distance, geo_bounding_box. Full-text search on names, addresses. Filter by type (restaurant, gas, etc.).
10. 📊 Road Network Graph Storage
- Adjacency list: node → list of (neighbor, weight). Compact, fast for graph traversal.
- Edge weights: travel time, distance. Updated per traffic.
- Graph partitioning: partition by region (e.g., by country, state). Route within region first; cross-region for long routes.
- Contraction Hierarchies: store precomputed shortcuts. ~50 GB for global graph.
11. 📱 Offline Maps
An offline package contains a bounded region’s map geometry, place information where supported, and a compatible routing graph. A manifest names the package version and checksums so the device does not combine new tiles with incompatible old graph identifiers. The download size depends on region, detail, and included search data; measure representative packages instead of treating one fixed range as universal.
The device can render the stored map and compute supported routes without a connection. It lacks fresh incidents and live traffic, so describe estimates accordingly. When connectivity returns, download versioned deltas or a replacement package, verify it, and switch atomically while retaining a usable previous copy until installation completes.
Map Matching & GPS Data
Map matching infers which road a sequence of noisy GPS measurements follows. Choosing the nearest road independently can jump between a motorway and its parallel service road. A probabilistic sequence model combines distance from candidate roads with heading, speed, legal connectivity, and the previous matched position. Retain a confidence score; an uncertain match should not contribute as strongly to the speed estimate as a consistent trace.
- Batch GPS updates in time windows (e.g., 1 min)
- Filter outliers: GPS errors, tunnels, bridges
- Privacy: anonymize, aggregate. No individual user tracking.
Hard Part: Fresh Traffic Without Tracking People
Freshness and privacy invariant
Route quality depends on recent segment speeds, but the system should not expose individual trips. Keep raw pings short-lived, aggregate by road segment and time bucket, and serve freshness labels with every traffic layer.
- Raw ping retention: minutes to hours, enough for map matching and abuse filtering.
- Aggregate retention: segment_id, speed, count, confidence, bucket_start, bucket_end.
- Privacy threshold: do not publish segment speeds until at least K distinct devices contribute to the bucket.
- Freshness rule: live traffic older than 5 minutes falls back to historical speed with a stale badge.
Map matching drill
A ping near a parallel road must not flip segment speed. Use heading, speed, previous matched segment, and confidence before writing an aggregate.
Freshness math
If stream lag is 7 minutes and freshness SLO is 5 minutes, route service should use historical weights plus incident flags rather than pretending traffic is live.
Privacy guard
For sparse roads, delay or coarsen updates until enough independent devices contribute to the time bucket. A count threshold reduces direct disclosure, but aggregation alone does not prove that individuals cannot be inferred through repeated queries or external knowledge. Limit raw trace access and retention, prevent arbitrary fine-grained queries, and review how repeated releases compose. Explicitly accept reduced traffic precision where publishing it would expose too much about individual movement.
12. ⚠️ Bottlenecks
Tile storage & bandwidth
50 PB tiles. Mitigation: Content Delivery Network (CDN), vector tiles (smaller), lazy load.
Routing latency
Long routes, large graph. Mitigation: Contraction Hierarchies, pre-compute.
GPS data volume
50M pings/min. Mitigation: stream processing, sampling, aggregation.
Graph partitioning
Cross-region routes. Mitigation: hierarchical routing, boundary nodes.
13. Production Readiness
SLOs and metrics
- Tile p99 <200ms at edge; route p99 <1 sec for regional routes.
- Traffic freshness p95 <5 min; ETA error median and p90 tracked by city and route type.
- Monitor tile hit rate, origin egress, map-match confidence, geocode zero-result rate, and offline sync success.
Alerting
- Page on routing error spike, traffic stream lag above freshness SLO, or tile origin overload.
- Warn on map-match confidence drop, POI import delay, route CPU saturation, and offline package failure.
- City-level alerts prevent one region's commute spike from hiding global health.
Runbook and degraded mode
- Traffic lag: use historical segment speeds and label traffic stale.
- Routing overload: switch to coarser graph, fewer alternatives, and cached popular routes.
- Tile origin outage: serve cached tiles longer and disable low-priority style variants.
Security and threat model
- Assets: precise location pings, routes, home/work inference, POI edits, and traffic aggregates.
- Actors: location scrapers, fake GPS injectors, abusive POI editors, and insiders querying raw traces.
- Controls: aggregation thresholds, short raw retention, access audits, signed clients, anomaly detection, and privacy-safe logs.
Test plan
- Replay GPS traces with tunnels, parallel roads, U-turns, and noisy phones to validate map matching.
- Load test 500K tile QPS and 20K route QPS with cache miss and origin-shield scenarios.
- Privacy tests verify raw ping TTL, aggregate thresholds, and support-tool audit coverage.
Rollout, DR, and 10x scale
- Canary new map data by region and version tiles so clients can roll back to the previous graph.
- DR keeps tile serving independent from dynamic routing; traffic stream RPO can be minutes if stale fallback is explicit.
- At 10x: regionalize route compute, push more vector tiles to edge, sample GPS adaptively, and partition graph updates by spatial cells.
Review the design
Map tiles: pre-rendered pyramid (z/x/y), Content Delivery Network (CDN). Vector tiles for smaller size.
Routing: road graph, Contraction Hierarchies for millisecond queries. A* for simple cases.
ETA: historical + live traffic + ML. Segment speed aggregation.
Traffic: GPS pings → map matching → segment speed → time-series DB.
Search: geospatial search index for geocoding, reverse geocoding, and POI lookup.
Offline: pre-download tiles + graph subset for region.
Compare a starting answer with a more complete design
A starting answer
Separate tile serving, place search, geocoding, routing, traffic, and mobile offline support.
Developing the reasoning
Explain vector versus raster tiles, spatial cells, preprocessed routing graphs, traffic-weight updates, ETA error tracking, origin shielding, and stale traffic fallback.
Deeper walkthrough
Maps deeper walkthrough
Maps combines mostly static tile delivery with dynamic search, routing, and traffic. These paths need different storage and latency strategies.
Requirement refinements
Clarify map display, place search, geocoding, routing, live traffic, offline maps, and business data updates.
State whether routes optimize distance, time, tolls, traffic, transit, walking, or multiple stops.
API design details
Tile APIs should be cache-friendly by zoom, x, y, style, and version.
Routing APIs should include origin, destination, mode, departure time, constraints, and route alternatives.
Data model and storage
Store map tiles or vector tile data separately from places, road graph, traffic observations, and routing metadata.
Partition places and road graph data by spatial cells or regions for locality.
Scaling strategy
Serve tiles through Content Delivery Network (CDN) and origin shielding; compute routes on regional graph partitions with preprocessing.
Stream traffic updates into edge-cost aggregates rather than rebuilding the whole road graph.
Reliability, recovery, and operations
If live traffic lags, use historical traffic with freshness labels; if route service times out, retry with a coarser graph.
Monitor tile hit rate, route p99, ETA error, geocode zero-result rate, and traffic freshness.
Deepening reference
Maps and Navigation: realistic production notes
Beginner mental model: Maps is tile serving, geospatial search, routing graphs, traffic ingestion, and offline/mobile constraints.
Production scope: A strong design separates static map tiles from dynamic routing and traffic. The routing graph is preprocessed; live traffic adjusts weights rather than rebuilding the whole graph.
Choose what the first version must guarantee
Start by deciding which maps and navigation capabilities are essential. Describe the main read and write operations before choosing infrastructure. For each operation, identify the stored records it uses and the condition that makes its result correct. A fast response is useful only if it satisfies that condition.
Next, separate work the user must wait for from work that can finish later. Estimate requests per second, storage growth, and the busiest object or customer. Use those estimates to choose one bottleneck to investigate. The calculations below are example workloads with stated assumptions; they are not measured limits of a particular product.
Core flow to walk through
Map view: client requests tiles by zoom/x/y, CDN serves cached tiles.
Search nearby: geocode query, use spatial index, rank places by relevance and distance.
Route: map-match origin/destination, run routing on regional graph, apply traffic weights.
Production readiness
Maps and Navigation: ship, operate, and evolve
Now examine the same request flow during failures and deployments. Tie each operational control to the user behavior it protects.
Observability
Track maps and navigation p95/p99 latency, error rate, saturation, and user-visible freshness separately for read, write, and async paths.
Alert on leading indicators such as queue age, hot-key skew, cache miss storms, reconciliation mismatches, and error-budget burn.
Security and abuse
Enforce authentication, authorization, rate limits, input validation, audit trails, and privacy checks at the service boundary.
Treat abuse controls as a first-class path: throttling, quota isolation, moderation hooks, revocation, and safe handling of sensitive data.
Degraded modes
Name what still works if cache, search, ranking, stream processing, object storage, or a regional dependency is slow.
Prefer stale-but-safe reads, partial results, async retry, admission control, and feature disablement over corrupting core state.
Testing and rollout
Load test average, peak, and hot-object traffic; add failure-injection for retries, timeouts, backlog growth, and dependency outages.
Ship with canaries, shadow reads or dual writes when useful, rollback switches, schema compatibility checks, and replay validation.
Runbooks
Document dashboards, paging thresholds, owner actions, rollback steps, data repair commands, and customer-impact language.
Keep backfills and replays idempotent, resumable, rate-limited, and observable so repair work does not create a second incident.
10x evolution
Say which metric forces the next architecture change: shard count, cache footprint, write amplification, queue lag, p99 latency, or regional failover reserve.
Evolve one bottleneck at a time: partition by access pattern, isolate hot tenants, regionalize reads, add replayable async pipelines, then harden multi-region behavior.
Hard parts worth deepening
Tiles are cacheable; routing and traffic are much more dynamic.
Use geohash/H3/S2 style cells for nearby lookup and regional partitioning.
Traffic updates are streams that adjust edge costs with time windows.
Mobile clients need progressive loading and offline regions.
Failure modes and recovery
Traffic pipeline lags; route with historical traffic and mark freshness.
Tile CDN misses spike; use pre-rendered popular tiles and origin shielding.
Geocoder ambiguity; return candidates with context and personalization.
Routing service timeout; return approximate route or retry with coarser graph.
Signals to monitor
Tile CDN hit rate determines origin demand for map imagery, while route p99 measures a separate computation path. A healthy tile cache cannot compensate for an overloaded routing service.
Compare ETA error with traffic-data freshness to identify stale inputs. Geocoding zero-result rate shows how often an address cannot be resolved; segment it by input language and region before treating it as a single global quality score.
| Choice | Best when | Cost |
|---|---|---|
| Pre-rendered raster tiles | High cacheability and simple clients. | Less styling flexibility. |
| Vector tiles | Client-side styling and smaller transfers matter. | More client complexity. |
| Preprocessed routing graph | Fast route queries matter. | Graph updates are more complex. |
Try this scenario
Describe how live traffic from phones changes ETA without recomputing the entire road graph.
Primary sources
- Google S2 Geometry Library: spatial indexing for maps.
- OpenStreetMap: Tiles: map tile serving model.
- RFC 7946: GeoJSON: geo feature interchange.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Combine tile serving, spatial indexing, map matching, route graph partitioning, live closures, ETA models, privacy, and offline delta updates.
Explain the decision
Why is nearest road not always correct map matching?
Read the reasoning
GPS error, parallel roads, speed/direction, topology, and prior points require probabilistic/path context rather than point distance alone.
Apply it to a production scenario
A bridge closes during active navigation. How does it propagate?
Read one approach
Version the road event, invalidate affected route regions, reroute impacted sessions, preserve last-known map safety, and measure closure-to-client latency.
Work through the numbers
Twenty million clients download 2 MB of map deltas/day. Estimate daily egress.
Read the worked calculation
40 TB/day before CDN offload, retries, regional versions, and compression.
Reason through a failure
What must offline navigation preserve?
Read the recovery reasoning
The client knows map/version freshness, applies signed deltas atomically, and falls back safely when route data is incomplete.
Sources and further study
Continue with Design Ticket Booking.