Ride Sharing

Requirements

Functional Requirements

• Rider: request ride, track driver location, rate driver, cancel ride
• Driver: accept/reject ride request, navigate to pickup, complete trip
• Admin: view analytics, manage pricing rules, handle disputes

Non-Functional Requirements

• Low latency matching (< 10 seconds)
• High availability (99.99%)
• Consistent driver location updates
• Scalable to millions of concurrent users

Core Entities

User (base)
├── Rider
│   - userId, name, phone, email
│   - paymentMethods[]
│   - rating
└── Driver
    - userId, name, phone, email
    - vehicleDetails
    - currentLocation (lat, lng)
    - status (AVAILABLE, ON_TRIP, OFFLINE)
    - rating

Trip
- tripId
- riderId
- driverId
- pickupLocation
- dropoffLocation
- status (TripStatus enum)
- fare
- distance
- duration
- createdAt, startedAt, completedAt

Location
- latitude
- longitude
- timestamp

Trip State Machine

REQUESTED ──→ MATCHED ──→ IN_PROGRESS ──→ COMPLETED
    │              │             │
    │              │             └──→ CANCELLED (by driver/rider)
    │              └──→ CANCELLED (rider cancels before pickup)
    └──→ CANCELLED (rider cancels immediately)

Design Patterns

Pattern	Where	Why
State	Trip status transitions	Encapsulate valid transitions per state
Strategy	Pricing algorithms	Swap pricing rules (normal, surge, promo)
Observer	Location updates	Notify riders of driver position
Factory	Trip creation	Create trips with different ride types

Matching Algorithm

Location Service

Use geohash for spatial indexing. Geohash converts (lat, lng) to a string prefix; nearby locations share prefixes.

Geohash precision:
precision=5 → ~5km x 5km cell
precision=6 → ~1.2km x 600m cell
precision=7 → ~153m x 153m cell

Store drivers in a Map<String, Set<DriverId>> where key is geohash prefix. To find nearby drivers:

1. Compute rider's geohash
2. Look up current cell + 8 neighboring cells
3. Filter drivers by actual Haversine distance < threshold

Haversine Distance Formula

d = 2R * arcsin(
    sqrt(
        sin²((lat2-lat1)/2) +
        cos(lat1) * cos(lat2) * sin²((lng2-lng1)/2)
    )
)

Matching Flow

Rider requests ride
        │
        ▼
┌─────────────────┐
│ LocationService │──→ Get nearby drivers (geohash + distance filter)
└─────────────────┘
        │
        ▼
┌──────────────────┐
│ MatchingService  │──→ Rank drivers by score
└──────────────────┘
        │
        ▼
┌──────────────────┐
│ Notify top-N     │──→ Push notification to top 3 drivers
│ drivers          │
└──────────────────┘
        │
        ▼
┌──────────────────┐
│ Wait for accept  │──→ Timeout? Try next driver
│ or reject        │
└──────────────────┘
        │
        ▼
    Trip MATCHED

Driver Ranking Score

score = w1 * (1 / distance) +
        w2 * (1 / eta) +
        w3 * driverRating +
        w4 * acceptanceRate

Weights: distance (0.4), ETA (0.3), rating (0.2), acceptance rate (0.1)

Java Implementation

public class LocationService {
    private final Map<String, Set<String>> geohashToDrivers = new ConcurrentHashMap<>();
    private final Map<String, Location> driverLocations = new ConcurrentHashMap<>();

    public void updateDriverLocation(String driverId, double lat, double lng) {
        Location loc = new Location(lat, lng, System.currentTimeMillis());
        driverLocations.put(driverId, loc);
        String geohash = Geohash.encode(lat, lng, 7);
        geohashToDrivers.computeIfAbsent(geohash, k -> ConcurrentHashMap.newKeySet()).add(driverId);
    }

    public List<String> findNearbyDrivers(double lat, double lng, double radiusKm) {
        String centerHash = Geohash.encode(lat, lng, 7);
        Set<String> candidates = new HashSet<>();
        for (String neighbor : Geohash.neighbors(centerHash)) {
            candidates.addAll(geohashToDrivers.getOrDefault(neighbor, Set.of()));
        }
        candidates.addAll(geohashToDrivers.getOrDefault(centerHash, Set.of()));

        return candidates.stream()
            .filter(id -> {
                Location loc = driverLocations.get(id);
                return loc != null && haversine(lat, lng, loc.lat, loc.lng) <= radiusKm;
            })
            .sorted(Comparator.comparingDouble(id -> {
                Location loc = driverLocations.get(id);
                return haversine(lat, lng, loc.lat, loc.lng);
            }))
            .collect(Collectors.toList());
    }

    private double haversine(double lat1, double lng1, double lat2, double lng2) {
        double R = 6371;
        double dLat = Math.toRadians(lat2 - lat1);
        double dLng = Math.toRadians(lng2 - lng1);
        double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
                   Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
                   Math.sin(dLng/2) * Math.sin(dLng/2);
        return R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
    }
}

public class MatchingService {
    private final LocationService locationService;
    private final NotificationService notificationService;
    private final double SEARCH_RADIUS_KM = 5.0;

    public Optional<Driver> matchDriver(Rider rider, Location pickup) {
        List<String> nearbyDriverIds = locationService.findNearbyDrivers(
            pickup.lat, pickup.lng, SEARCH_RADIUS_KM
        );

        List<Driver> ranked = nearbyDriverIds.stream()
            .map(driverService::getDriver)
            .filter(d -> d.getStatus() == DriverStatus.AVAILABLE)
            .sorted(this::compareDrivers)
            .limit(3)
            .collect(Collectors.toList());

        for (Driver driver : ranked) {
            boolean accepted = notificationService.notifyDriverForTrip(driver, rider);
            if (accepted) return Optional.of(driver);
        }
        return Optional.empty();
    }

    private int compareDrivers(Driver a, Driver b) {
        double scoreA = calculateScore(a);
        double scoreB = calculateScore(b);
        return Double.compare(scoreB, scoreA);
    }

    private double calculateScore(Driver driver) {
        return 0.4 * (1.0 / Math.max(driver.getEta(), 1)) +
               0.3 * (driver.getRating() / 5.0) +
               0.2 * (driver.getAcceptanceRate()) +
               0.1 * (driver.getTripCount() > 0 ? 1.0 : 0.5);
    }
}

Pricing

Pricing Formula

Total Fare = Base Fare + (Distance × Per-KM Rate) + (Time × Per-Min Rate) + Surge Multiplier - Promo Discount

Ride Type	Base Fare	Per-KM	Per-Min
Economy	$2.00	$1.00	$0.15
Comfort	$3.50	$1.50	$0.20
Premium	$5.00	$2.50	$0.35

Surge Pricing

Surge Multiplier = Demand / Supply

If surge < 1.0 → multiplier = 1.0 (no discount)
If 1.0 ≤ surge < 1.5 → multiplier = 1.2
If 1.5 ≤ surge < 2.0 → multiplier = 1.5
If surge ≥ 2.0 → multiplier = min(surge, 3.0)

Payment Flow

1. Rider requests trip
2. System places HOLD on rider's payment method (estimated fare × 1.2)
3. Trip completes
4. System CHARGES actual fare
5. If hold > actual → release difference
6. If split payment → divide among group members

Java Implementation

public interface PricingStrategy {
    double calculateFare(Trip trip);
}

public class StandardPricing implements PricingStrategy {
    private static final double BASE_FARE = 2.0;
    private static final double PER_KM = 1.0;
    private static final double PER_MINUTE = 0.15;

    @Override
    public double calculateFare(Trip trip) {
        double distanceFare = trip.getDistanceKm() * PER_KM;
        double timeFare = trip.getDurationMinutes() * PER_MINUTE;
        return BASE_FARE + distanceFare + timeFare;
    }
}

public class SurgePricing implements PricingStrategy {
    private final PricingStrategy basePricing;
    private final Map<String, Double> surgeZones; // geohash → multiplier

    public SurgePricing(PricingStrategy basePricing, Map<String, Double> surgeZones) {
        this.basePricing = basePricing;
        this.surgeZones = surgeZones;
    }

    @Override
    public double calculateFare(Trip trip) {
        double baseFare = basePricing.calculateFare(trip);
        String pickupGeohash = Geohash.encode(
            trip.getPickup().lat, trip.getPickup().lng, 5
        );
        double multiplier = surgeZones.getOrDefault(pickupGeohash, 1.0);
        return baseFare * multiplier;
    }
}

public class PricingService {
    private final Map<RideType, PricingStrategy> strategies = Map.of(
        RideType.ECONOMY, new SurgePricing(new StandardPricing(), new HashMap<>()),
        RideType.COMFORT, new SurgePricing(new ComfortPricing(), new HashMap<>()),
        RideType.PREMIUM, new SurgePricing(new PremiumPricing(), new HashMap<>())
    );

    public double calculateFare(Trip trip) {
        PricingStrategy strategy = strategies.get(trip.getRideType());
        double fare = strategy.calculateFare(trip);
        return Math.round(fare * 100.0) / 100.0; // round to 2 decimals
    }
}

public class PaymentService {
    public void processPayment(Trip trip) {
        double estimatedFare = pricingService.calculateFare(trip);

        // Hold amount
        paymentGateway.hold(trip.getRider().getPaymentMethod(), estimatedFare * 1.2);

        // On trip completion...
        double actualFare = pricingService.calculateFare(trip);
        paymentGateway.charge(trip.getRider().getPaymentMethod(), actualFare);

        if (estimatedFare * 1.2 > actualFare) {
            paymentGateway.release(trip.getRider().getPaymentMethod(),
                estimatedFare * 1.2 - actualFare);
        }
    }
}

Follow-ups

1. Ride Sharing / Pool Rides

Match multiple riders heading in the same direction.

Rider A: Downtown → Airport
Rider B: Downtown → Airport (3 blocks away)

→ Match both to same driver
→ Route: A_pickup → B_pickup → A_dropoff → B_dropoff (or reverse)
→ Split fare: each pays 60-70% of solo fare

2. ETA Prediction

Use historical trip data + real-time traffic:

• ML Model: Features = distance, time of day, day of week, weather, road type
• Simple heuristic: ETA = distance / avg_speed + traffic_penalty

3. Cancellation Handling

Who Cancels	When	Consequence
Rider	Before driver arrives	Free, driver gets small compensation
Rider	After driver arrives	Rider pays cancellation fee
Driver	Before pickup	No penalty
Driver	After multiple cancellations	Reduced ranking

4. Scaling Concerns

• Location updates: 1M drivers × 1 update/sec = 1M writes/sec → use Redis for hot data, Kafka for event stream
• Matching: Partition by geohash region, each partition handled by separate service instance
• Database: Sharding by city/region, read replicas for tracking, write-heavy for trip data

5. Driver Location Tracking

// WebSocket connection for real-time tracking
public class LocationWebSocket {
    public void onDriverLocationUpdate(String driverId, Location loc) {
        locationService.updateDriverLocation(driverId, loc.lat, loc.lng);
        // Notify all riders tracking this driver
        eventBus.publish(new DriverLocationEvent(driverId, loc));
    }
}

// Polling fallback (every 5 seconds)
@Scheduled(fixedRate = 5000)
public void broadcastDriverLocations() {
    List<ActiveTrip> activeTrips = tripService.getActiveTrips();
    for (ActiveTrip trip : activeTrips) {
        Location driverLoc = locationService.getLocation(trip.getDriverId());
        notificationService.notifyRider(trip.getRiderId(), driverLoc);
    }
}

6. Class Diagram

┌─────────┐       ┌──────────────┐
│  Rider   │──────▶│    Trip      │
└─────────┘       └──────────────┘
                        │
                        ▼
┌─────────┐       ┌──────────────┐
│ Driver  │◀──────│TripState     │
└─────────┘       │(State pattern)│
     │            └──────────────┘
     ▼
┌──────────┐     ┌────────────────┐
│ Location │     │PricingStrategy │
│  Service │     │ (Strategy)     │
└──────────┘     └────────────────┘
     │                  │
     ▼                  ▼
┌──────────┐     ┌────────────────┐
│ Geohash  │     │ PaymentGateway │
│  Index   │     └────────────────┘
└──────────┘