Matching Systems

A matching system takes two sides and connects them. Riders and drivers. Diners and delivery partners. Buyers and sellers. It sounds like a database join — SELECT closest driver, assign, done — and that's exactly the intuition that's going to get you into trouble. The join is the version of the problem that fits on a whiteboard. The version that fits in production is a different animal wearing the same fur.

Here's what actually has to happen at Uber's scale: 5 million ride requests a day, spread across hundreds of cities, each one needing a driver within about 10 seconds — or the rider closes the app and flags down a cab, and you've lost both the fare and a little of their faith that the app works. The join model is fine at a thousand requests a day: load your riders, load your available drivers, join on proximity, assign the closest, go home. At 58 requests per second — which is what 5 million a day works out to — that model falls apart at the first full-table scan. And the location data feeding the join is stale by the time you read it, so it falls apart a second time, for a second reason, before you've even finished diagnosing the first.

Strip away the domain and the core is this: two pools of entities are changing continuously, and you have to produce valid pairings faster than the pools themselves change. The difficulty arrives from three directions at once — scale (too many entities to iterate naively), geography (location decides validity, and location won't hold still), and fairness (someone has to define "best," and that definition has consequences at scale that never show up on the whiteboard). Solve one and you've touched neither of the others. The honest move is to constrain all three at the same time and accept that you've built something provably suboptimal — just good enough, fast enough, consistently enough, and never more than that.

This is also the most consequential code at Uber, and it's worth being blunt about why. Every dollar of driver income, every rider who stays or leaves, every surge multiplier flows through match quality. When the matching algorithm started de-prioritizing drivers with low acceptance rates in 2017, driver income fell for specific people in specific neighborhoods — at a scale large enough to attract regulators. Nothing crashed. No alert fired. The system was working precisely as designed. "Best match" had simply turned out to be a value judgment encoded in a ranking function, wearing the costume of an optimization problem. That costume is the thing this chapter is really about.

So we'll cover not just how matching works, but what each design decision quietly commits you to:

• Why matching a 1M-driver pool against 5M daily requests needs spatial indexing, not a cleverer query
• How geohash partitioning shrinks the problem to something tractable — and how zone boundaries sabotage match quality at the edges while every dashboard stays green
• The race condition living in the gap between "driver is available" and "driver is assigned," and why it's nastier than it looks
• What Uber actually built, what Swiggy bolted on top, and why food delivery is approximately one more state machine than anyone signed up for
• When a real matching engine is the right call, and when you're building one for a problem you don't have yet

Three problems make up the matching challenge. They're easy to state one at a time, which is the trap — because in production they arrive together, and progress on one routinely makes another worse.

The Scale Problem

Uber has roughly a million active drivers worldwide. On a busy Friday night in New York alone there are tens of thousands of trip requests in flight at once. The naive algorithm — for each request, iterate every available driver, compute the distance, take the closest — is O(drivers × requests), and that's fine right up until it isn't. At a thousand drivers and ten requests it's instant. At 50,000 drivers in one city and 5,000 concurrent requests, you're doing 250 million distance computations per matching cycle. At a 100ms cycle time, which is already aggressive, that's 25 seconds of arithmetic — and the rider is watching "finding your driver" spin while a driver three blocks away takes a fare from a competitor.

The reason a sharp engineer ships the naive version anyway is that it works beautifully in the demo. It works in the pilot city. The quadratic term is invisible at small N — it hides inside a loop that returns in microseconds — and it stays invisible right up until the city fills in, at which point it doesn't degrade gracefully, it falls off a cliff. Nobody profiles a nested loop that returns instantly. That's the whole problem with O(n²): it's not slow when you write it, only when you succeed.

The Geo Problem

Distance matters, but distance in a city is not Euclidean. A driver half a mile away across a river with no nearby bridge is worse than a driver 0.8 miles away on your side of the water. The haversine formula gives you great-circle distance in about 200 microseconds and tells you exactly nothing about the highway median between the driver and the rider. So real systems split it: road-network distance for the final ranking, cheap Euclidean distance for the initial candidate filter. The road-network query is too slow to run against every driver in the pool, but plenty fast against the twenty candidates a spatial filter already narrowed it to.

Here's where a good engineer goes wrong, and it's a tidy little trap: accuracy feels obviously better, so the instinct is to run the accurate, road-network query first and skip the crude approximation entirely. Why filter on a distance you know is wrong? Because the accurate query is two orders of magnitude more expensive, and run against the full pool it's the thing that blows your latency budget. The crude filter isn't a compromise you tolerate — it's the load-bearing wall. Get the sequencing backwards and you've built a matching engine that is technically correct and operationally useless, which is a category of system that passes every unit test and fails every rider.

The Fairness Problem

"Match the closest driver" sounds fair until you're the driver. Park in a quiet residential neighborhood and you'll watch request after request route to someone downtown, because there is always a closer driver near the rider, and "closest" means you never win. So you add acceptance rate to the ranking, penalizing drivers who decline — and you've just invented a different unfairness, because the drivers declining rides into low-surge dead zones are making a perfectly rational economic decision, and your ranking function has decided to punish them for it.

The fairness problem has no engineering solution. It has a product solution — fair to whom, measured how? — and then an engineering implementation of whatever that product decision turns out to be. The engineering half is the easy half. Engineers forget this constantly, because the problem is handed to them dressed as an optimization ("maximize match quality"), and optimization problems have right answers. This one doesn't. It has trade-offs with names and addresses attached, and we'll come back to that when the regulators do.

The foundation is two live pools: active ride requests and available drivers, both indexed and queryable in real time.

The request pool holds every ride that hasn't been matched or cancelled — pickup location, request timestamp, rider preferences, and an SLA deadline, the moment the request expires and the rider is written off as lost. The driver pool holds everyone logged in and available — not mid-trip, not in the cooldown that follows a decline — with their last known location, vehicle type, acceptance rate, and average response time.

The engine runs as a loop: for each unmatched request, find the best candidate, attempt the assignment, handle success or failure, advance. In practice "loop" is a polite fiction — requests and driver-state updates arrive as a continuous stream, and the engine processes them as they land rather than in tidy batches.

The whole game is hidden in the word "find." If "find" means scanning the full driver pool per request, you're back to O(drivers × requests) and the previous section's cliff. The trick is that you never query the full pool. You constrain to a small candidate set first — that's what spatial indexing buys you — and rank only those. The pool is the abstraction you reason about; the index is what makes it survive contact with traffic.

The race condition lives right here, and it fires far more often than the textbook model suggests. Two requests query the pool in the same instant and both get the same driver as their top candidate. Both fire an assignment. One wins; the loser gets a conflict rejection — not from the driver, who never saw it, but from the system catching the collision — and reruns candidate selection, now minus the driver who just got taken. Every cent of that retry shows up in your p99 matching latency.

The first time I watched this in production I was sure it was a bug in the lock. It wasn't. The mental model that betrays you is treating the race as a coincidence — two requests, same microsecond, same driver, surely one in a million. In a dense downtown it's nothing of the kind. Everyone within a few blocks wants the same three nearby drivers, so the "coincidence" isn't an edge case, it's the steady state. The collision rate isn't noise on top of the system; on a Friday night in a downtown core, it is the system. That reframing — from "rare race" to "the common case wearing a rare-race disguise" — is the one that changes how you build the thing.

Solutions run from optimistic locking (fire the assignment, expect the occasional collision, retry fast) to distributed lease acquisition (claim the driver before you build the ranking, release the lease if the assignment doesn't land in time). Uber runs a variant of the latter at scale; the lease bookkeeping costs something you can see in the instrumentation, and they pay it gladly rather than eat retry amplification under high concurrency. Neither option is clean. One is faster, one is more predictable, and which one is right depends on your concurrency profile — which is a thing you learn from production, not from a design review.

The insight that makes large-scale matching tractable is almost embarrassingly simple: a driver five miles away in crosstown traffic is not a candidate, and neither is a driver two neighborhoods over when there are two within a block. You can throw out 99% of the driver pool before the ranking function runs a single comparison, on geography alone. The expensive question ("who is the best match?") only ever gets asked of a tiny, local set.

Geohash is the standard tool for the throwing-out. It encodes a latitude/longitude pair as a string where shared prefixes mean geographic proximity. At precision 6 each cell covers roughly 1.2km × 0.6km; at precision 5, about 4.9km × 4.9km. You pick precision by your matching radius — level 6 for urban ride-sharing, level 5 for the suburbs.

The engine keeps a Redis geo index of available drivers, refreshed on every location ping. A request comes in, you compute its geohash, query the matching cell plus its eight neighbors — nine cells, so a rider standing near an edge isn't cut off from the driver just across the line — and you've got a candidate set. In dense Manhattan at level 6 those nine cells span about 11 km² and might hold a few hundred available drivers. You rank the hundreds. You never touch the million.

The zone-boundary problem is subtler than it first looks, and it's the kind of thing that surfaces as a mystery. A geohash grid is a hard partition, and the best driver for a request might be 1.3km out — just past the nine-cell query — while the driver you actually match is 1.2km out but five traffic lights less convenient. The grid is a lie you tell the problem to make it tractable, and like every useful lie it has edges, and the edges are where it bites. Most engines paper over it with a fallback: if the nine-cell set comes back too thin (fewer than N candidates, or none above some quality bar), expand to a 5×5 neighborhood and re-query. That costs latency, because you've now run two queries where you budgeted for one. Worse, the expansion threshold is a tuning knob that drifts out of calibration every time city density shifts — a stadium empties and pulls drivers out of their usual cells, a new tower opens, or a neighborhood gentrifies faster than anyone updates the config. The grid is static. The city is not. That mismatch is permanent, and managing it is somebody's actual job.

Both pools are streams. Requests arrive as events. Driver positions arrive as events — GPS pings every few seconds off the driver's phone. An engine that treats these as static snapshots is building on a lie it told itself: the driver who sat at location X when you queried is at X plus fifty meters by the time your assignment reaches their phone.

A Kafka-shaped architecture handles this without drama. Requests publish to a requests topic; driver positions publish to a driver-locations topic. The engine consumes both, keeps a Redis geo index of current positions (rewritten on every location event), and for each request runs a geo query against Redis at match time. The answer it gets back is "where drivers were as of their last ping" — close to now, never exactly now.

The staleness is real, chronic, and built in. GPS pings every 4 seconds; publishing adds ~500ms; the Redis write adds ~100ms. By the time a request reads a driver's position, the engine can be working off data that's 5 seconds old. At 30 km/h that's about 40 meters. For most matches, 40 meters is noise no one notices.

And then there's the failure mode nobody designs for, because it runs exactly opposite to intuition: driver state is freshest when it matters least, and stalest when it matters most. Stuck in heavy traffic, a driver barely moves, so 5-second-old data is nearly perfect — and it doesn't matter, because they're not going anywhere. The moment they clear an intersection and accelerate is the moment their position changes fastest and the moment a lot of phones throttle GPS to save battery. So the data degrades precisely when the driver is moving precisely when accuracy matters. The engine that doesn't account for this will, under load, hand out assignments that die at the confirmation step — the driver glances at the map, sees the pickup is now behind them, and declines. The tell is in the metrics, if you split them: watch assignment-confirmation failure rate as its own signal, separate from match latency. When confirmation failures climb and latency doesn't, you're not looking at an algorithm problem. You're looking at stale location data, and no amount of ranking cleverness will fix a position that was wrong before the ranker ever saw it.

Latency vs. Match Quality

The most important trade-off in matching is also the one nobody likes to say out loud: faster matching produces worse matches.

The optimal match — accounting for road-network distance, driver wait time, platform-wide utilization, fairness across driver demographics, and coordinated optimization across every concurrent request at once — is NP-hard. The literature exists. The algorithms exist. They are also completely beside the point, because computing a provably optimal match under all those constraints at Uber's scale would outlast the rider's patience by a margin wide enough that no one seriously tries. So you approximate. Uber targets end-to-end matching under 10 seconds, and inside that window the goal is the best match you can compute, not the best match that exists. The 10-second number is set by product, not engineering — past it, rider abandonment climbs hard — and the algorithm is simply whatever fits in the box.

Here's the finding that surprises people every time, because it runs against the obvious instinct: feeding more candidates into the ranking stage does not reliably improve match quality. The instinct says give the ranker more to work with and it'll find something better. The reality is that if candidate selection hands you 200 drivers instead of 20, the extra 180 are almost all worse — they dilute the ranking signal, they cost latency in the ranking step, and they raise the odds that some other concurrent request is fighting you for the same top few candidates. There's a sweet spot: enough candidates for a real choice, few enough to rank cheaply and claim cleanly. Uber found their number by burning years of production data on the question. For a new system it's a parameter you discover the hard way, and it moves with city density and time of day, so you never quite stop discovering it.

Match quality versus latency isn't a trade-off you settle at design time and forget. It's a dial somebody tends forever — and whoever owns the matching service owns that dial, whether or not it's in their job description.

Uber: Matching at Scale

Uber's architecture is built around a single constraint — sub-10-second end-to-end from request to driver acceptance, at millions of requests a day — and once you see that constraint, every other choice reads as a consequence of it.

A request hits a frontend service, gets validated, and publishes an event to Kafka. The matching engine — a custom stateful service, not off-the-shelf Flink, though the Flink concepts apply throughout — consumes it. It queries the Redis geo index for drivers in the relevant geohash cells, pulls a candidate set, and runs the ranking function. The ranker weighs three things: ETA from real-time traffic (not straight-line distance), driver acceptance rate (penalizing chronic decliners, partly to keep people from gaming the system), and a wait-time bonus for drivers idle the longest (the fairness thumb on the scale). Out comes an ordered list.

The engine offers the assignment to the top candidate with a 15-second acceptance window. Accept, and the match commits — both pools update, the rider's app lights up with the driver's location. Decline or time out, and the engine drops to the next name on the same list — it deliberately does not re-query Redis, because re-querying is slower and a candidate set that's a few seconds old is still good enough. Burn through the whole list with no taker and the engine widens the search radius and runs it again.

The failure mode Uber's own engineers have written about is position drift during demand spikes, and it's a small masterpiece of bad timing. A concert or a stadium game lets out; every driver in the area starts catching assignment offers at once; acceptance windows stack up; drivers sit on multiple live offers the lease system is supposed to prevent and mostly does, except at the edges. Meanwhile the GPS ingestion pipeline backs up under the same load spike, so the gap between a driver's Redis position and their real position widens — which means match quality degrades exactly when demand, and the cost of a bad match, peaks. The fix is the counterintuitive part: it isn't a smarter algorithm. It's scaling the GPS ingestion pipeline harder so positions stay fresh under the spike. The bottleneck wasn't where anyone instinctively looks — in the matcher — it was upstream, in the boring plumbing that keeps the map honest.

One principle is worth tattooing somewhere visible: Uber does not match for global optimality. It matches for local sufficiency — the best available match for this request, right now, from this candidate set. A coordinated optimizer solving all concurrent requests together would, in theory, post better aggregate numbers (lower average ETA across everyone). It also misses the latency budget by orders of magnitude, so it stays in theory. Thousands of local-sufficiency problems solved in parallel, fast, add up to an aggregate that's good enough to run a company on. The globally optimal solution is a conference paper. Local sufficiency is a business.

Swiggy: Food Delivery Matching

Swiggy's problem looks like Uber's from across the room — order comes in, find a nearby delivery partner, assign — and it is, plus one restaurant, and that one restaurant turns out to matter enormously.

Uber's driver is available the instant they accept; pickup is immediate; the engine models three driver states — available, in-trip, offline — and that's the whole story.

Food delivery adds a restaurant as a third party with a state machine of its own. The restaurant has to accept the order, then cook it. The delivery partner mustn't show up before the food is ready — early means they stand around bleeding idle minutes and eventually quit the platform, which is an economics problem — and mustn't show up too late either, because cold food means refunds and a restaurant that stops answering your calls. So the engine now has to model, simultaneously: order state (received, accepted, in-preparation, ready), restaurant prep time (which varies by dish, by order size, by kitchen load, and by whether the head cook is having a good evening), and the partner's travel time to the restaurant — and then land the partner at the door inside some tolerable window around food-ready.

This is a fundamentally different optimization than ride-sharing, and it's worth being precise about why. Uber matches on spatial proximity plus a couple of smooth, continuous variables. Swiggy matches on spatial proximity plus a discrete state machine with an unreliable clock. The restaurant turns a continuous problem into a scheduling problem where the most important input — when is the food ready — is a guess. That prep-time estimate is its own machine-learning model running alongside the matcher, and when it's wrong by fifteen minutes — routine, the day a catering order lands mid-service — the partner arrives early or late, and both have a price that lands on the P&L.

The practical upshot: Swiggy's matching has more failure modes than Uber's, and most of them are invisible to the matching engine itself. The restaurant rejects the order after a partner's already been dispatched. The prep estimate blows up because a sixteen-top just sat down. The restaurant shows "accepting orders" while the kitchen quietly closed early. Each needs a fallback — reassign, cancel, notify — that simply doesn't exist in the clean two-sided problem. So the thing Swiggy calls a "matching engine" is really a matching engine plus an order-orchestration layer babysitting the unhappy paths. In most org charts those two live on different teams, which is the soil where the more memorable production incidents grow — the matcher did exactly what it was told, the orchestrator did exactly what it was told, and the order still ended up on the floor between them.

Redis Geo is the workhorse for storing driver positions and pulling spatial candidates. GEOADD stores lat/lon keyed by driver ID; GEOSEARCH returns members inside a radius or box. At Uber's scale a Redis cluster holds millions of positions and serves thousands of geo queries a second, all on a sorted set using geohash scores, which is what makes range queries fast and memory-cheap. The catch to keep an eye on: geo commands run O(N + log M), N being the result size and M the total members. Narrow radii keep N small. Widen the radius under sparse supply and N grows — so each query gets more expensive at exactly the moment the system is already straining, which is the kind of feedback loop that turns a bad night into an outage. Monitor per-query geo latency separately from overall Redis latency; they part ways in interesting and educational ways during a demand spike.

Kafka carries the two streams into the engine: requests and location updates. The request topic is usually partitioned by geography — by city, or a coarse geohash prefix — because matching is local and New York's engine has no use for Chicago's requests. Location events are the firehose: a million drivers pinging every 4 seconds is 250,000 events a second, and partitioning them carelessly gives you a hot shard and a bad time. Partition by driver ID and it spreads cleanly; the real work is making sure a city's engine can consume across all those partitions without re-partitioning on ingest.

Flink (or a hand-rolled stateful processor) runs the matching logic. Stateful stream processing is the right primitive because the engine has to carry state across events — the live request pool, per-driver assignment history, retry counts on rejected offers — and Flink's checkpointing means a restart doesn't drop in-flight requests on the floor. One sharp edge worth saying plainly: "exactly-once," in matching, means "at most one driver assigned per request," and that requires your assignment step to be idempotent regardless of what the framework promises. The framework keeps you from processing an event twice. It does precisely nothing to keep you from assigning a driver twice if your own assignment logic isn't idempotent — that part is on you, and the framework's marketing will not save you.

1. Zone boundary analysis: Given a city partitioned into geohash level-6 cells, design the logic that decides whether a failed primary match (no viable candidates in the nine-cell query) should expand to a 5×5 neighborhood or wait for supply to recover in the primary zone. What threshold triggers expansion? What are the latency implications of each path? How does your answer change at 3 PM versus 11 PM on a Friday?

2. Race condition protocol: Sketch the distributed lease protocol that prevents double-assignment — two concurrent requests both picking the same driver. What happens when lease acquisition itself fails (a network partition between the engine and the lease coordinator)? How does the engine recover without leaving the driver stuck in a "claimed but not assigned" limbo that locks them out of every other ride?

3. Staleness measurement: Design a metric that quantifies driver-location staleness at query time. How do you tell "the ping is 5 seconds old because ping frequency is low" apart from "the ping is 5 seconds old because the ingestion pipeline is backed up under load"? What alert threshold would you set on each, and what different remediation does each imply?

4. Swiggy extension: Add restaurant state to the matching model. The restaurant has three operational states: accepting, at-capacity (still accepting, but prep times stretch), and closed. How does this change the matching loop? What happens when a restaurant flips from accepting to at-capacity after a delivery partner has already been dispatched toward it?

5. Fairness auditing: Given a week of match data — pickup location, driver assigned, driver wait time at assignment, driver acceptance rate, driver home neighborhood — write the query that surfaces whether the ranking function systematically produces worse outcomes for drivers in low-density neighborhoods. What does "worse" even mean here? And how do you control for the fact that low-density areas also generate fewer requests in the first place?

← Chapter 7 (Stream Processing): The request topic and the location topic feeding the engine are textbook Kafka consumers, and the stateful processing that maintains both pools maps straight onto the patterns from that chapter. The failure modes — lost events, duplicate assignments, out-of-order location updates — are stream-processing failure modes wearing domain-specific clothing. If Chapter 7 taught you to flinch at "we'll just process each event once," that flinch is correct here too.

→ Chapter 15 (Dynamic Pricing): Once a match commits, the fare needs a price. Pricing reads the same supply-demand signals the matcher uses — driver density per zone, request rate per zone — and turns them into a multiplier. Which means the two engines have to agree on which zone a request belongs to. Let their geohash conventions drift apart — one on level 6, one on level 5, or both on level 6 with different origin conventions — and you get surge anomalies that are genuinely hard to explain to a rider staring at a $40 quote for yesterday's $12 ride. It's a real class of bug, and the cruel part is it ships clean: it fails no tests, because both engines are individually correct and only disagree at the seam.

← Chapter 12 (Saga Pattern): The matching flow — request, assignment, acceptance, confirmation, or fallback — is a saga. Every step can fail, and every failure needs a compensating action. The engine's retry loop is a saga orchestrator that hasn't been told that's what it is. Learn the saga failure modes and matching's stop surprising you; learn matching's and you're warmed up for the gnarlier sagas in Chapter 12.

The matching problem is deceptively simple to state: find the best pair. The trouble is that "best" is a value judgment, "find" is an engineering problem at scale, and "pair" hides a race condition in a distributed system. Most systems that claim to have a matching engine have a nearest-neighbor query wrapped in optimism — and that's genuinely fine, right up until the traffic spike arrives, the geohash boundaries start mattering, and the position data goes stale at the worst possible moment, all on the same Friday night, which is of course when they always arrive together.

Next: Chapter 15 — Dynamic Pricing