Part 5 of 8 · 2 min read
Matching
One driver, one trip.
Ranking. Candidates are ranked by estimated pickup time (from the ETA service), not straight-line distance, since a driver across a river may be slow to reach. Other inputs: rating, vehicle type, driver acceptance rate, and fairness (a driver who has waited longest).
Offer sequence. Offer to one driver at a time with a time limit (say 15 seconds). If declined or expired, offer to the next. Or offer to a few at once and take the first accept, which is faster but wastes more driver attention. Batching is another approach: collect requests and drivers in a window of a few seconds and solve the assignment of the whole group together, which gives better overall pickup times.
Exclusive assignment. The danger is two requests choosing the same driver at the same time, or one driver accepting two offers. Treat the driver's availability as a lock (page 6):
- Before offering, the dispatch service marks the driver as RESERVED for this trip with a short lease (for example 20 seconds), using a compare-and-set on the driver's state: only AVAILABLE can become RESERVED.
- If the compare-and-set fails, the driver is taken, and dispatch picks the next candidate.
- On accept, the driver becomes ON_TRIP. On decline or timeout, the lease expires and the driver returns to AVAILABLE.
Store driver state in a store that supports an atomic compare-and-set (a replicated key-value store or the coordination service). The trip also needs a single owner: use one dispatch worker per region or per trip id, so that two workers do not run the same request.
Idempotency. Rider apps retry on a bad network. A request carries a request id generated by the app. The trip service creates a trip once per id and returns the existing trip for a repeat (Level 1 idempotency).
A worked example (made up). Requests R1 and R2 arrive in the same millisecond and both pick driver D as the best. R1 does compare-and-set (D: AVAILABLE to RESERVED) and wins. R2's compare-and-set fails, so R2 picks driver E. D gets exactly one offer.
Common mistake
Reading the driver's state, deciding, then writing it. Two dispatchers can read AVAILABLE at the same time. The check and the change must be one atomic step.
Check yourself: 1. Why rank by pickup time and not distance? 2. How does compare-and-set stop a double offer? 3. What does the request id protect against?