Ride matching — a full worked answer

Assumptions: one city at a time as the unit of scale, so I design for a city and replicate the design rather than building one global matcher. Hundreds of thousands of active drivers per large city at peak. Drivers report location every 4 seconds. Payments and identity are elsewhere. Riders are impatient: a match must happen in under about 10 seconds.

First question, which changes correctness rather than polish: do we offer a trip to one driver at a time and wait, or broadcast to several and take the first to accept? Broadcasting means two drivers can accept the same ride, which is a contested-resource problem needing a lock or a conditional write; sequential offering avoids that entirely but is slower when drivers ignore their phones. I will assume sequential offers with a short timeout, falling back to a small parallel batch if the first few time out.

Second question: does the rider get to see drivers moving on the map before requesting? That turns a matching problem into a continuous streaming problem for every open app, which is a much larger read load than matching itself. I will assume yes, since most ride-hailing apps do it, and treat it as a separate lower-priority path.

Scope: request a ride, find candidate drivers, offer and confirm, and handle nobody accepting. Out of scope: pricing and surge, routing and navigation, payments, and the trip itself once it has started.

Actors: rider, driver, and the system, which is unusually active here. The system decides which drivers are candidates, in what order to offer, how long to wait for each, when to widen the search, when to give up, and whether a driver who ignores offers should keep receiving them.

The chain: requested → candidates found → offered to a driver → accepted → driver en route → picked up. The design lives in the first four states.

Failure branches, which are the substance of the problem. At candidates found: there are no drivers in range. Widen the radius, then tell the rider honestly rather than spinning forever. At offered: the driver does not respond within the timeout. Withdraw the offer and move to the next candidate. The offer must expire server-side, or a driver accepting late collides with a driver who already took it. At offered: the driver declines. Move to the next candidate and record the decline, because a driver declining everything is a supply problem, not a matching one. At offered: every candidate declines or times out. Candidates often skip this branch, and it is common. The answer is to re-run the search, since the world has moved on in ten seconds, widen the radius, and after a bounded number of rounds tell the rider no driver is available and stop, because an endless spinner is the worst outcome.

At accepted: two drivers accept, which is only possible in the broadcast variant and is why the accept must be a conditional write: first accept wins, second is told the trip is gone. At accepted: the rider cancels in the same moment the driver accepts, so both operations race. The trip state machine must have a single owner and reject invalid transitions, rather than two services each deciding. At en route: the driver goes offline or their app crashes. Detect it via missed heartbeats and re-match, which means a trip can go back to the offering state, and the rider must be told.

One more the system must handle on its own: a driver whose location is 45 seconds stale should not be a candidate at all, because offering to a driver who is no longer where you think they are burns the rider's patience budget for nothing.

Take a large city at peak: 100,000 active drivers, each reporting every 4 seconds. That is 25,000 location writes per second, from one city, continuously, all day.

Ride requests in the same city at peak: perhaps 500 per second, fifty times fewer than the location writes. So this is a write-dominated system, the opposite of most products, and that fact decides the storage choice.

Each match reads the candidate drivers in a small area: maybe 50 to 200 drivers examined per request, so 500 requests a second is around 50,000 candidate reads a second. Significant, but small next to the writes.

Storage: a live position is a driver id, a coordinate, a timestamp and a status — under 100 bytes. Current positions for 100,000 drivers is 10 MB. That fits in memory easily, and it is the most useful conclusion in this estimate: the live index is a memory-sized problem, so it should not be in a database at all.

Historical positions are a different matter: 25,000 a second at 100 bytes is 2.5 MB a second, about 200 GB a day per city. That is a real data volume, and it exists for analytics and disputes, not for matching. So it goes to a separate append-only path and never touches the matching system.

So the hard part here is a very high write rate against an index that must stay queryable by location — and doing it inside a rider's ten-second patience budget. Not storage, not read throughput, and not the matching algorithm, which is simple once the index is right.

Location ingestion: drivers send positions over a persistent connection to a location service, which updates the in-memory geo index and separately fires the position onto a stream for the historical path. Justified by 25,000 writes a second: a persistent connection avoids per-ping HTTP overhead, and the two destinations have different requirements.

The geo index, which is the heart of it. Encode each position as a geohash of 6 characters (a cell of about 1.2 km by 0.6 km) and keep, per cell, a sorted set of drivers with their exact coordinates and last-seen time. Redis is the natural fit: in-memory, fast writes, and native support for this shape. A driver moving between cells is a remove and an add. Finding candidates means reading the rider's cell plus the eight neighbouring cells, because a driver 100 metres away can be just over a cell boundary, and missing them is a real bug.

Then filter and rank: drop anyone whose position is older than about 15 seconds, drop anyone not available, compute a real distance, and rank by estimated arrival time rather than straight-line distance. A driver 200 metres away across a motorway with no crossing is further away in practice than one 600 metres down the same road. The routing call is on the hot path, so it is a batch call for the top handful of candidates only, not for all 200.

Matching service: takes the ranked candidates and runs the offer protocol: offer to the top candidate, wait a few seconds, withdraw and move on, widening the search every couple of rounds, giving up after a bounded number. Greedy, not optimal, justified directly by the ten-second budget from Stage 1.

Trip state machine: one service owns trip state, in a durable store, with transitions enforced as conditional updates. This is the one part that must be strongly consistent and durable, because it is the record of who is going where and who gets paid. Justified by the Stage 2 races: two accepts, and cancel-versus-accept.

Push to drivers and riders: persistent connections, so an offer reaches a driver immediately and the rider sees status change without polling. Justified by the patience budget: polling every 2 seconds could waste a fifth of it.

Historical positions: the stream feeds an append-only store for analytics and dispute resolution. Separate on purpose, with no coupling to matching, so a problem in the analytics pipeline cannot slow down a match.

Partitioning: everything is sharded by city, and within a large city by geohash prefix, so a match only touches the shard covering that area. Justified by the numbers: 25,000 writes a second per city is fine on one in-memory node, and city isolation bounds the blast radius.

Hard part one: the offer protocol under a hard deadline. Sequential offers with a 5-second timeout mean three failed offers consume 15 seconds, already past the budget. So the protocol adapts: offer to one driver, and if the first two time out, switch to offering a small batch of three or four simultaneously and take the first accept. That converts a latency problem into a correctness problem, which I then solve explicitly. Accept is a conditional update on trip state (assign the driver only if the trip is still unassigned), so the first accept wins and the others are told the trip is gone, with a clear message rather than an error. Cost: drivers occasionally tap accept and lose, which is a bad experience and needs handling in the app; and a batch offer means several drivers stop looking at other work for a few seconds.

The offer must expire on the server, not just in the driver's app. If expiry lives only on the client, a driver with a frozen screen accepts 40 seconds later and collides with a completed match. Cost: server-side expiry means holding per-offer state with timers, which is more moving parts than a stateless design.

Nobody accepting, in detail, because it is a common real failure: after a bounded number of rounds (say three, with the radius widening each time), stop and tell the rider no drivers are available, with a retry option. Between rounds, re-run the search rather than reusing the candidate list, because in ten seconds drivers have moved and some have become free. Cost: re-running means more index reads per request, and the read estimate leaves room for that.

Hard part two: peak and hot cells. Demand is not uniform. A stadium emptying creates a single geohash cell with thousands of requests and few drivers. That cell's shard becomes hot for both reads and writes, and the index reads return the same overloaded candidate set to everyone. Defences: sub-partition hot cells so the load spreads. More importantly, once a cell is starved, stop pretending. Show honest wait times rather than searching endlessly: a rider told "8 minutes" can decide to wait, and a rider shown a spinner tends to leave. Cost: this is a product-visible degradation, and it needs the pricing and supply systems to respond, which is outside this design but must be acknowledged.

Driver disappearing after accepting: heartbeats every few seconds, and if they stop for more than about 30 seconds, move the trip back to offering and tell the rider we are finding another driver. Cost: a false positive on a bad network cancels a driver who was actually on their way, so the threshold must be generous and the driver must be able to reclaim the trip if they come back before it is reassigned.

Idempotency, because mobile networks retry constantly: a ride request carries a client-generated key so a retry does not create two trips, and an accept carries the offer id so a duplicated accept is a no-op rather than a second assignment. Cost: an idempotency key store on the write path with a retention window. It is cheap, and mandatory here.

Consistency per feature: driver positions are stale by seconds on purpose and that is fine. The candidate list is a best-effort snapshot. Trip state is strongly consistent and durable, because it decides who gets paid. Saying those three things separately is the answer. One blanket consistency statement would be wrong for two of the three.

What I would monitor: time-to-match at p50 and p95, the rate of requests ending in no-driver-found, and offer acceptance rate per area. Acceptance rate falling in one area is an early signal of a supply problem, and it tends to show up before riders complain.