System design deep dive · HLD
Design Uber (ride-hailing): full high-level design.
Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for ride matching and for the trip lifecycle state machine, and an entity-relationship diagram for riders, drivers, trips, and driver locations - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
Ride-hailing has one component with no analogue in most CRUD systems: a continuously moving, massively concurrent geospatial index that must answer "who is nearby right now" in well under a second. Naming that up front sets the right scope.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers decide everything: whether the location index can be a single in-memory structure or must be sharded, and whether ride requests can go straight to a relational database or need a queue in front of them.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Concurrent active drivers | 5 million online globally at peak | 5M drivers pinging location, distributed across geo-sharded regions |
| Location update writes | One GPS ping every 4 seconds per active driver | 5,000,000 / 4 ≈ 1.25 million location writes/sec globally - must be an in-memory geo index, not a relational table |
| Ride requests | ~20 million rides/day globally | ~231 requests/sec average, ~2,000 requests/sec peak (rush hour, event surges) |
| Nearby-driver query | Each ride request scans a geohash cell + 8 neighbors | ~2,000 queries/sec × ~9 cells × ~dozens of drivers/cell - trivially served by an in-memory grid, never a full table scan |
| Trip state writes | Each trip transitions through ~6 states | 20M rides/day × 6 ≈ 120M state-transition writes/day - modest compared to location traffic, fits a normal durable database |
3. High-level design (HLD)
The HLD separates the high-frequency, ephemeral location-ingestion path from the lower-frequency, durable trip-lifecycle path - they share almost nothing except the driver_id used to look each other up.
What each box owns
Location ingest service & geo index
Every GPS ping from an online driver is written to an in-memory geospatial index keyed by a geohash (or quadtree cell) covering their current position, with a short TTL - if a driver stops pinging, they silently expire out of "available nearby" results within seconds. This index is never the source of truth for anything durable; it is a fast, disposable, constantly-overwritten cache of "who is roughly where right now."
Matching service
On a ride request, looks up the rider's geohash cell and its 8 neighboring cells in the geo index, filters to available (not currently on a trip) drivers, ranks candidates by ETA and acceptance-rate heuristics, and sends a sequential or batched offer. It is deliberately stateless and horizontally scalable - all the state it needs lives in the geo index and the trip service.
Trip service (state machine)
Owns the authoritative trip record and its lifecycle: requested → matched → driver_arriving → in_progress → completed (or cancelled at several points). Every transition is a conditional write guarded by the current state, so a driver can't be double-matched and a trip can't skip a state - this is the one part of the system that must be strongly consistent.
Location history & pricing
Raw location pings are also asynchronously appended to a durable, append-only history store used for post-trip ETA analysis, fraud detection (route deviation), and rider-facing "track my ride" replay - this write is decoupled from the real-time index so a slow analytics write can never delay a location update reaching the matching path.
4. Detailed architecture diagram
The architecture diagram shows the geo index sharded by region (so a Tokyo rider never queries a US-hosted index), the trip database sharded by trip_id, and the fully decoupled async pipeline that feeds ETA models and fraud detection.
| Decision | Choice | Reasoning |
|---|---|---|
| Geo index sharding | By region/city cluster, not a single global structure | A rider in Tokyo never needs to search among drivers in São Paulo; regional sharding keeps each index small and query latency low. |
| Geo index technology | In-memory (Redis geo commands / custom quadtree service) | 1.25M writes/sec and sub-second nearby queries rule out a disk-backed relational index entirely. |
| Trip database consistency | Strongly consistent, conditional writes per state transition | Double-matching a driver or corrupting a trip's state is a correctness bug, not a performance one - this is the one place to trade some latency for correctness. |
| Location history isolation | Separate async time-series store, not the live geo index | Historical replay and fraud analysis are read patterns completely different from "who is nearby now," and must not compete with matching for the same hot storage. |
5. Sequence diagrams for the two critical flows
Matching is a synchronous, latency-critical read of the geo index; the trip lifecycle is a synchronous, consistency-critical sequence of guarded state transitions. Both must work correctly even when a driver rejects an offer or goes offline mid-trip.
5.1 Ride request & nearby-driver matching
Step 3 returns candidates ranked purely by proximity from the fast in-memory index; step 4's ETA ranking and acceptance-likelihood scoring happen in the matching service itself, not in the geo index, which stays a dumb, extremely fast spatial lookup. If the driver in step 6 rejects or times out, the trip service reverts to requested and the matching service tries the next candidate - this retry loop is the reason the trip's state transitions must be strictly guarded.
5.2 Trip lifecycle state machine
Every transition in steps 1, 3, and 5 is a conditional write - "set state=X only if current state is Y" - which is what prevents a stale or duplicate client action (e.g. the driver's app retrying "start trip" after a flaky network response) from corrupting the state machine or double-charging the rider. Step 6's fare computation deliberately happens only after the trip reaches in_progress → completed, never speculatively earlier, since the final route and duration aren't known until the trip actually ends.
6. Entity-relationship (ER) diagram and schema
The schema has to answer: how is the current trip for a driver or rider looked up instantly, how is high-frequency location data kept out of the transactional path, and how is the trip state machine enforced at the data layer.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| Relational (Postgres), sharded by trip_id, for trips/riders/drivers | Strong consistency and conditional writes are required for the trip state machine and billing correctness. | Cross-shard queries (e.g. "all trips today across all cities") need a separate analytics pipeline. |
| In-memory key-value / geo index (Redis) for driver_locations | Access pattern is "who is near this point right now," refreshed every few seconds, disposable by nature. | Not durable by design - a full index rebuild after a cache failure relies on drivers simply re-pinging within seconds. |
7. Deep dives interviewers actually probe
Geohash vs quadtree - which one and why?
A geohash encodes lat/lng into a string prefix where nearby points often (not always) share a prefix - simple to shard and index in Redis, but has an edge-boundary problem where two physically close points can hash to completely different cells, which is why matching always queries the cell plus its 8 neighbors. A quadtree instead recursively subdivides space based on actual driver density, giving more uniform cell occupancy in both dense (Manhattan) and sparse (rural) areas at the cost of a more complex, custom-built index rather than reusable Redis geo commands. Geohash is the pragmatic default; quadtree is worth the complexity once density variance across a market becomes extreme.
What happens if two ride requests match the same driver at once?
The trip service's conditional write is the safeguard: assigning a driver is really "set drivers.status = on_trip WHERE status = available," and only one of two concurrent requests can win that compare-and-swap. The losing request's matching attempt simply falls through to the next-ranked candidate driver, invisibly to the rider - this is why driver status must be a strongly consistent field, never eventually consistent.
How do you handle a driver who goes offline (phone dies) mid-trip?
Location pings simply stop, so the driver ages out of the "available" pool automatically via TTL - but the trip itself does not auto-cancel on a location gap alone, since a dead phone with a trip still legitimately in progress is common (tunnels, poor signal). Instead, a timeout on the trip's expected state duration (e.g. no completion event within an anomalously long window for the estimated route) triggers a support/ops escalation path rather than an automatic silent cancellation.
How does surge pricing avoid becoming a performance bottleneck on every request?
Surge multipliers are precomputed per geohash cell on a short interval (e.g. every 30-60 seconds) from the ratio of open ride requests to available drivers in that cell, cached, and simply read (not recomputed) at request time. Computing a real-time supply/demand ratio synchronously on every single ride request would add unnecessary latency to the one path that most needs to stay fast.
What is the single biggest bottleneck as this scales 10x?
Not the trip database - it's comparatively low-volume and shards cleanly by trip_id. The real bottleneck becomes the in-memory geo index in the densest single markets (a stadium letting out, a city center at rush hour) where the ratio of location writes to matching reads spikes locally far faster than global averages suggest. The fix is finer-grained cell sharding within a single hot region (not just city-level sharding) so one dense neighborhood's traffic doesn't degrade an entire metro's matching latency.
Post a Comment
Add