Uber / Lyft — Match Drivers and Riders

Match a rider to the closest acceptable driver in under 3 s. Geohash, S2, surge.

SavedSaved on this device

The problem

Match a rider to the closest acceptable driver in under 3 s. Geohash, S2, surge.

Build the matching/dispatch core of a ride-hailing marketplace at Uber/Lyft scale. Drivers stream their GPS over a persistent socket; riders tap "request" and expect a driver's phone to ring within ~3 seconds. The system must pick a driver who is geographically close, currently available, likely to accept, and quote a fare with a surge multiplier that's both real-time and stable enough not to flicker between offer and confirm. Out of scope for this canonical: payments, in-trip telemetry, fraud, accounting — this is the matching main flow only.

The interesting pressure is: (a) the geo-index is write-dominant at ~125:1 vs reads — every driver heartbeat is a write, only one rider request consumes ~19 cells of fan-out — flipping every assumption the typical "read-through cache" canonical relies on; (b) demand is violently skewed — a single H3 r9 cell at MSG when a concert lets out can take 100x normal load while everything else is idle; (c) the dispatch path must be sharded by geography, not by tenant, because that's the only way one CPU can hold authoritative in-memory state for a contiguous patch of map.

Reading: H3: Uber's Hexagonal Hierarchical Spatial Index (Uber Eng, 2018) · Scaling Uber's Real-time Market Platform — Matt Ranney, QCon 2015 · Ringpop: Scalable, Fault-tolerant Application-Layer Sharding (Uber Eng, 2016) · Schemaless, Uber's Highly Available Datastore (Uber Eng) · DeepETA: How Uber Predicts Arrival Times (Uber Eng, 2022) · Streaming Lyft Ride Prices on Flink (Flink Forward SF, 2019) · Solving Dispatch in a Ridesharing Problem Space (Lyft Eng) · Real-time Data Infrastructure at Uber (arXiv:2104.00087) · Google SRE Workbook: Managing Cascading Failures

H3 hexagonal hierarchical index
kRing candidate search
geo-sharded dispatch (RingPop / DISCO)
windowed supply/demand surge
offer state machine + idempotency
transactional outbox + CDC relay
write-dominant geo-index
region-pinned active-active

01Clarifications

What would you ask before drawing a single box?

Ambiguity you would resolve with the interviewer: scope, scale, who uses it, what counts as done.

About Uber / Lyft — Match Drivers and Riders

Match a rider to the closest acceptable driver in under 3 s. Geohash, S2, surge.

Difficulty: advanced
Time: about 60 minutes
Stages: 10
Topic: Geospatial & Location Systems

How this problem is worked

Ten stages, from the questions you would ask an interviewer to the trade-offs you would defend. Each asks one question, and the simulator runs the architecture you draw against the requirements you wrote.

01ClarificationsWhat would you ask before drawing a single box?
02Functional reqsWhat must this system actually do?
03Non-functionalWhat must it promise about speed, uptime and correctness?
04Capacity estimationHow much load and data does this have to hold?
05API designWhat does the outside world call, and what comes back?
06Data modelWhat gets stored, and what is it looked up by?
07Use-case breakdownHow does each requirement actually get served?
08High-level designWhich components handle a request, and in what order?
09Deep divesWhich part breaks first, and what do you do about it?
10Trade-offsWhat did this design cost, and what breaks at 10×?

Primary sources for this problem

H3: Uber's Hexagonal Hierarchical Spatial Index (Uber Eng, 2018)
Scaling Uber's Real-time Market Platform — Matt Ranney, QCon 2015
Ringpop: Scalable, Fault-tolerant Application-Layer Sharding (Uber Eng, 2016)
Schemaless, Uber's Highly Available Datastore (Uber Eng)
DeepETA: How Uber Predicts Arrival Times (Uber Eng, 2022)
Streaming Lyft Ride Prices on Flink (Flink Forward SF, 2019)
Solving Dispatch in a Ridesharing Problem Space (Lyft Eng)
Real-time Data Infrastructure at Uber (arXiv:2104.00087)
Google SRE Workbook: Managing Cascading Failures

Build the primitives this design leans on

Each one is an animated curriculum that constructs the system from scratch.

Browse the full problem catalog, or see what the simulator does and does not model.