Uber Rider/Driver Matcher

What is being asked

Design the matching service of a ride app. Given a rider's location, find suitable nearby drivers, pick one, offer the trip, and handle acceptance, refusal and timeouts.

Requirements

Functional

• Find available drivers near a point; rank them.
• Offer to one driver at a time, or to a few; fall back when refused.
• Lock a driver while an offer is pending.

Non-functional

• Match within a few seconds.
• A driver gets one offer at a time and one trip at a time.
• Works city by city, with wide differences in density.

Design

1. Drivers' current positions are kept in a spatial index of cells (geohash, quad-tree or hexagons).
2. For a request, the matcher takes drivers from the rider's cell and neighbouring cells, widening the ring until it has enough candidates.
3. It ranks candidates by estimated pick-up time on the road network, not straight-line distance.
4. It atomically marks the chosen driver as offered with an expiry, then sends the offer. Acceptance creates the trip; refusal or timeout releases the driver and tries the next.

Key decisions and trade-offs

• Greedy or batched matching. Giving each request its nearest driver immediately is simple. Collecting requests for a couple of seconds and solving the assignment together gives lower total waiting in busy areas.
• Quad-tree or fixed cells. A quad-tree adapts to density with deeper subdivision downtown; fixed geohash or hexagon cells are simpler to shard and update.
• The driver lock is what prevents double assignment. It must be an atomic conditional write with a time limit, so a crashed matcher cannot strand a driver.
• Shard by city. Matches never cross cities, so each shard holds a complete, small problem.

Follow-up questions

• How would you match a driver who is about to finish a trip nearby?
• How do you keep offers fair between drivers?
• What happens when the rider cancels while an offer is out?
• How would you support shared rides with two pick-ups?