Case study: Uber (ride matching)
Design real-time ride matching: an in-memory H3 cell index for 250k location pings/s, atomic conditional claims so no driver is double-booked, and city-scoped failover.
35 min9 steps
By the end you can
- Estimate location ping rate, in-memory supply index size and ride-matching request rate
- Index moving drivers with H3 hexagonal cells in memory rather than a disk-backed relational database
- Prevent double assignment under contention using atomic conditional updates and leases
- Predict how the system behaves during a downtown surge, a ping storm or a dispatch database failover
Requirements
Request, assign, track trips
- Nearby drivers; exactly one assignment; city outage isolation
Matching ~1s
- GPS pings loss-tolerant; never two concurrent trips/driver
Estimates
Location writes/s
250k
1M drivers / 4s
Location ingress
~75 MB/s
~100 B payload + headers
Supply memory
400 MB
1M / 200 B / 2 replicas
Peak rides/s
~700
20M/day / 3 / 86,400
Search neighbourhood
~2 km
H3 cell + covering rings; tens/hundreds of candidates
API
POST /v1/drivers/{id}/location
- lat/lng, heading, ts; discard stale pings
POST /v1/rides; POST /v1/trips/{id}/complete
- Idempotency-Key; claim conflict 409; completion restores availability
Data model
Ephemeral geo
- driverId, H3 cell, lat/lng, updatedAt; R=1/W=1, two replicas
Authoritative dispatchdb
- driverId, available, tripId; conditional claims; semi-sync replication + fencing
High-level design
Order the steps when a rider requests a ride.
- 1Once a claim succeeds, the trip is recorded and returned to the rider and driver
- 2The dispatch server executes an atomic conditional update (available 1 → 0) on the top candidate in the dispatch database
- 3The dispatch server maps the pickup lat/lng to an H3 cell and queries the in-memory location index for that cell and its neighbours
- 4If another request claimed that driver first (409), the server moves to the next candidate in its ranked list
- 5The dispatch server filters free candidates and ranks them by road-network ETA
Deep dive: atomic claims, leases and city failover
Claim + lease
- Atomic available=1 / 0; unanswered offer expires; fence stale responses
City matching
- Greedy or 1-2s batch optimisation; city failure domains; rebuild geo from pings
Alternatives
uber-unsafe-claim
- Read-then-write double-books hot drivers
SQL locations
- Durable; ping writes starve trip transactions
Quadtree
- Adaptive density; moving-car rebalancing complicates sharding
Failure scenarios you can run
Inject
Hot driver: 20%
Observe
Exactly one claim succeeds
Result
409 contenders try next candidate
Inject
Ping storm: 3x fixture
Observe
Geo ring absorbs writes
Result
Matching latency barely changes
Inject
Dispatch leader failure: ~0.5s
Observe
Pings continue; claims/completions pause
Result
Semi-sync + fencing; no confirmed trip loss
Wrap up
Watch
- Matching p99, 409 conflicts, supply staleness
Separate
- High-rate ephemeral coordinates; lower-rate authoritative claims; city shards
Score yourself from 1 to 4 against the rubric.
Answer this step to continue.