Low-Level Design: Ride-sharing Matching Engine — Driver Matching, Pricing, and Trip State Machine

By /
⏱ 5 min read

Core Entities

Driver: driver_id, current_location (lat/lng), status (AVAILABLE, ON_TRIP, OFFLINE), vehicle_type, rating. Rider: rider_id, payment_method_id, rating. Trip: trip_id, rider_id, driver_id, pickup_location, dropoff_location, status, fare_cents, started_at, ended_at. TripRequest: request_id, rider_id, pickup, dropoff, vehicle_type, status (SEARCHING, MATCHED, CANCELLED).

Trip State Machine

REQUESTED → SEARCHING → DRIVER_ASSIGNED → DRIVER_EN_ROUTE → ARRIVED → IN_PROGRESS → COMPLETED / CANCELLED.

Transitions: rider requests → SEARCHING. System finds driver → DRIVER_ASSIGNED. Driver accepts → DRIVER_EN_ROUTE. Driver reaches pickup → ARRIVED. Rider boards → IN_PROGRESS. Dropoff confirmed → COMPLETED. Either party cancels → CANCELLED (with cancellation fee if applicable).

Geo-Spatial Driver Matching

Store driver locations in Redis using the GEO commands: GEOADD drivers lng lat driver_id. On trip request: GEORADIUS drivers lng lat 5 km ASC COUNT 20 to find the 20 nearest available drivers within 5km. Filter by AVAILABLE status (stored as a Redis Hash per driver). Score candidates by: proximity (primary), driver rating (secondary), acceptance rate (tertiary). Offer the trip to the top-ranked driver first. If no response within 10 seconds, offer to the next candidate.

Driver location updates: each driver app sends GPS coordinates every 4-5 seconds. Update via GEOADD (overwrites existing position). At 1M active drivers, this is 200K-250K Redis writes/second — requires Redis Cluster.

Surge Pricing (Dynamic Pricing)

Surge multiplier = f(supply, demand) in a geo-cell. Divide the city into hexagonal cells (H3 library). For each cell, count active trip requests (demand) and available drivers (supply). Surge multiplier = max(1.0, demand / (supply * baseline_ratio)). Cap at configured maximum (e.g., 5x). Recalculate every 60 seconds. Store multipliers in Redis with TTL. Fare = base_fare * surge_multiplier. Show the surge to riders before confirmation and require explicit acceptance.

Fare Calculation

Base fare = base_fee + (per_minute_rate * duration_minutes) + (per_mile_rate * distance_miles). Apply surge multiplier. Apply promotions/discounts. Minimum fare enforced. Store all components on the Trip record for transparency and dispute resolution. Distance computed from GPS trace (Haversine formula between sequential GPS points) not straight-line estimate.

Driver Matching Algorithm

class MatchingEngine:
    def find_driver(self, request: TripRequest) -> Optional[Driver]:
        candidates = self.geo.nearby_drivers(
            request.pickup, radius_km=5, limit=20
        )
        available = [d for d in candidates 
                     if d.status == DriverStatus.AVAILABLE]
        scored = sorted(available, key=lambda d: self.score(d, request))
        for driver in scored:
            if self.offer_trip(driver, request, timeout=10):
                return driver
        return None  # no driver found — retry or notify rider

    def score(self, driver, request):
        distance = haversine(driver.location, request.pickup)
        return distance - (driver.rating * 0.5)  # closer + higher rating

Handling Driver Rejection and Timeout

Track offer history per request to avoid re-offering to the same driver. After offering to all nearby candidates with no acceptance, expand the search radius (5km → 8km → 12km) and retry. After N expansions with no match, cancel the request with a “No drivers available” message. Monitor acceptance rate per driver; low acceptance rates affect scoring. Timeout handling: if a driver does not respond in 10 seconds, mark the offer as expired and move to the next candidate (do not block the matching thread — use async tasks with deadlines).

Concurrency: Preventing Double-Assignment

When offering a trip to a driver, use optimistic locking: UPDATE drivers SET status=ON_TRIP, current_trip_id=X WHERE driver_id=Y AND status=AVAILABLE. If 0 rows updated, the driver was already assigned elsewhere — try the next candidate. This atomic check-and-update prevents two riders from being matched to the same driver simultaneously.

Asked at: Uber Interview Guide

Asked at: Lyft Interview Guide

Asked at: DoorDash Interview Guide

Asked at: Airbnb Interview Guide

Scroll to Top