Ride Matching Service Low-Level Design: Driver-Rider Matching, ETA Calculation, and Surge Pricing

Ride Matching Service Low-Level Design

A ride matching service connects riders with nearby drivers in real time, computing ETAs, scoring candidates, and handling surge pricing. This LLD covers driver location tracking, the dispatch loop, and the driver state machine.

Driver Location Tracking

Active drivers send a GPS update every 5 seconds from the mobile app. The location service writes each update to a Redis geospatial index:

GEOADD drivers_available {longitude} {latitude} {driver_id}

Only drivers in the AVAILABLE state are in the drivers_available key. When a driver is dispatched or goes offline, they are removed with ZREM drivers_available {driver_id}. Redis geospatial commands provide O(N+log(M)) nearby lookups without a specialized spatial DB.

Driver State Machine

AVAILABLE → DISPATCHED → ENROUTE_TO_RIDER → TRIP_IN_PROGRESS → COMPLETED
                      ↘ (no accept, timeout) → AVAILABLE

State is stored in Redis as driver:{id}:state for low-latency reads. Transitions are written to the driver DB table as well for audit and analytics. Invalid transitions (e.g., COMPLETED → TRIP_IN_PROGRESS) are rejected at the service layer.

Nearby Driver Search

When a rider requests a trip, the matching service runs:

GEORADIUS drivers_available {rider_lng} {rider_lat} 5 km
  ASC COUNT 20

This returns up to 20 available drivers within 5km, sorted by distance. The 20-candidate limit caps the scoring workload while providing enough candidates to handle fast acceptance.

Match Scoring

Each candidate driver is scored:

score = w1 * (1 / eta_minutes)
      + w2 * driver_rating        // 0-5 scale
      + w3 * acceptance_rate      // 0-1 ratio

ETA weight (w1) is highest — a nearby driver with a 2-minute ETA beats a highly rated driver 8 minutes away. For the top 5 candidates after fast scoring, the routing API is called to get accurate ETA (traffic-aware). The remaining candidates use the straight-line / average speed estimate.

Dispatch Algorithm

Score and rank all candidates.
Atomically mark the top driver as DISPATCHED using Redis SET NX: SET driver:{id}:state DISPATCHED NX EX 15. If another process already dispatched this driver, move to the next candidate.
Send push notification to the driver with trip details.
Start a 10-second acceptance timer. If the driver does not accept within 10 seconds, set state back to AVAILABLE and dispatch to the next candidate.
On accept: create trip record, notify rider of matched driver and ETA.

The NX flag ensures only one dispatch wins the race for a given driver even under concurrent rider requests.

ETA Calculation

Two-tier ETA approach: fast estimate using Haversine distance divided by average city speed (used for all 20 candidates in scoring); accurate routing API call (Google Maps / Mapbox) used only for top-5 candidates to get traffic-aware ETA shown to the rider. The routing API result is cached per (driver_location_cell, destination_cell) for 60 seconds to reduce API cost.

Surge Pricing

The city is partitioned into geohash cells (~1km x 1km). Every minute, a background job computes per-cell supply/demand:

active_riders    = pending_requests in cell in last 5 min
active_drivers   = AVAILABLE drivers in cell
ratio            = active_riders / max(active_drivers, 1)
surge_multiplier = max(1.0, ratio / target_ratio)

The target ratio is tuned per city (typically 0.5-0.7). Surge multipliers are stored in Redis and displayed to riders before they request. The multiplier is locked to the rider's request time so the fare does not change mid-trip.

Trip Pricing

fare = (base_fare
      + per_mile_rate * distance_miles
      + per_minute_rate * duration_minutes)
     * surge_multiplier

Distance and duration are computed from the actual GPS track, not the route estimate, to ensure accurate billing for detours or traffic.

Driver Cancellation Handling

If the driver cancels while ENROUTE_TO_RIDER, the system: resets driver state to AVAILABLE (but logs a cancellation event against the driver quality score); immediately re-runs the matching algorithm for the rider using the same flow; notifies the rider that a new driver is being found. Too many cancellations penalize the driver's acceptance_rate weight in future scoring.

Geofencing

Drivers are only added to the drivers_available index if their current location falls within the service area polygon. On each location update, a point-in-polygon check runs against the city's GeoJSON boundary. Drivers who drift outside the service zone are automatically removed from the available pool and notified.

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you design the core driver-rider matching algorithm for a ride-hailing platform at scale?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Partition the city into a geospatial grid using S2 cells or geohashes (precision level 6-7 gives ~1-2 km cells). When a rider requests a ride, query active drivers in the rider's cell and adjacent cells. Score each candidate driver with a weighted function: score = w1*(1/ETA) + w2*driver_rating + w3*acceptance_rate. Use a min-heap to extract the top-k candidates efficiently. Send match requests to candidates in ranked order with a short timeout (e.g., 8 seconds); if declined or no response, move to the next candidate. For very high demand, batch incoming requests over a 500ms window and solve as a bipartite matching problem (Hungarian algorithm or auction algorithm) to globally minimize total ETA rather than greedily matching one at a time.”
}
},
{
“@type”: “Question”,
“name”: “How would you calculate accurate ETAs for ride-hailing at scale, accounting for real-time traffic?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Maintain a weighted directed graph of road segments where edge weights represent travel time. Update edge weights continuously using GPS telemetry from active drivers — aggregate speed observations per segment in a sliding 5-minute window and apply exponential moving average to smooth noise. For routing, run a bidirectional Dijkstra or A* on this live graph. Pre-compute landmark-to-landmark distances (ALT algorithm) for common city-wide paths to speed up queries. Expose ETA as a range (e.g., 4-6 min) rather than a point estimate since precision implies false certainty. Cache segment weights in Redis with a short TTL (30-60s); on cache miss, fall back to historical average speeds segmented by time-of-day and day-of-week.”
}
},
{
“@type”: “Question”,
“name”: “How do you design a surge pricing system that responds to real-time supply-demand imbalance?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Continuously compute supply-demand ratio per geospatial zone: ratio = active_available_drivers / open_ride_requests in the last 60 seconds. Map ratio ranges to surge multipliers using a configurable lookup table (e.g., ratio 2.0x, 0.5-0.7 -> 1.5x, > 0.7 -> 1.0x). Recalculate every 30 seconds per zone using a stream processor (Kafka Streams or Flink) consuming driver-location and ride-request events. Store current multipliers in Redis for low-latency reads at pricing time. Apply hysteresis: require the ratio to stay in the surge-triggering range for two consecutive intervals before activating surge, and keep surge active for at least one interval after the ratio recovers, preventing rapid oscillation. Always show the surge multiplier to riders before booking confirmation to meet regulatory and UX requirements.”
}
},
{
“@type”: “Question”,
“name”: “How would you handle the data model and state machine for a ride in a ride-hailing system?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Model a ride with states: REQUESTED -> DRIVER_ASSIGNED -> DRIVER_EN_ROUTE -> ARRIVED -> IN_PROGRESS -> COMPLETED (terminal) or CANCELLED (terminal). Store the ride row with columns: ride_id (UUID), rider_id, driver_id, status, pickup_location (PostGIS POINT), dropoff_location, requested_at, matched_at, pickup_at, dropoff_at, base_fare, surge_multiplier, final_fare. Enforce valid transitions in your service layer (never let the database directly accept arbitrary status updates) and write each transition as an append-only event to a ride_events table for auditability and replay. Publish state-change events to a Kafka topic so downstream services (billing, notifications, analytics) react asynchronously without coupling to the ride service. Use distributed locking (Redis Redlock) on ride_id during status transitions to prevent race conditions when driver and rider actions arrive concurrently.”
}
}
]
}