Design ride-hailing dispatch and geo-indexing
"Design the dispatch system: match riders to drivers in a city with 100,000 active drivers, in under two seconds."
Step 1: clarify (4 minutes)
Is dispatch greedy or batched? The single most consequential question, and most candidates never ask it.
Greedy Each request matched immediately to the nearest available
driver. Simple, low latency, and provably worse: the
nearest driver to request 1 may be the ONLY driver near
request 2, which arrives 200 ms later.
Batched Accumulate requests for a few seconds, then solve an
assignment problem over the whole batch. Better global
outcome (measurably shorter total wait), at the cost of
a few seconds of added latency.
Assume batched with a short window, because it is what the mature systems converged on, and be ready to defend the latency cost.
What is the objective function? "Nearest driver" is not it, and saying so early is a strong signal:
Minimise rider wait? Favours dense areas, starves the suburbs.
Maximise driver utilisation? Favours long trips, riders wait longer.
Maximise completed trips? The platform's actual objective.
Balance supply and demand? Requires repositioning idle drivers, which
is a different problem than matching.
Assume: minimise expected time-to-pickup, weighted by trip completion probability, with fairness constraints so no request waits beyond a bound.
Other clarifications:
Scale 100k active drivers/city, 10k requests/min at peak
= ~170 requests/sec in one city
Location Driver pings every 4 s -> 25,000 location updates/sec
Latency Match within 2 s; the rider sees "finding your driver"
Geography Road-network distance, not straight-line. This matters:
a driver 200 m away across a river is 15 minutes away.
Step 2: capacity math (4 minutes)
Location writes
100k drivers x 1 ping / 4 s = 25,000 writes/sec per city
x 50 cities = 1.25M writes/sec globally
Each ping ~100 bytes -> 125 MB/sec
These writes are HIGH VOLUME, LOW VALUE (superseded 4 s later)
and must NOT go to durable storage on the hot path.
-> In-memory geo-index, with an async durable trail for analytics.
Geo queries
170 requests/sec x 1 spatial query each = 170 queries/sec
Each returns ~20-50 candidate drivers within a radius.
Trivial QPS. The hard part is that the index is being updated
25,000 times/sec WHILE being queried.
-> Read-optimised, lock-free or sharded-by-cell structure.
Matching computation
Batch window 3 s -> ~510 requests, ~2,000 candidate drivers.
Assignment problem: 510 x 2000 cost matrix = ~1M entries.
Hungarian algorithm is O(n^3): 510^3 = 133M operations, ~100 ms.
Feasible. At 5,000 requests per batch it would not be, which is
why the batch is bounded by count as well as by time.
ETA computation
1M cost-matrix entries, each needing a road-network ETA.
A routing engine at ~1 ms per query is 1,000 seconds. IMPOSSIBLE.
-> This is the real constraint, and step 5 is about it.
Memory
100k drivers x ~200 bytes of state = 20 MB per city. Trivial.
The index is small; the compute around it is not.
The number that dominates the design: one million ETA computations per batch, at roughly a millisecond each. Everything in step 5 exists to avoid computing them.
Step 3: geospatial indexing
Three approaches, and the choice matters.
GEOHASH Interleave lat/lon bits into a string. Prefix
length = precision. Simple, and it has a
well-known problem: adjacent cells can have
completely different prefixes near boundaries,
so a naive prefix query misses nearby drivers.
You must query the cell plus its 8 neighbours.
QUADTREE Recursive subdivision, adapts to density: dense
downtown cells subdivide further than rural ones.
Good adaptivity, and rebalancing under 25k
updates/sec is expensive.
S2 / H3 Hierarchical cells on a sphere. S2 uses a Hilbert
curve for locality, H3 uses hexagons.
H3's advantage is worth stating: hexagons have
SIX equidistant neighbours, whereas squares have
4 edge-neighbours at distance d and 4 corner-
neighbours at d*sqrt(2), which distorts every
radius query and every heatmap.
Take H3. The hexagon property is not aesthetic: uniform neighbour distance means "all cells within k rings" is a genuine radius, which is exactly the query dispatch needs.
import h3
# Resolution 9 hexagons average ~0.1 km², roughly a city block.
# The right resolution is the one where a cell holds a workable
# candidate count: too fine and you scan many cells, too coarse
# and you scan many drivers.
RES = 9
class DriverIndex:
def __init__(self):
# cell -> set of driver ids. Sharded by cell so updates to
# different cells never contend.
self.cells: dict[str, set[str]] = defaultdict(set)
self.driver_cell: dict[str, str] = {}
def update(self, driver_id: str, lat: float, lon: float) -> None:
cell = h3.latlng_to_cell(lat, lon, RES)
old = self.driver_cell.get(driver_id)
if old == cell:
return # ~80% of pings: no index change
if old:
self.cells[old].discard(driver_id)
self.cells[cell].add(driver_id)
self.driver_cell[driver_id] = cell
def nearby(self, lat: float, lon: float, rings: int = 2) -> list[str]:
centre = h3.latlng_to_cell(lat, lon, RES)
# grid_disk returns the centre plus all cells within k rings.
# With hexagons this is a genuine radius; with squares it is not.
return [d for cell in h3.grid_disk(centre, rings)
for d in self.cells[cell]]
The if old == cell: return line matters more than it looks. At a 4-second ping
interval and roughly 100-metre cells, most pings do not change the cell, so the index
mutation rate is a fraction of the ping rate. That is the difference between an index
that keeps up and one that does not.
Adaptive ring expansion rather than a fixed radius:
def find_candidates(lat, lon, min_candidates=20, max_rings=5):
for rings in range(1, max_rings + 1):
c = index.nearby(lat, lon, rings)
if len(c) >= min_candidates:
return c
return c # sparse area: return what exists, widen the ETA
Downtown finds 20 drivers in one ring; a suburb needs four. A fixed radius is wrong in both places.
Step 4: the batched assignment
def dispatch_batch(requests: list[Request], window_s: float = 3.0):
# 1. Candidate generation per request. Cheap, spatial only.
candidates = {r.id: find_candidates(r.lat, r.lon) for r in requests}
# 2. Cost matrix. This is the expensive part; step 5 is about
# making these ETAs cheap.
cost = {}
for r in requests:
for d in candidates[r.id]:
cost[(r.id, d)] = compute_cost(r, driver_state[d])
# 3. Solve the assignment. Hungarian gives the OPTIMAL
# assignment minimising total cost, not a greedy one.
return hungarian(cost, requests, drivers)
def compute_cost(request, driver) -> float:
eta = eta_service.estimate(driver.position, request.pickup) # seconds
# The cost function IS the product strategy. Every term is a
# deliberate choice with a business consequence.
cost = eta
cost *= (1.0 - 0.15 * driver.acceptance_rate) # likely to accept
cost *= (1.0 - 0.10 * driver.rating_normalised)
cost += 60 * request.waiting_minutes ** -1 # fairness: an old
# request gets cheaper
if driver.heading_away_from(request.pickup):
cost *= 1.3 # a U-turn is real time
if driver.minutes_until_dropoff < 3:
cost += driver.minutes_until_dropoff * 60 # nearly-free driver
return cost
Why batching wins, concretely:
Greedy, two requests 200 ms apart:
R1 at (0,0): nearest is D_a at 2 min, D_b at 9 min. Assign D_a.
R2 at (0.1, 0): D_a is taken. D_b at 8 min. Assign D_b.
Total wait: 10 min.
Batched:
R1 -> D_b (3 min), R2 -> D_a (3 min).
Total wait: 6 min.
The greedy choice was locally optimal and globally 40% worse.
The Hungarian algorithm gives the provably optimal assignment for the batch, in O(n³). At 510 requests that is around 100 ms, which fits. Beyond roughly 1,000 requests per batch it does not, and the answer is to partition the city geographically and solve each region independently, accepting slight sub-optimality at region boundaries. Saying that shows you know the algorithm's limit rather than just its name.
The batch window is a tuned parameter, not a constant. Longer windows give better matches and worse perceived latency. Dense areas can use a shorter window because good matches are available immediately; sparse areas benefit from waiting. Making the window adaptive to local supply density is a real improvement and is the kind of detail worth volunteering.
Step 5: ETAs, the actual hard problem
One million cost-matrix entries per batch at 1 ms of routing each is 1,000 seconds of compute for a 3-second batch. This is where the design is won or lost.
A four-tier approach:
TIER 1 Haversine (straight-line) distance. ~0.1 µs
Used to PRUNE: any driver whose straight-line distance
exceeds the best-known road ETA cannot possibly win,
because road distance >= straight-line distance.
Removes 80-90% of pairs for free.
TIER 2 Cached cell-to-cell ETA matrix. ~1 µs
Precomputed H3-cell to H3-cell travel times, updated
every few minutes from live traffic. For a city with
20,000 relevant cells at res 9, a full matrix is 400M
entries, so cache only the ~50 x 50 cell neighbourhood
around each cell, which is what dispatch ever queries.
TIER 3 Contraction-hierarchy road routing. ~1 ms
For the top ~20 candidates per request only.
Real road-network path with turn restrictions.
TIER 4 ML-corrected ETA. ~0.1 ms
A learned model over (route features, time of day,
weather, historical residuals) correcting tier 3's
physics-based estimate. Routing engines are
systematically optimistic about pickup because they
ignore parking, one-way streets near the pickup, and
the walk to the car.
def estimate_batch(pairs) -> dict:
# Tier 1: prune. The triangle inequality does the work.
survivors = [(r, d) for (r, d) in pairs
if haversine(r.pickup, d.pos) < r.best_known_eta_m]
# Tier 2: cheap cell-level lookup for the survivors.
coarse = {p: cell_eta_cache[cell_of(p[0]), cell_of(p[1])]
for p in survivors}
# Tier 3+4: exact routing for the top candidates only.
top = take_best_per_request(coarse, k=20)
return {p: ml_correct(road_route(p), features(p)) for p in top}
Result: from 1 million road-routing calls to roughly 10,000, which at 1 ms is 10 seconds across a parallel fleet, so well within the window. The tier-1 pruning using the triangle inequality is the highest-leverage single idea in the design, and it is exact rather than approximate: straight-line distance is a strict lower bound on road distance, so pruning on it cannot discard the true best candidate.
Step 6: the driver state machine, and double-assignment
┌─────────┐ goes online ┌───────────┐
│ OFFLINE ├───────────────►│ AVAILABLE │◄──────────┐
└─────────┘ └─────┬─────┘ │
│ offered │ declined /
▼ │ timed out
┌───────────┐ │
│ OFFERED ├───────────┘
│ (locked, │
│ 15 s TTL)│
└─────┬─────┘ accepted
▼
┌───────────┐
│ EN ROUTE │
└─────┬─────┘
▼
┌───────────┐
│ ON TRIP │
└───────────┘
The OFFERED state with a short TTL lock is the mechanism preventing
double-assignment, and it is the same conditional-update pattern as
ticketing:
-- Atomic. Zero rows means another batch got them first, which is a
-- normal outcome and not an error.
UPDATE drivers
SET state = 'offered', offered_request = $1, offer_expires = now() + '15 s'
WHERE id = $2
AND (state = 'available'
OR (state = 'offered' AND offer_expires < now()))
RETURNING id;
Declines are the failure mode that matters operationally. At a 20 percent decline rate, a batch of 500 requests has 100 unmatched after the first round. The design answer:
Round 1: assign the batch, offer to drivers, wait up to 15 s.
Round 2: re-batch the declined requests with the next arrivals,
with their waiting time now weighting them cheaper.
The fairness term in the cost function is what stops
a request being repeatedly passed over.
Round 3+: widen the search radius, then relax constraints
(allow a lower-rated driver, a further one), then
surface a "no drivers available" state honestly.
Offering to several drivers simultaneously is tempting and wrong: it produces a race where multiple drivers accept, and the losers have driven toward a pickup they will not get, which is the fastest way to destroy driver trust. Sequential offers with a short TTL is the correct trade even though it is slower.
Step 7: failure modes
Location index node fails
-> Drivers re-ping within 4 s, so the index self-heals quickly.
This is the payoff for keeping it in memory and treating
location as disposable: there is nothing to recover.
Routing engine unavailable
-> Degrade to tier 2 (cached cell ETAs), then tier 1 (haversine
with a road-factor multiplier, typically ~1.3x in a grid city).
Match quality drops; dispatch keeps working. Do NOT fail
dispatch because ETAs are unavailable.
Batch solver times out
-> Fall back to greedy for that batch. Worse assignment, and it
ships. A dispatch system that stops dispatching is much worse
than one that dispatches sub-optimally.
Supply collapse (a concert ends, a storm starts)
-> Demand spikes 10x in one area. Matching cannot create drivers.
The levers are surge pricing (reduces demand, attracts supply)
and honest wait-time communication. This is a marketplace
problem, not a dispatch problem, and conflating them leads to
designing the wrong thing.
GPS noise / urban canyon
-> Raw GPS in a downtown core can be 50 m off, which crosses
several H3 cells. Map-match pings to the road network and
smooth with a Kalman filter before indexing, or drivers
teleport across cells and the index churns.
Clock skew on driver devices
-> Timestamp pings server-side. Client timestamps are used only
for ordering within a device, never for cross-device ordering.
City-wide dispatch outage
-> Per-city sharding means a failure is contained to one city.
This is the strongest argument for sharding by city rather
than by anything else.
Step 8: what changes at ten times the scale
At 1 million active drivers per city (which does not happen) or 500 cities (which does):
Cities shard naturally and completely. Dispatch has no cross-city queries, so each city is an independent deployment with its own index, solver and ETA cache. This is the cleanest sharding key in any of these designs and it is worth naming as such: the domain hands you a partition with no cross-partition traffic.
Within a megacity, geographic partitioning of the solver. Solve independently per region, with a boundary-handling pass that allows a driver near a border to be considered by both regions and resolves conflicts by cost. Slight sub-optimality at boundaries, enormous reduction in the O(n³) term.
The ETA cache becomes a streaming pipeline. Cell-to-cell travel times updated every few minutes from live trip telemetry is a windowed aggregation over the trip stream, which is the same shape as the ad click aggregation problem.
Repositioning becomes as important as matching. At scale, the largest gains come from moving idle drivers toward predicted demand before requests arrive, which is a forecasting and incentive problem rather than an assignment one.
Production evidence
Uber's H3 was open-sourced specifically for this workload, and their published rationale is the hexagon neighbour-uniformity property: with squares, four neighbours are at distance d and four at d√2, which distorts radius queries and surge heatmaps.
Uber's published dispatch write-ups describe batching over a short window and solving an assignment problem rather than matching greedily, and report that the batched approach reduces both wait times and unmatched requests relative to greedy.
Google's S2 library is the alternative hierarchical spherical index, using a Hilbert curve for locality, and is used widely for the same class of problem.
Contraction hierarchies (Geisberger et al., 2008) is the algorithmic basis for sub-millisecond road-network routing, and it is what makes tier 3 affordable at all.
Uber's DeepETA work documents the ML-correction layer over a physics-based routing estimate, including that residuals are systematic rather than random, which is the justification for tier 4.
The Hungarian algorithm (Kuhn, 1955) solves the assignment problem optimally in O(n³), and its cubic cost is precisely why batch size must be bounded.
The debate
The case for greedy matching: simple, no batching latency, no solver to operate, and it degrades gracefully. For a small market with sparse supply it is nearly as good, because there is usually only one plausible driver anyway.
The case for batched assignment: provably better global outcomes, measurably shorter total wait, and it makes fairness expressible (a request that has waited gets cheaper), which greedy cannot do at all. The cost is a few seconds of latency and a solver in the critical path.
The case for a market mechanism (drivers bid or choose): driver autonomy, no central solver, and it is what some competitors do. It produces worse global outcomes and much higher variance in rider wait, and it makes the platform's objective unenforceable.
My position: batched assignment with an adaptive window, and the cost function as the place where product strategy lives. The window should be short (2 to 4 seconds) and adaptive to local supply density, because in a dense area good matches are available immediately and waiting only adds latency, while in a sparse area waiting materially improves the match.
The decision I hold most firmly is that "nearest driver" is the wrong objective and saying so early matters. The cost function needs acceptance probability, because assigning to a driver who declines costs 15 seconds and a re-match; it needs a fairness term, because without one a request in a marginal location can be passed over indefinitely while the system reports good average wait times; and it needs the soon-to-be-free driver, because a driver two minutes from dropoff and one minute from the pickup beats an available driver five minutes away.
The engineering decision I would defend hardest is tier-1 haversine pruning. It is exact rather than approximate, because straight-line distance is a strict lower bound on road distance, so it cannot discard the true best candidate. It removes 80 to 90 percent of the cost matrix for essentially free, and it converts an impossible million road-routing calls into a feasible ten thousand. That is the difference between a design that works and one that does not, and it comes from the triangle inequality rather than from infrastructure.
Where I would push back on the framing: matching cannot fix a supply problem. When a concert ends and demand spikes tenfold in one area, no assignment algorithm creates drivers. That is pricing and repositioning, and a candidate who tries to solve it in the dispatcher is designing the wrong system.
Follow-up Q&A
"Greedy or batched, and why?" Batched, with a short adaptive window. Greedy makes locally optimal choices that are globally worse: two requests 200 milliseconds apart can each take the other's best driver, and I have seen that produce roughly 40 percent longer total wait in the simple two-request case. Batching lets me solve an assignment problem over the whole window, which the Hungarian algorithm does optimally in O(n³). The cost is two to four seconds of latency, and I would make the window adaptive to local supply density, because in a dense area good matches are available immediately and waiting only adds latency.
"Why H3 rather than geohash?" Hexagons have six equidistant neighbours. Squares have four edge-neighbours at distance d and four corner-neighbours at d times root two, which distorts every radius query and every heatmap. So "all cells within k rings" is a genuine radius with hexagons and is not with squares, and radius query is exactly what dispatch does. Geohash also has the boundary problem where adjacent cells can have completely different prefixes, so a prefix query silently misses nearby drivers unless you explicitly query all eight neighbours.
"You need a million ETAs per batch. How?" You do not compute them. Four tiers. First, haversine pruning: straight-line distance is a strict lower bound on road distance, so any driver whose straight-line distance exceeds the best-known road ETA cannot win, and that removes 80 to 90 percent of pairs exactly rather than approximately. Second, a cached cell-to-cell ETA matrix refreshed from live traffic, at about a microsecond. Third, real contraction-hierarchy routing for only the top 20 candidates per request. Fourth, an ML correction on top, because routing engines are systematically optimistic about pickup: they ignore parking and the walk to the car. That takes a million routing calls down to about ten thousand.
"What's in the cost function, and why isn't it just ETA?" Because nearest is the wrong objective. Acceptance probability, because assigning to a driver who declines costs fifteen seconds and a re-match. A fairness term weighted by how long the request has waited, because without one a request in a marginal location gets passed over indefinitely while the aggregate wait time looks fine. Heading, because a driver pointed away needs a U-turn that is real time. And soon-to-be-free drivers, because someone two minutes from dropoff and one minute from the pickup beats an available driver five minutes away. The cost function is where product strategy actually lives.
"How do you prevent two batches assigning the same driver?" An OFFERED state with a short TTL, claimed by a conditional update: set state to offered where state is available or where a previous offer has expired, returning the id. Zero rows means another batch got there first, which is a normal outcome rather than an error. It is the same non-blocking claim pattern as seat holds in a ticketing system.
"Twenty percent of drivers decline. What happens?" Re-batch. The declined requests join the next window with their waiting time now weighting them cheaper through the fairness term, so they get progressively better candidates. After a few rounds, widen the search radius, then relax constraints, then be honest and show "no drivers available". What I would not do is offer to several drivers simultaneously, because the losers have driven toward a pickup they will not get, and that destroys driver trust faster than anything else in the system.
"The routing engine goes down. Now what?" Degrade through the tiers rather than fail. Fall back to the cached cell-to-cell ETAs, then to haversine with a road-factor multiplier, typically around 1.3 in a grid city. Match quality drops and dispatch keeps working. A dispatch system that stops dispatching because ETAs are unavailable is much worse than one dispatching sub-optimally, and the same applies if the batch solver times out: fall back to greedy for that batch.
"A concert ends and demand spikes tenfold. What does dispatch do?" Very little, and I would say so. Matching cannot create drivers. The levers are pricing, which reduces demand and attracts supply, and repositioning, which moves idle drivers toward predicted demand before the spike. Trying to solve a supply shortage inside the dispatcher means building the wrong system. What dispatch should do is communicate honestly: an accurate long wait is better than an optimistic estimate that keeps sliding.
"How do you shard this?" By city, and it is the cleanest partition key in any of these designs, because dispatch has no cross-city queries at all. Each city is an independent deployment with its own index, solver and ETA cache, so a failure is contained to one city. Within a megacity, partition the solver geographically and let drivers near a border be considered by both regions, resolving by cost. That accepts slight sub-optimality at boundaries in exchange for a large reduction in the cubic solver term.
Common misconceptions
"Dispatch is a nearest-neighbour query." Nearest is the wrong objective, and the spatial query is the cheap part. ETAs and the assignment are where the work is.
"Straight-line distance is close enough." A driver 200 metres away across a river is fifteen minutes away. Straight-line is useful as a pruning bound, not as a cost.
"Batching adds latency, so it's worse." It adds seconds and removes minutes, because the assignment is globally better. The trade is strongly favourable.
"Location data must be durably stored." It is superseded every four seconds. Keep it in memory, trail it asynchronously for analytics, and let the index self-heal from the next round of pings.
"Offer to several drivers to reduce decline latency." The losers drive toward a pickup they will not get. Sequential offers with a short TTL is slower and correct.
Interview delivery note
Ask greedy-or-batched first and answer it with a concrete example, because it is the decision the rest depends on: "Greedy or batched? I'd batch, because greedy makes locally optimal choices that are globally worse. Two requests two hundred milliseconds apart can each take the other's best driver, and in the simple two-request case that's about forty percent more total wait. Batching lets me solve an assignment problem over the window, optimally, with Hungarian in O(n³)."
Then reject "nearest driver" explicitly: "And the objective isn't nearest. The cost function needs acceptance probability, because a decline costs fifteen seconds and a re-match; a fairness term, because without one a request in a marginal location gets passed over indefinitely while the average looks fine; and soon-to-be-free drivers, because two minutes from dropoff and one from the pickup beats available and five minutes away."
Do the ETA arithmetic, because it is the part that separates a real answer: "The cost matrix for a three-second batch is about a million pairs, and road routing is a millisecond each, so that's a thousand seconds of compute for a three-second window. So I don't compute them. Haversine pruning first, and that's exact rather than approximate, because straight-line is a strict lower bound on road distance, so it can't discard the true best candidate. That removes eighty to ninety percent of pairs for free."
The line that shows product judgement: "and when a concert ends and demand spikes tenfold, dispatch does very little. Matching can't create drivers. That's pricing and repositioning, and trying to solve it in the dispatcher means building the wrong system."
Further reading
- Uber Engineering, "H3: Uber's Hexagonal Hierarchical Spatial Index", for the hexagon neighbour-uniformity argument.
- Uber Engineering's dispatch and matching write-ups, for batched assignment in production.
- Geisberger et al., "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks" (2008).
- Kuhn, "The Hungarian Method for the assignment problem" (1955).
- Uber Engineering, "DeepETA", for the ML correction layer over physics-based routing.