Dev Learning
Matching under time pressure

Ride matching

Design the matching part of a ride-hailing service. A rider requests a ride from where they are standing; the system finds a nearby driver, offers them the trip, and confirms the match. Drivers move continuously and can decline.

hardGeospatial indexingConsensus, at concept levelIdempotency, and why exactly-once is a mythLong polling vs WebSockets vs SSEDistributed countersLatency vs throughputClocks, ordering and why timestamps lie

Where’s the slack?

Match: ~10 seconds, and every second is visible.

A person is standing on a street with a phone in their hand. There is no cooking time and no processing window to hide latency inside. Few problems in this app have less slack.

Compare this to food delivery, which looks like the same problem. There, a courier does not need to be assigned the moment the order is placed. The restaurant needs 15 minutes to cook, and the system can spend several of those minutes finding the best courier, batching orders together, and waiting for a better option to come free. Those 15 minutes are slack, and they make a different design possible: batched optimisation rather than immediate assignment.

Ride hailing has none of it. The rider is outside, possibly in the rain, watching a spinner. Ten seconds without a driver feels broken; after thirty they may open a competing app. So matching must be greedy and immediate: take a good driver now, not the best driver in forty seconds. That rules out global optimisation, which is the elegant answer and the wrong one here.

There is one small pocket of slack: the few seconds between offering a trip to a driver and their tap. That window lets you sequence offers rather than blasting all candidates at once. But the rider is waiting through it and other drivers are moving away, so it is measured in seconds and cannot be spent freely.

Everything not on the matching path (receipts, ratings, driver earnings, analytics) has hours of slack and should be nowhere near this design.

So: Zero slack means greedy immediate matching, not batch optimisation. It also means the failure branches (nobody accepts, everybody declines) are the design, because they happen while a human is watching.

Work it through

Five stages, gated. You write your answer for each stage before its model answer unlocks. That is the core of the method.

Loading your progress…

Reference material for this problem. The diagrams below are here to check your own against once you have drawn it, not to read first.

The lifecycle

RequestedriderCandidates foundsystemOfferedsystemAccepteddriverEn routedriverNo drivers in rangewiden radius, then say so honestly — never spin foreverDriver times outserver-side expiry, withdraw, next candidateEveryone declinesbounded rounds, re-search each round, then a real no-driver resultTwo drivers acceptconditional write on trip state — first wins, second told clearlyRider cancels simultaneouslysingle owner of trip state rejects the invalid transitionDriver goes offlinemissed heartbeats for 30s → back to offering, tell the rider
The trip request. Every branch below happens routinely at peak. "Nobody accepted" is not an edge case; it happens every day.

The numbers

Driver location pings~25,000 / sec
Candidate reads~50,000 / sec (~100 per request)
Ride requests~500 / sec
All live positions in memory~10 MB

All live positions fit in 10 MB. That number says the live index belongs in memory, not in a database, and that durability for a position that expires in 4 seconds is money spent protecting nothing.

One large city at peak. Location writes outnumber ride requests fifty to one, the opposite of most systems.

The architecture

candidatesrank by ETAaccept = conditionalDriver appping / 4sLocation svcGeo indexin-memory, by cellPosition streamHistory storeanalytics onlyRider appMatching svcoffer protocolTrip statedurable, conditionalRoutingETA, top N only
Live positions live in memory and are never durable. Trip state is durable and strongly consistent. The two are separate systems on purpose.

The mechanism

Writeshash(key)Shard Aa–hShard Bi–pShard Cq–z
the key decides the shard — same key, same box, every time
Positions are routed to the shard owning their geo cell. A match reads its own cell plus the eight neighbours, because a driver just over a boundary can still be 100 metres away.

The decision this turns on

A
Greedy immediate matching
  • —Offer to the best available driver right now and commit.
  • —Match in seconds, which is the only budget that exists here.
  • —Globally worse assignments, with longer average pickups.
  • —Simple to reason about and to debug during an incident.
B
Batched optimisation
  • —Collect requests for 30–60 seconds, then assign the whole set optimally.
  • —Noticeably better assignments overall, and it can pair trips going the same way.
  • —Requires slack that ride hailing does not have: the rider is outside, waiting.
  • —Right for food delivery, where 15 minutes of cooking hides the delay completely.
Which one: Greedy, because there is no slack to optimise inside. This is one of the clearest examples in the curriculum of a same-shaped problem getting opposite designs: food delivery has 15 minutes of cooking to hide latency in, so batching wins there. Ask "where is the slack?" before choosing.
The design fork that separates ride hailing from every other matching problem.

Follow-ups you should expect

Many interviews are decided in the follow-ups, not the first diagram.

One key gets 90% of the traffic. What breaks, and what do you do?A whole region is down. What do users see?Two users click at the same millisecond. What happens?Why this database and not Postgres?Which alert fires first when this system starts failing?Now it must support scheduled actions — do this thing at 8am next Tuesday.The cache just died. What happens?There is an option that is 40% cheaper but 10% slower. Do you take it?

Same shape, other products

Two sides need to find each other, and one of them is a human who is waiting.

Supply moves, demand is impatient, and the interesting design is what happens when nobody accepts, rather than the happy path.

Others with this shape: Ride hailing · Food delivery dispatch · Any two-sided marketplace

Before you leave
Try this problem again in a week without reading anything. Comparing what you write then with what you wrote today shows you what stuck.
Stuck, or new to this?Read the full worked solutionAll five stages end to end, with the diagrams and the costs, written out the way you would say it. Best read after you have had a go.Read it →

How it is really built

Write your own answer first. Then read how teams who run this at scale describe it. Their constraints were real, and the write-ups often say what their choices cost.