Design a Ride-Hailing System (Uber / Lyft)
Real-time geospatial matching. How to index a moving fleet, find nearby drivers in milliseconds, and run a matching algorithm that is correct under heavy concurrency.
Covers: Geospatial indexing, driver location updates, matching, surge pricing, trip state machine, ETA
Ride hailing is the best case study for geospatial systems and for concurrency: two riders must never be matched to the same driver, and 'find drivers near me' must run in milliseconds against a fleet whose positions change every four seconds.
- Scale: 5 M active drivers, 20 M daily rides, peak 500,000 concurrent trips.
- Location updates: 5 M drivers × every 4 s ≈ 1.25 M writes/s. This is the dominant write load in the system.
- Matching: find drivers within a radius and assign one, in under 2 seconds end to end.
- Correctness: a driver may be assigned to exactly one trip. This is a hard constraint, not a best effort.
30-second answer
Use a grid-based spatial index that turns a two-dimensional proximity query into a one-dimensional key lookup. Geohash or Uber's H3 hexagonal system encodes a location into a cell identifier, so 'nearby' becomes 'in this cell or its neighbours' - a handful of key lookups rather than a scan. Keep live positions in memory in Redis rather than a database, because at 1.25 million writes per second the durability of each individual position is worthless: a position four seconds old is already stale, so losing it costs nothing.
| Approach | Query cost | Update cost | Notes |
|---|---|---|---|
| Scan all drivers, compute distance | O(n) - 5 M rows | O(1) | Hopeless at this scale |
| Database spatial index (PostGIS) | O(log n) | Index update per write | Excellent, but not at 1.25 M writes/s |
| Geohash prefix in Redis | O(1) per cell | O(1) | Simple; cells are rectangular and vary with latitude |
| H3 hexagons | O(1) per cell | O(1) | Uniform neighbour distance; Uber's own choice |
| Quadtree | O(log n) | Rebalancing on movement | Adapts to density; awkward with constant movement |
# Write path: 1.25 M/s. In-memory only - durability here is worthless.
def update_location(driver_id, lat, lng):
cell = h3.geo_to_h3(lat, lng, resolution=8) # ~0.7 km² hexagons
old = redis.hget("driver:cell", driver_id)
pipe = redis.pipeline()
if old and old != cell:
pipe.srem(f"cell:{old}", driver_id) # left the old cell
pipe.sadd(f"cell:{cell}", driver_id)
pipe.hset("driver:cell", driver_id, cell)
pipe.hset("driver:pos", driver_id, f"{lat},{lng}")
pipe.expire(f"cell:{cell}", 60) # stale drivers age out
pipe.execute()
# Read path: ring of cells, then exact distance on a small candidate set.
def find_nearby(lat, lng, radius_km=2):
centre = h3.geo_to_h3(lat, lng, resolution=8)
rings = max(1, int(radius_km / 0.7))
cells = h3.k_ring(centre, rings) # centre + surrounding rings
ids = set().union(*(redis.smembers(f"cell:{c}") for c in cells))
out = []
for d in ids: # tens, not millions
dlat, dlng = map(float, redis.hget("driver:pos", d).split(","))
dist = haversine(lat, lng, dlat, dlng)
if dist <= radius_km:
out.append((d, dist))
return sorted(out, key=lambda x: x[1])Say these points
- Grid indexing turns 2D proximity into 1D key lookups.
- H3 hexagons give uniform neighbour distances and cleaner radius queries.
- Live positions in Redis; durability of an individual position is worthless.
- Query the k-ring of cells, then compute exact distance on a small candidate set.
- Persist only trip paths, asynchronously, not every location ping.
Avoid these mistakes
- Scanning all drivers and computing distance.
- Writing every location update to a durable database.
- One grid resolution for both dense city centres and sparse suburbs.
- Forgetting TTLs, so drivers who go offline linger in cells forever.
Expect these follow-ups
- A driver is exactly on a cell boundary. Does your query still find them?
- How would you find drivers along a route rather than within a radius?
- How do you handle a stadium emptying - 50,000 requests from one cell?
30-second answer
Make the assignment an atomic compare-and-set on the driver's state: transition from `available` to `offered` only if the current state is `available`, so exactly one rider wins and the other immediately gets the next-best driver. Never do a read-then-write. Model the trip as an explicit state machine with allowed transitions and enforce them in the database, and give every offer a short expiry so a driver who does not respond within a few seconds releases automatically rather than being stuck.
-- ❌ Read then write: both riders read 'available' and both proceed.
-- SELECT status FROM drivers WHERE id = 42; -- 'available' for both
-- UPDATE drivers SET status = 'offered' WHERE id = 42;
-- ✅ Compare-and-set: exactly one UPDATE affects a row.
UPDATE drivers
SET status = 'offered',
offered_trip = :trip_id,
offer_expires_at = now() + interval '15 seconds'
WHERE id = :driver_id
AND status = 'available'; -- the guard that makes this atomic
-- 0 rows affected => someone else won. Move to the next candidate immediately.The trip state machine
Trip lifecycle
Every transition is guarded and logged. Illegal transitions are rejected by the database, not by application discipline.
Flow
- RequestedOffered
- OfferedAccepted
- OfferedRequested(expired / declined)
- AcceptedIn progress
- In progressCompleted
- RequestedCancelled
- OfferedCancelled
- AcceptedCancelled
Matching is not just 'nearest'
- ETA, not straight-line distance. A driver 500 m away across a river may be twelve minutes out. Use road-network ETA from a routing service.
- Driver acceptance likelihood - offering to a driver who will decline costs 15 seconds of rider wait time.
- Fairness across drivers - always picking the same high-rated drivers starves the rest of the fleet and drives them off the platform.
- Batch matching - instead of assigning greedily on each request, collect requests over a few seconds and solve a global assignment. This measurably reduces total wait time versus first-come-first-served, and is a genuinely differentiating point to raise.
Say these points
- Atomic compare-and-set on driver status; rows-affected decides the winner.
- Explicit trip state machine with database-enforced transitions.
- Offers must expire so an unresponsive driver does not stall the trip.
- Match on ETA and acceptance likelihood, not straight-line distance.
- Batch matching beats greedy assignment on total wait time.
Avoid these mistakes
- Read-then-write for driver assignment.
- A distributed lock where a conditional UPDATE suffices.
- No offer expiry, leaving trips stuck on an unresponsive driver.
- Straight-line distance as the matching metric.
- Surge that oscillates because it is not smoothed.
Expect these follow-ups
- A driver goes offline mid-trip. What happens to the rider?
- How do you compute ETA at 500,000 concurrent trips without hammering a routing service?
- How would you support scheduled rides an hour in advance?
Showing 2 of 2 questions for design-a-ride-hailing-system.
Check your understanding
4 questions · no sign-up, nothing stored
Hands-on challenge
Build it - this is what you talk about in a deep-dive round.
Design the matching service
Handle 1.25 million location updates per second and match riders to drivers in under two seconds, correctly under concurrency.
Requirements
- Choose a spatial index and resolution, and justify both against candidate-set size and boundary crossings.
- Design the location write path and state exactly what is and is not persisted.
- Write the atomic assignment query and prove it is race-free.
- Define the full trip state machine with guards, timeouts and cancellation rules.
- Design surge pricing as a smoothed, capped control loop with price locking at request time.
Stretch goals
- Implement batch matching over a 3-second window and compare wait times against greedy assignment.
- Handle a stadium emptying: 50,000 requests from one cell in 60 seconds.