skip to content

In a ride-hailing dispatch system with several concurrent matchers, how do you guarantee a driver is never assigned to two riders at once?

level: seniorimportance: must knowfreq 68%

answer

  1. check-then-act race
  2. authoritative state, not the index
  3. compare-and-set on status
  4. offers expire after a hold
  5. accept checks the same offer id

basics

~20 s

Keep each driver's dispatch state in an authoritative store and move it from available to offered with a conditional write that only one matcher can win. Offers expire, and accepting is another conditional write checked against the offer id.

solid answer

~40 s

Reading "available" from the geo index and then assigning is a **check-then-act race**: two matchers can both see the driver as free. The fix is an **authoritative driver-state record**, separate from the ephemeral index, updated with a **conditional write** (compare-and-set): set `status = OFFERED, offerId = X` *only if* `status = AVAILABLE`. Exactly one matcher succeeds; the others move to their next candidate. The offer carries an **expiry**, a time-limited hold, so an unanswered offer returns the driver to available. **Accept** is also conditional: it succeeds only if the driver is still `OFFERED` with the same `offerId` and the hold has not expired, and the ride itself moves from searching to assigned with its own conditional write. Accepts are **idempotent** by offer id, so retries are safe.

code

sql · 9 lines
sql
UPDATE driver_dispatch_state
SET status = 'OFFERED',
    offer_id = :offer_id,
    ride_id = :ride_id,
    offer_expires_at = CURRENT_TIMESTAMP + INTERVAL '15' SECOND
WHERE driver_id = :driver_id
  AND status = 'AVAILABLE';
-- 1 row updated: this matcher won the driver
-- 0 rows updated: someone else did; try the next candidate

go deeper

for a junior

Recall that two processes reading the same free driver can both assign them, and that the fix is a write that succeeds only if the driver is still free.

for a middle

Walk through the driver state machine and show which condition each transition checks, including the offer expiry.

for a senior

Show the failure cases: a matcher crashing after claiming, retried accepts, several drivers offered one ride, and why the fast index is never the guard.

for a principal

Weigh offering one driver at a time against parallel offers, and explain why regional ownership reduces contention but cannot replace the conditional write.

## The race In a **ride-hailing dispatch system**, several **matchers** run concurrently: different processes, regions or threads, each handling incoming ride requests. Each one queries the in-memory geo index for nearby available drivers, picks the best, and sends that driver an offer. The geo index is fast but **eventually consistent**: it reflects the last ping, not the latest dispatch decision. So this sequence is possible: 1. Matcher 1 reads driver D as available. 2. Matcher 2 reads driver D as available. 3. Both send D an offer, and D ends up with two riders, or accepts one while the other rider waits for a driver who is never coming. This is the classic **check-then-act** race: the check (is D free?) and the act (assign D) are not atomic. ## Guard 1: a conditional claim The cure is to make the claim itself atomic. Keep each driver's **dispatch state** in an authoritative store that supports **conditional writes** (compare-and-set on a field or a version number), and never trust the geo index's copy of the status for the final decision. - `AVAILABLE -> OFFERED` succeeds **only if** the current status is still `AVAILABLE`. - The winning write records `offerId`, `rideId` and `offerExpiresAt`. - A losing matcher gets a failed condition, not an error, and simply tries its next candidate. ## Guard 2: the offer expires An offer is a **time-limited hold** on the driver, in effect a lease used as a tool. Without an expiry, a driver whose phone died mid-offer would be stuck in `OFFERED` forever. With it: - if the driver does not answer by `offerExpiresAt` (for example 15 seconds), a sweeper or the next reader reverts `OFFERED -> AVAILABLE`, **conditional on the same offerId**, so it cannot undo a newer offer; - expiry is judged against **one clock**, the store's or the dispatch service's, not the phone's. The deeper theory of leases (clock skew, paused processes, fencing tokens) belongs to leader-election material; here the hold only needs to be conditional and bounded. ## Guard 3: accept is conditional too The driver's accept must prove it answers **the current offer**: ```pseudocode function accept(driverId, offerId): d = driverState.read(driverId) if d.status == ASSIGNED and d.offerId == offerId: return ALREADY_ACCEPTED # idempotent retry ok = driverState.conditionalUpdate(driverId, condition: status == OFFERED and offerId == offerId and serverNow() < offerExpiresAt, set: status = ASSIGNED) if not ok: return OFFER_NO_LONGER_VALID rideOk = rides.conditionalUpdate(d.rideId, condition: status == SEARCHING, set: status = ASSIGNED, driverId = driverId) if not rideOk: driverState.conditionalUpdate(driverId, condition: status == ASSIGNED and offerId == offerId, set: status = AVAILABLE) return RIDE_ALREADY_TAKEN return ACCEPTED ``` The second conditional write guards the **rider side**: if a ride was offered to several drivers at once (first accept wins), only one accept can move the ride out of `SEARCHING`; the others release their driver. ## The state machine | From | Event | To | Condition | |---|---|---|---| | AVAILABLE | matcher claims | OFFERED | status is AVAILABLE | | OFFERED | driver accepts | ASSIGNED | same offerId, not expired | | OFFERED | declines or times out | AVAILABLE | same offerId | | ASSIGNED | trip ends or is cancelled | AVAILABLE | same trip | Every transition is a conditional write, so any interleaving of matchers, retries and sweepers leaves the driver in exactly one state. ## Design choices around the guard - **Offer one driver at a time per ride** (simpler, slower) or **several at once** (faster, but needs the ride-side guard and creates declined offers). - **One matcher per region** reduces contention, but failover can still briefly run two, so the conditional write stays. - **Update the geo index** after a successful claim so other matchers stop picking that driver, as an optimisation, not as the guard. - **Idempotency** by `offerId` makes retried accepts and repeated timeout sweeps harmless. The principle: the fast index proposes candidates; only the conditional write in the authoritative store decides. ## How to test it 1. Run two matchers against the same driver in a loop and assert that exactly one claim succeeds each time. 2. Kill a matcher between claim and offer and assert that the driver returns to available after the hold. 3. Replay an accept twice and assert that the second call reports the existing assignment.

  • Why not just lock the driver record while a matcher decides?
    A lock held across ranking, ETA calls and the driver's response would block other matchers for seconds and needs its own timeout if the holder crashes. A conditional write takes the claim in one short atomic step, and the offer expiry plays the role of a bounded hold, so nothing waits on a stuck process.
  • A matcher's claim succeeds but it crashes before sending the offer. What happens to the driver?
    The driver sits in OFFERED with an offer they never received. Because the offer carries an expiry, the timeout sweep reverts the driver to AVAILABLE, conditional on the same offer id, after the hold ends. The cost is a driver idle for up to one hold period, which is why holds are kept short.
  • If a single matcher owns each region, is the conditional write still needed?
    Yes. During a failover or a slow handoff, an old and a new matcher can briefly both act for the same region, and a driver near a region edge can be seen by two matchers. The conditional write makes the claim safe regardless of how many matchers exist, so ownership reduces contention but is not the guarantee.

saying these in an interview costs you the question

  • Checking the geo index status right before assigning is enough to avoid conflicts.
  • Running a single matcher per region makes double assignment impossible.
  • An offer can hold a driver until they answer, however long that takes.
  • A retried accept should create a new assignment.
  • The driver's phone clock should decide whether an offer has expired.