Design Uber: fare, request, match, accept
"A ride request is a short multi-step process with a human in the loop: price it, persist it, find nearby available drivers from a live location index, offer it to one driver at a time with a timeout, and never let a driver hold two offers. Matching has to stay one offer per driver and one driver per ride under retries, crashes and timeouts."
Understanding the problem
5 minFunctional Requirements
- A rider enters pickup and destination and gets a fare estimate.
- A rider requests a ride against that estimate.
- The request is matched to a nearby, available driver.
- The driver accepts or declines, then navigates to pickup and drop-off.
Below the line (out of scope):
- Ratings both ways, scheduled rides, and ride categories (X, XL, Comfort).
- Privacy and GDPR, general redundancy, monitoring, CI/CD.
Non-Functional Requirements
- Location writes: 10M drivers / 5 s = 2M writes a second, which is a ceiling because 10M counts registered drivers, not online ones.
- 10M is closer to all registered drivers than to drivers online at once.
- At that rate a disk database is the wrong tool, and the bill proves it.
- DynamoDB on-demand, about 100 B per ping, 1 write unit each: 2M × 86,400 s = 172.8B writes a day.
- × $0.625 per million = about $108K a day, about $39M a year.
- That buys durability for a value overwritten 5 s later.
- Offer window: the driver sees a 10 s countdown and the server waits 12 s, so the minute buys at most 5 offers.
- 60 s / 12 s = 5 sequential offers, fewer if the request waits before its first offer.
- The geo index is small but write-bound: one node cannot absorb 2M writes a second.
- 10M × about 100 B = about 1 GB, so memory is fine.
- One node takes about 100k to 200k writes/s, so 2M/s needs 10 to 20 nodes.
- Match fast: under 1 minute to a match or a clear failure.
- Strong consistency in matching: no driver on two rides, one offer per driver at a time.
- A ride is offered to one driver at a time.
- Survive spikes: a burst of about 100k requests from one area (a stadium emptying).
Entities + API
5 minDefining the Core Entities
- Rider: identity, contact, payment methods.
- Driver: identity, vehicle, availability status.
- The accept flips
available→on_trip.
- The accept flips
- Fare: pickup, destination, price, ETA,
riderId,expiresAt.- Pins the quoted price before the rider commits; expires because surge moves.
- Ride: rider, driver, fare, status,
offered_driver,attempt, route, final fare, pickup and drop-off times.offered_driverandattemptname the current offer.
- Location: the driver's latest lat/long plus the time of that update. Only the latest matters.
API or System Interface
POST /fare // { pickupLocation, destination } -> Fare
POST /rides // { fareId } -> Ride { status: "requested" }, starts matching
POST /drivers/location // { lat, long }, driver id from the session / JWT
PATCH /rides/:rideId // { accept | deny } -> Ride, with pickup + destination
POST /fareis a POST because it creates a Fare row, and that row pins the quoted price.POST /ridestakes only thefareIdand dedupes on it.- The server checks the Fare's
riderIdandexpiresAt, so a double tap or a retry creates one ride. - Price, rider id and timestamps come from the server.
- The server checks the Fare's
- The driver id on a location ping comes from the session or JWT, never the body.
- The accept returns pickup and destination for navigation.
- Never trust client-sent user ids, timestamps or prices.
High-level design
10 min, end to end, no dives yet1) Fare estimate
- Rider client → API gateway → Ride Service. The gateway does auth and rate limiting.
- The Ride Service asks a third-party mapping API for distance and time, then prices the trip.
- It stores the Fare because it is the quote the rider requests against: a fixed price that expires.
2) Request a ride
POST /rides {fareId}reaches the Ride Service, which writes a Ride row linked to the Fare with statusrequested.- Then it kicks off matching and returns the Ride to the rider.
- Persist before matching, so a crash does not lose the ride.
3) Match to a nearby driver
- Driver clients stream locations to a Location Service, which keeps the latest position per driver.
- The Ride Matching Service queries for the closest available drivers and ranks them.
- A geo search returns every online driver in the radius, busy or not, so the matcher drops drivers whose status is not available before ranking.
- The ranked list is the offer order. With at most 5 offers in the minute, the top of it has to be good.
- The location store takes up to 2M writes a second and must answer "nearest" fast, so it is a store with a spatial index, not the main database; the location-storage dive picks the store.
4) Offer, accept or decline
- Per offer, the Ride Matching Service records the offer on the Ride, then pushes it.
- Record:
offered_driver= the driver,attempt+ 1. - Push: through a Notification Service (APNs / FCM).
- Record:
- The driver's
PATCHaccept is one transaction in the Ride Service: Riderequested→accepted, Driveravailable→on_trip. - A decline or no answer in 12 s offers the ride to the next driver in the ranked list.
- When the ranked list runs out, the ride fails "no driver".
- Two matchers can pick the same driver at once; the dive on one offer per driver handles it.
- An accept can arrive after the offer moved on, and a crashed matcher loses its 12 s wait; the dive on drivers who never answer handles both.
Potential deep dives
~20 min, interviewer steers1) 2M location writes a second: where do they go, and how do you search them?
- Write each ping as a row and search with a lat/long range.
- B-tree indexes do not answer 2D "nearest" queries.
- 2M writes a second sinks the database.
- Batch pings over a short interval into a geospatial database (a quad-tree style index, or PostGIS).
- Proximity search works, but the batch delay makes positions stale.
- Redis stores each driver in a sorted set with the geohash as a 52-bit score. GEOSEARCH answers "drivers within r of this point".
- Each GEOADD overwrites the driver's last position. There is no history to store.
- Stale drivers leave through a last-seen sorted set and a sweeper that removes anyone silent for 30 s.
- Last-seen is scored by update time, written in the same pipeline as the GEOADD.
- The sweeper runs every few seconds and ZREMs from both (a geo set is a sorted set; no GEOREM).
- Not a TTL: Redis TTL works on whole keys, and the geo set is one key.
- The search reads available drivers only.
- Keep a separate geo set of available drivers: ZREM on offer or trip, GEOADD when free.
- Or over-fetch with COUNT and drop drivers who hold a pending offer or are not available.
- Durability is a small concern: an emptied index refills within one maximum ping interval, 15 s.
- Persistence (RDB/AOF) or Sentinel failover covers the common case.
2) Too many location updates: how do you send fewer?
- Every online driver sends a ping every 5 s, moving or parked.
- That is the full 2M writes a second.
- A parked driver's pings carry no new position and still drain the battery.
- Raise the ping interval for every driver.
- Writes and battery use drop in proportion.
- Positions go stale for fast, turning, or near-a-pending-request drivers, the ones a match depends on.
- Stationary or slow drivers report less often than the 5 s default.
- Fast, turning, or near-a-pending-request drivers report more often, because those are the positions a match depends on.
- The interval is capped at 15 s for any online driver, so the 30 s sweeper never drops a parked one.
- The cap also bounds recovery: an emptied index refills within 15 s.
- Each ping is a GEOADD plus a ZADD on the last-seen set, in one pipeline.
3) How do you keep one offer per driver at a time?
- This is the strong-consistency requirement from step 1.
- Same shape as Ticketmaster's seat hold: reserve briefly, release on timeout.
- Each matcher instance keeps a set of "locked" drivers and a timer per offer.
- No coordination between instances, so two matchers offer the same driver.
- A crashed instance leaves the lock forever.
- Set
outstanding_requeston the driver row when offering; clear it on answer or timeout.- Every matcher reads the same row, so coordination is solved.
- The timer dies with the process, so a cron sweep has to clear stuck locks.
- Lock the driver for 12 s:
SET lock:driver:{id} {rideId:attempt} NX PX 12000. One matcher wins; the loser moves to its next candidate. - The lock expires by itself if the driver never answers, so there is no sweep and no stuck driver.
- Release with a compare-and-delete (a Lua script) on the value, otherwise a matcher deletes a lock that expired and another matcher re-acquired.
- 12 s is a grace period over the driver's 10 s countdown, so an accept tapped at 9.9 s lands inside the lock.
- The lock only stops double offers; an accept commits only if the ride is still offered to this driver and the driver is still available. That conditional write, which also checks attempt n, makes the assignment exact.
- A Redis failover with async replication can lose a lock: at worst a double offer.
- The accept is one transaction of two conditional writes in the Ride Service:
- Ride
requested→acceptedonly ifoffered_driver = me AND attempt = n: stops a late accept on a ride that moved on. - Driver
available→on_triponly if still available: stops one driver landing two rides.
- Ride
- Cost: the design depends on the lock store's availability. Acceptable, because locks live seconds.
4) How do you avoid dropping requests at peak?
- The Ride Service calls a matcher directly for every request.
- Spikes overwhelm the matchers.
- A crashed matcher loses the requests it held.
- Requests land in a queue, matchers scale on its depth, and a matcher commits the offset once the ride is matched.
- A crash before the commit leaves the request for another consumer, so nothing is lost.
- Kafka commits a contiguous prefix per partition and a match takes up to 60 s, so the partition stalls behind its slowest ride.
- Requests land in a queue, and matchers scale on its depth. A burst becomes a backlog, not an outage.
- Partition by region, so a stadium in one city does not slow matching in another.
- Commit the offset once the request is handed to the durable workflow (the dive on drivers who never answer).
- A crash before the handoff leaves it uncommitted, so another consumer picks it up.
- Not after the match: Kafka commits a contiguous prefix per partition, and a match takes up to 60 s, so the partition stalls behind its slowest ride.
- The handoff is idempotent on
rideId, so a redelivered ride that is already matching or matched is skipped. - Two costs: running the queue (use a managed one), and head-of-line blocking in a FIFO, which a priority queue addresses.
5) What happens when a driver never answers?
- Matching has a human in the loop: offer, wait, then accept, decline or silence.
- Whatever owns the 12 s wait has to survive a crash, or the ride sits in
requestedforever.
- The matcher waits 12 s per offer in its own process, then moves to the next driver.
- A crashed matcher loses the timer, so the ride sits in
requestedforever.
- A crashed matcher loses the timer, so the ride sits in
- With each offer, schedule a 12 s delayed message (for example SQS) carrying the attempt number; when it fires, advance the Ride to the next driver.
- The timer outlives a crashed matcher.
- SQS cannot cancel a delayed message, so a stale one updates zero rows and is dropped.
- Cost: you hand-manage the loop's state across messages and rows.
- The matching loop is one workflow per ride (MatchingWorkflow) that waits 12 s per offer. Offer, wait, finish on accept, move on on decline or timeout.
- Each move to the next driver d' is one compare-and-set on the Ride's attempt counter n: set attempt = n+1, offered_driver = d', only if status = requested AND attempt = n.
UPDATE ride SET attempt = n+1, offered_driver = d' WHERE id = :ride AND status = 'requested' AND attempt = n- The first offer is the same write from
attempt = 0. - Order per offer: lock d', advance, push. No driver left:
offered_driver = NULL, ride fails "no driver".
- One winner: the accept and the advance both check attempt = n, so whichever commits second updates zero rows. A late accept (second 13) finds
attempt = n+1. - The workflow's state survives crashes, so the timer and the position in the ranked list resume on another worker.
- Cost: a workflow engine (Temporal, Step Functions) is a new system to run and learn.
- Uber built Cadence, its general-purpose workflow engine and Temporal's ancestor.
6) How do you scale further?
- Buy a bigger box.
- Costly and capped.
- A single point of failure.
- Put read replicas behind each primary.
- Reads spread, and a replica takes over when the primary fails.
- Every write still lands on one primary, and one node takes about 100k to 200k writes/s against 2M.
- The shard key is a geo cell (a geohash prefix, or an S2/H3 cell), and consistent hashing maps cells to nodes.
- A search queries only the shards owning cells that meet its radius and merges by distance. Away from a boundary that is one shard.
- A driver crossing a boundary is removed from the old shard, or the merge dedupes by driver id.
- Sharding spreads the 2M writes a second; read replicas spread reads and handle failover.
- Services, queues and data split geographically, which cuts latency.
- The Driver row is homed in the driver's current region, so it normally shares a shard with the Ride.
- Into an in-memory Redis geo set, sharded by geo cell. GEOADD overwrites the last position.
- Only the latest position matters; an emptied index refills within 15 s.
- A disk database pays for durability nobody needs: B-trees do not answer 2D nearest, and DynamoDB at 2M/s costs about $108K a day.
- Stale drivers leave through a last-seen sorted set and a sweeper (ZREM from both), because Redis TTL works on whole keys.
- A Redis lock per driver:
SET lock:driver:{id} {rideId:attempt} NX PX 12000. One SET wins; the loser moves to its next candidate. - The TTL frees the driver if the offer is never answered, with no sweeper.
- 12 s on the server against a 10 s countdown, so a tap at 9.9 s lands inside the lock.
- Release is a compare-and-delete on the value, so a matcher never deletes a lock another matcher has since acquired.
- A lock lost on failover means at worst a double offer; the Driver-row write stops a double assignment.
- The accept is a conditional write: Ride
requested→acceptedonly ifoffered_driver = me AND attempt = n. - At 12 s the workflow advanced the Ride and set attempt to n+1, so the accept updates zero rows and the driver sees "offer expired".
- Both writes check
attempt = nwhile the ride isrequested, so whichever commits first wins. - Driver side:
available→on_tripin the same transaction, so one driver never holds two rides.
- The request sits in a queue partitioned by region.
- Its offset commits only once the request is handed to the durable workflow, so another consumer picks it up after a crash.
- The workflow (Temporal) keeps its state and 12 s timer through the crash and resumes on another worker.
- The handoff is idempotent on
rideId, so a redelivered ride that is already matching or matched is skipped. - Committing after the match instead would stall the partition behind its slowest ride, up to 60 s.
- GEOSEARCH returns every online driver in the radius, busy or not, so "available" needs its own mechanism.
- Keep a separate available-drivers geo set: ZREM on offer or trip, GEOADD when free.
- Or over-fetch with COUNT and filter by lock and status.
- Widen the radius if still empty.
Final design + what is expected at each level
wrapFinal Design
- Path: gateway → Ride Service → queue by region → MatchingWorkflow; drivers ping the Location Service into Redis.
- The Ride Service prices with the mapping API and writes Fare and Ride rows.
- The queue's offset commits once the workflow starts; the start is idempotent on
rideId. - MatchingWorkflow is the Ride Matching Service, built as a durable workflow.
- Pings, at an interval capped at 15 s, write the geo index plus a last-seen set; a sweeper removes drivers silent for 30 s.
- Per offer: lock the next driver d' (SET NX PX 12000), advance the Ride from attempt n to n+1 with offered_driver = d', only if it is still requested at attempt n, then push.
- The Ride Service signals the workflow on an accept or a decline.
- A 12 s timeout or a decline runs the same advance for the next driver.
- Accept is one transaction: Ride requested → accepted if offered_driver = me AND attempt = n; Driver available → on_trip only if still available.
- The primary DB is sharded by region with read replicas; the Redis geo index is sharded by geo cell. Ride and Driver normally share a shard, because the Driver row moves with the driver's region.
- The invariant: every ride ends with at most one driver and every driver with at most one trip. The lock keeps offers single in the normal case, one transaction of conditional writes on Ride and Driver keeps assignment exact in every case, and a durable workflow owns every timeout so no request is lost.
- A lost lock means at worst a double offer.
- A crashed matcher's workflow resumes on another worker.
- An emptied index refills within 15 s.
What is Expected at Each Level
- Mid (E4):
- Clear API and data model.
- A working high-level design that meets the requirements.
- Knows a spatial index is needed, even without naming one.
- At least the Good answer to driver locking.
- Senior (E5):
- Gets through the high-level design fast.
- Goes deep on at least 2 of the deep dives, most often location search, driver locking and request queueing.
- Location writes: batches pings into a geospatial database (a quad-tree style index, or PostGIS), and says the batch delay leaves positions stale.
- Fewer location updates: raises the ping interval for every driver, and says positions then go stale exactly where a match depends on them.
- One offer per driver: locks the driver with a TTL in a distributed cache (Redis
SET NX PX), and says a failover can lose the lock. - Peak load: puts a queue in front of matching that matchers scale on, and says committing after the match stalls the partition behind its slowest ride.
- Drivers who never answer: schedules a 12 s delayed message with each offer, and says a stale one must update zero rows because SQS cannot cancel it.
- Scaling further: adds read replicas for reads and failover, and says every write still lands on one primary.
- Weighs the trade-offs of each choice.
- Knows sharding and replication for scale.
- Staff+:
- Deep on 3 or more areas.
- Proactive: the interviewer only focuses, never steers.
- Practical judgment about technologies.
- Insight the interviewer did not already have.
Say the opener out loud without notes: price it, persist it, find nearby available drivers, offer to one at a time with a timeout, never two offers per driver.
Then write the location math from memory: 10M / 5 s = 2M writes a second, a ceiling; 2M × 86,400 = 172.8B a day; about $108K a day on DynamoDB, so in-memory Redis, sharded across 10 to 20 primaries.
Then say the accept in one sentence: Ride requested → accepted only if offered_driver = me AND attempt = n, and Driver available → on_trip only if still available, in one transaction.