Cruxly › System design › Design Exercises

Ride Matching

an index over a set that never stops moving

Prompt: design the matching core of a ride-hailing service. Drivers stream their location continuously; a rider requests a ride from a pickup point; the system picks a nearby driver and assigns the trip. One driver must never be assigned two trips.

40 minutes first. The hard part is that every row in your index is stale a second after you write it.

Applying the four moves: Scope — drivers stream location, a rider requests, the system assigns one nearby driver, never two trips per driver; pricing and routing out. Estimate — location updates per second (drivers × update frequency) dwarfs ride requests, so the write path is the location stream, not the booking. Sketch — an in-memory geospatial index of driver positions, a matcher that queries it, and an atomic assignment step. Deep dive — every row is stale a second after it's written, so "nearest" is always approximate; the correctness guarantee lives in the assignment step, which must atomically claim a driver so two concurrent requests can't both win the same one.

Scope and the asymmetry that shapes everything

In scope: driver location ingestion, finding candidate drivers near a pickup point, assigning exactly one driver to one trip, trip state transitions. Out of scope: pricing and surge (a separate system reading the same supply/demand signals), routing and ETA computation (assume a maps service — say it, don't design it), payments (covered by the ledger exercise elsewhere in this track), driver onboarding.

Estimate. Say 3 million drivers online at peak, each sending a location every 4 seconds, and 1 million ride requests per hour at peak.

Location writes: 3 x 10^6 / 4 = 750,000 writes/s. Enormous.
Ride requests: 10^6 / 3600 ≈ 280 matches/s. Tiny by comparison.
The ratio is roughly 2,700 writes per read, which is the inverse of nearly every other system in this track — and it is the fact that drives the whole design.

What that asymmetry means. A location update is worth almost nothing individually: it is superseded 4 seconds later, and nobody ever asks "where was driver X at 14:32:08." So do not durably store it on the write path. Keep current positions in memory, write them to a durable store only asynchronously (for the trip history and analytics that genuinely need it), and accept that a crash loses a few seconds of positions — which self-heals, because every driver reports again almost immediately.

Saying "these writes are disposable, so they do not get the durability treatment" early is the single highest-value observation in this problem. Candidates who treat location updates like ledger entries end up designing a write pipeline an order of magnitude more expensive than it needs to be.

Everywhere else in this track, the ratio argues for caching reads. Here it argues for something rarer: not bothering to durably store the writes at all.

Geospatial indexing: why B-trees fail and what replaces them

The query is "give me drivers within ~2km of this point." A standard index cannot answer it.

Why indexing on (lat, lon) does not work. A composite B-tree index on latitude then longitude answers "latitude between A and B" efficiently, then must scan every one of those rows to filter longitude. A thin horizontal band across the planet contains a vast number of drivers. The index prunes one dimension and leaves the other to a scan — which is a property of B-trees, not a tuning problem.

The fix is to reduce two dimensions to one, preserving locality. Divide the world into cells with a hierarchical grid, give each cell an ID, and index drivers by cell ID. Now "near this point" becomes "in this cell, plus its neighbours" — an exact-match lookup on a handful of keys, which every ordinary index does well.

Turning a 2-D radius query into exact-match lookups on a small set of cell IDs is the entire trick. Everything else is bookkeeping.

Which grid. Geohash (recursive rectangle subdivision, string prefixes share a region), S2 (projects the sphere onto a cube, gives near-uniform cell areas), or H3 (hexagons, so all neighbours are equidistant — no awkward diagonal cases). Name one and say what it buys; the interviewer cares that you know why the family exists, not which library you would import.

The edge case every candidate misses: a driver 50 metres away can sit in a different cell if the pickup point is near a cell boundary. Querying only the containing cell silently returns nothing while a driver is across the street. Always query the containing cell plus its ring of neighbours, then filter by true distance. This is not an optimisation — it is a correctness requirement, and naming it unprompted is a strong signal.

Matching, and the invariant that actually matters

The invariant: one driver is assigned to at most one active trip. Everything in the matching path exists to protect it, exactly like the seat-booking exercise elsewhere in this track — and the resolution is the same shape.

@@ 1 | Query candidates

Look up the pickup cell plus neighbours, get back the drivers currently in them. This is a read from an in-memory index and is deliberately cheap and approximate — it is a candidate set, not an answer.

@@ 2 | Filter and rank

Discard drivers already on a trip, offline, or wrong vehicle class. Rank what remains by ETA (not straight-line distance — a driver 200m away across a river is not close). ETA comes from the maps service, so cap how many candidates you ask about; ranking 200 drivers by real ETA is slower than the match is worth.

@@ 3 | Claim the driver atomically

UPDATE driver_state
   SET status = 'assigned', trip_id = :trip
 WHERE driver_id = :driver
   AND status = 'available'      -- claim only if still free

One conditional update. If it matches zero rows, another rider claimed that driver a millisecond earlier — take the next candidate and retry. This is compare-and-set, the same find-and-claim atomicity as the parking lot and the seat booking: check and act must be one step.

@@ 4 | Offer, and handle the driver declining

The driver gets a push with a short deadline. On accept, the trip goes live. On decline or timeout, release the claim (status back to available) and offer to the next candidate. The claim is therefore a hold with a timeout, not a permanent assignment — and, exactly as in seat booking, expiry is evaluated on read rather than by a sweeper job that would race the accept.

:::key Why the index does not need to be consistent The candidate query can be stale, wrong, or miss a driver entirely and the system stays correct — you just get a slightly worse match. Only the claim in step 3 needs to be strongly consistent. Keeping the expensive guarantee confined to one conditional update, and letting the 750,000-writes-per-second half be eventually consistent, is the core architectural move. :::

Only the claim needs the expensive guarantee — everything that feeds into it can be wrong without breaking correctness, only quality.

Sharding, hot cities, and the failure modes

Shard by geography, not by driver ID. A query for one cell must not fan out across every shard. Partitioning by a coarse cell prefix keeps a matching query inside a single shard, which is the geospatial equivalent of "shard by what is in your WHERE clause."

Hot shards are guaranteed, not hypothetical. Manhattan at 6pm and rural Montana are not the same load, and a uniform grid guarantees imbalance. Mitigations worth naming: subdivide hot cells further (this is why a hierarchical grid matters — the cell size can vary by density), and assign shards by measured load rather than by equal area. Saying "I would shard by geography" without acknowledging that geography is wildly non-uniform is the half-answer.

Failure modes:

A matching shard dies. Rides in that region stop matching. The blast radius is exactly one geography, which is the correct trade — and recovery is fast because the in-memory index rebuilds from driver location updates within seconds, as every driver reports again on the next tick. This is the payoff for treating location data as disposable.

Driver accepts, then the network drops before the rider is told. The trip exists from the driver's perspective and not the rider's. Resolve by making the trip record the single source of truth and having both clients reconcile against it on reconnect — the same "durable write first, then deliver" discipline as the messaging exercise.

Thundering herd on surge. A price drop or event ending produces a spike of simultaneous requests in one cell. Rate-limit per cell and queue rather than letting the matcher thrash on the same small candidate set.

Stale drivers. A driver whose app crashed still sits in the index. Treat a location update as a heartbeat with a TTL — no update for 30 seconds and the driver leaves the index automatically. Without this, the matcher repeatedly offers rides to a phone that is not listening, and every one of those offers costs a rider 10 seconds of waiting.

A uniform grid treats "shard by geography" as if geography were uniform — the hierarchical version is what actually delivers on that idea.

How to say it in the interview

"Two things drive this. The write volume is location updates from every online driver, continuously, which is enormous and almost entirely disposable. And the read is a geospatial nearest-neighbour query, which no ordinary index answers — so the index structure is the design."

Checklist

Derived the ~2,700:1 write-to-read ratio and called it the inverse of a normal system
Declared location updates disposable and kept them off the durable write path
Explained why a (lat, lon) B-tree cannot answer a radius query
Used a hierarchical grid to collapse two dimensions into one indexable key
Queried the containing cell plus its neighbour ring, then filtered by true distance
Ranked by ETA rather than straight-line distance, and capped how many candidates get ETAs
Claimed the driver with one conditional update rather than check-then-assign
Made the assignment a hold with a timeout, expired on read rather than by a sweeper
Confined strong consistency to the claim and let the index be eventually consistent
Sharded by geography so a cell query stays within one shard
Acknowledged that uniform grids guarantee hot shards, and gave a mitigation
Treated location updates as heartbeats with a TTL so crashed drivers leave the index

Practice this interactively