Design Uber / a Ride-Sharing Dispatch System
HardAsked at: Uber, Lyft, Amazon, Google
Riders request a trip; the system must find and dispatch a nearby available driver in real time, track live locations of both parties, and compute dynamic pricing. The core challenge is efficient real-time geospatial matching at scale, plus keeping millions of location updates flowing continuously.
Request flow
Functional Requirements
- Riders can request a ride from location A to B; drivers can go online/offline and accept/decline ride requests.
- System matches a rider to a nearby available driver within seconds.
- Both parties see the other's live location during an active trip.
- Dynamic ('surge') pricing based on local supply/demand.
Non-Functional Requirements
- Matching latency must be very low (a few seconds) — this is the core user-facing SLA.
- Must handle continuous, high-volume location updates from every active driver (e.g. every 4 seconds).
- Available-driver search must be geospatially efficient — 'find drivers within 2km' should never mean scanning every driver on Earth.
- Eventual consistency for location is fine (a few seconds of staleness is imperceptible); the final ride-match decision must avoid double-booking a driver.
Capacity Estimation
- 5M daily active drivers, each pinging location every 4 seconds while online (~6 active hours) → roughly 5M * (6*3600/4) ≈ tens of millions of location updates/day → on the order of 5,000–10,000 location writes/sec sustained.
- 1M ride requests/day ≈ ~12 requests/sec average, bursty around commute hours (design for 10x+ peak).
- Each location update is tiny (~100 bytes: driver_id, lat, lng, timestamp, heading) — the challenge here is write throughput and query pattern (geospatial), not storage volume.
Design Walkthrough
1. High-level architecture
Driver app periodically streams {driver_id, lat, lng, status} to a Location Service over a persistent connection (WebSocket) or frequent lightweight HTTP/gRPC calls.
Location Service writes the latest position into a geospatial index (see below) and publishes location deltas so any active rider tracking that driver gets a live update.
Rider requests a ride → Matching Service queries the geospatial index for nearby available drivers → applies ranking (distance, ETA, driver rating) → dispatches a request to the top candidate → on decline/timeout, tries the next candidate.
Pricing Service computes a surge multiplier per geographic cell based on the real-time ratio of open ride requests to available drivers in that cell.
2. Geospatial indexing — the core design decision
A naive 'lat/lng range scan' in a normal DB is inefficient because 2D proximity doesn't map cleanly onto a 1D sorted index. The standard fix is to convert 2D coordinates into a 1D representation that preserves locality.
Geohashing: encode (lat, lng) into a base32 string where nearby points usually share a prefix — you can then find 'nearby' drivers by querying for keys sharing a prefix, and adjust precision (string length) to control search radius. Simple to reason about and to shard by (shard key = geohash prefix), but has known edge-case bugs (two very close points near a boundary can have very different geohash prefixes).
Quadtree: recursively divide the map into 4 cells, subdividing further wherever driver density is high — naturally adapts resolution to density (dense cities get fine-grained cells, empty areas stay coarse), which is a nice property for the real, highly uneven distribution of drivers.
Either approach turns 'find nearby drivers' into 'look up drivers in this cell and its immediate neighbor cells' — an O(1)-ish indexed lookup instead of a full scan. In an interview, geohashing is simpler to explain fully; quadtrees are the 'I know the more sophisticated real-world answer' follow-up.
3. Data storage
Live driver locations: kept in an in-memory store (Redis supports geospatial commands like GEOADD/GEORADIUS directly) rather than a disk-backed DB, since this data is high-write, ephemeral (only the latest position matters), and needs very low query latency.
Trip/ride records: a normal transactional DB (Postgres/MySQL) for the durable record of each ride (rider, driver, route, fare, timestamps) — this is the source of truth for billing/history and doesn't need the same real-time properties as location.
Historical location trails (for ETAs, fraud detection, analytics) can be streamed via a message queue into a data lake / time-series store, decoupled from the real-time matching path.
4. Matching & avoiding double-dispatch
When the Matching Service selects a candidate driver, it must atomically mark that driver as 'pending offer' so no other concurrent match request can also dispatch to them — a short-TTL distributed lock (or a conditional/atomic update in the driver-status store, e.g. Redis `SET driver:123:status pending NX`) prevents the classic double-booking race.
If the driver doesn't respond within a timeout, release the lock and try the next-ranked candidate.
Bottlenecks & Mitigations
- Continuous high-frequency location writes from millions of drivers — mitigated by using an in-memory geospatial store and batching/throttling update frequency based on movement (e.g. skip updates if the driver hasn't moved).
- Matching race conditions (two riders matched to the same driver) — solved via atomic status locking described above.
- Hot geographic cells (e.g. a stadium letting out after an event) create a local supply/demand spike — surge pricing plus geographically-aware sharding of the matching load helps isolate the hot spot from the rest of the system.
Likely Follow-Up Questions
- How would you compute ETA accurately? (A separate routing/ETA service, typically backed by a road-graph + real-time traffic data — usually treated as a black-box dependency in this interview.)
- How do you handle a driver going offline mid-dispatch (phone dies)? (Heartbeat/TTL on driver status; if no location update within N seconds, mark offline and exclude from matching.)
- How would you extend this to support pooled/shared rides? (Matching becomes a batch optimization problem over a rolling window of requests rather than a single nearest-driver lookup — worth mentioning as a much harder variant.)