The whole design, in writing
Every step of the build above, written out: the problem each piece solves, the option that was taken and the ones that were not, the numbers, and how it fails in production.
The big idea
What is a matching engine, specifically?
Not the whole ride-hailing product — just the one hard question buried inside it: given a rider who just requested a ride and a hundred available drivers scattered across the city, WHICH driver should be assigned? Pick wrong and you've either sent a driver 20 minutes away when a 3-minute driver existed, or you've locally optimized one match while leaving the rest of the marketplace worse off.
We'll build the matching pipeline specifically: how "nearby" is actually measured, why matching one rider at a time is provably worse than matching a whole window together, how surge pricing balances a two-sided marketplace, and how fairness keeps the system healthy for drivers, not just efficient for any one rider.
What the new pieces do
- Riderclient
- Wants a driver assigned fast, and wants that driver to actually be close by real travel time — not just close on a map.
- Driverclient
- Streams a location update every few seconds while online and available, and expects fair, not-too-sparse ride offers.
Step 1 · The baseline
Nearest driver, by straight-line distance
Simplest matching: find the geographically closest available driver (straight-line distance on a map) and assign them immediately, one rider at a time. What goes wrong?
Matching by straight-line distance, one rider at a time, immediately. What's the core failure?
Closest ON A MAP and closest by actual travel time are very different things the moment a river, highway, or one-way street sits between two points — "closest" needs a better definition.
Two separate flaws stack here: the DISTANCE METRIC is wrong (straight-line ≠ real travel time across a road network with barriers), and the ALGORITHM is short-sighted (assigning the first rider to their nearest driver might use up a driver who was actually the BEST match for a rider arriving a second later, while a different driver would have served the first rider almost as well).
Driver acceptance behavior is a real factor in production systems, but it's not the CORE algorithmic flaw here — the flaw exists even assuming every driver accepts every offer.
Two separate problems: the distance metric is wrong (straight-line ignores rivers, highways, one-way streets — real travel time can differ wildly from map distance), and the algorithm is short-sighted (matching greedily, one rider at a time, can lock in an assignment that's locally fine but globally worse than considering multiple pending riders and drivers together).
Why this piece earns its place
The baseline also bakes in an assumption nobody states out loud: that the drivers worth considering are the ones sitting idle at the instant the request lands. That holds in a quiet suburb and breaks exactly where it matters most — downtown at peak, where almost every driver is mid-trip and the idle pool is thin or empty. The genuinely best answer to a request arriving now is often a driver a block away who is about to drop off, not the one free car on the far side of a river. A matcher that cannot see them either offers a bad driver or tells the rider nobody is available while the street outside is full of cars. So let a driver enter the candidate pool before they are free: carry their predicted drop-off point and the time they will be free, and cost them as available-from-then rather than unavailable-now. It buys nothing when supply is loose, and it is most of the difference during a rush — which is precisely when every other part of this design is also under strain.
What the new pieces do
- Dispatch APIgateway
- Ingests ride requests and driver location pings, and is the front door to the whole matching pipeline.
- Driver Geo Indexcache
- A fast, frequently-updated spatial index of every available driver's current location — the thing matching queries against.
Step 2 · Real ETA, not map distance
Route, don't just measure
Fix the metric: use actual predicted travel time instead of straight-line distance.
Introduce an ETA / Routing service that computes real road-network travel time between a candidate driver and the rider — accounting for actual streets, current traffic conditions, and turn restrictions. This becomes the true cost function for matching: rank candidate drivers by predicted pickup ETA, not by distance on a map.
Why this piece earns its place
Real routing is the correct cost and also the most expensive thing on this page. A straight-line lookup against the geo index is nearly free; a road-network route is not, and one request against a hundred available drivers means a hundred of them — worse in Step 4, where a whole window of riders and drivers needs a cost matrix, not a column. So straight-line distance does not disappear when we stop ranking with it; it gets demoted to the candidate filter. Pull a handful of plausible drivers cheaply out of the index, then spend real routing only on those. The radius of that filter is now a knob, and both directions cost something: too tight in a sparse area and you route three drivers, none of them good, so the rider waits for a bad match; too wide downtown and you are paying to route cars that were never going to win the assignment. Tie it to local driver density rather than pinning one number citywide, and widen it automatically when a region returns too few candidates to choose between.
What the new pieces do
- ETA / Routingservice
- Computes actual road-network travel time between a candidate driver and a rider — the real cost function, not straight-line distance.
Step 3 · Surge pricing
When demand outstrips nearby supply
A concert lets out: 500 ride requests appear in six square blocks with 40 available drivers. Matching can't manufacture drivers that don't exist. What should the system do?
Demand vastly exceeds nearby driver supply. What can the system actually do about it?
Doing nothing beyond matching leaves both sides of the marketplace unaddressed: riders have no signal about the wait, and there's no incentive pulling additional drivers toward the imbalance.
Surge is a two-sided lever: it moderates demand (price-sensitive riders wait it out) AND grows supply (higher fares pull drivers who'd otherwise be elsewhere or offline). It's a real-time price signal doing double duty in a two-sided marketplace with a genuine, temporary supply shortage.
Hiding the reason for a long wait removes the price signal that would otherwise pull in more supply, and gives riders no information to make an informed choice (wait, or find another way).
Introduce surge pricing: when a geographic area's demand meaningfully exceeds nearby supply, raise the price for that area in near-real-time. This is a genuine market-clearing mechanism, not just a revenue lever — it rations demand toward those who value the ride most right now, and pulls additional driver supply toward the shortage.
Why this piece earns its place
Surge is a feedback loop, and feedback loops oscillate unless you damp them. Price rises because supply is short, drivers reposition toward the money, the shortage clears, the price falls — and the drivers who crossed town arrive into an ordinary fare and learn not to chase it next time. Two things keep that honest. Quote the price when the rider requests and honour it, so nobody is repriced mid-decision; and rate-limit how fast the multiplier can move in either direction, so it describes a real imbalance rather than a momentary blip in arrivals. The other knob is the zone itself. Draw it too coarse and you surge riders several blocks from the concert who caused none of it. Draw it too fine and the boundary becomes the game — riders walk one street over to dodge it, drivers idle on the profitable side of a line rather than where riders are. Neither is a pricing bug you patch later; both follow directly from where the box was drawn, which makes the box a design decision, not a configuration detail.
What the new pieces do
- Surge Pricingservice
- Raises price when demand outstrips nearby supply — both rationing demand and pulling more drivers online toward the imbalance.
Step 4 · Batch, don't match greedily
Solve the whole board, not one move at a time
Even with correct ETAs, matching riders the instant each request arrives — one at a time, in whatever order they happen to land — can produce a worse OVERALL assignment than considering several pending riders and drivers together. How do you match better than greedy, without making every rider wait forever for a "perfect" global solve?
Greedy one-at-a-time matching is provably suboptimal. What's the practical fix?
Riders need a driver in seconds, not hours — any fix has to preserve near-instant matching, not trade correctness for an unusable delay.
Randomizing doesn't improve on greedy's core flaw — it just replaces "locally good but globally suboptimal" with "not even locally good," which is strictly worse.
A short batching window (seconds, not minutes) barely delays any individual rider, but gives the matcher visibility into MULTIPLE riders and drivers simultaneously, so it can solve a proper assignment problem (conceptually similar to the Hungarian algorithm for bipartite matching) that minimizes total cost across the group — routinely better than whatever a greedy, one-at-a-time pass would have produced, for a negligible latency cost.
Introduce a Batch Matcher: collect pending requests and available drivers over a short window, then solve matching as an assignment-optimization problem across the whole batch — minimizing total cost (aggregate ETA) rather than optimizing each pair in isolation. A few seconds of batching buys a meaningfully better global outcome for a cost riders barely notice.
Why this piece earns its place
An optimizer serves the objective you wrote, and the objective as stated says nothing about any individual rider. Minimizing total ETA across a window can be achieved by serving most of the batch quickly and deferring one — the rider on a cul-de-sac, or across the bridge — because moving any driver to them costs more than it buys. That is the correct answer to the problem we posed. The trouble is that the next window poses the same problem over the same geography, so the same rider loses again, and nothing notices: every individual solve looks optimal, the aggregate wait-time chart looks healthy, and one person sits watching the app. Deferral therefore has to cost something. Carry the time a rider has already waited into their cost in the next solve, and let it grow, so the optimizer stops finding them cheap to skip and eventually eats the long pickup rather than the accumulated penalty. Set that growth deliberately: flat and it never bites; steep and one awkwardly-placed rider drags an entire window of matches toward them.
- secondstypical batch window
- assignment problemsolved per window
- lower total ETAthan greedy, on average
What the new pieces do
- Batch Matcherservice
- Solves matching for a whole window of pending riders and drivers together as an optimization problem, not one greedy pair at a time.
Step 5 · Ingesting driver locations at scale
A write-heavy problem, not a read-heavy one
Every online driver pings their location every few seconds. At real scale, that's an enormous, continuous write volume hitting the geo index — a very different load pattern than the mostly-read search traffic other systems deal with. What does that demand from the index?
The Driver Geo Index has to be optimized for high write throughput — frequent location updates from potentially millions of concurrently-online drivers — while still serving fast "who's nearby" spatial queries. In practice this means partitioning the index geographically (so writes and reads for one city's drivers don't contend with another's), keeping each update lightweight (overwrite last-known-location, not append an unbounded history), and treating slightly-stale location data as acceptable — a driver's last known ping from 3 seconds ago is a fine approximation of where they are now.
Why this piece earns its place
Overwriting last-known-location is the right call, and it quietly costs two things. The first is history. The index becomes a present-tense view, so nothing in it can later answer why a particular match was made, or replay a bad window to see what the matcher actually saw. Append the raw ping stream somewhere else, asynchronously and off the hot path, or that question is unanswerable forever afterward — and it is also the history Step 8 needs to smooth a noisy signal, which is why smoothing has to happen at ingest, before the overwrite. The second cost is the ping interval, a genuine knob with a price on each side. Ping faster and you buy freshness with write volume, driver battery and more raw noise to filter. Ping slower and you rank on where the driver was — harmless when they are a long way out, decisive when two candidates are a block apart, and far worse for a car at highway speed than a parked one. Make the rate adaptive rather than uniform, and carry heading and speed with the ping so the matcher can reason forward from the last one.
Step 6 · Cancellations and fast re-matching
A driver cancels — now what?
A driver accepts a match, then cancels (traffic, changed their mind, a better offer). The rider is now waiting with no driver at all.
Detect the cancellation immediately and re-queue the rider into the next matching window with priority (they've already waited once) rather than making them submit a fresh request. The freed driver simultaneously becomes available again for the same or the next window — cancellations are just another input to the ongoing batch-matching loop, not a special, separately-handled case.
Why this piece earns its place
Re-queueing is the right mechanism and it needs one guard, because as described it quietly pays for cancelling. If a cancelled driver drops straight back into the pool and the next solve ranks on cost alone, the driver who just walked away from a long pickup is immediately eligible for the short one that tempted them — and may even be re-offered the very rider they abandoned, who now gets the same driver back with a longer wait attached. So exclude a cancelling driver from that rider’s candidate set for the re-match, and record the cancellation against the driver rather than treating it as a free event; a marketplace works out which behaviours are profitable much faster than you would like. The word priority on the rider side wants pinning down too, because it should not arrive here as a second mechanism. Express it as time already spent: fold the wait that preceded the cancellation into the accumulated-wait term the objective is already carrying, rather than raising a separate re-queue flag the matcher consults before it solves. Two independent things that both decide who stops being skipped will eventually disagree about the same rider, and whichever one shouts louder wins for reasons nobody wrote down — and neither can be tuned without moving the other. One term, one weight, and a cancellation simply makes a rider expensive to defer for the same reason a long wait does.
Step 7 · Fairness for drivers
Don't always pick the single best driver
Pure cost-minimization always routes requests toward whichever driver has the best ETA. Over time, that concentrates rides (and earnings) on drivers who happen to sit in high-density pockets, while others in lower-demand areas stay idle far longer. Is "always pick the mathematically best match" actually the right objective?
Pure ETA-minimization concentrates rides on a few well-positioned drivers. Is that the right objective for the marketplace?
Optimizing ONLY for rider wait time, with zero regard for driver earnings distribution, degrades marketplace health over time: drivers who consistently get few rides leave the platform, which eventually hurts riders too by shrinking overall supply.
Adding an idle-time factor to the cost function is a deliberate, small trade of pure efficiency for marketplace health: riders experience a negligibly different wait on average, while driver earnings and idle time distribute more evenly, keeping more drivers engaged and online long-term — which ultimately benefits riders too through better overall supply.
Ignoring ETA entirely in favor of pure randomness would make wait times unpredictably bad for riders — fairness should be a MODERATING factor on top of ETA-based cost, not a replacement for it.
Blend the matching cost function with an idle-time fairness factor, tracked in an Idle-Time Ledger per driver: a driver who's been waiting longer gets a small cost-reduction bonus in the matcher's objective, so they occasionally win a match over a marginally-closer driver who just dropped off a rider. This is a deliberate, bounded trade of pure per-ride efficiency for long-run marketplace health.
Why this piece earns its place
A ledger is only as good as what it counts, and idle time can be earned two very different ways. One driver is idle because the matcher kept choosing someone marginally closer — exactly the person this term exists to protect. Another is idle because they parked in a quiet residential pocket where no requests originate, and a bonus that grows with raw clock time rewards them for staying there. Pay that long enough and you have taught part of the fleet to wait where demand is not, which is the opposite of what a dispatch system wants its supply doing. So accrue idle time where being idle was the system’s decision rather than the driver’s: count it while a driver sits inside an area that actually produced requests they could plausibly have been offered, and slow or stop the clock where there was nothing to lose. Cap the bonus as well, so a long idle streak cannot outweigh the ETA term outright — this factor is meant to break ties between comparable drivers, not to send a rider the car on the far side of town.
What the new pieces do
- Idle-Time Ledgerdata
- Tracks how long each driver has been idle, feeding a fairness factor into matching so earnings and offers don't concentrate on the same few drivers.
Step 8 · The sharp edges
Surge floods, GPS drift, and no-shows
Real-world stress tests: a sudden massive demand spike (handled by batching, from Step 4), noisy or drifting GPS signal producing bad ETA estimates, and a matched driver who never actually shows up.
GPS drift is dampened by smoothing location updates (discard implausible jumps, weight recent pings) before they feed the geo index, so a single noisy ping doesn't send a driver on a phantom route. A driver no-show is detected by a timeout on pickup confirmation, which immediately triggers the same re-matching path as an explicit cancellation from Step 6 — the rider is re-queued with priority rather than left stranded indefinitely.
Why this piece earns its place
The no-show timeout looks like a constant and should not be one. A wait that clearly means abandonment at a downtown curb is unremarkable in an airport queue or a stadium lot, where crawling to the pickup point legitimately takes a while, so one global number either strands curbside riders or fires constantly wherever pickups are slow by design. We already computed an honest, local number in Step 2: the predicted pickup ETA. Judge lateness against that estimate plus a margin and the timeout adapts to the geography for free. The two failure directions are not symmetric either. Fire late and a rider waits on someone who was never coming. Fire early and you burn two drivers on one ride and hand the rider a fresh, longer wait while their original driver was pulling around the corner — a worse outcome than the one being fixed. So before declaring a no-show, ask the thing the geo index already knows: if the matched driver’s position is still closing on the pickup point, they are late, not gone, and the right response is to say so, not to re-match.
You did it
You just designed a ride-matching engine.
Everything you assembled, in order
- Straight-line distance is a bad proxy for real travel time — a proper routing/ETA service is the true cost function for matching.
- Matching greedily, one rider at a time, is provably suboptimal — batching a short window and solving it as an assignment-optimization problem produces a better overall outcome for a negligible latency cost.
- Surge pricing is a genuine market-clearing mechanism: it rations demand AND pulls additional supply toward a shortage, which pure matching algorithms can't do on their own.
- Driver location ingestion is a write-heavy workload, unlike most search/matching read paths, and needs to be designed and partitioned accordingly.
- Cancellations and no-shows are handled by re-queueing into the same ongoing batch-matching loop, not a bespoke exception path.
- A pure cost-minimizing objective concentrates rides on well-positioned drivers — blending in an idle-time fairness factor trades a little efficiency for a healthier, more evenly-utilized driver base.