Build Uber's Real-Time Driver-Rider Matching System

Imagine a city block with 50 taxis circling and 200 people trying to hail a cab simultaneously. A human dispatcher would scan the block, pick the closest available cab, radio the driver, and confirm availability - all in about 10 seconds. Uber does this for 5 million concurrent sessions across 70+ countries, matching each rider to a driver in under 2 seconds, while the entire driver fleet moves in real time and demand spikes unpredictably by 10x during concerts or bad weather. That dispatcher’s 10-second workflow needs to collapse to under 200ms in the hot path.

The matching problem looks deceptively simple: find the nearest available driver to a rider’s pickup point. But “available” is a state that changes by the second as drivers accept, complete, and cancel trips. “Nearest” in a city is not Euclidean distance - a driver 400 meters away on the other side of a one-way system may be a 6-minute ETA while one 800 meters away on a clear boulevard is 3 minutes. And the match itself is a two-sided commitment: you cannot confirm a match without atomically locking the driver out of other match candidates for that instant, or you risk offering the same driver to two riders simultaneously.

At Uber’s scale - roughly 100,000 match requests per minute in a single metro during peak hours, with driver location updates arriving at 4-second intervals from 50,000 active drivers - the naive “query database for nearby drivers, pick the best one, update their status” approach falls apart immediately. The geo query alone at that frequency would saturate a conventional PostgreSQL cluster. Driver state updates create contention. And the 2-second SLA leaves almost no budget for retries.

We need to solve for sub-100ms geospatial lookup, optimistic driver locking with rollback, and graceful degradation during demand spikes simultaneously.

Requirements and Constraints

Functional Requirements

• Accept a ride request with pickup coordinates and rider preferences (vehicle type, accessibility)
• Find the top-N nearest available drivers within a configurable radius (default: 5km)
• Score candidates by estimated time of arrival, match quality, and acceptance probability
• Dispatch a match offer to the selected driver and wait up to 15 seconds for acceptance
• If driver declines or times out, re-offer to the next candidate without starting the search from scratch
• Update driver availability state atomically - a driver in “offered” state must not receive a second offer
• Notify rider of match result (accepted or searching) within 2 seconds of request submission
• Emit match events to downstream services (surge pricing, trip ledger, ETA updates)

Non-Functional Requirements

• Match latency: P95 under 2 seconds from rider request to driver notification
• Geo lookup throughput: 100,000 queries per minute per metro region
• Driver location update throughput: 50,000 drivers x 15 location pings per minute = 750,000 writes per minute per metro
• Availability: 99.99% for the match acceptance path; 99.9% for location ingestion (occasional gaps are tolerable)
• Match atomicity: zero double-matches - a single driver must never be simultaneously offered to two riders
• Degraded mode: during peak overload, match latency may extend to 10 seconds but must not produce errors

Constraints and Assumptions

• We design for a single metro region; cross-region routing is out of scope
• Driver location updates arrive via persistent WebSocket connections from the mobile app
• ETA computation is delegated to a separate routing service; we consume ETAs via an internal API
• The system must handle a 10x demand spike (New Year’s Eve scenario) without manual intervention
• Driver app timeout for offer acceptance is fixed at 15 seconds per the product contract

High-Level Architecture

The matching system comprises six major components organized across three logical layers.

The Location Ingestion Service is a stateless fleet of WebSocket servers that maintain persistent connections to all active driver apps. Every 4 seconds, each driver’s app sends a GPS coordinate update. The ingestion service writes each update into a Geo Index (Redis Cluster with GEOADD) and publishes a change event to a Kafka topic for any downstream consumers that need the raw stream (analytics, surge pricing).

The Match Request Service receives incoming ride requests from riders through the API Gateway. It validates the request, determines the appropriate vehicle class and search radius, and enqueues a match job into a partitioned work queue (one partition per city quadrant). This decouples request acceptance from the heavier matching computation.

The Matching Engine is a pool of stateful workers that consume match jobs. For each job, it queries the Geo Index for nearby drivers, fetches their current state from the Driver State Service, scores candidates, selects the best available driver, and issues an offer. The matching engine holds a soft lock on the selected driver by setting their state to OFFER_PENDING atomically before sending the push notification.

The Driver State Machine manages driver lifecycle: OFFLINE -> AVAILABLE -> OFFER_PENDING -> ON_TRIP -> AVAILABLE. All state transitions go through a Redis-backed state store with compare-and-swap semantics. The state machine also handles offer expiry - if no response arrives within 15 seconds, it automatically returns the driver to AVAILABLE and signals the matching engine to retry with the next candidate.

The Notification Service handles push delivery to both driver and rider via FCM/APNS, and also maintains the WebSocket connection channel for in-app real-time updates. Match results flow through this layer so neither mobile app must poll.

The Trip Record Store (PostgreSQL with logical replication) captures the final accepted match as a durable trip record for billing, analytics, and dispute resolution.

Geospatial Indexing with Redis GEOSEARCH

The core of fast nearby-driver lookup is a geospatial index that can answer “give me all drivers within 5km of coordinate X, sorted by distance” in under 5ms, even with 50,000 active points being updated continuously.

Redis provides exactly this with its GEO command family. Under the hood, Redis encodes latitude/longitude pairs as a 52-bit Geohash integer and stores them in a sorted set, where the score is the geohash. A radius search becomes a sorted set range query over the geohash space - O(log N + M) where M is the number of results. At 50,000 drivers in a city, a 5km radius typically returns 50-200 candidates, and the query completes in 2-4ms.

The critical design decision is how we partition the geo index. A single Redis instance can handle the full driver fleet of a metro, but we shard by vehicle class (MOTO, SEDAN, SUV, AUTO) to reduce search space per query and allow independent scaling. A rider requesting an SUV only searches the SUV geospace.

import redis
import time
from typing import Optional

r = redis.RedisCluster(host="redis-geo", port=6379)

GEO_KEY_PREFIX = "geo:drivers"
DRIVER_STATE_PREFIX = "driver:state"

def update_driver_location(driver_id: str, lat: float, lon: float, vehicle_class: str):
    """
    Called by Location Ingestion Service on every driver ping.
    Uses pipeline to batch geoadd + state TTL refresh atomically.
    """
    geo_key = f"{GEO_KEY_PREFIX}:{vehicle_class}"
    pipe = r.pipeline(transaction=False)
    # GEOADD is idempotent - updates position if member already exists
    pipe.geoadd(geo_key, [lon, lat, driver_id])
    # Refresh driver "seen recently" TTL - if no ping for 60s, treat as offline
    pipe.expire(f"driver:heartbeat:{driver_id}", 60)
    pipe.execute()

def find_nearby_drivers(
    lat: float,
    lon: float,
    radius_km: float,
    vehicle_class: str,
    max_candidates: int = 10
) -> list[dict]:
    """
    Returns up to max_candidates nearby drivers sorted by distance.
    Filters to AVAILABLE state only.
    """
    geo_key = f"{GEO_KEY_PREFIX}:{vehicle_class}"
    # GEOSEARCH returns (member, distance_meters) tuples
    raw = r.geosearch(
        geo_key,
        longitude=lon,
        latitude=lat,
        radius=radius_km,
        unit="km",
        sort="ASC",
        count=max_candidates * 3,  # over-fetch to account for unavailable drivers
        withcoord=True,
        withdist=True
    )
    candidates = []
    for member, dist_km, (member_lon, member_lat) in raw:
        driver_id = member.decode()
        state = r.hget(f"{DRIVER_STATE_PREFIX}:{driver_id}", "status")
        if state and state.decode() == "AVAILABLE":
            candidates.append({
                "driver_id": driver_id,
                "distance_km": dist_km,
                "lat": member_lat,
                "lon": member_lon
            })
        if len(candidates) >= max_candidates:
            break
    return candidates

Driver State Machine

Driver state management is where most matching systems make catastrophic mistakes. The naive approach - “read driver status, if available send offer, update to pending” - is a classic check-then-act race condition. Between the read and the write, another matching worker may have selected the same driver for a different rider.

The solution is to use Redis atomic compare-and-swap for all state transitions. We never read state and then write state in two separate operations. Every transition uses a Lua script that performs the read and conditional write atomically inside Redis’s single-threaded command executor.

import redis
import time

r = redis.Redis(host="redis-state", port=6379, decode_responses=True)

# Lua script for atomic state transition
# Returns 1 on success, 0 if current state doesn't match expected
TRANSITION_SCRIPT = r.register_script("""
local key = KEYS[1]
local expected = ARGV[1]
local new_state = ARGV[2]
local driver_id = ARGV[3]
local offer_id = ARGV[4]
local ttl = tonumber(ARGV[5])

local current = redis.call('HGET', key, 'status')
if current ~= expected then
    return 0
end

redis.call('HSET', key, 'status', new_state, 'offer_id', offer_id, 'offer_ts', ARGV[6])
if ttl > 0 then
    -- Set offer expiry - if driver doesn't respond, auto-expire back to AVAILABLE
    redis.call('SET', 'offer:expiry:' .. driver_id, offer_id, 'EX', ttl)
end
return 1
""")

OFFER_TTL_SECONDS = 15

def try_lock_driver_for_offer(driver_id: str, offer_id: str) -> bool:
    """
    Atomically transitions driver AVAILABLE -> OFFER_PENDING.
    Returns True if the lock was acquired (we own this driver for this offer).
    Returns False if driver was already taken by a concurrent match.
    """
    state_key = f"driver:state:{driver_id}"
    result = TRANSITION_SCRIPT(
        keys=[state_key],
        args=[
            "AVAILABLE",       # expected current state
            "OFFER_PENDING",   # new state
            driver_id,
            offer_id,
            OFFER_TTL_SECONDS,
            int(time.time())
        ]
    )
    return bool(result)

def handle_driver_accept(driver_id: str, offer_id: str) -> bool:
    """Transitions OFFER_PENDING -> ON_TRIP after driver accepts."""
    state_key = f"driver:state:{driver_id}"
    # Verify offer_id matches to prevent stale accept after re-offer
    current_offer = r.hget(state_key, "offer_id")
    if current_offer != offer_id:
        return False  # Stale response from previous offer cycle
    result = TRANSITION_SCRIPT(
        keys=[state_key],
        args=["OFFER_PENDING", "ON_TRIP", driver_id, offer_id, 0, int(time.time())]
    )
    return bool(result)

def handle_driver_decline_or_timeout(driver_id: str, offer_id: str):
    """Returns driver to AVAILABLE pool, triggers retry matching."""
    state_key = f"driver:state:{driver_id}"
    current_offer = r.hget(state_key, "offer_id")
    if current_offer != offer_id:
        return  # Already processed by a different path
    TRANSITION_SCRIPT(
        keys=[state_key],
        args=["OFFER_PENDING", "AVAILABLE", driver_id, "", 0, int(time.time())]
    )
    # Signal match coordinator to retry with next candidate
    r.publish(f"match:retry:{offer_id}", driver_id)

Match Scoring and Assignment Algorithm

Finding nearby drivers is fast. Choosing which one to offer is where match quality gets determined. Uber’s matching is not simply “give me the closest driver” - it optimizes a multi-objective function balancing ETA, driver acceptance probability, trip quality, and system-level fairness.

The scoring function runs after the geo candidates are fetched and their ETAs are retrieved from the routing service. We compute a score for each candidate and pick the highest-scoring available driver.

import asyncio
from dataclasses import dataclass
from typing import Optional

@dataclass
class DriverCandidate:
    driver_id: str
    distance_km: float
    eta_seconds: Optional[int]  # None if routing call failed
    acceptance_rate_30d: float   # historical, from driver profile store
    trips_today: int             # for fairness/earnings optimization
    rating: float

@dataclass
class RideRequest:
    rider_id: str
    pickup_lat: float
    pickup_lon: float
    vehicle_class: str
    request_ts: float

def score_candidate(candidate: DriverCandidate, request: RideRequest) -> float:
    """
    Returns a score in [0, 1]. Higher is better.
    Weights tuned empirically; in production these would be ML-model outputs.
    """
    if candidate.eta_seconds is None:
        # Routing call failed - penalize but don't exclude
        eta_score = 0.3
    else:
        # Linear decay: 0 ETA = 1.0, 10 min ETA = 0.0
        eta_score = max(0.0, 1.0 - (candidate.eta_seconds / 600))

    # Drivers who accept more often get priority - reduces phantom supply
    acceptance_score = candidate.acceptance_rate_30d  # already in [0,1]

    # Fairness: slightly boost drivers with fewer trips today to distribute earnings
    # Cap at 20 trips to avoid over-weighting idle drivers
    fairness_score = max(0.0, 1.0 - (candidate.trips_today / 20))

    # Rating as a quality signal (4.5-5.0 range normalized)
    rating_score = (candidate.rating - 4.0) / 1.0  # maps 4.0-5.0 to 0.0-1.0

    return (
        0.55 * eta_score +
        0.25 * acceptance_score +
        0.12 * fairness_score +
        0.08 * rating_score
    )

async def run_match(request: RideRequest, routing_client, driver_state_client) -> Optional[str]:
    """
    Full match cycle: find candidates, score, offer, handle response.
    Returns matched driver_id or None if no match found.
    """
    candidates = find_nearby_drivers(
        request.pickup_lat, request.pickup_lon,
        radius_km=5.0, vehicle_class=request.vehicle_class, max_candidates=15
    )
    if not candidates:
        return None

    # Batch ETA requests - routing service accepts up to 20 origins per call
    etas = await routing_client.batch_eta(
        origins=[(c["lat"], c["lon"]) for c in candidates],
        destination=(request.pickup_lat, request.pickup_lon)
    )

    scored = []
    for c, eta in zip(candidates, etas):
        driver_profile = await driver_state_client.get_profile(c["driver_id"])
        candidate = DriverCandidate(
            driver_id=c["driver_id"],
            distance_km=c["distance_km"],
            eta_seconds=eta,
            acceptance_rate_30d=driver_profile.acceptance_rate,
            trips_today=driver_profile.trips_today,
            rating=driver_profile.rating
        )
        scored.append((score_candidate(candidate, request), candidate))

    scored.sort(key=lambda x: x[0], reverse=True)

    # Waterfall offer: try each candidate in score order until one accepts
    for score, candidate in scored:
        offer_id = f"{request.rider_id}:{candidate.driver_id}:{int(request.request_ts)}"
        if try_lock_driver_for_offer(candidate.driver_id, offer_id):
            accepted = await send_offer_and_wait(
                candidate.driver_id, offer_id, request, timeout=15
            )
            if accepted:
                return candidate.driver_id
            # Declined or timed out - next candidate automatically tried
    return None

Data Model

-- Driver real-time state (also mirrored in Redis for hot reads)
CREATE TABLE driver_states (
    driver_id       UUID PRIMARY KEY,
    status          VARCHAR(20) NOT NULL DEFAULT 'OFFLINE',
                    -- OFFLINE, AVAILABLE, OFFER_PENDING, ON_TRIP
    vehicle_class   VARCHAR(10) NOT NULL,
    current_lat     DOUBLE PRECISION,
    current_lon     DOUBLE PRECISION,
    last_seen_at    TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    current_offer_id UUID,
    updated_at      TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    CONSTRAINT valid_status CHECK (status IN ('OFFLINE','AVAILABLE','OFFER_PENDING','ON_TRIP'))
);

CREATE INDEX idx_driver_states_status_class ON driver_states (status, vehicle_class)
    WHERE status = 'AVAILABLE';
CREATE INDEX idx_driver_states_last_seen ON driver_states (last_seen_at)
    WHERE status != 'OFFLINE';

-- Spatial index for fallback queries when Redis is degraded
CREATE EXTENSION IF NOT EXISTS postgis;
ALTER TABLE driver_states ADD COLUMN location GEOGRAPHY(POINT, 4326);
CREATE INDEX idx_driver_states_location ON driver_states USING GIST (location);

-- Match offers - audit trail for every offer sent
CREATE TABLE match_offers (
    offer_id        UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    ride_request_id UUID NOT NULL,
    driver_id       UUID NOT NULL,
    rider_id        UUID NOT NULL,
    status          VARCHAR(20) NOT NULL DEFAULT 'PENDING',
                    -- PENDING, ACCEPTED, DECLINED, EXPIRED, CANCELLED
    offered_at      TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    responded_at    TIMESTAMPTZ,
    offer_seq       SMALLINT NOT NULL DEFAULT 1, -- which attempt for this ride request
    score           REAL,
    eta_seconds     INT,
    distance_meters INT,
    CONSTRAINT valid_offer_status CHECK (status IN ('PENDING','ACCEPTED','DECLINED','EXPIRED','CANCELLED'))
);

CREATE INDEX idx_match_offers_ride ON match_offers (ride_request_id, status);
CREATE INDEX idx_match_offers_driver ON match_offers (driver_id, offered_at DESC);

-- Trip records (created when offer accepted)
CREATE TABLE trips (
    trip_id             UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    offer_id            UUID NOT NULL UNIQUE REFERENCES match_offers(offer_id),
    driver_id           UUID NOT NULL,
    rider_id            UUID NOT NULL,
    vehicle_class       VARCHAR(10) NOT NULL,
    pickup_lat          DOUBLE PRECISION NOT NULL,
    pickup_lon          DOUBLE PRECISION NOT NULL,
    status              VARCHAR(20) NOT NULL DEFAULT 'DRIVER_EN_ROUTE',
    matched_at          TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    pickup_at           TIMESTAMPTZ,
    dropoff_at          TIMESTAMPTZ,
    surge_multiplier    REAL NOT NULL DEFAULT 1.0
) PARTITION BY RANGE (matched_at);

CREATE TABLE trips_2026_06 PARTITION OF trips
    FOR VALUES FROM ('2026-06-01') TO ('2026-07-01');

-- Ride requests - the demand side record
CREATE TABLE ride_requests (
    request_id      UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    rider_id        UUID NOT NULL,
    vehicle_class   VARCHAR(10) NOT NULL,
    pickup_lat      DOUBLE PRECISION NOT NULL,
    pickup_lon      DOUBLE PRECISION NOT NULL,
    status          VARCHAR(20) NOT NULL DEFAULT 'SEARCHING',
    requested_at    TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    matched_at      TIMESTAMPTZ,
    cancelled_at    TIMESTAMPTZ,
    no_drivers_at   TIMESTAMPTZ -- set if exhausted all candidates
);

CREATE INDEX idx_ride_requests_rider ON ride_requests (rider_id, requested_at DESC);
CREATE INDEX idx_ride_requests_status ON ride_requests (status, requested_at)
    WHERE status = 'SEARCHING';

Key Algorithms and Protocols

The most latency-sensitive operation is the batch ETA request that converts geo-distance candidates to routable ETAs. We cannot afford a sequential HTTP call per candidate.

import asyncio
import aiohttp
from typing import List, Tuple, Optional

async def batch_eta_request(
    origins: List[Tuple[float, float]],
    destination: Tuple[float, float],
    routing_url: str,
    timeout_ms: int = 150
) -> List[Optional[int]]:
    """
    Fetches ETAs for multiple driver origins to a single destination.
    Returns list of ETA in seconds, None for failed lookups.
    Times out aggressively - a slow ETA is worse than a missing one.
    """
    payload = {
        "origins": [{"lat": lat, "lon": lon} for lat, lon in origins],
        "destination": {"lat": destination[0], "lon": destination[1]},
        "mode": "driving",
        "departure_time": "now"
    }
    try:
        async with aiohttp.ClientSession() as session:
            async with session.post(
                f"{routing_url}/batch_eta",
                json=payload,
                timeout=aiohttp.ClientTimeout(total=timeout_ms / 1000)
            ) as resp:
                if resp.status == 200:
                    data = await resp.json()
                    return [row.get("eta_seconds") for row in data["results"]]
    except (asyncio.TimeoutError, aiohttp.ClientError):
        pass
    return [None] * len(origins)


def h3_ring_search(lat: float, lon: float, max_rings: int = 3) -> List[str]:
    """
    Returns H3 cell IDs in concentric rings around the point.
    Resolution 9 cells are ~0.1 km2 each. Ring 1 adds 6 neighbors,
    ring 2 adds 12, ring 3 adds 18. We search outward until we find
    enough candidates or exhaust max_rings.
    """
    import h3
    resolution = 9
    center_cell = h3.latlng_to_cell(lat, lon, resolution)
    cells = [center_cell]
    for ring in range(1, max_rings + 1):
        ring_cells = h3.grid_ring(center_cell, ring)
        cells.extend(ring_cells)
    return cells

The offer expiry monitor is a background worker that scans for expired offers and returns drivers to the available pool:

import time
import redis

r = redis.Redis(host="redis-state", decode_responses=True)

def run_offer_expiry_monitor():
    """
    Polls for expired offer keys every 500ms.
    In production, use Redis keyspace notifications instead of polling.
    """
    pubsub = r.pubsub()
    pubsub.psubscribe("__keyevent@0__:expired")

    for message in pubsub.listen():
        if message["type"] != "pmessage":
            continue
        key = message["data"]
        if not key.startswith("offer:expiry:"):
            continue
        driver_id = key.split(":", 2)[2]
        # The TTL on the expiry key fired - driver did not respond in time
        state_key = f"driver:state:{driver_id}"
        current_state = r.hget(state_key, "status")
        if current_state == "OFFER_PENDING":
            r.hset(state_key, "status", "AVAILABLE")
            expired_offer_id = r.hget(state_key, "offer_id")
            r.publish(f"match:retry:{expired_offer_id}", driver_id)

Scaling and Performance

# Capacity Estimation - Single Metro (Mumbai, ~50k active drivers at peak)
# =========================================================================

# Driver location writes
drivers_active        = 50,000
ping_interval_sec     = 4
location_writes_sec   = 50,000 / 4 = 12,500 writes/sec
redis_geoadd_latency  = 0.2ms P99
redis_memory_per_driver = ~64 bytes (geohash + driver_id)
redis_total_memory    = 50,000 * 64B = ~3.2 MB  # trivially fits in RAM

# Match requests
peak_ride_requests_min = 100,000
peak_ride_requests_sec = ~1,667 req/sec
match_workers_needed   = 1,667 / 50 matches_per_worker_sec = 34 workers

# Per-match latency budget (2s SLA)
geo_lookup             = 5ms
etas_batch_call        = 150ms
state_lock_attempt     = 2ms
push_notification      = 50ms
network_driver_to_ack  = ~1,500ms (driver sees notification, taps)
total_p95              = ~1,710ms  # fits in 2s budget

# Redis cluster sizing
writes_per_sec         = 12,500 (location) + 1,667 (state) = ~14,200/sec
single_redis_capacity  = ~100,000 ops/sec
cluster_nodes_needed   = 3 primaries + 3 replicas (1 per vehicle class)

# PostgreSQL for durable records
match_writes_per_sec   = 1,667 offer rows + 500 trip rows = ~2,200 writes/sec
pg_instance            = r6g.4xlarge (16 vCPU, 128GB RAM)
pg_write_throughput    = ~5,000 TPS  # comfortably handles load

The geo index shards naturally by vehicle class - 4 classes means 4 separate Redis keys with roughly 12,500 drivers each. Within a vehicle class, if a single metro grows beyond 100,000 drivers, we can shard by H3 geographic sector - each Redis shard owns a set of H3 cells at resolution 4 (roughly 100x100km cells). Match queries route to the shard(s) covering the rider’s location and the surrounding cells.

The demand spike scenario (10x normal load) is handled through three mechanisms: First, the match job queue absorbs the burst - riders see “Searching for a driver” while jobs drain from the queue. Second, the matching engine auto-scales horizontally (10 to 100 workers) in under 2 minutes via ECS/Kubernetes HPA. Third, we expand the geo search radius automatically from 5km to 10km when the match queue depth exceeds a threshold, trading ETA quality for match likelihood.

Failure Modes and Recovery

Comparison of Approaches

Key Takeaways

• Separate location writes from match state: location updates are high-volume and eventually consistent; match state transitions must be atomic and strongly consistent. Different tools for different jobs.
• Redis GEOSEARCH for hot geo lookups: 50,000 active drivers fit in megabytes of RAM; geohash sorted sets enable sub-5ms radius queries that no relational database can match at this throughput.
• Atomic compare-and-swap for driver locking: a Lua script in Redis performs the read-check-write transition atomically, eliminating the double-match race condition that destroys user trust.
• ETA beats geo-distance for candidate scoring: the closest driver by GPS is rarely the fastest - routing-aware ETAs must inform the final sort, even at the cost of a 150ms batch API call.
• Waterfall vs. parallel offers is a product decision: waterfall minimizes driver friction; parallel maximizes rider speed. In sparse supply, parallel is necessary.
• Offer expiry must be infrastructure-level: relying on application timers for offer cleanup means a crashed matching worker leaves drivers stuck in OFFER_PENDING. TTL-based expiry in Redis is crash-safe.
• H3 spatial indexing enables predictable sharding: mapping coordinates to discrete hexagonal cells makes partitioning deterministic and cell counts uniform across geographic areas.
• Graceful degradation requires pre-planned fallback paths: the PostGIS fallback is 20x slower but tested in production. An untested fallback is not a fallback.

Matching at Uber’s scale is ultimately a concurrent reservation system operating against a moving inventory of human suppliers. The engineering decisions that matter most are not the data structure choices but the consistency boundaries - deciding which operations must be atomic and which can tolerate staleness. Get that boundary wrong and you get double-booked drivers and furious users. Get it right and the system handles 10x spikes without a pager alert.

Frequently Asked Questions

Why not use a database with native geospatial support (PostGIS) instead of Redis?

PostGIS is excellent for offline analytics and complex spatial queries, but it is not designed for the write-read pattern of real-time driver tracking. At 12,500 location writes per second plus 1,667 geo queries per second, PostgreSQL’s MVCC overhead and buffer pool churn become significant. Redis keeps the entire driver fleet position set in RAM with O(log N) updates - no page cache eviction, no vacuum, no write amplification. We use PostGIS as a warm fallback and for durable storage, not as the hot query path.

Why not just send offers to all nearby drivers in parallel?

Parallel offers would require you to cancel N-1 offers after the first driver accepts. This creates a bad experience for the declined drivers (they see an offer that immediately disappears) and breeds distrust in the platform. More subtly, drivers learn to hesitate before accepting because they fear the offer might vanish - this actually decreases overall acceptance rates. Waterfall offers avoid this dynamic.

How do you prevent a driver from gaming their location to cherry-pick high-demand areas?

The driver app encrypts GPS telemetry with a device-bound key. Server-side, we validate location continuity - a driver cannot teleport 5km between pings. If location jumps exceed physically plausible movement (checked against max_speed * ping_interval), we flag the driver for review and fall back to their last known valid position.

What happens when the routing service is completely down?

We maintain a local cache of the last-known ETA for each (origin_cell, destination_cell) pair using H3 resolution 6 cells (~36km2 each). This cache covers the most frequent O-D pairs and has a 5-minute TTL. When the routing service is down, we serve cache hits and fall back to a speed-based ETA formula (distance / average_city_speed) for misses. Match quality degrades but matching continues.

How do you handle supply-demand imbalance at peak (more riders than drivers)?

The match queue acts as a buffer. Riders see “Searching for a driver” while their request waits. The matching engine widens the search radius incrementally: 5km at 0s, 7km at 30s, 10km at 60s. After 5 minutes with no match, the request is cancelled and the rider sees an “unavailable” message. The surge pricing engine (a separate system) is signaled by the queue depth exceeding a threshold - it raises prices to attract more supply, closing the imbalance.

Why is the driver state stored in both Redis and PostgreSQL?

Redis is the source of truth for live state (sub-millisecond reads, CAS transitions). PostgreSQL is the durable audit log. After each successful state transition in Redis, we write an async event to Kafka that a consumer writes to PostgreSQL. This decouples durability from latency. On Redis failure, we can rebuild live state from the PostgreSQL log, though it takes about 60 seconds for a full metro.

Interview Questions

Design the geo-sharding scheme for a global Uber deployment. How do you route a match request to the right shard?

Expected depth: Discuss H3 cell hierarchy (resolution 3 for global shards, resolution 9 for per-metro cells). Explain that the API gateway reads the rider’s city from their GPS coordinate (reverse geocoded at login, cached), routes the request to the metro-specific matching cluster. Mention cell boundary cases where a driver is in one cell but closer than drivers in the rider’s cell. A ring-search that checks neighboring cells solves this.

Walk me through what happens when two riders simultaneously request the same driver - the most popular driver near a concert venue.

Expected depth: Describe the race condition in detail (both workers fetch geo results, both see the same driver as AVAILABLE). Explain the Lua CAS script - only one worker’s HSET succeeds because Redis executes commands serially. The losing worker gets return value 0, moves to next candidate. Discuss what “next candidate” means when all 10 candidates are being simultaneously contested by 50 concurrent match requests - this is the hot-spot problem and requires expanding radius or queuing.

How would you modify this system to support scheduled rides (book a ride 2 hours in advance)?

Expected depth: The current system matches on demand. Scheduled rides require a time-windowed matching run starting 10-15 minutes before pickup. Discuss storing future requests in a PostgreSQL table with a scheduled_pickup_at column, and a cron-based scheduler that materializes them into the live match queue at T-12 minutes. Driver pre-allocation is tricky - a driver available now may be on a trip at T-12; handle with soft reservation and fallback to live matching.

What metrics would you monitor and what alerts would you set?

Expected depth: Key metrics: match_latency_p95 (alert > 3s), match_success_rate (alert < 85%), offer_acceptance_rate per driver cohort (alert < 60%), geo_query_latency_p99 (alert > 20ms), driver_stuck_in_offer_pending_count (alert > 100 for 5 min), kafka_consumer_lag_location_ingestion (alert > 50k). Discuss the difference between a supply shortage alert (expected during demand spikes) and a system malfunction alert (unexpected match failure rate spike).

How would you backfill Redis geo state after a complete Redis cluster failure and replacement?

Expected depth: Read driver_states from PostgreSQL where status != ‘OFFLINE’ AND last_seen_at > NOW() - interval ‘5 minutes’. For each driver, issue GEOADD to the new cluster. This is a cold start from durable state. The tricky part is OFFER_PENDING drivers - some may have accepted or declined during the outage. Describe replaying the Kafka event log from the last checkpoint to reconstruct in-flight offer states before opening the new cluster for live traffic.