The matching engine: clearing the market
- Design dispatch: candidate search, ranking, sequential offers, and the accept race.
- Guarantee the exchange's two invariants: one driver per trip, one trip per driver.
This lesson composes three schemas you already hold: the geo index ring query (1.4) finds candidates, the Geo facade (1.3) refines their ETAs, and the persisted quote (1.5) anchors the price. Matching adds only one new idea: the offer protocol.
This is the heart of the exchange. When a request arrives, the matcher queries the geo index for candidate drivers (ring-expanding from the pickup cell), filters them (right tier, not already offered this trip, acceptable rating), ranks them — v1 ranking is simply refined ETA to pickup — and then runs the offer protocol: offer the trip to the best driver with a 12-second countdown; on decline or timeout, advance to the next. Sequential offers keep v1 simple and fair; broadcast offers ("first tap wins") create races and driver resentment, and we note them only as a contrast.
The invariant that makes this an exchange and not a suggestion box: a driver holds at most one active trip, and a trip has at most one driver. We enforce it where it can't be raced — a conditional, transactional assignment in the database at accept time. The offer itself is optimistic; the accept is authoritative.
flowchart TB
REQ["Ride request + quote id"] --> M["Matching service"]
M --> RD[("Redis geo index — ring query: candidates in expanding cells")]
M --> F["Filter — tier, no repeat offer, driver eligible"]
F --> RANK["Rank by refined ETA to pickup — Geo facade"]
RANK --> OFF["Offer protocol — sequential, 12 s each"]
OFF --> DA["🚗 Driver app — push + WebSocket offer"]
DA -- "accept" --> CAS["Transactional assign — driver free AND trip unassigned"]
CAS -- "success" --> TRIP["Trip service — trip Assigned (1.7)"]
CAS -- "lost race" --> OFF
DA -- "decline / 12 s timeout" --> OFF
OFF -- "candidates exhausted" --> EXP["Widen search or fail request gracefully"]
Worked example: request to assignment
sequenceDiagram
autonumber
participant R as Rider app
participant M as Matching service
participant RD as Geo index
participant D1 as Driver A
participant D2 as Driver B
participant T as Trip service
R->>M: request ride {quote id}
M->>M: validate quote — unexpired, unused
M->>RD: candidates near pickup cell
RD-->>M: drivers A, B, C with positions
M->>D1: offer {pickup, fare, 12 s countdown}
D1-->>M: decline
M->>D2: offer
Note over D2: 12 s pass — no response
M->>M: timeout, mark B unresponsive
M->>D2: offer expired (revoke)
M->>RD: re-query — driver D now closer
M->>D2: skipped
M->>D1: skipped
M->>T: driver D accepted — conditional assign OK
T-->>R: driver assigned {driver, car, plate, ETA 4 min}
The classic race: driver accepts at the same instant the offer times out and moves on, and two drivers head to one rider. The revoke message is best-effort; the conditional assignment is the truth. A late accept must fail cleanly at the transaction and tell the driver "already taken" — annoying, but consistent. Never resolve the race in the matcher's memory; memory is exactly what a crash erases.
Real ranking blends ETA with driver earnings fairness, acceptance history, and batch optimization (matching several requests and drivers jointly). Pooled rides make it a windowed assignment problem. We defer all of it — the offer protocol and invariants don't change, and they are today's load.