Module 12 · Lesson 08
Design a ride-hailing matcher
Find nearby drivers, pick one, and never assign the same driver twice.
What you will be able to do
- Index moving drivers so nearby queries stay cheap
- Update locations without thrashing the index
- Assign a driver atomically across concurrent requests
- Model trip state transitions and failures
Requirements and estimates
- Functional: rider requests a trip, system returns a driver and ETA, updates location during the trip, completes or cancels.
- Non-functional: match under 5 s, no double assignment, location freshness under 10 s.
- Scale: 1M active drivers, 10M rides/day, location update every 4 s per driver.
location writes: 1M drivers / 4 s = 250k updates/s ride requests: 10M/day = ~115/s avg, 1,000/s peak nearby query: ~2 km radius, 10-50 candidate drivers geohash-6 cell ~1.2 km x 0.6 km => query 3x3 cells
The update rate is the design driver. Two hundred and fifty thousand location writes per second cannot go to a relational database as row updates. They go into an in-memory geospatial index per region, with periodic snapshots for recovery.
Geospatial index
| Choice | Cell size | Notes |
|---|---|---|
| Geohash-5 | ~4.9 km | Fewer cells, more candidates |
| Geohash-6 | ~1.2 km | Common starting point for city matching |
| Geohash-7 | ~150 m | Dense cities, many cells to scan |
| S2 / H3 | Configurable | Better neighbours, hexagons for even distance |
Partition by region
Each city or metro has its own matcher, so load and failure are isolated.
Index driver location
In-memory map from cell to driver ids, plus a driver record with status.
Query neighbouring cells
Rider's cell plus adjacent cells, filter by status and distance, rank by ETA.
Claim atomically
Conditional update from AVAILABLE to RESERVED on the winning driver; only one request succeeds.
The double-assignment race
Two riders query nearby at the same moment, both see driver 42 available, both send an offer. Without an atomic claim, both get a confirmation. The fix is a compare-and-set on driver status with a short reservation TTL.
Trip state machine
- REQUESTED → MATCHED: offer sent with a 15-second acceptance window.
- MATCHED → ARRIVING → IN_PROGRESS → COMPLETED: driver and rider see the same state, sourced from the trip record.
- MATCHED → REQUESTED: driver declines or times out; release the driver and try the next candidate.
- Any → CANCELLED: record who cancelled and why; pricing and refunds depend on it.
- Location during trip: high-frequency, low durability — stream to a time-series store, keep only the last position in the fast store.
What to emphasise
"Drivers are indexed in memory per city with geohash-6 cells, updated every few seconds and snapshotted for recovery. Matching scans neighbouring cells, ranks by ETA, and claims the driver with a conditional status update so concurrent riders cannot both win."
Worth remembering
- Geohash prefix length sets cell size, and cell size trades query radius against candidate volume.
- Locations change constantly; in-memory geospatial indexes with periodic persistence beat database writes per update.
- Assignment must be an atomic claim — a conditional update on driver status — or two riders get one driver.
- Every trip needs explicit states and a timeout for each, because the real world fails halfway.
Checkpoint
Answer all 3 questions to finish the lesson.
1. Why is a per-update database write a poor design for driver locations?
Location updates are high frequency and short-lived. An in-memory index with snapshots handles the rate and tolerates losing a few seconds.
2. What prevents two riders from being assigned the same driver?
Only one compare-and-set can move the driver from AVAILABLE to RESERVED. The loser retries with another candidate.
3. What does a smaller geohash cell change?
Smaller cells sharpen locality, so more cells must be scanned while each returns fewer drivers — a trade-off against candidate filtering.