LLD Masterclass: Designing a Ride-Sharing Engine (Uber)

1. Requirements (The Scope)

To design a production-grade ride-sharing engine like Uber or Lyft, we must translate ambiguous business processes into a precise technical design. In an advanced Low-Level Design (LLD) interview, we categorize the requirements into functional bounds and non-functional guarantees:

Functional Requirements:

1. User Management: Support two primary actors: Riders and Drivers.
2. Location Telemetry: Track real-time driver coordinates (Latitude & Longitude).
3. Trip Life-Cycle: A rider requests a trip from an origin to a destination. The system calculates pricing, locates nearby drivers, and issues an assignment.
4. State Transition: Model the exact status of a trip: CREATED, ASSIGNED, EN_ROUTE, COMPLETED, CANCELLED.
5. Dynamic Pricing: Compute fares dynamically based on distance, duration, and demand surge multiplier.
6. Matching Logic: Pair riders with the optimal active driver within a spatial radius (e.g., 5km).

Non-Functional Requirements:

1. High Concurrency: The system must handle thousands of matching requests concurrently.
2. Strict Assignment Safety (No Double-Booking): Ensure a single active driver cannot be assigned to two different riders simultaneously.
3. High Availability & Extensibility: Support swapping matching strategies or pricing algorithms at runtime (Open-Closed Principle).

2. Architectural Blueprint & Domain Modeling

A. The Core Entities

To align with Object-Oriented Design (OOD) standards, we establish strong encapsulated models:

• User (Abstract base) $\rightarrow$ Rider and Driver.
• Location: Encapsulates spatial coordinates and provides distance calculators.
• Trip: Manages trip-specific details, state, and route parameters.
• MatchingStrategy (Interface): Strategy pattern to find nearby available drivers.
• PricingStrategy (Interface): Strategy pattern to calculate dynamic trip fares.
• TripStateManager (State pattern): Restricts invalid state transitions (e.g., transitioning from CREATED directly to COMPLETED).

3. High-Fidelity Diagrams

A. Sequence Diagram: Booking & Assignment Flow

The interaction below illustrates how the components coordinate to process a ride request:

sequenceDiagram
    autonumber
    actor R as Rider
    participant M as RideSharingManager
    participant P as PricingStrategy
    participant MS as MatchingStrategy
    actor D as Driver

    R->>M: requestRide(riderId, origin, destination)
    activate M
    M->>P: calculateFare(origin, destination, surge)
    P-->>M: return estimatedFare
    M->>M: createTrip(R, origin, destination, fare)
    M->>MS: findMatchingDriver(origin, radius)
    activate MS
    MS-->>M: return optimalDriver
    deactivate MS
    M->>M: lockDriverAndAssign(tripId, driverId)
    M->>D: offerTrip(tripId)
    D-->>M: acceptTrip(tripId)
    M->>R: notifyTripAssigned(driverDetails, fare)
    deactivate M

B. Trip State Machine Transition

Every trip progresses through strict sequential steps. Invalid transitions must be blocked:

stateDiagram-v2
    [*] --> CREATED : rider requests ride
    CREATED --> ASSIGNED : driver accepts offer
    CREATED --> CANCELLED : rider/system cancels
    ASSIGNED --> EN_ROUTE : driver starts trip
    ASSIGNED --> CANCELLED : rider/driver cancels
    EN_ROUTE --> COMPLETED : driver finishes trip
    COMPLETED --> [*]
    CANCELLED --> [*]

4. Production-Grade Java Implementation

Let's build the complete, thread-safe Java codebase. We use standard packaging paradigms and robust concurrency controls:

A. Location & Telemetry

package com.codesprintpro.ridesharing.model;

public class Location {
    private final double latitude;
    private final double longitude;

    public Location(double latitude, double longitude) {
        this.latitude = latitude;
        this.longitude = longitude;
    }

    public double getLatitude() { return latitude; }
    public double getLongitude() { return longitude; }

    // Computes Haversine or simple Euclidean distance for simulator accuracy
    public double distanceTo(Location other) {
        double theta = this.longitude - other.getLongitude();
        double dist = Math.sin(Math.toRadians(this.latitude)) * Math.sin(Math.toRadians(other.getLatitude()))
                + Math.cos(Math.toRadians(this.latitude)) * Math.cos(Math.toRadians(other.getLatitude()))
                * Math.cos(Math.toRadians(theta));
        dist = Math.acos(dist);
        dist = Math.toDegrees(dist);
        return dist * 60 * 1.1515 * 1.609344; // Distance in Kilometers
    }
}

B. User Entities

package com.codesprintpro.ridesharing.model;

public abstract class User {
    private final String id;
    private final String name;
    private final String email;

    public User(String id, String name, String email) {
        this.id = id;
        this.name = name;
        this.email = email;
    }

    public String getId() { return id; }
    public String getName() { return name; }
}

public class Rider extends User {
    public Rider(String id, String name, String email) {
        super(id, name, email);
    }
}

public class Driver extends User {
    private Location currentLocation;
    private boolean isAvailable;
    private final Object lock = new Object(); // Synchronizing driver availability mutations

    public Driver(String id, String name, String email, Location initialLocation) {
        super(id, name, email);
        this.currentLocation = initialLocation;
        this.isAvailable = true;
    }

    public Location getCurrentLocation() { return currentLocation; }
    
    public void updateLocation(Location newLocation) {
        synchronized(lock) {
            this.currentLocation = newLocation;
        }
    }

    public boolean isAvailable() { return isAvailable; }

    // Thread-safe state check & toggle to prevent double-booking
    public boolean reserveIfAvailable() {
        synchronized(lock) {
            if (isAvailable) {
                isAvailable = false;
                return true;
            }
            return false;
        }
    }

    public void releaseAvailability() {
        synchronized(lock) {
            this.isAvailable = true;
        }
    }
}

C. The Trip & State Enums

package com.codesprintpro.ridesharing.model;

public enum TripStatus {
    CREATED,
    ASSIGNED,
    EN_ROUTE,
    COMPLETED,
    CANCELLED
}

public class Trip {
    private final String tripId;
    private final Rider rider;
    private final Location origin;
    private final Location destination;
    private final double fare;
    
    private Driver driver;
    private TripStatus status;
    private final Object stateLock = new Object();

    public Trip(String tripId, Rider rider, Location origin, Location destination, double fare) {
        this.tripId = tripId;
        this.rider = rider;
        this.origin = origin;
        this.destination = destination;
        this.fare = fare;
        this.status = TripStatus.CREATED;
    }

    public String getTripId() { return tripId; }
    public Rider getRider() { return rider; }
    public Location getOrigin() { return origin; }
    public Location getDestination() { return destination; }
    public double getFare() { return fare; }
    public Driver getDriver() { return driver; }
    public TripStatus getStatus() { return status; }

    // Transition state with thread-safe validation
    public boolean transitionTo(TripStatus targetStatus) {
        synchronized (stateLock) {
            if (isValidTransition(this.status, targetStatus)) {
                this.status = targetStatus;
                return true;
            }
            return false;
        }
    }

    public void assignDriver(Driver driver) {
        synchronized (stateLock) {
            this.driver = driver;
            this.status = TripStatus.ASSIGNED;
        }
    }

    private boolean isValidTransition(TripStatus current, TripStatus target) {
        switch (current) {
            case CREATED:
                return target == TripStatus.ASSIGNED || target == TripStatus.CANCELLED;
            case ASSIGNED:
                return target == TripStatus.EN_ROUTE || target == TripStatus.CANCELLED;
            case EN_ROUTE:
                return target == TripStatus.COMPLETED;
            case COMPLETED:
            case CANCELLED:
            default:
                return false; // Terminal states
        }
    }
}

D. Strategy Contracts (Pricing & Spatial Matching)

package com.codesprintpro.ridesharing.strategy;

import com.codesprintpro.ridesharing.model.Location;
import com.codesprintpro.ridesharing.model.Driver;
import java.util.List;

public interface PricingStrategy {
    double calculateFare(Location origin, Location destination, double surgeMultiplier);
}

public interface MatchingStrategy {
    Driver findDriver(Location origin, List<Driver> availableDrivers, double maxRadiusKm);
}

package com.codesprintpro.ridesharing.strategy;

import com.codesprintpro.ridesharing.model.Location;

public class SurgePricingStrategy implements PricingStrategy {
    private static final double BASE_FARE = 5.0; // Fixed booking charge
    private static final double PER_KM_RATE = 2.0;

    @Override
    public double calculateFare(Location origin, Location destination, double surgeMultiplier) {
        double distance = origin.distanceTo(destination);
        return (BASE_FARE + (distance * PER_KM_RATE)) * surgeMultiplier;
    }
}

package com.codesprintpro.ridesharing.strategy;

import com.codesprintpro.ridesharing.model.Location;
import com.codesprintpro.ridesharing.model.Driver;
import java.util.List;

public class NearestDriverMatchingStrategy implements MatchingStrategy {
    @Override
    public Driver findDriver(Location origin, List<Driver> drivers, double maxRadiusKm) {
        Driver bestDriver = null;
        double minDistance = Double.MAX_VALUE;

        for (Driver driver : drivers) {
            if (driver.isAvailable()) {
                double distance = origin.distanceTo(driver.getCurrentLocation());
                if (distance <= maxRadiusKm && distance < minDistance) {
                    minDistance = distance;
                    bestDriver = driver;
                }
            }
        }
        return bestDriver;
    }
}

E. The Central Coordinator (Thread-Safe Manager)

package com.codesprintpro.ridesharing.manager;

import com.codesprintpro.ridesharing.model.*;
import com.codesprintpro.ridesharing.strategy.*;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.atomic.AtomicInteger;

public class RideSharingManager {
    private static RideSharingManager instance;
    private final Map<String, Trip> activeTrips = new ConcurrentHashMap<>();
    private final List<Driver> drivers = new CopyOnWriteArrayList<>();
    private final AtomicInteger tripCounter = new AtomicInteger(1000);

    private PricingStrategy pricingStrategy;
    private MatchingStrategy matchingStrategy;

    private RideSharingManager() {
        // Defaults
        this.pricingStrategy = new SurgePricingStrategy();
        this.matchingStrategy = new NearestDriverMatchingStrategy();
    }

    public static synchronized RideSharingManager getInstance() {
        if (instance == null) {
            instance = new RideSharingManager();
        }
        return instance;
    }

    public void registerDriver(Driver driver) {
        drivers.add(driver);
    }

    public void setPricingStrategy(PricingStrategy pricingStrategy) {
        this.pricingStrategy = pricingStrategy;
    }

    public void setMatchingStrategy(MatchingStrategy matchingStrategy) {
        this.matchingStrategy = matchingStrategy;
    }

    // High-concurrency matching endpoint
    public Trip requestRide(Rider rider, Location origin, Location destination, double surgeMultiplier) {
        double fare = pricingStrategy.calculateFare(origin, destination, surgeMultiplier);
        String tripId = "TRIP-" + tripCounter.incrementAndGet();
        Trip trip = new Trip(tripId, rider, origin, destination, fare);
        activeTrips.put(tripId, trip);

        System.out.println("[System] Created ride request " + tripId + " for Rider: " + rider.getName() + " | Estimated Fare: $" + String.format("%.2f", fare));

        // Find optimal available driver within 5km radius
        Driver assignedDriver = matchingStrategy.findDriver(origin, drivers, 5.0);

        if (assignedDriver != null) {
            // Strict transaction lock check to secure driver assignment from multi-rider race conditions
            if (assignedDriver.reserveIfAvailable()) {
                trip.assignDriver(assignedDriver);
                System.out.println("[System] SUCCESS! Trip " + tripId + " is assigned to Driver: " + assignedDriver.getName());
            } else {
                System.out.println("[System] COLLISION! Driver " + assignedDriver.getName() + " was matched but reserved by another passenger concurrently.");
                trip.transitionTo(TripStatus.CANCELLED);
            }
        } else {
            System.out.println("[System] FAILED! No available drivers found within radius for Trip " + tripId);
            trip.transitionTo(TripStatus.CANCELLED);
        }

        return trip;
    }

    public void completeTrip(String tripId) {
        Trip trip = activeTrips.get(tripId);
        if (trip != null && trip.transitionTo(TripStatus.COMPLETED)) {
            Driver driver = trip.getDriver();
            if (driver != null) {
                driver.releaseAvailability();
                System.out.println("[System] COMPLETED! Driver " + driver.getName() + " finished Trip " + tripId + " and is now available.");
            }
        }
    }
}

5. Staff-Level Concurrency & Scaling Considerations

During senior and staff interviews, the coding section accounts for only 40% of the grade. The remaining 60% rests on your ability to handle concurrency failures, resource limits, and distribution problems.

1. Eliminating the In-Memory State Limitation

In our Low-Level Design model, we rely on synchronized in-memory hooks (synchronized(lock)). However, in a distributed production deployment spanning 100 microservice nodes, in-memory locks will result in split-brain assignment failures (two separate servers matching the same driver).

• Staff Solution: Switch to a Distributed Lock pattern. Acquire a lock in Redis using a key containing the driver's ID: lock:driver:{id} with a short TTL (e.g., 5 seconds) during matching.

SET lock:driver:12345 UUID NX PX 5000

Only the service thread that successfully acquires this Redis key is authorized to issue the assignment.

2. High-Performance Spatial Indexing

Iterating through a global array of drivers (O(N)) to calculate Haversine distances is completely unviable for large metropolitan areas.

• Staff Solution: Index drivers dynamically using Google S2 or Uber H3 Spatial Hexagons. Represent locations as 64-bit integer cell coordinates. When matching, retrieve active drivers exclusively from cells overlapping the matching search circle. This reduces matching overhead from linear time O(N) to logarithmic time O(log N + K) using cell-spatial hashes.

6. Verification Playground (Simulating Real Operations)

To verify the robust, thread-safe behaviors under concurrent environments, run the simulated operational verification harness:

import com.codesprintpro.ridesharing.manager.RideSharingManager;
import com.codesprintpro.ridesharing.model.*;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class Main {
    public static void main(String[] args) throws InterruptedException {
        RideSharingManager manager = RideSharingManager.getInstance();

        // 1. Register active drivers in metropolitan grid
        Driver driverA = new Driver("D-1", "James", "james@uber.com", new Location(40.7128, -74.0060)); // Midtown NY
        Driver driverB = new Driver("D-2", "Sarah", "sarah@uber.com", new Location(40.7150, -74.0090)); // Nearby NY
        manager.registerDriver(driverA);
        manager.registerDriver(driverB);

        // 2. Set up Riders
        Rider rider1 = new Rider("R-1", "Alice", "alice@gmail.com");
        Rider rider2 = new Rider("R-2", "Bob", "bob@gmail.com");
        Rider rider3 = new Rider("R-3", "Charlie", "charlie@gmail.com");

        Location nycOrigin = new Location(40.7130, -74.0062);
        Location nycDestination = new Location(40.7306, -73.9352);

        System.out.println("--- Starting Uber Ride-Sharing Simulation ---\n");

        // 3. Simulate high concurrent ride requests aiming for the same drivers
        ExecutorService executor = Executors.newFixedThreadPool(3);

        executor.submit(() -> manager.requestRide(rider1, nycOrigin, nycDestination, 1.0));
        executor.submit(() -> manager.requestRide(rider2, nycOrigin, nycDestination, 1.2)); // Surge pricing active
        executor.submit(() -> manager.requestRide(rider3, nycOrigin, nycDestination, 1.0));

        executor.shutdown();
        executor.awaitTermination(5, TimeUnit.SECONDS);

        System.out.println("\n--- Simulation Complete. Concurrency check passed cleanly. ---");
    }
}

7. The LLD Masterclass Scorecard