A system design interview guide to building an Uber-style dispatch system that matches a rider to the best nearby driver in seconds — over a sea of driver locations that change every few seconds, without ever handing the same driver to two riders.
Student edition · start with the guarantee
Use approximate location candidates but one authoritative state transition for exclusive trip assignment.
Correctness contract: One driver and one rider can each have at most one active accepted assignment. Offer identity/version/expiry guard all callbacks; location updates cannot overwrite assignment state.
Basic HTTP, databases, and programming are assumed. Specialized terms are explained below. Named products motivate the problem; this is an educational design, not a claim about their current internals. Capacity numbers are illustrative decimal payload estimates, not benchmarks. Add indexes, protocol overhead, replicas, headroom, and failure capacity before provisioning.
Ride matching looks like a proximity search with a twist, and the twist is where the design gets hard. Finding drivers near a rider is the same "what is near me?" spatial-index problem a Yelp-style service solves — but here the things you are indexing move, and you do not just read the result, you act on it by assigning a specific driver to a specific rider exactly once. Two new pressures dominate: an enormous, constant stream of driver location updates that must keep the index fresh, and a correctness requirement that two riders are never matched to the same driver. This guide walks through the location pipeline, the matching flow, the concurrency problem at its core, and how the system recovers when a driver declines or goes silent.
Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.
Geohash
A string encoding a rectangular latitude/longitude cell by interleaving longitude and latitude subdivision bits and representing them in base32. Longer shared prefixes identify a smaller shared cell.
Example. Two cafes 20 metres apart across a cell boundary may have unrelated prefixes. A radius search must cover all cells intersecting the query region, then filter candidates by distance.
Limit. Eight neighbors suffice only under specific cell-size/radius assumptions. Longitude wraps at the antimeridian and widths shrink toward the poles. Haversine is a spherical approximation, not ellipsoidal exactness.
ETA and uncertainty
An estimated time of arrival combines location, route, historical travel time, and current conditions. A distance-only estimate is not a road-network travel-time estimate; predictions should include uncertainty and freshness.
Example. A nearby driver across a river may take longer than a farther driver already on the correct road. Rank by road ETA after cheap geographic candidate filtering.
Limit. GPS timestamps can be stale or wrong. State the location age, update version, cancellation policy, and fallback when routing or traffic data is unavailable.
Optimistic concurrency and compare-and-set
Update state only if the expected version or status still matches, in the same atomic operation that changes it. A failed comparison means a conflicting operation won; reread or return a conflict.
Example. UPDATE seats SET status='held', version=version+1 WHERE id=? AND status='available' allows only one concurrent claimant to update the row.
Limit. Application-level GET then unconditional SET is not equivalent. Include acquisition identity to reject stale callbacks, and couple related invariants in a transaction.
Leases
Time-limited permission issued by an authority. Expiry lets new work proceed after a client stops renewing; it does not prove that the previous holder is dead or unable to act.
Example. A 30-second lease expires while A is paused for 45 seconds. B can acquire a new lease, but A can still wake up and send a delayed write.
Limit. Heartbeats improve recovery time, not safety by themselves. Compare-and-renew/delete must verify a unique acquisition token atomically, and protected effects need fencing or equivalent serialization.
State machines and projections
A state machine specifies legal states and transitions. An event-sourced projection derives read state from a durable event history under a deterministic ordering and conflict policy.
Example. A shipment can go from transit to exception and back; it is not a simple increasing status integer. A late prerequisite scan may require rebuilding the projection.
Limit. Keeping only the newest legal event can lose an earlier rejected transition forever. Timestamps need deterministic tie handling and source trust; append-only storage still has retention/privacy rules.
Transactional outbox
A business transaction writes its state change and an event row to the same database. A relay publishes committed event rows later, retrying until the broker durably accepts them.
Example. An order and its OrderCreated outbox row commit together. A relay crash after publish but before marking sent publishes the same event ID again on restart.
Limit. The relay is at-least-once, not magically exactly-once. Consumers dedup transactionally; preserve per-entity sequence when order matters. CDC is change data capture: reading committed database changes.
1. Requirements and Clarifying Questions
What kind of ride? One rider, one car [yes]; shared or pooled rides [out of scope].
How is the driver chosen? Best ETA among nearby available drivers [yes]; driver ratings and fairness [mention only].
How do offers work? Offer one driver at a time with a short timeout [yes], or broadcast to several and take the first accept?
How often do drivers send location? Every ~4 seconds while online [yes].
Scale? 1 million drivers online at peak worldwide, 20 million trips a day.
Functional
Non-functional
Drivers go online/offline and stream their location.
A driver is never assigned to two riders (correctness beats speed).
A rider requests a trip and is matched to a nearby driver.
Match within a few seconds; location reads are fresh to ~5 s.
Driver accepts or declines; rider sees driver approaching.
Absorb hundreds of thousands of location writes per second.
Trip ends and the driver becomes available again.
Highly available per city; one city's outage does not affect others.
Intuition
Picture a dispatcher with a wall map covered in magnets, one per taxi. Drivers radio in and the dispatcher slides their magnet (the location pipeline). A caller asks for a cab; the dispatcher looks at magnets near the caller (the geo index), picks the closest by road, and turns that magnet upside down so nobody else picks it (the atomic reservation).
2. Back-of-the-Envelope Estimation
Quantity
Working
Result
Drivers online at peak
assumption
1 M
Location writes
1 M / 4 s
250,000 writes/s
Write bandwidth
250 K × ~100 B
≈ 25 MB/s
Trips per day
assumption
20 M
Average match requests
20 M / 86,400 s
≈ 230/s
Peak match requests
avg × 5 (Friday night, events)
≈ 1,200/s
Live index memory
1 M drivers × ~100 B
≈ 100 MB
Write : match ratio
250,000 / 1,200
≈ 200 : 1
The index itself is tiny, about 100 MB, but the write rate is huge. That is the opposite of the proximity service, which had a big index and few writes. It tells you where to spend effort: a store that can take hundreds of thousands of small overwrites per second, partitioned by city or region so no single node takes all of them. If you keep location history for analytics or trip receipts, send it to a separate log (for example Kafka into cheap storage) instead of the hot index.
3. API and Data Model
# driver app
POST /v1/drivers/me/location { "lat": 37.77, "lng": -122.42, "heading": 90, "ts": ... }
POST /v1/drivers/me/status { "status": "online" | "offline" }
POST /v1/offers/{offer_id} { "decision": "accept" | "decline" }
# rider app
POST /v1/trips { "pickup": {...}, "dropoff": {...} } -> { "trip_id": ... }
GET /v1/trips/{trip_id} -> { "state": "matching" | "driver_assigned" | ..., "driver": {...}, "eta_s": 240 }
# server -> driver push (WebSocket or mobile push)
OFFER { "offer_id": ..., "pickup": {...}, "expires_at": ... }
Data
Where it lives
Key fields
Live driver location
In-memory geo store (for example Redis with GEOADD / GEOSEARCH), partitioned by city
driver_id, ts, lat, lng (for receipts and analytics)
4. What Makes Matching Hard
The headline feature — "show me a driver and send them to me" — hides three distinct hard problems that an interviewer wants you to separate cleanly. Conflating them is the most common way the design goes wrong.
The data moves constantly. Every active driver reports a new location every few seconds. With many thousands of drivers in a city, that is a relentless write stream into the very index you also need to query for matching. A spatial index that is cheap to read but expensive to update will not survive this.
Matching is an action, not a read. A proximity query returns a list; ride matching must pick one driver and reserve them. The moment you turn a read into a reservation, concurrency rears its head.
The best match is not just the nearest. The driver to offer is the one who can get there soonest, which depends on road network and traffic (ETA), not raw straight-line distance — and availability changes second to second.
The clean mental model for an interview: ride matching is a high-write geospatial index feeding a matching service that performs an exactly-once assignment. Keep those two responsibilities separate in your head and most of the design falls out naturally.
5. The Location Pipeline
Start with the firehose. Each driver's app sends a location ping on a short interval, and these pings must flow into a geospatial index fast enough that a matching query a moment later sees a fresh picture of where everyone is. The defining trait of this path is that it is write-dominated — far more location updates arrive than ride requests — so it is built and scaled around absorbing writes.
Because a driver's position is only useful while it is current, this data is a natural fit for a fast, in-memory, frequently overwritten store rather than a durable disk-backed database. You do not need the full history of every GPS point; you need the latest position, indexed spatially, available in milliseconds. A geo-indexed in-memory store (or an in-memory quadtree) keyed by location is the usual choice.
# driver app pings every few seconds
function on_location_update(driver_id, lat, lng):
new_cell = geo_cell(lat, lng) # geohash / quadtree leaf
old_cell = geo_index.cell_of(driver_id)
if old_cell != new_cell:
geo_index.remove(old_cell, driver_id) # or it shows up in two cells
geo_index.upsert(new_cell, driver_id, lat, lng, ts=now())
# overwrite, don't append — only the latest fix matters.# status (AVAILABLE / OFFERED / ON_TRIP) is a separate field that# location pings never touch, so a ping cannot undo a reservation.
The key design decisions on this path:
Overwrite, do not accumulate. Each update replaces the driver's previous position. You are maintaining a current-state map, not a log, which keeps storage bounded and writes cheap.
In-memory for speed. Reads and writes both have to be fast, and the data is disposable, so it lives in memory rather than on disk.
Index by cell. Each driver is tagged with a spatial cell (geohash or quadtree leaf) so the matching service can fetch "drivers near here" with a cell lookup rather than scanning everyone.
6. The Geospatial Index
The index is the bridge between the two halves of the system: the location pipeline writes into it, and the matching service reads from it. Conceptually it is the same spatial index a proximity service uses — drivers are placed into cells, and a query for a rider returns the drivers in the cell the rider is in plus the neighboring cells, trimmed to a radius.
The matcher reads the rider's cell plus its eight neighbors (shaded), not every driver in the city. A driver is a candidate (blue) only if it is available, its location is fresh, and it is inside the radius. Busy drivers (orange), stale locations (hollow) and drivers past the radius (gray) are skipped.
The difference from a static proximity service is churn: entries are constantly being overwritten as drivers move, and they carry a freshness timestamp so the matcher can ignore a driver whose last ping is stale. A driver also has a status — available, offered, or on a trip — and only available drivers are eligible candidates. The index therefore answers a slightly richer question than "who is near here": it is "which available drivers are near here, with a recent location."
function nearby_available(rider_lat, rider_lng, radius):
cells = cells_for(rider_lat, rider_lng, radius) # cell + neighbors
drivers = []
for cell in cells:
for d in geo_index.in_cell(cell):
if d.status == AVAILABLE and fresh(d.ts): # skip stale / busy
if haversine(rider_lat, rider_lng, d.lat, d.lng) <= radius:
drivers.append(d)
return drivers
7. The Rider Request Flow
When a rider requests a trip, the matching service runs a short pipeline: find candidate drivers nearby, rank them by who can arrive soonest, then offer and dispatch the best one. Crucially, ranking is by estimated time of arrival, not raw distance — a driver two blocks away stuck behind a closed road may be a worse pick than one slightly farther on an open route.
The matching pipeline: find nearby drivers and rank them by ETA. Reserve the best one with a compare-and-set from AVAILABLE to OFFERED that records an offer_id; if the CAS loses, try the next driver. On accept, a CAS on the same offer_id moves the driver to ON_TRIP. On decline or timeout, a CAS returns the driver to AVAILABLE and the rider is re-dispatched.
Reading the flow:
Request. The rider submits a pickup location (and destination). The matching service receives it.
Find nearby. Query the geospatial index for available drivers within a radius of the pickup point.
Rank by ETA. Order candidates by estimated arrival time, factoring in road network and traffic, not just straight-line distance.
Claim driver and rider/request invariants atomically or through a recoverable reservation protocol. Use exact offer identity/expiry for all callbacks; a driver-only lock does not stop duplicate rider attempts claiming different drivers.
Offer and confirm. Present the trip to the driver. On acceptance, confirm the match; on decline or timeout, release and move to the next candidate.
8. The Concurrency Problem
Candidate location queries can be stale; assignment authority cannot. Claim the driver and the rider/request version under an atomic transaction or a reviewed reservation protocol. A driver-only CAS prevents two riders sharing one driver but does not prevent one rider's duplicated request from claiming two different drivers.
Persist offer_id, rider_request_id/version, expiry, and status with dispatch intent/outbox. GPS writes update separate location/version fields and cannot reset OFFERED/ON_TRIP status. Revalidate heartbeat/location age at the authoritative claim. A Redis geo index is a derived candidate store unless its durability/failover contract can enforce the actual assignment invariant.
9. Decline, Timeout, and Re-dispatch
Accept/decline/timeout callbacks match the exact current offer_id and rider request version. Acceptance also checks expiry in the authority's transaction; a late accept must not succeed merely because the sweeper has not removed the expired offer. Duplicate results are idempotent.
Update driver, rider, and trip state atomically where possible, or durably coordinate a recoverable protocol; publish dispatch/confirm intent with the same committed transition. A crash after a driver CAS but before creating the offer/trip must not strand state forever. Cancellation races and repeated redispatch need bounded attempts/deadlines and conditional cleanup. A timeout guarantees progress only if the authority and recovery workers can run.
10. ETA and Supply/Demand
Two pieces of intelligence make the matching genuinely good rather than merely correct. The first is ETA estimation: the time for a driver to reach the rider depends on the road network and current traffic, so the system estimates travel time along real routes rather than comparing straight-line distances. Ranking by ETA is what makes the offered driver the one who actually arrives first, which is what the rider experiences as a good match.
The second is the broader supply and demand picture. At any moment a city has a shifting balance of available drivers (supply) against waiting riders (demand), and that balance varies sharply by neighborhood and time. The system tracks it both to set expectations (longer waits where supply is thin) and, in mature designs, to nudge behavior — surfacing where demand is high so supply can follow. For the core matching problem, the relevant point is that candidate availability is dynamic: a cell that was driver-rich a minute ago may be empty now, which is exactly why the index must stay fresh and the matcher must tolerate "no driver found" and retry.
11. Separating the Services
The single most important structural decision is to split the high-write location service from the matching service. They have opposite profiles — one is a write firehose with disposable data, the other does relatively rare but logically heavy work that must be exactly-once — and forcing them into one component makes both worse.
Drivers stream location updates into a location service, which upserts them into the in-memory geo index. The matching service, driven by rider requests, queries that index and performs the atomic assignment. The write-heavy location path is deliberately kept separate from the read-and-assign matching path.
Location service. Optimized purely for ingesting the update firehose and keeping the geo index current. It can be scaled and tuned independently for write throughput.
Matching service. Reads the index, ranks by ETA, and performs the atomic lock-and-assign. Its correctness logic is isolated from the noise of constant location writes.
Shared geo index. The in-memory spatial store both sides touch — written by the location service, read and status-mutated by the matcher.
This separation means a surge of location pings cannot starve the matching logic, and a flurry of ride requests cannot back up location ingestion. Each side scales on its own axis, and the geo index is the clean, narrow contract between them.
12. Failure Modes
What breaks
Effect
How to handle it
Driver phone loses signal
Stale location; driver may look available but cannot respond.
Freshness check on every read (ignore pings older than ~10 s); offers time out and re-dispatch.
Matching server crashes mid-offer
Driver stuck in OFFERED forever.
Store expires_at with the reservation; a sweeper resets expired offers with a CAS on offer_id.
Geo index node for a city dies
Matching in that city stops.
Keep a replica; drivers re-send location every 4 s, so a fresh node refills in seconds.
Idempotency key on POST /trips; one active trip per rider.
Demand spike after a concert
Match latency climbs; many "no driver" results.
Queue requests per area, widen the radius step by step, surge pricing to balance supply and demand.
13. Tradeoffs and Alternatives
Choice
Option A
Option B
Rule of thumb
Offer strategy
One driver at a time
Broadcast to several, first accept wins
One at a time is fair and simple but slow if drivers decline. Broadcast is faster but annoys drivers who lose the race.
Matching algorithm
Greedy: best driver for each request now
Batch: collect requests for ~2 s and solve an assignment problem
Greedy is easy. Batching lowers total pickup time across the city, and large ride-hailing companies describe using it.
Ranking
Straight-line distance
Road ETA
Use distance to get ~10 candidates cheaply, then ETA to rank those few.
Location store
In-memory, lossy on crash
Durable database
In-memory. Positions are refreshed every few seconds, so losing them costs seconds, not data.
Partitioning
By city / region
By driver id hash
By region, because a match only looks at nearby drivers; hashing by driver id would scatter one area's drivers across all nodes.
Worked example: a late acceptance after redispatch
Offer O1 expires; driver D is then offered O2.
Read top to bottom. The table below explains the state and guarantee at each step.
Step
State, calculation, and reasoning
1. Reserve O1
Atomically claim driver D for rider R and record the durable offer/dispatch intent. Location freshness is checked separately.
2. Timeout O1
Conditional release checks status, offer_id=O1, and expiry. The rider's request version also prevents duplicate parallel redispatch.
3. Create O2
New offer identity/version protects the driver and rider allocation. A stale location update cannot set status back to available.
4. Receive late accept O1
Reject because the current offer is O2 or expiry passed. Even if the sweeper has not run, acceptance must enforce authoritative expiry.
Check your understanding: Does a driver-only compare-and-set prevent all duplicate trips?
No. Two concurrent matching attempts for the same rider can claim two different drivers. Coordinate both driver and rider/request invariants.
Run a small, testable model
Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:
python3 concepts.py seats
python3 concepts.py test
The acquisition-identity model demonstrates stale-accept rejection. Adapt its seat state to driver and rider claims; the real matching transaction must guard both.
The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.
Single rides, ETA ranking, sequential offers with a timeout, pings every 4 s.
5–10
Estimate
250K writes/s, ~1K matches/s at peak, 100 MB live index.
10–15
API and data
Location, status, trips, offers; live store vs durable trips DB.
15–25
High-level design
Location service → geo index (per city) ← matching service → offer push; trip service.
25–38
Deep dive
The double-booking race and CAS; offer ids and the late-accept race; timeouts and re-dispatch.
38–45
Wrap up
Failures, surge, batching, what you would monitor (match time, acceptance rate, stale-location rate).
15. Common Mistakes
Mistake 1: storing locations in a durable SQL table and updating it 250K times a second
Positions are disposable and change constantly. Keep them in memory and send history to a log if you need it.
Mistake 2: "read then write" status updates
Checking status == AVAILABLE and then writing OFFERED in two steps lets two requests both pass the check. Use one atomic compare-and-set.
Mistake 3: no offer timeout
A driver who locks their phone would hold the reservation forever and strand the rider.
Mistake 4: ranking by straight-line distance only
A driver across a river may be 300 m away and 15 minutes by road.
Mistake 5: forgetting to remove a driver from the old cell
If moving cells only adds, the driver appears in two places and can be found twice.
16. Summary
Ride matching is a high-write geospatial index feeding an exactly-once assignment engine. The design is a set of choices that keep those two halves fast and correct:
Concern
Mechanism
How do we track constantly-moving drivers?
A write-dominated location pipeline that upserts the latest position every few seconds.
Where do driver locations live?
A fast, in-memory, frequently overwritten geospatial index (geo store or quadtree).
How do we find candidates for a rider?
Query the index for available, fresh drivers in the rider's cell plus neighbors, within a radius.
Which driver do we offer?
Rank candidates by ETA over the road network, not by straight-line distance.
How do we avoid double-booking a driver?
An atomic lock / compare-and-set on driver status — exactly one request wins.
What if the driver declines or goes silent?
Release the reservation on decline or timeout and re-dispatch to the next candidate.
How do we keep the system scalable?
Separate the high-write location service from the read-and-assign matching service.
The through-line: treat the proximity read as fast and approximate, but make the assignment atomic and exactly-once — and keep the write firehose of locations on its own service so it never collides with the matching logic.
17. Check Yourself
Why is the live location index tiny (about 100 MB) but still hard to build?
Answer
Because of the write rate, not the size. 1 million drivers pinging every 4 s is 250,000 overwrites per second, all into the same structure that matching reads.
Two riders one block apart both see driver D as their best candidate. Walk through what happens with compare-and-set.
Answer
Both try CAS(D, expect=AVAILABLE, set=OFFERED). The store applies them one at a time; the first succeeds and gets an offer id, the second sees OFFERED, fails, and moves to its next candidate.
An offer times out and the driver is re-offered to rider B. Then rider A's delayed accept arrives. What stops the driver being double-booked?
Answer
The accept is a CAS that expects (OFFERED, offer_A). The driver now holds (OFFERED, offer_B), so the CAS fails and the driver is told the offer expired.
Why partition the geo index by city or region rather than by driver id?
Answer
A match only needs drivers near the rider. Region partitioning keeps them on one node. Hashing by driver id would force every search to ask every node.
What is the benefit of batching requests for a couple of seconds before matching?
Answer
The system can solve all nearby requests together and minimize total pickup time. Greedy matching might give the one driver who is best for two riders to the first rider, forcing the second into a long wait.
The matching server crashes right after reserving a driver. How does the driver ever become available again?
Answer
The reservation carries expires_at. A sweeper (or the next reader) sees it has expired and resets it with a CAS on the same offer id.
18. Key Terms
Compare-and-set (CAS)
An atomic "if the value is still X, set it to Y" operation; fails if someone changed it first.
Offer id
A unique token for one reservation, so stale replies can be recognized and ignored.
Dispatch
Choosing a driver for a request and sending them the offer.
ETA
Estimated time of arrival, computed on the road network with traffic.
Freshness
How old a driver's last location ping is; stale drivers are skipped.
Supply / demand
Available drivers vs. waiting riders in an area; drives wait times and surge pricing.
Batch matching
Collecting requests for a short window and assigning drivers to all of them together.
19. Further Reading
Redis documentation for GEOADD and GEOSEARCH (geo sets built on sorted sets and geohash).
H3 documentation (h3geo.org) and Uber Engineering's blog post introducing H3 (2018).
Martin Kleppmann, Designing Data-Intensive Applications, chapters on transactions and linearizability (why CAS matters).
H. W. Kuhn, "The Hungarian Method for the Assignment Problem," 1955, the classic algorithm behind batch matching.
Alex Xu and Sahn Lam, System Design Interview, Volume 2, chapter "Nearby Friends," for the location-update side.
