Designing Uber Dispatch System

Dispatch is an assignment problem under a clock

State the problem precisely before designing anything, because the imprecise version leads directly to the wrong architecture. At any instant there is a set of open requests and a set of available drivers, and the system must produce a mapping between them that is good by some objective, using information that is already stale, before the requests expire. Three properties in that sentence do the damage.

First, it is a mapping, not a series of lookups. The quality of an assignment depends on the other assignments made alongside it, which is exactly the property that a per-request "find me the nearest driver" API destroys.

Second, it runs under a clock. A rider staring at a spinner has a tolerance measured in seconds, and that tolerance is the entire latency budget for reading supply, scoring candidates, solving the assignment, offering it, and waiting for a human to tap accept. The human tap is usually the largest term, which is worth internalising early: shaving milliseconds off the index query optimises the wrong part of the budget.

Third, the inputs are stale by construction. A driver's last reported position is some seconds old and the driver has moved since. No amount of consistency machinery fixes this, because the staleness is in the physical world, not in your replication lag. Dispatch is therefore a system that must make defensible decisions on knowingly wrong data and correct them afterwards — a framing that shapes the state machines later in this article far more than it shapes the storage layer.

The location write path is the unglamorous half

Every driver app on shift reports its position on a timer. Multiply a modest cadence by the number of drivers on the road in a large market and you have a sustained write rate that dwarfs the request rate by orders of magnitude — the ratio, not any absolute figure, is the design fact. Ninety-nine percent of those writes will never be read by anyone, because the driver was not near a request when they landed.

That asymmetry rules out the obvious implementation. Writing each ping as a durable row in a transactional store buys you durability for data that is worthless within seconds and expensive to index. The shape that works is an in-memory, TTL-bearing view of current supply — last known position per driver, keyed for spatial lookup, expiring on its own if the pings stop — with the raw stream teed off to a log for the things that genuinely need history: billing disputes, fraud review, ETA model training, and map inference. That is a textbook split between a hot serving cache and an append-only event log, and dispatch is one of the cleanest examples of why the split exists.

Ping cadence itself is a real knob with real costs on both sides. Faster reporting means fresher supply and better ETAs, at the price of write amplification and mobile battery and data usage — which drivers notice and complain about. Slower reporting saves all of that and degrades every downstream decision. The usual resolution is not a single number but adaptive cadence: report frequently while moving in a dense area or while on an active trip, back off sharply while stationary or idle, and always send an immediate ping on state transitions. Note that the connection carrying those pings is itself a long-lived one with its own liveness and backpressure problems; that tier is developed in the chat system article and is not repeated here.

Indexing supply — resolution is a dispatch decision

The mechanics of turning coordinates into an index key — geohash prefixes, S2 cells on a Hilbert curve, quadtrees, or the hexagonal tiling of the published H3 library — are covered properly in geo proximity search, including the seam problem and why you always query a ring of neighbours rather than a single cell. Read that for the geometry. What is specific to dispatch is that cell resolution is not one choice but several, made for different consumers.

The supply lookup wants a resolution where one cell plus its immediate ring covers roughly the radius from which a driver could plausibly reach the rider — small enough that the candidate set stays bounded, large enough that the ring provably covers the search area. The demand and pricing aggregations want a coarser resolution, because a supply-demand ratio computed over a handful of drivers is noise, not signal. Dispatch-time debugging and operational dashboards want coarser still. Systems that pick one resolution to serve all three end up with a matching layer that is either too broad to be fast or aggregates that flap.

The failure mode to design for is density skew, and it is severe here because vehicles cluster exactly where demand clusters. A cell covering a stadium at closing time or an airport queue holds orders of magnitude more drivers than the cell next to it, so it is simultaneously the hottest read key, the hottest write key, and the largest candidate set to score. The mitigations are the standard ones — finer resolution in dense regions, capped candidate sets, and the techniques in hot-key mitigation — but the operational point is that dispatch quality degrades first in your most valuable markets, so a load test on uniform synthetic supply proves nothing.

Why nearest driver is the wrong answer

Greedy nearest-driver is the design everyone writes first and it is wrong in a way that does not show up in unit tests. Consider two requests arriving within a second of each other and two available drivers. Serving the first request greedily takes the driver who happens to be marginally closer to it — who may also be the only driver within reach of the second request. The first rider saves a few seconds; the second waits minutes or gets nothing. Total wait went up because a locally optimal choice was made without reference to the other choice on the table.

The correct formulation is the classic assignment problem: given a cost for every viable (request, driver) pair, choose the set of pairings that minimises total cost subject to each driver and each request being used at most once. This is weighted bipartite matching, solvable exactly in polynomial time — the Hungarian method is the textbook algorithm, and a min-cost-flow formulation handles the same problem with more flexible constraints. The sizes involved make this tractable: after the geospatial filter, a batch is tens of requests against tens or hundreds of candidate drivers within a single dispatch region, not a global problem.

What goes into the cost is where the product lives, and distance is only its crudest term. A defensible cost function is a weighted combination of pickup ETA, not straight-line distance; the probability that this driver accepts this offer, since an assignment that gets declined costs a full round of latency; how long the request has already waited, so an aging request outbids a fresh one; and supply-shaping terms such as avoiding pulling the last driver out of a thinly covered area. Each term you add is a policy decision that someone will have to defend to drivers or regulators, so keeping them explicit and separately weighted beats burying them in a single learned score.

The batching window and what it actually buys

Batch matching only helps if there is a batch, which means the system must deliberately wait before deciding. That waiting is the single most counter-intuitive design choice in dispatch: you make every individual request slower in order to make the average rider better off.

The trade-off is clean in both directions. A longer window accumulates more requests and more drivers, so the assignment solved over it is closer to globally optimal and more likely to find a genuinely good pairing rather than an acceptable one. A shorter window gets the rider an answer sooner and reduces the chance that the supply snapshot has gone stale — drivers move and go offline during the window, so a match computed over a long window is solving yesterday's problem with more precision. Windows on the order of seconds are the region where those pressures balance for ride-hailing; the exact value is an empirical tuning question per market and per time of day, not a constant, and treating a published figure as one is how designs get cargo-culted.

Two refinements matter in practice. The window should be adaptive rather than fixed: when supply is abundant relative to demand, there is nothing to optimise and waiting is pure harm, so collapse toward immediate dispatch; when supply is scarce, the window earns its keep. And the window must be bounded on the other end by request expiry — a batch that has not been solved by the time riders start cancelling has failed regardless of how good its matching would have been.

ETA is the cost function, and it is a dependency

Every interesting cost term reduces to a time estimate, which makes the routing service dispatch's most load-bearing dependency and its most under-appreciated one. Straight-line distance is a trap in exactly the places that matter: a driver two hundred metres away across a river, a motorway with no exit, or a one-way system is not two hundred metres away in any sense the rider experiences. Real dispatch scores on estimated travel time over the road network, adjusted for current traffic.

The volume is the problem. A batch of R requests against D candidate drivers needs up to R × D estimates, all inside a window measured in low seconds, and a full route computation per pair is not affordable. The standard resolutions are layered: compute cheap lower-bound estimates first and prune candidates that cannot possibly win, then spend real routing calls only on the survivors; precompute and cache travel times between cell centroids so that most pairs are answered by a lookup with a small correction term; and refresh those matrices on a cadence tied to how fast traffic actually changes. This is a caching problem with an unusually explicit staleness budget — the cached number is wrong the moment it is written, and the design question is only how wrong you can tolerate.

Because the routing service is on the critical path of every dispatch, it also needs an answer for when it is slow or down. Degrading to haversine distance produces worse matches but keeps the marketplace running, which is almost always the right call — and it should be an explicit, monitored mode rather than an accident of a timeout default.

Offer, accept, decline — the loop is a state machine

Solving the assignment does not dispatch anything. It produces a proposal, and every proposal has to survive contact with a human who can decline it, ignore it, or lose connectivity while it is on screen. This is the point where a design that modelled dispatch as a function call falls apart, because the operation is not request-response; it is a short-lived distributed protocol with a timeout on each side.

The workable shape is an explicit offer state machine per (request, driver) pair. The matcher reserves the driver — a soft, short-lived hold, not a durable lock — then sends the offer with a deadline. Three things can end it: the driver accepts, and the reservation converts to an assignment; the driver declines, and the driver is released immediately; or the deadline passes with no answer, and the offer expires. Expiry is the case that must be handled first-class, because it is common and because a late accept arriving after expiry is the classic double-assignment bug.

offer: PENDING --accept--> ACCEPTED   (driver committed to request)
                --decline--> DECLINED  (release driver, requeue request)
                --timeout--> EXPIRED   (release driver, requeue request)

late accept on an EXPIRED offer  ->  rejected, driver already released
accept on an offer whose request ->  rejected, request already served
  was matched elsewhere

The reservation should be a lease with a TTL that outlives the offer deadline by a small margin, so a crashed matcher cannot strand a driver as permanently unavailable. That is the general lease-and-fencing-token pattern, and the fencing part is not optional: a matcher that pauses, resumes after its lease expired, and then writes an assignment is precisely the scenario that puts two riders in one car.

Declines and expiries feed straight back into the next batch. A request that has been declined twice should not be offered to a similar driver a third time — carry the rejection history into the cost function, and let the waiting-time term escalate its priority.

Exactly-once dispatch, or at least never twice

Dispatch has an asymmetric correctness requirement that is worth stating plainly: dispatching a request twice is a marketplace incident, while failing to dispatch it is a retryable disappointment. Two drivers arriving for one rider means an unpaid deadhead trip, a support ticket, and a driver who trusts the platform less. So every retry path in the system must be built to fail closed.

The mechanism is ordinary idempotency applied with unusual discipline. The client generates a request identifier when the rider taps, and it survives app retries and reconnects — a retried booking must be recognised as the same booking, not a second one. The assignment write is then a conditional operation on the request's state: commit the assignment only if the request is still unassigned and the driver's reservation is still valid, in a single atomic step. A compare-and-set on a single partition is enough and is far preferable to a distributed transaction on the dispatch path; this is one reason to keep a request and its candidate drivers within one shard.

The notification side is where exactly-once quietly becomes impossible. Telling the driver app about the assignment goes over an unreliable network to a device that may be offline, so the delivery is at-least-once and the app must dedupe on the assignment identifier. Treat "exactly-once dispatch" as exactly-once commitment in the store plus at-least-once delivery with idempotent consumers — the honest decomposition, and the same one the transactional outbox exists to implement: write the assignment and its outbound event in one transaction, publish afterwards, and never try to make the network atomic with the database.

The trip state machine and what hangs off it

Once an offer is accepted the interaction becomes long-running — minutes to hours — and spans several services. The discipline that keeps this manageable is to model the trip as an explicit state machine with a single authoritative writer, rather than as a row that many services update opportunistically.

The states are unglamorous and the value is entirely in their being enumerated: requested, matched, driver en route, driver arrived, in progress, completed, plus the cancellation and failure terminals that carry who cancelled and when, because that determines the fee. Every transition is validated against the current state, every transition emits an event, and the event stream is the input for everything downstream. Legal transitions being written down is what stops a system from billing a trip that was cancelled before pickup, or from letting a GPS glitch mark an arrival that never happened.

Downstream of completion sits a multi-service workflow — fare calculation, payment authorisation and capture, driver earnings, receipts, ratings — that spans systems with no shared transaction. That is the saga pattern: a sequence of local transactions with defined compensations, because a payment capture that fails after the trip has ended cannot be resolved by rolling back the trip. Keeping the trip event log as the source of truth also makes the whole pipeline replayable, which is the practical argument for event sourcing here: disputes and reconciliations arrive weeks later and need to see what the system believed at the time, and read-side views for driver apps, support tools and analytics can be rebuilt independently in the CQRS style. Events that fail to process go to a dead-letter queue rather than blocking the stream, since one poisonous trip must not stop payouts for everyone else.

Surge as a control signal, not just a price

The economics of dynamic pricing are a topic of their own, and the machine-learned side of it is developed in the smart pricing architecture article. What belongs here is narrower and more mechanical: within a dispatch system, a multiplier is a feedback controller whose job is to push a geographic area back toward supply-demand balance, and it should be engineered like one.

The measured error signal is some ratio of open demand to available supply in an area over a recent interval. The actuator is price, which acts on both sides at once: it suppresses price-sensitive demand within seconds and attracts supply from neighbouring areas over minutes. That difference in response times is the whole engineering problem — a controller with two very different lag terms and a noisy sensor will oscillate if you let it react instantly.

The defences are the ones any control engineer would recognise. Smooth the input over a window long enough to suppress noise from small counts. Apply hysteresis so that going up requires a stronger signal than coming down, since a multiplier that flickers on and off destroys trust on both sides. Bound the output, because an unbounded ratio during an outage or a data glitch produces prices that become a news story. Rate-limit how fast it may change. And smooth across space as well as time: a hard multiplier boundary at a cell edge means two riders standing metres apart see different prices, so blend across neighbouring cells rather than stepping. Every one of those knobs is a policy choice, and none of the specific values are universal.

The subtle failure is the feedback loop closing on itself: the multiplier moves drivers into an area, the area's ratio falls, the multiplier drops, drivers leave, and the ratio spikes again. Damping and hysteresis are what keep that from turning into a standing wave, and the diagnostic to watch is not average price but the variance of the multiplier over time in a single area.

Sharding by geography, failing by geography

Dispatch has an unusually convenient partition key. A rider in one city is never matched to a driver in another, so the natural shard is the market — a city or metropolitan region — and almost every dispatch operation is local to one. That is a rare luxury: no cross-shard joins on the hot path, no distributed transaction to commit an assignment, and a batch that fits comfortably in one process's memory. It also means the generic sharding and consistent hashing machinery is mostly unnecessary here; geography already told you the answer.

The trade-off is that markets are wildly unequal — one metro can outweigh dozens of others — so shards must be splittable, and the natural split is finer geography with an explicit rule for requests near an internal boundary. The boundary rule matters: a matcher that only sees its own partition will fail to offer the driver parked fifty metres over the line. Either overlap the partitions so each matcher reads a margin of neighbouring supply, or route boundary requests to a designated owner. Silently missing cross-boundary supply is the same class of quiet, unalerting bug as the geospatial seam problem.

The upside of geographic partitioning is blast radius. A failure in one market's dispatch should not touch another's, which argues for per-region deployment, per-region leadership for whatever must be singular, and regional data stores — the same structure that geo-distributed systems arrive at for latency, and that data-residency law imposes anyway in several jurisdictions. Within a region, the honest position is that the matcher is a stateful component holding a supply snapshot, so plan its restart: it should be able to rebuild that snapshot from the location stream in seconds, and in-flight offers must live in a store that outlives the process rather than in its heap.

Finally, design the degraded mode deliberately instead of discovering it. When the router is unavailable, fall back to distance. When the matcher is overloaded, shrink the batch window toward zero and dispatch greedily — worse matches, but a functioning marketplace. When the region is genuinely over capacity, shed load explicitly by telling some riders no rides are available rather than letting everyone's request time out. A marketplace that answers badly beats one that does not answer.