Design a Ride-Sharing Service (Uber)
Match riders to nearby drivers in real time with geospatial indexing and live location updates.
Overview
A ride-sharing service matches a rider to a nearby available driver, tracks both in real time, and manages the trip lifecycle. The defining challenge is efficient geospatial queries over millions of continuously-moving drivers, plus a matching engine that's fast and fair.
Requirements
Functional
- Riders request a ride; system finds nearby available drivers.
- Match a driver, show live ETA and driver location.
- Track the trip through its lifecycle (requested → matched → en route → complete).
- Dynamic (surge) pricing based on supply/demand.
Non-functional
- Low-latency matching (< a few seconds) and location updates.
- Handle millions of drivers emitting location every few seconds.
- High availability; consistency of a single trip's state.
Back-of-the-envelope
The numbers that justify the architecture.
| Active drivers | 5M | |
| Location updates | ~1M/sec | 5M drivers × ping every ~4s |
| Ride requests / sec (peak) | ~10K | |
| Match latency target | < 2 s |
Reference architecture
Drivers stream location into a geospatial index (sharded by cell); a matching service queries nearby drivers and coordinates the trip through a stateful trip service.
Deep dives
Geospatial indexing
The core question is 'which drivers are near this point?'. Naively scanning all drivers is O(n). Instead index the map with a spatial structure: geohash (encode lat/long into a string prefix so nearby points share prefixes → a simple KV lookup by cell) or a quadtree (recursively subdivide dense areas). Uber uses Google's S2 hierarchy. Drivers are bucketed into cells; a proximity query reads the rider's cell plus neighbors. Dense cities get finer cells; empty highways get coarse ones.
Handling a firehose of moving points
Millions of drivers ping every few seconds — that's ~1M writes/sec of location. Keep the live index in memory (Redis geo / an in-memory sharded grid), not a disk DB, and shard it by geographic cell so a city's load stays local. Updating a moving driver means removing it from its old cell and adding it to the new one. Persist a sampled trail to Kafka for analytics, but the matching index is hot memory.
Matching
On a request, query nearby cells for available drivers, rank by ETA (road-network distance, not straight-line), and dispatch offers. To avoid two riders grabbing one driver, matching must be atomic — lock/claim the driver during the offer, with a timeout to release if declined. Batch matching (assign a set of riders to drivers together) improves global efficiency over pure greedy first-come.
Trip lifecycle and pricing
A trip is a small state machine (requested → accepted → arriving → in-progress → completed), owned by a trip service with a durable record — this is the one place you want strong consistency (double-charging or lost trips are unacceptable). Surge pricing reads live supply/demand per cell and multiplies fares to rebalance the market.
Key trade-offs
For each decision: the two options, and when to pick which.
Bottlenecks & follow-ups
Where it breaks under load — and what an interviewer will probe.
- ▲1M location writes/sec → shard the geo index by cell; keep it in memory.
- ▲Double-booking a driver → atomic claim with timeout.
- ▲Hot cells in dense downtowns → finer subdivision + per-cell sharding.
What a strong answer sounds like
- ✓Name a concrete spatial index (geohash or quadtree/S2) — vagueness here is the fail mode.
- ✓Stress that the live location index is in-memory and sharded by geography.
- ✓Point out the one strongly-consistent component: the trip/payment state machine.