Back to System design
Design Uber / Ride-Hailing
hardA rider opens the app and wants a car. Somewhere nearby, drivers are moving around. The system has to match them in a few seconds.
Scale10M active drivers; ~100K dispatches/min peak globally
StorageGeo index hot in RAM (cell-sharded); trips in DW for compliance
Key Concepts
1
Most people start with the matching. The matching is the easy half.
2
Where the work actually is. Every driver's phone reports its location every 4 seconds. With 5 million
drivers online, that is 1.25 million location updates per second.
Where the work actually is.1.25 million location updates per second
3
Ride requests, meanwhile, might be 5,000 per second. So location updates outnumber ride requests 250 to 1.
4
This tells you something immediately: locations cannot go into a normal database. Current positions live
in memory, keyed by driver. The history of where a driver has been is written separately, in the
background, because nobody needs last Tuesday's route in under a second.
5
Finding nearby drivers without checking everyone. You cannot measure the distance to 5 million drivers
for every request.
Finding nearby drivers without checking everyone.
6
So divide the map into cells, like a chessboard laid over the city. Each driver is filed under the cell
they are in. A request looks at the rider's cell and the ring of cells around it, which narrows 5 million
drivers down to a few hundred before any distance maths happens.
7
Cell size matters. Too big and you scan thousands of drivers; too small and you read dozens of cells. In a
busy city you want roughly 50 to 100 drivers per cell, which means the right size differs by city.
8
The nearest driver is not the closest one. A driver 200 metres away across a river, or on the wrong
side of a one-way street, may be ten minutes from you. Use the cells to find candidates, then ask a routing
service for driving time, and order by that.
The nearest driver is not the closest one.
9
The bug this question is really about. Two riders request at the same moment and the system offers the
same driver to both. Both riders are told a car is coming. One of them is wrong.
The bug this question is really about.
10
Fix it by making the offer a claim. Change the driver's state from "available" to "offered" in one atomic
step, so only one request can win. The loser looks for the next driver. Add a timeout, so a driver who
never answers goes back to available on their own.
11
Without those timeouts, drivers slowly leak out of the pool: available drivers who are stuck in a state
nobody cleared.
12
Surge pricing is a feedback loop, and loops oscillate. Price rises when demand beats supply, which
attracts drivers, which drops the price, which sends them away. Smooth it over a window, limit how fast it
can change, and lock the price you quoted the rider for the length of the request.
Surge pricing is a feedback loop, and loops oscillate.
13
What the interviewer is probing.
What the interviewer is probing.
14
1. "Design Uber." Probing: whether you find the real load. Stalls: starting with the rides table.
Moves up: 1.25 million location updates per second against 5,000 requests, so locations never touch the
database.
1. "Design Uber."
15
2. "How do you find nearby drivers?" Probing: grid versus checking everyone. Stalls: "Find drivers
within 2 km" — against 5 million rows, per request. Moves up: map cells, read the middle and its
neighbours, size the cells by how dense the city is.
2. "How do you find nearby drivers?"
16
3. "You matched the closest driver. Is that the best one?" Probing: straight line versus roads.
Stalls: "Yes, they are nearest." Moves up: rivers and one-way streets; use driving time to order the
candidates.
3. "You matched the closest driver. Is that the best one?"
17
4. "Two riders request at the same instant." Probing: the correctness bug. Stalls: "The database
handles it." Moves up: an atomic claim on the driver, the loser retries, and a timeout returns
unanswered offers.
4. "Two riders request at the same instant."
18
5. "Surge prices swing wildly." Probing: whether you recognise a feedback loop. Stalls: "Raise the
price when demand is high." Moves up: smoothing, a cap on how fast it moves, and a locked quote.
5. "Surge prices swing wildly."
High-level design
Driver: app → gRPC → location service → geo-sharded Redis (cell → driver list) + presence service.
Rider request: app → API gateway → dispatcher → geo index lookup → ETA scoring → offer service → driver app push.
Trip lifecycle: state machine in trip service (strongly consistent store), persisted on every transition.
Pricing: stream processor on demand/supply events → per-cell multipliers → quote service.
Payments: separate service; trip end triggers idempotent charge.
Analytics + Fraud: async pipelines from event stream.
Components
- Mobile gateway (long-polling or WebSocket for driver, stateless API for rider).
- Location service + geo-sharded Redis (per-cell driver lists).
- Dispatcher service (in-memory state per active request, persists snapshots).
- Pricing/surge stream processor (Flink/Spark Streaming).
- Trip service (Spanner / Vitess / sharded MySQL with sync replication).
- Payments service (separate, idempotent).
- Maps / ETA service (third-party or in-house OSRM/Valhalla).
- Notification service (push to driver app).
Capacity, worked
Drivers online at peak 5,000,000 GPS ping interval 4 seconds Ride requests at peak 5,000 / second --------------------------------------------------------------- Location writes 5M / 4 = 1,250,000 / second Write : request ratio 250 : 1
Location record in memory
driver id 8 B + lat/lon 16 B + heading, speed, ts 16 B
+ cell id 8 B = ~48 bytes
5M drivers x 48 B = 240 MB Historical trail (async, time-series)
1.25M writes/s x 48 B = 60 MB/second
= 5.2 TB/day
At 10:1 compression = 520 GB/day Candidate narrowing per request
Drivers in city 50,000
Target per cell 50-100
Cells read (centre + ring) 7
Candidates examined 350-700
Distance/ETA calls after filtering 10-20Consequences:
- 240 MB of live location fits in memory on one node, replicated. The
database never sees a ping.
- 5.2 TB/day of trail is a cost decision: sample it, compress it, or
expire it. Say which.
- 7 cell reads per request is why the grid exists; 5M distance
calculations per request is why nothing else works.
Dispatch without double-booking
The race
Two riders, same second, same nearby driver. Both matchers read
"available". Both send an offer. Both riders are told a car is coming. Fix 1 -- compare-and-set on the driver record
UPDATE drivers SET state='offered', offer_id=:id
WHERE driver_id=:d AND state='available'
Rows affected = 0 means someone else won; re-query for the next
candidate. One round trip, no locks held across a network call. Fix 2 -- short lease
Matcher takes a 10-second lease on the driver before offering. Lease
expiry returns the driver automatically, so a crashed matcher cannot
strand supply. The state machine, with timeouts
offline -> available driver goes online
available -> offered dispatch claims (CAS or lease)
offered -> assigned driver accepts
offered -> available driver declines, or 15s timeout
assigned -> on_trip pickup confirmed
assigned -> available rider cancels
on_trip -> available drop-offEvery transition out of `offered` and `assigned` needs a timeout. Without them, unanswered offers leak supply out of the pool one driver at a time.
Failure modes in production
GPS drift in dense areas
Symptom: drivers appear to jump between cells; matches look wrong.
Cause: multipath reflection between tall buildings.
Fix: smooth the track (map-match to roads), and require two consistent
readings before moving a driver across a cell boundary.
Cell hotspot at an airport or stadium
Symptom: one cell holds thousands of drivers; lookups slow down.
Cause: fixed cell size meeting non-uniform supply.
Fix: subdivide dense cells (H3 supports resolution changes), or cap
candidates and sort by ETA within the cap. Stranded supply
Symptom: available driver count falls through the evening without
drivers going offline.
Cause: offers with no timeout leaving drivers in `offered` forever.
Fix: timeouts on every non-terminal state, plus a sweeper that audits
for drivers whose state has not changed in an hour. Trail write backpressure
Symptom: location ingestion lags; live positions go stale.
Cause: the historical write path sharing a queue with live updates.
Fix: separate them. Live location is a memory overwrite; the trail is
a lossy sampled stream that is allowed to drop under pressure.