How Uber matches riders to drivers in real time

The scenario

A rider requests a trip while nearby drivers are moving, going offline, or competing for several riders at once. The nearest-driver answer is fast, but it can give one rider a great assignment and leave another with a poor one.

Real-time dispatch balances freshness, fairness, ETA accuracy, supply preservation, and computation. A useful design narrows the search geographically, scores feasible rider-driver pairs, and solves a bounded assignment problem.

30-second mental model

Ingest fresh driver locations into a spatial index, expand around the pickup to build a small candidate set, estimate road-network ETAs, then assign drivers to a batch of requests. Optimistic reservation makes the final assignment atomic; if a driver is taken or the ETA becomes stale, the request returns to the dispatch loop.

Uber’s H3 library is public and relevant to the geospatial discussion. The dispatch batching window, score weights, thresholds, and private service topology below are illustrative rather than claims about Uber’s current production system.

5-minute end-to-end flow

1. Accept and validate the rider request, including pickup, destination, product, and constraints.
2. Consume recent driver location/status updates and materialize available drivers in a spatial index.
3. Expand neighboring cells until each request has enough eligible candidates; discard stale, busy, or incompatible drivers.
4. Query or approximate road ETAs and score pairs using wait time, supply preservation, driver constraints, and product policy.
5. Solve the batch assignment or use a bounded approximation when the matrix is too large.
6. Reserve drivers atomically, notify them, and re-dispatch on decline, timeout, stale location, or an invalidated route.

The Architecture

Here is the end-to-end architecture from the rider tapping "Request" to the driver receiving the match notification:

Let me walk through the flow.

When a rider taps "Request," their app sends the pickup location, destination, and ride type to the API gateway. This request is published to Kafka and consumed by the Request Collector, which batches incoming requests over a 2-second window grouped by H3 region.

Meanwhile, every active driver's app sends GPS coordinates every 4 seconds to the Location Service, which maintains an in-memory H3 geospatial index of all available drivers.

For each batch, the Candidate Selector queries the H3 index to find the 10-20 closest available drivers for each request. The Scoring Engine then evaluates each rider-driver pair using ETA estimates and supply-demand ratios. Finally, the Batch Matcher runs the Hungarian algorithm to find the globally optimal assignment across all requests in the batch.

The matched driver receives a push notification and has 15 seconds to accept. If they decline or do not respond, the system re-matches the rider in the next batch cycle.

For your interview: the phrase "batch matching over a 2-second window" is the key insight that separates a strong answer from a naive one. It shows you understand the tension between greedy and optimal matching.

Let me call out the scale numbers here. In Manhattan at peak hours:

• ~10,000 active drivers sending GPS every 4s = 2,500 location updates/second
• ~100 ride requests per second
• Each 2-second batch: ~200 requests
• Each request × 15 candidates = 3,000 rider-driver pairs per batch
• 3,000 ETA queries per batch (must complete in < 200ms)
• One Hungarian algorithm solve per H3 region per batch

This is not a toy problem. The entire pipeline must complete in under 3 seconds, and every millisecond of added latency means a rider is staring at a loading screen.

Geospatial Indexing with H3 Hexagons

The first challenge is: how do you answer the question "which drivers are near this pickup location?" when you have 50,000 active drivers in Manhattan? You cannot iterate through all 50,000 and compute distances. You need a spatial index.

Uber uses H3, a hexagonal hierarchical spatial index developed in-house and open-sourced. The key idea: the entire earth's surface is divided into hexagonal cells at multiple resolutions. Each cell has a unique 64-bit ID. Converting a lat/lng to an H3 cell ID is O(1). Finding neighboring cells is O(1). This turns "find drivers within 2km" into "find drivers in these 7-19 H3 cells."

Why hexagons instead of squares or rectangles? Two reasons.

Uniform distance: The center of a hexagon is equidistant from the centers of all its neighbors. With square grids, diagonal neighbors are ~1.41x farther than cardinal neighbors. This means ring-based expansion gives consistent distance guarantees with hexagons.

No gaps or overlaps: Hexagons tile perfectly. You can expand outward ring by ring without any coverage gaps. This matters when the candidate search says "give me all drivers within 3 rings of the pickup."

The H3 index is stored in memory (Redis or a custom in-memory store) with the cell ID as the key and a list of driver IDs as the value. When a driver moves and their GPS update crosses a cell boundary, the Location Service removes them from the old cell's list and adds them to the new cell's list. This happens roughly every 4 seconds per driver.

The Dispatch Scoring and Matching Pipeline

Once we have 10-20 candidate drivers for each ride request, the system needs to decide which driver gets which ride. This is where the magic happens, and where most candidates give a weak answer.

The naive approach is "assign each rider to their nearest driver." This is a greedy algorithm: process requests in arrival order, and for each request, pick the closest available driver. The problem is that it is globally suboptimal.

Imagine two riders (A and B) and two drivers (D1 and D2). D1 is 2 minutes from A and 5 minutes from B. D2 is 3 minutes from A and 2 minutes from B. Greedy matching processes A first, assigns D1 (2 min), then assigns D2 to B (2 min). Total wait: 4 minutes. But what if we swapped? A→D2 (3 min), B→D1 (5 min) = 8 min total. Here greedy won. But consider a different scenario: D1 is 1 min from A and 10 min from B. D2 is 2 min from both. Greedy: A→D1 (1), B→D2 (2) = 3 total. Optimal: same. These small examples often look fine, but at scale with 50 riders and 50 drivers, greedy consistently produces 10-20% worse total wait time because it locks in early locally-good assignments that block globally-better ones later.

The scoring function combines multiple signals:

ETA (40% weight): How quickly the driver can reach the pickup. This is the most important factor because riders care most about wait time. The ETA is not straight-line distance; it comes from Uber's routing engine, which accounts for real-time traffic, turn restrictions, and road closures.

Supply-demand ratio (30% weight): The ratio of available drivers to active requests in the pickup's H3 region. In a surge zone with few drivers, the system might assign a slightly farther driver to avoid leaving the zone completely empty for the next request. This is where matching and surge pricing interact.

Driver preference (20% weight): Drivers who are heading toward the pickup area (based on heading and recent trajectory) score higher than drivers who would need to make a U-turn. A driver 2km away driving toward you is better than a driver 1km away driving away from you.

Trip value (10% weight): Longer trips generate more revenue. In some versions of the algorithm, the system slightly favors assigning high-rated, experienced drivers to longer trips to ensure a good experience. This is controversial internally but is a real signal.

Real-Time ETA Estimation

ETA estimation is the foundation of the entire matching system. If the ETA is wrong by 3 minutes, the matching algorithm assigns the wrong driver. If the routing engine is slow, the entire dispatch pipeline misses the 3-second latency budget. This is why Uber built their own routing engine instead of using Google Maps.

The ETA challenge has three aspects:

Graph representation: The road network is a directed graph with ~100 million edges (road segments) globally. Each edge has time-variable weights based on traffic conditions. Rush hour in Manhattan means a 200-meter block might take 5 minutes, while the same block at 3 AM takes 20 seconds.

Real-time traffic: Every driver's GPS trace is a traffic probe. When 200 drivers on a road segment go from 30 mph to 5 mph, the system knows there is congestion within 30 seconds. These speed observations update the edge weights in the routing graph continuously.

Batch ETA queries: The scoring engine needs ETAs for 300-500 rider-driver pairs per batch. That is 300-500 routing queries that must complete within 200ms total. Uber uses a pre-computed hierarchy (Contraction Hierarchies or similar) that answers single-pair queries in 1-2ms, making batch queries feasible.

I want to highlight the feedback loop here. Driver GPS traces create traffic data, which updates the routing graph, which improves ETA estimates, which improves matching quality, which reduces driver idle time, which puts more drivers on the road, which generates more GPS probes. This is a virtuous cycle that benefits from scale. More drivers means better traffic data, which means better matching, which means more riders, which means more drivers.

The accuracy requirements are strict. Uber's internal benchmarks target ETAs within 20% of actual travel time for 90% of requests. Missing this target means the matching algorithm makes suboptimal assignments, riders get frustrated by inaccurate wait times, and surge pricing calculations are wrong (because surge is based on the ratio of estimated demand to estimated supply-time-to-pickup).

For roads with no recent driver data (a suburban cul-de-sac at 3 AM, for example), the system falls back through three layers: historical speed for that road at this time-of-day, average speed for that road class (residential, arterial, highway) in the city, and finally a conservative default speed based on the speed limit. This cascading fallback ensures the system always returns an ETA, even if the confidence is lower.

Bottlenecks, failure modes, and operations

1. Concurrent assignment races. Two batching windows might overlap in a way that both select the same driver as a candidate. If both matchers assign that driver, one of the assignments fails. The system handles this with optimistic locking: the match is only confirmed when the driver's status is atomically changed from "available" to "assigned." If the CAS (compare-and-swap) fails, the request goes back into the next batch cycle.

2. Cold start in new cities. When Uber launches in a new city, there are very few drivers and no historical traffic data. The H3 index is sparse (big cells have zero drivers), the ETA engine has no real-time data, and the matching algorithm degenerates to greedy because batches contain only 1-2 requests. Uber bootstraps by using map provider data for initial ETAs and running promotions to build driver supply before advertising to riders.

3. The airport queue problem. Airports have a fixed queue of drivers waiting in a staging lot. The matching system must balance between the queue (FIFO fairness for waiting drivers) and nearby street drivers who might be closer to the terminal. Most airports have regulatory requirements that airport rides must go to queued drivers, which overrides the optimization algorithm entirely.

4. Driver location staleness. GPS updates arrive every 4 seconds. A driver moving at 30 mph travels about 55 meters between updates. In dense areas, 55 meters can mean the driver is on a completely different street. The system interpolates between GPS points using the road graph (map-matched trajectory), but there is inherent uncertainty in the driver's exact position.

5. Surge pricing interaction. High surge zones attract drivers from neighboring areas, which drains supply from those areas, potentially creating secondary surge zones. The matching system must account for this cascade effect. If you aggressively match all drivers into a surge zone, you create a supply desert in the surrounding areas that triggers new surges.

6. Driver-side accept rate. Not every matched driver accepts the ride. Some drivers decline low-value short trips, some are about to go offline, and some are in areas with poor network connectivity and miss the notification. Uber tracks per-driver accept rates and factors them into the matching score. A driver with a 95% accept rate is more valuable as a match than one with a 60% accept rate, because the latter is likely to decline and force a re-match cycle.

Common mistakes and misconceptions

Practical checklist

• Define the dispatch objective and constraints before selecting an algorithm: wait time, fairness, supply preservation, product rules, and safety.
• Treat location freshness and driver availability as inputs with explicit staleness bounds.
• Use a spatial index to generate candidates, then road-network ETA to score the small candidate matrix.
• Batch only long enough to gain useful coordination; use bounded approximations when the batch is too large.
• Reserve a driver atomically and make decline, timeout, stale location, and cancellation paths idempotent.
• Preserve domain rules such as airport queues or accessibility requirements even when they reduce mathematical optimality.
• Monitor match latency, acceptance, rematch rate, ETA error, supply imbalance, regional hotspots, and location-ingestion lag.
• Keep H3’s public library role separate from claims about Uber’s current private dispatch implementation.

Test Your Understanding

---

---

---

---

---

---

---

Quick Recap

1. Uber indexes driver locations using H3 hexagonal cells for O(1) spatial lookups with uniform neighbor distances.
2. The candidate selector expands H3 rings outward from the pickup location to find 10-20 nearby available drivers.
3. Each rider-driver pair is scored on ETA (40%), supply-demand ratio (30%), driver heading (20%), and trip value (10%).
4. Requests are batched over a 2-second window, and the Hungarian algorithm finds the globally optimal assignment across the batch.
5. ETA estimation uses Contraction Hierarchies on the road graph with edge weights updated every 30 seconds from driver GPS traces.
6. Driver GPS updates arrive every 4 seconds, and map-matching infers the trajectory between updates.
7. Concurrent assignment races are resolved with optimistic locking on driver status (CAS on available to assigned).
8. Batch matching reduces average wait times by 10-20% compared to greedy nearest-driver assignment.
9. Surge pricing interacts with matching by shifting driver supply toward high-demand areas, changing the candidate pool before matching even begins.
10. Chained dispatching includes drivers who are about to finish their current trip, scoring them by current-trip ETA plus pickup ETA.

Related Concepts

• How geospatial indexing works: H3 is one approach to spatial indexing. Others include R-trees, quadtrees, and S2 cells (used by Google). Understanding the tradeoffs between these structures helps you reason about when each is appropriate.
• How real-time event streaming works: The driver location pipeline is a classic streaming architecture: high-volume GPS events ingested via Kafka, processed in real time, and materialized into an in-memory index.
• How CDN cache invalidation works: The H3 index is conceptually similar to a distributed cache that must be kept consistent as driver locations change. The "invalidation" is the cell-boundary crossing that moves a driver from one cell to another.
• How push notifications work: The driver match notification is a time-critical push message. If the notification is delayed by even 5 seconds, the driver might have moved, changing the ETA and potentially invalidating the match.
• How rate limiting works: The batching window in the dispatch pipeline is conceptually similar to a sliding window: requests accumulate over a fixed interval before being processed as a group.