System design deep dive · HLD
Design a Google-Maps-style live location and ETA system: full high-level design.
Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for route computation and live ETA recalculation, and an entity-relationship diagram for the data model - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
This system has two very different halves that get conflated if you're not careful: computing a route once against a mostly-static road graph, and continuously refreshing an ETA against traffic that changes every few seconds - they need different architectures.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers decide how the road graph must be geo-partitioned across routing servers, how much streaming state the traffic aggregator holds, and how tile serving can be almost entirely CDN-cached.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Concurrent navigation sessions | ~20 million active trips at global peak (commute hours) | each pinging location every ~5 seconds |
| Location ping throughput | 20M sessions / 5s interval, 1.5x peak burst | ~4M pings/sec average, ~6M pings/sec peak |
| Ping payload size | ~100 bytes (device_id, lat/lng, speed, heading, ts) | 4M/s × 100B ≈ 400 MB/sec ≈ ~34 TB/day raw, short-retained |
| Route query rate | New route requests (not live pings), ~100,000/sec globally at peak | drives the routing service's fleet size, independent of ping volume |
| Road graph size | ~600 million road segments (edges) worldwide, precomputed hierarchy | too large for one machine's routing query - must be geo-sharded across regional routing servers, each holding its region's graph in memory |
| Tile requests | ~2 billion map tile fetches/day during panning/zooming | ~23,000/sec average - but ~95%+ servable from CDN edge cache since tiles are mostly static per zoom/region |
3. High-level design (HLD)
The HLD names the major components and the two data flows - route computation and live traffic/ETA - without yet committing to geo-sharding boundaries, graph precomputation strategy, or CDN topology.
What each box owns
Road graph and routing service
The road network is modeled as a graph (intersections as nodes, road segments as weighted edges) and precomputed offline into a contraction hierarchy so that shortest-path queries, which would be too slow to run Dijkstra's algorithm on a continent-scale graph per request, instead run in milliseconds. The routing service combines this static structure with the current live traffic_segments weights to compute both the route geometry and its ETA in one pass.
Location ingestion and the geo-partitioned stream
Accepts GPS pings from every active client and immediately writes them onto a stream partitioned by geo cell (e.g. S2 or geohash), so pings from the same neighborhood are processed together - this is what lets the traffic aggregator compute per-segment speeds without needing global coordination across the entire fleet of moving devices.
Traffic aggregator
Consumes the location stream, map-matches each noisy GPS point onto the nearest actual road segment, filters clearly erroneous pings (GPS jumps, parked vehicles, pedestrians on a highway segment), and maintains a rolling average speed per segment. It writes updated speeds to traffic_segments and, when a segment's speed changes enough to matter, emits an event that can trigger ETA recalculation for routes currently passing through it.
Tile server
Serves pre-rendered map tiles (roads, labels, terrain) per zoom level and geographic tile coordinate. Because the underlying map geometry changes far less often than traffic, the overwhelming majority of tile requests are served from CDN edge cache rather than hitting an origin renderer at all - traffic and live location are drawn as an overlay on top of these mostly-static tiles, not baked into them.
4. Detailed architecture diagram
The architecture diagram answers how the road graph is geo-sharded across routing servers, how traffic aggregation scales per region, and how tiles achieve near-total CDN offload - the details an interviewer checks once the HLD shape is accepted.
| Decision | Choice | Reasoning |
|---|---|---|
| Route precomputation | Contraction hierarchies, rebuilt offline nightly | Shortest-path search on a 600M-edge graph is too slow per-request from scratch; precomputing shortcuts once lets online queries run in milliseconds, at the cost of the graph structure lagging real road changes by up to a day. |
| Geo-sharding by macro-region | Each routing shard holds one region's graph in memory | The full global graph doesn't fit affordably in one server's memory, and almost all trips stay within one region, so cross-shard routing is the rare case, not the common one. |
| Traffic weights kept separate from the static graph | Live traffic_segments overlay applied at query time, not baked into the hierarchy | Traffic changes every few minutes; the hierarchy is rebuilt nightly. Keeping them separate means a traffic spike is reflected in the next query instantly, without waiting for a graph rebuild. |
| Tile serving | CDN-cached, pre-rendered per zoom/tile coordinate | Map geometry changes rarely; caching tiles at the edge avoids origin load for the ~2 billion/day tile requests, while live traffic/location render as a client-side overlay on top. |
5. Sequence diagrams for the two critical flows
A sequence diagram is where an interviewer checks whether a candidate understands that "compute a route" and "keep its ETA fresh" are fundamentally different operations with different triggers.
5.1 Initial route request
Step 2 searches the precomputed hierarchy for the structurally shortest path using static edge weights (distance/speed limit), which is fast but traffic-unaware. Step 4-6 apply live traffic as a second pass over just that path's segments to compute the actual ETA - this two-step design is what keeps route search itself cheap while still returning a traffic-aware time estimate.
5.2 Live ETA recalculation as traffic changes
Step 3's active-route index is what keeps this cheap at scale: rather than recomputing every one of 20 million active routes on every traffic tick, the system only recomputes the small subset of routes that actually pass through the segment that changed. Step 5's threshold check (only push if the ETA delta exceeds ~2 minutes) exists so a driver isn't bombarded with a new estimate every time traffic shifts by a few seconds - the update has to be worth interrupting for.
6. Entity-relationship (ER) diagram and schema
The data model has to answer: how is "which routes pass through this segment" answered fast enough to drive step 3 above, how are live locations kept cheap to write at millions per second, and how does a route stay independent of any one device's connection.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| In-memory KV / Redis geo-index for live_locations and traffic_segments | Write volume is extreme (millions/sec) and only the latest value per key matters. | Not durable by default; acceptable here since losing a few seconds of live state is recoverable from the next ping, unlike losing a financial record. |
| Relational/spatial DB (PostGIS-style) for routes | You need geometry operations (path intersects segment) and moderate write volume (route creation, not per-ping updates). | Not sized for the location-ping write path - keep that separated as shown in the architecture diagram. |
7. Deep dives interviewers actually probe
Why precompute a contraction hierarchy instead of running Dijkstra/A* per request?
Plain Dijkstra on a graph with hundreds of millions of edges would take seconds per query - unacceptable for an interactive app. A contraction hierarchy precomputes "shortcut" edges that let a bidirectional search skip over large swaths of the graph, turning a query that would touch millions of nodes into one touching a few thousand, at the cost of expensive offline precomputation (hours) whenever the underlying road network changes meaningfully - which is why it's rebuilt nightly rather than per edit.
How do you get an accurate segment speed from noisy, sparse GPS pings?
Raw GPS coordinates are first map-matched onto the most probable actual road segment (accounting for GPS error of 5-15 meters, especially in urban canyons), then obviously invalid points are filtered - a ping showing a device on a highway at walking speed likely means it's a pedestrian on an adjacent path, not highway congestion. The aggregator maintains a rolling window average per segment rather than trusting any single ping, and falls back to historical time-of-day averages when sample_count is too low to be statistically meaningful.
How do you avoid recomputing every active route on every traffic update?
The active-route index (an inverted map from segment_id to the set of route_ids currently traversing it) means a traffic update on one segment only triggers recomputation for the routes actually affected - typically a tiny fraction of the 20 million concurrently active routes - rather than a full scan. This is the same reverse-index principle used by search engines, applied to geospatial route membership instead of text tokens.
What happens when a route crosses a geo-shard boundary?
Most trips stay within one regional shard's graph, but cross-region trips (e.g. a long interstate drive) require the routing service to stitch together a path across two shards' hierarchies at a small number of well-known border nodes precomputed as part of the offline build. The query fans out to both shards, computes the sub-path in each, and joins them at the shared border node with the lowest combined cost - a design that keeps per-shard graphs bounded in size while still supporting long cross-region routes.
How is map tile serving kept fast without live traffic making every tile dynamic?
Tiles encode only the mostly-static map (roads, labels, buildings) and are cached at CDN edges keyed by zoom level and tile coordinate, refreshed on a slow cadence (days, driven by map data updates, not traffic). Live traffic coloring and the driver's own position are rendered as a client-side vector overlay fetched separately and refreshed frequently - decoupling "what rarely changes and can be cached forever" from "what changes every few seconds and never should be."
Post a Comment
Add