System 12.15 — Uber (Location-based Matching)
In one line
The geospatial problem: driver discovery, live positions, matching, pink dot metaphor — and the map is the app.
Think of it like this
Figuring out, in under a second, which of the thousands of nearby drivers should get matched to your ride request — a giant, constantly-updating game of 'find the closest available person on a map.'
Key ideas
- 01
Two data planes: transactional (rides, fares, payments — classic DB) and realtime geo (driver positions, availability).
- 02
Geo store: grid/hash-based index (H3, geohash) or a geo DB (PostGIS, MongoDB geo, Redis GEO) sharded by region.
- 03
Matching: rider request → find nearby available drivers (geo query <= 5km) → push offers → first-accept wins (atomic claim!).
- 04
Driver position pipeline: drivers heartbeat GPS every 3–5s → Kafka → update geo index → enables ETA + availability.
- 05
ETA: distance/speed over road graph (routing service) — separate from matching; ETA shown before match.
- 06
Surge pricing: demand/supply ratio per region → multiplier policy — the dynamic pricing strategy (with caps).
- 07
Trip lifecycle state machine: REQUESTED → MATCHED → EN_ROUTE → ON_TRIP → COMPLETED (+ cancel/auto-expiry timers).
- 08
Consistency: fresh positions are eventual (3s lag fine); the ride assignment MUST be atomic (one driver, one ride).
- 09
Failures: driver app offline → position TTL expiry → removed from matching; matching retry on dead offer.
Java / Spring map
- →
Geo index with Redis GEO / PostGIS; Kafka for position stream; a matching service; ride state machine.
Code & diagrams
The atomic one-driver claim — the heart of matching.
Rider requests → (riderId, lat, lng, radius)
│
▼
geoIndex.nearestAvailableDrivers(lat, lng, 5km) → [d3, d7, d12] (fresh positions)
│
▼
offer-push d3, d7, d12 (each with 15s accept window)
│
▼
d7 accepts → rideMatch.claim(d7, rideId) // atomic!
│
▼
Redis SETNX "match:d7" → success ⇒ booked, notify d3/d12 (offers cancelled)
Concurrent accept by d5+d7 for the SAME ride ⇒ ONE SETNX wins
Guarantee: a driver can accept exactly one ride at a time — same
one-writer claim as parking spots and seats, at fleet scale.Explain without notes
Why is 'nearest driver' computed on a 3s-old position acceptable? What breaks if positions are 5 minutes old?
Practice
Design the position TTL and the driver-availability lifecycle (online→matched→on-trip→offline).
Trade-offs
- ↔
Geo index memory vs precision; per-region sharding moves hot zones (airport hits) into managed cells.
Completion checklist
I can present geo index + position stream + atomic matching + ETA + surge as a coherent system.