Design a Ride Matching Service

Prompt

"Design the part of a ride-hailing service that tracks driver locations and matches a rider's request to a nearby driver. Assume a large city and many cities."

Clarifying questions

• How often do drivers report location? Every few seconds while online. Riders report once per request and then during the trip.
• What does 'match' mean? Find candidate drivers near the pickup, rank them by estimated arrival time, offer the ride to one, and if they decline within a timeout, offer to the next.
• Can a driver be matched to two riders at once? No. That is the correctness requirement.
• Latency expectations? A rider should see "driver found" within a few seconds; the candidate search itself should take well under 100 ms.
• Do we need ETA from a real routing engine? Assume a routing service exists with a bounded latency we can call for the top few candidates; the coarse filter can use straight-line distance.
• Cities are independent? Yes. A ride never crosses a city boundary for matching purposes; cities are natural shards.
• Surge pricing, ratings, pooling? Out of scope unless time permits; pooling is a follow-up.

Requirements

Functional

• Ingest driver location updates and maintain "current position and status" per driver.
• Given a pickup point, return the N nearest available drivers within a radius.
• Run an offer loop that assigns exactly one driver to one ride.
• Track trip state from request through completion.

Non-functional

• Location update ingest at high write rate with per-driver last-write-wins semantics.
• Nearest-driver query p99 under 100 ms.
• No double assignment, even with concurrent requests in the same area.
• Availability per city: a city's matching should not depend on other cities.

Back-of-envelope

• Assume 5 million drivers online at global peak, reporting every 4 s: 1.25 million location writes/s. Each update is ~100 bytes: 125 MB/s ingest. This is the dominant load and it is write-heavy.
• Ride requests: 30 million rides/day globally; peak hour holds ~10%, so ~830 requests/s at peak. Each request triggers one spatial query, a handful of ETA calls, and a few offer messages. Matching load is small compared to location ingest.
• Location state: 5 M drivers x ~200 bytes (id, lat, lng, heading, status, timestamp, cell) = 1 GB. Fits in memory on a handful of machines; per city it is megabytes.
• Location history for analytics: 1.25 M/s x 100 B x 86,400 = ~10 TB/day raw; keep a downsampled version (one point per 30 s) for ~1.3 TB/day, ~475 TB/year. Cold storage, not on the matching path.
• Spatial query fan-out: a 3 km search radius in a dense city at cell size ~500 m touches ~100 cells; each cell in a dense area holds tens of drivers, so a query scans a few thousand candidates and returns the nearest 10-20. Cheap if the index is in memory.