Low Level Design: Ride-Share Driver-Rider Matching

What Is a Ride-Share Matching System?

A ride-share matching system pairs riders who need a trip with nearby available drivers. The matching logic must account for proximity, driver preferences, ETA accuracy, and graceful fallback when a driver declines or does not respond. Companies like Uber and Lyft process millions of match attempts per day.

Requirements

Functional Requirements

Maintain a real-time index of available driver locations.
When a ride request arrives, find the best matching driver within a configurable radius.
Estimate pickup ETA for each candidate driver.
Send a match offer to the selected driver; handle acceptance or timeout.
Fall back to the next-best driver if the first declines or does not respond within N seconds.
Mark a driver unavailable once a trip is accepted.

Non-Functional Requirements

Match latency <500 ms p99 (from request received to offer dispatched).
Support 100,000 concurrent active drivers and 10,000 ride requests per second at peak.
Exactly one driver offered per ride request at a time (no double-dispatch).
Stateless matching workers for horizontal scalability.

Core Entities

Driver
------
id              UUID
status          ENUM('available', 'on_trip', 'offline')
lat             DOUBLE
lng             DOUBLE
last_update_ts  TIMESTAMP
vehicle_type    ENUM('economy', 'xl', 'luxury')

RideRequest
-----------
id              UUID
rider_id        UUID
pickup_lat      DOUBLE
pickup_lng      DOUBLE
dropoff_lat     DOUBLE
dropoff_lng     DOUBLE
vehicle_type    ENUM('economy', 'xl', 'luxury')
status          ENUM('searching', 'matched', 'cancelled')
created_at      TIMESTAMP

MatchOffer
----------
id              UUID
ride_id         UUID
driver_id       UUID
offered_at      TIMESTAMP
expires_at      TIMESTAMP
status          ENUM('pending', 'accepted', 'declined', 'expired')

Geospatial Driver Index

Drivers report their location every 4-5 seconds via a lightweight heartbeat. The index must support fast nearest-neighbor queries.

Redis GEO

Use Redis GEOADD drivers:available {lng} {lat} {driver_id} on each heartbeat.
On ride request: GEORADIUS drivers:available {pickup_lng} {pickup_lat} 5 km ASC COUNT 20 to get up to 20 nearest candidates.
Remove driver from the set when they go on a trip or offline.
Use a separate Redis sorted set per vehicle type (e.g., drivers:available:economy) to filter at query time.

Matching Algorithm

function match(ride_request):
    candidates = geo_index.nearest(ride_request.pickup, radius=5km, type=ride_request.vehicle_type, limit=20)
    if candidates is empty:
        return NO_DRIVERS_AVAILABLE

    ranked = []
    for driver in candidates:
        eta = estimate_eta(driver.location, ride_request.pickup)
        score = compute_score(eta, driver)   // lower ETA = better score; add fairness weight
        ranked.append((driver, eta, score))

    ranked.sort(by=score)
    return ranked[0]

Scoring Factors

ETA to pickup: Primary factor. Computed via a routing microservice or approximate Haversine / road-speed heuristic.
Driver acceptance rate: Penalize drivers with high decline rates to reduce offer waste.
Consecutive trip count: Fairness metric to distribute rides among drivers.

ETA Estimation

Fast path: Haversine distance / average road speed for initial ranking (sub-millisecond).
Accurate path: Call a routing service (e.g., OSRM, Google Maps Routes API) asynchronously for the top 3 candidates. Use accurate ETAs to re-rank before dispatching the offer.
Caching: Cache routing results keyed by (grid_cell_origin, grid_cell_dest) with a 30 s TTL to reduce routing API calls during surge periods.

Offer Dispatch and Acceptance Timeout

function dispatch_offer(ride_id, driver_id, eta):
    offer = MatchOffer(ride_id, driver_id, expires_at=now()+15s)
    db.save(offer)
    push_notification(driver_id, offer)          // mobile push or WebSocket
    schedule_timeout(offer.id, delay=15s)        // delayed task via Redis key expiry or task queue

function on_driver_response(offer_id, response):  // ACCEPT or DECLINE
    offer = db.get(offer_id)
    if offer.status != PENDING: return            // already expired or handled
    if response == ACCEPT:
        atomic_claim(offer)                       // mark offer ACCEPTED, set ride MATCHED, remove driver from index
    else:
        mark_offer(offer, DECLINED)
        retry_match(ride_id)                      // fetch next candidate from ranked list

function on_offer_timeout(offer_id):
    offer = db.get(offer_id)
    if offer.status == PENDING:
        mark_offer(offer, EXPIRED)
        retry_match(offer.ride_id)

Preventing Double-Dispatch

Before sending an offer, acquire a distributed lock on the driver ID (Redis SET driver_lock:{id} NX EX 20).
Release the lock only when the offer is accepted, declined, or expired.
This ensures a driver cannot receive two simultaneous offers from concurrent ride requests.

Fallback Strategies

Radius expansion: If no drivers in 5 km, retry with 10 km, then 20 km (configurable per market).
Retry queue: Unmatched ride requests enter a retry queue with exponential backoff. Matched candidates from the original ranked list are tried in order before re-querying the geo index.
Surge-mode batching: Under heavy load, collect ride requests for 500 ms and run a global assignment optimization (bipartite matching) to minimize total ETA across all pairs rather than greedy first-come first-served.

System Architecture

Driver App          Rider App
    |                   |
    v                   v
[Driver Location Service]   [Ride Request Service]
    |  GEOADD to Redis       |  publishes to Kafka: ride-requests
    v                        v
[Redis GEO Index]       [Match Workers] -- Kafka consumers
                              |  query Redis, call Routing Service
                              |  acquire driver lock
                              |  persist MatchOffer to DB
                              v
                         [Notification Service] -- push offer to driver
                              |
                         [Driver App]  -- ACCEPT / DECLINE response
                              |
                         [Offer Handler] -- updates DB, releases lock, triggers retry if needed

Scaling Considerations

Redis cluster: Shard the geo index by city or geohash prefix to avoid single hot keys.
Match worker scaling: Workers are stateless; scale horizontally. Partition Kafka topic by city_id to colocate relevant geo data.
Routing service caching: Warm the cache during pre-peak hours with common origin/destination grid pairs.
Driver heartbeat TTL: Automatically expire stale driver entries from Redis if no heartbeat for >30 s.

Interview Tips

Clarify whether to use greedy matching (first fit) or global optimization (bipartite). Greedy is simpler; global is better under surge.
Distinguish ETA estimation (fast heuristic vs. routing API) and when each is appropriate.
Highlight the distributed lock pattern to prevent double-dispatch early; interviewers look for this.
Discuss acceptance timeout and fallback as a state machine rather than ad hoc logic.

Frequently Asked Questions

How does ride-share driver-rider matching work at scale?

Matching pipelines continuously evaluate open ride requests against available drivers. A typical architecture publishes each new request to a matching service that queries a spatial index for nearby drivers, scores each candidate, and selects the best match — all within a tight SLA (often under 500 ms). At companies like Uber and Lyft the matching loop runs every few seconds, batching multiple open requests to find globally optimal assignments using algorithms borrowed from bipartite graph matching.

What scoring factors determine which driver gets matched to a rider?

Key scoring signals include proximity (straight-line or road-network distance to pickup), estimated time of arrival (ETA), driver rating, acceptance rate, current trip direction (to minimize detours), and driver preference or vehicle type match. Some platforms add fairness signals to prevent the same high-rated drivers from monopolizing requests. Scores are combined via a weighted linear model or a learned ranking model trained on historical completion and rating data.

How do you handle driver acceptance timeouts in a matching system?

When a driver is offered a ride the system starts a countdown timer (typically 10–15 seconds). If the driver doesn’t accept in time, the offer is rescinded and the request re-enters the matching pool so the next-best candidate can be tried. Internally this is implemented with a distributed timer service or a delayed-message queue (e.g., Kafka with scheduled delivery or a Redis sorted set keyed by expiry timestamp). The matching service tracks offer state in a fast store (Redis) so it can atomically cancel the offer and re-dispatch without race conditions.

How does ETA estimation affect matching decisions?

ETA is one of the strongest signals in the matching score because it directly predicts rider wait time, which is the primary satisfaction driver. ETA is computed using real-time traffic data, road network graphs (often stored as routing engines like OSRM or Google Maps Platform), and historical speed profiles by time of day. A driver 0.3 miles away through heavy traffic may have a worse ETA than one 0.5 miles away on a clear highway. Inaccurate ETA estimates cause mismatches — routing engines are therefore kept warm with live traffic feeds and recalibrated continuously.