Design a Ride Sharing System

Design a Ride Sharing System

A ride sharing system like Lyft or Ola connects riders with drivers using real-time geospatial matching. While similar to Uber (covered in a separate case study), this guide focuses on the unique challenges of ride sharing: carpooling/shared rides, driver allocation optimization, dynamic pricing, and real-time ETA computation. This is a frequently asked system design question that tests geospatial indexing, real-time processing, and distributed systems knowledge.

1. Requirements

Functional Requirements

• Riders request rides by specifying pickup and destination.
• System matches riders with the best available driver.
• Support shared/pooled rides (multiple riders sharing a vehicle).
• Real-time driver tracking on the rider's map.
• Dynamic (surge) pricing based on supply and demand.
• ETA estimation for pickup and trip duration.
• Driver allocation and route optimization.
• Trip fare calculation, payment processing, and receipts.
• Rating system for drivers and riders.

Non-Functional Requirements

• Low latency: Matching within 10 seconds. Location updates in real-time.
• High availability: 99.99% uptime.
• Accuracy: Precise ETA and fare calculations.
• Consistency: No double-booking of drivers.
• Scalability: Handle millions of concurrent rides and drivers globally.

2. Capacity Estimation

3. High-Level Design

4. Detailed Component Design

4.1 Geospatial Matching

The matching engine finds optimal drivers using a spatial index. We use H3 hexagonal grid cells for uniform spatial partitioning:

import h3

class SpatialIndex:
    def __init__(self, resolution=7):
        self.resolution = resolution  # ~1.2 km cell edge
        self.cells = defaultdict(set)  # h3_cell -> set of driver_ids
        self.driver_locations = {}     # driver_id -> (lat, lng, cell, status)

    def update(self, driver_id, lat, lng, status):
        cell = h3.latlng_to_cell(lat, lng, self.resolution)
        old = self.driver_locations.get(driver_id)
        if old and old[2] != cell:
            self.cells[old[2]].discard(driver_id)
        self.cells[cell].add(driver_id)
        self.driver_locations[driver_id] = (lat, lng, cell, status)

    def find_available_nearby(self, lat, lng, radius_rings=2, vehicle_type=None):
        center = h3.latlng_to_cell(lat, lng, self.resolution)
        search_cells = h3.grid_disk(center, radius_rings)

        candidates = []
        for cell in search_cells:
            for driver_id in self.cells.get(cell, set()):
                loc = self.driver_locations[driver_id]
                if loc[3] != "available":
                    continue
                dist = haversine_km(lat, lng, loc[0], loc[1])
                candidates.append((driver_id, dist, loc[0], loc[1]))

        return sorted(candidates, key=lambda x: x[1])

4.2 Driver Allocation Algorithm

Unlike simple nearest-driver matching, ride sharing benefits from batch optimization:

class BatchMatchingEngine:
    """
    Collects ride requests over a 2-second window and solves
    a global assignment problem to minimize total wait time.
    """
    def __init__(self):
        self.pending_requests = []
        self.batch_interval = 2  # seconds

    async def process_batch(self):
        requests = self.drain_pending()
        if not requests:
            return

        # For each request, find top-K candidate drivers
        cost_matrix = []
        for req in requests:
            candidates = spatial_index.find_available_nearby(
                req.pickup_lat, req.pickup_lng, radius_rings=3
            )
            # Cost = ETA to pickup (road network time)
            costs = []
            for driver_id, dist, d_lat, d_lng in candidates[:20]:
                eta = await eta_service.calculate(d_lat, d_lng, req.pickup_lat, req.pickup_lng)
                costs.append((driver_id, eta))
            cost_matrix.append(costs)

        # Solve assignment problem (Hungarian algorithm or greedy)
        assignments = solve_assignment(requests, cost_matrix)

        for req, driver_id, eta in assignments:
            await dispatch(req, driver_id, eta)

Batch matching is superior to greedy nearest-driver because it considers the global picture. For example, if Driver A is equidistant from two riders, batch matching assigns them optimally rather than first-come-first-served.

4.3 Shared/Pooled Rides

Pooled rides (e.g., UberPool, Lyft Shared) match multiple riders going in the same direction into one vehicle:

function findPoolMatch(newRequest, activePoolTrips) {
    const candidates = [];

    for (const trip of activePoolTrips) {
        if (trip.passengerCount >= trip.maxPassengers) continue;

        // Check if the new rider's route aligns with the current trip
        const detourMinutes = calculateDetour(
            trip.currentRoute,
            newRequest.pickup, newRequest.dropoff
        );

        // Max 10 min detour for existing passengers
        const maxDetourForExisting = trip.passengers.map(p =>
            additionalDelay(p.dropoff, newRequest.pickup, newRequest.dropoff)
        );

        if (detourMinutes <= 10 && Math.max(...maxDetourForExisting) <= 10) {
            candidates.push({
                tripId: trip.id,
                detour: detourMinutes,
                savings: calculateFareSavings(newRequest, trip)
            });
        }
    }

    // Return best match by least detour
    return candidates.sort((a, b) => a.detour - b.detour)[0] || null;
}

4.4 Dynamic Pricing (Surge)

The Pricing Engine computes surge per geographic cell:

Surge is calculated every 1-2 minutes per H3 cell. Demand is measured by ride requests in a rolling 5-minute window. Supply is the count of available drivers in the cell and adjacent cells.

4.5 ETA Calculation

ETA computation uses road-network routing with real-time traffic data:

• Road graph: Nodes are intersections, edges are road segments with travel time weights.
• Traffic-weighted edges: Real-time GPS data from active drivers updates edge weights. Historical data fills in where real-time data is sparse.
• Contraction hierarchies: A pre-processing step that adds shortcut edges to speed up Dijkstra queries from O(V log V) to near-constant time for most queries.

function calculateETA(origin, destination, departureTime) {
    // Use contraction hierarchy for fast path computation
    const path = contractionHierarchy.shortestPath(
        nearestNode(origin),
        nearestNode(destination)
    );

    // Sum up travel times with real-time traffic adjustments
    let totalSeconds = 0;
    for (const edge of path.edges) {
        const baseTime = edge.baseTimeSec;
        const trafficFactor = getTrafficFactor(edge.id, departureTime);
        totalSeconds += baseTime * trafficFactor;
    }

    // Add pickup time, traffic light delays
    totalSeconds += estimatePickupDelay(origin);

    return { etaSeconds: Math.round(totalSeconds), path: path };
}

5. Database Schema

CREATE TABLE drivers (
    id BIGINT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    phone VARCHAR(20) UNIQUE NOT NULL,
    vehicle_type VARCHAR(20) NOT NULL,
    vehicle_plate VARCHAR(20) NOT NULL,
    rating DECIMAL(3,2) DEFAULT 5.00,
    status ENUM('offline','available','on_trip','pool_available') DEFAULT 'offline',
    current_lat DECIMAL(9,6),
    current_lng DECIMAL(9,6),
    current_h3_cell VARCHAR(15),
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

CREATE INDEX idx_drivers_h3 ON drivers(current_h3_cell, status);

CREATE TABLE trips (
    id BIGINT PRIMARY KEY,
    rider_id BIGINT NOT NULL,
    driver_id BIGINT,
    pool_trip_id BIGINT,
    status ENUM('requested','matching','accepted','en_route',
                'arrived','in_progress','completed','cancelled'),
    ride_type ENUM('standard','pool','premium','xl'),
    pickup_lat DECIMAL(9,6) NOT NULL,
    pickup_lng DECIMAL(9,6) NOT NULL,
    dropoff_lat DECIMAL(9,6) NOT NULL,
    dropoff_lng DECIMAL(9,6) NOT NULL,
    surge_multiplier DECIMAL(3,2) DEFAULT 1.00,
    estimated_fare_cents BIGINT,
    actual_fare_cents BIGINT,
    distance_meters INT,
    duration_seconds INT,
    requested_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    completed_at TIMESTAMP
);

CREATE TABLE pool_trips (
    id BIGINT PRIMARY KEY,
    driver_id BIGINT NOT NULL,
    status ENUM('active','completed','cancelled'),
    max_passengers INT DEFAULT 3,
    current_passengers INT DEFAULT 0,
    route_polyline TEXT,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

CREATE TABLE ratings (
    trip_id BIGINT NOT NULL,
    rater_id BIGINT NOT NULL,
    ratee_id BIGINT NOT NULL,
    rating SMALLINT NOT NULL CHECK (rating BETWEEN 1 AND 5),
    comment TEXT,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    PRIMARY KEY (trip_id, rater_id)
);

6. Key Trade-offs

7. Scaling Considerations

7.1 Location Processing

500K location updates/sec flow through Kafka, partitioned by driver_id. Consumer services update the in-memory spatial index and write to a time-series store. The spatial index is sharded by geographic region across multiple servers using consistent hashing.

7.2 Matching Engine

The matching engine is partitioned by city/region. Each partition handles only its local area. Auto-scale matching workers based on ride request rate. Use Redis to lock drivers during matching to prevent double-booking.

7.3 Database Sharding

Shard trips by city/region for write scaling. Use read replicas for analytics queries. Location history goes to a time-series database (TimescaleDB or Cassandra) optimized for high-throughput writes.

Use swehelper.com tools to practice ride sharing system design.

8. Frequently Asked Questions

Q1: How does ride pooling match multiple riders into one vehicle?

The pooling service looks for active pool trips where adding the new rider's route would cause minimal detour (under 10 minutes extra) for existing passengers. It checks if the new pickup and dropoff can be inserted into the existing route without exceeding detour limits. If a match is found, the driver's route is updated. If not, a new pool trip is created. Fare is split proportionally based on distance.

Q2: How do you prevent drivers from being matched to multiple rides simultaneously?

Use optimistic concurrency control. When the matching engine selects a driver, it atomically attempts to change the driver's status from "available" to "matching" using a compare-and-swap operation in Redis. Only one concurrent match attempt can succeed. The losing request retries with the next candidate. This is the same pattern used in Uber's design.

Q3: How is surge pricing communicated to riders?

Before confirming a ride, the app shows the rider an upfront fare estimate that includes any surge multiplier. The rider must explicitly accept the surge price. Once confirmed, the surge rate is locked for that ride. If the surge changes before the driver arrives, the rider's fare remains at the locked rate. This transparency is required by regulations in many jurisdictions.

Q4: How does the system handle traffic data for ETA accuracy?

Active drivers continuously send GPS data (every 4 seconds). This data is aggregated per road segment to compute real-time average speed. For road segments without current data, historical averages (time-of-day, day-of-week) are used. Machine learning models trained on millions of historical trips further refine ETA predictions. The combination of real-time, historical, and ML-based signals produces ETA accuracy within 2-3 minutes for most trips.