Skip to main content

Design Uber / Ride-sharing

Uber processes millions of trips daily, with real-time location updates, driver-rider matching, and dynamic pricing. It's a rich system design problem involving geospatial data, real-time systems, and complex matching algorithms.

Requirements​

Functional:

  • Riders can request a ride from their current location to a destination
  • Drivers can accept/decline ride requests
  • Real-time location tracking for both riders and drivers
  • ETA and price estimation before booking
  • Trip tracking during the ride
  • Rating system for drivers and riders

Non-functional:

  • 20M DAU (riders + drivers)
  • 10M trips/day
  • Location updates every 4 seconds per active driver/rider
  • Driver matching latency < 5 seconds
  • 99.99% availability (people depend on this to get home)

Scale Estimation​

Location updates:
- 1M active drivers at peak
- Update every 4 seconds
- 1M / 4 = 250,000 location updates/sec

Trip requests:
- 10M trips/day = ~120 requests/sec (peak: ~500/sec)

Storage:
- Trip record: ~1 KB
- 10M trips/day × 365 × 3 years × 1 KB ≈ 11 TB

Location data:
- Store last known location per driver (~1 KB each)
- 1M drivers × 1 KB = 1 GB (easily in memory)

Core Architecture​

1. Location Tracking Service​

Every driver's app sends a location update every 4 seconds.

// Driver app sends:
{
  driverId: "d123",
  lat: 37.7749,
  lng: -122.4194,
  heading: 270,        // degrees
  speed: 35,           // mph
  status: "available", // available | on_trip | offline
  timestamp: 1704067200000
}

Storage: Use Redis for in-memory location data (fast, supports geospatial queries):

// Store driver location using Redis GEO commands
await redis.geoadd('driver:locations', longitude, latitude, driverId);

// Set additional metadata
await redis.hset(`driver:${driverId}`, {
  status: 'available',
  heading: 270,
  speed: 35,
  lastUpdated: Date.now()
});

// Expire driver if no update for 60 seconds (went offline)
await redis.expire(`driver:${driverId}`, 60);

2. Driver Matching Service​

When a rider requests a ride:

async function findNearbyDrivers(riderLat, riderLng, radiusMiles = 2) {
  // Redis GEORADIUS command — find all drivers within radius
  const nearbyDrivers = await redis.georadius(
    'driver:locations',
    riderLng,
    riderLat,
    radiusMiles,
    'mi',
    'WITHCOORD',  // Include coordinates
    'WITHDIST',   // Include distance
    'ASC'         // Sort by distance
  );

  // Filter to only available drivers
  const availableDrivers = [];
  for (const [driverId, dist, coords] of nearbyDrivers) {
    const driverInfo = await redis.hgetall(`driver:${driverId}`);

    if (driverInfo.status === 'available') {
      availableDrivers.push({
        driverId,
        distance: parseFloat(dist),
        lat: parseFloat(coords[1]),
        lng: parseFloat(coords[0]),
        rating: parseFloat(driverInfo.rating)
      });
    }
  }

  return availableDrivers;
}

async function matchDriver(riderId, riderLocation, destination) {
  // Get price estimate first
  const priceEstimate = await calculatePrice(riderLocation, destination);

  // Find nearby drivers
  const drivers = await findNearbyDrivers(riderLocation.lat, riderLocation.lng);

  if (drivers.length === 0) {
    throw new Error('No drivers available in your area');
  }

  // Score drivers by: distance, rating, acceptance rate
  const scored = drivers.map(d => ({
    ...d,
    score: scoreDriver(d)
  })).sort((a, b) => b.score - a.score);

  // Send request to top drivers in sequence (or parallel for speed)
  for (const driver of scored.slice(0, 3)) {
    const accepted = await sendRideRequest(driver.driverId, {
      riderId,
      pickup: riderLocation,
      dropoff: destination,
      estimatedPrice: priceEstimate,
      timeout: 15000  // 15 second timeout
    });

    if (accepted) {
      await createTrip({ riderId, driverId: driver.driverId, ...});
      return driver;
    }
  }

  throw new Error('No drivers accepted your request');
}

function scoreDriver(driver) {
  const distanceScore = 1 / (driver.distance + 0.1);  // Closer is better
  const ratingScore = driver.rating / 5;
  return distanceScore * 0.7 + ratingScore * 0.3;
}

3. Trip Service​

CREATE TABLE trips (
  trip_id         UUID PRIMARY KEY,
  rider_id        UUID NOT NULL,
  driver_id       UUID NOT NULL,
  status          ENUM('requested', 'accepted', 'in_progress', 'completed', 'cancelled'),
  pickup_lat      DECIMAL(9,6),
  pickup_lng      DECIMAL(9,6),
  dropoff_lat     DECIMAL(9,6),
  dropoff_lng     DECIMAL(9,6),
  distance_miles  DECIMAL(6,2),
  estimated_price DECIMAL(8,2),
  final_price     DECIMAL(8,2),
  surge_multiplier DECIMAL(4,2) DEFAULT 1.0,
  started_at      TIMESTAMP,
  completed_at    TIMESTAMP,
  created_at      TIMESTAMP DEFAULT NOW()
);

4. Surge Pricing​

When demand exceeds supply in an area, prices increase.

async function calculateSurgeMultiplier(lat, lng, radius = 1) {
  const geohash = encodeGeohash(lat, lng, precision = 6);  // ~1.2km precision

  // Count active requests in area
  const requestCount = await getActiveRequestCount(geohash);

  // Count available drivers in area
  const driverCount = await getAvailableDriverCount(lat, lng, radius);

  if (driverCount === 0) return 3.0;  // Maximum surge

  const demandRatio = requestCount / driverCount;

  if (demandRatio < 1.0) return 1.0;        // Normal pricing
  if (demandRatio < 1.5) return 1.25;       // 25% surge
  if (demandRatio < 2.0) return 1.5;        // 50% surge
  if (demandRatio < 3.0) return 2.0;        // 2x surge
  return Math.min(3.0, demandRatio * 0.8);  // Cap at 3x
}

Full Architecture​

[Driver App] → WebSocket → [Location Service] → Redis GEO
[Rider App]  → REST      → [Trip Service]     → PostgreSQL
                             |
                             ↓
                        [Matching Service]
                             |
                    Redis GEO (driver lookup)
                             |
                        [Notification Service]
                             |
                     [Driver App] (push to accept)

Interview Follow-up Questions​

Q: How do you handle the case where a driver accepts a trip and then their app crashes?

Set a timeout on trip acceptance (e.g., 30 seconds). If the driver doesn't confirm pickup within the timeout, reassign the trip. Store trip state in Redis with TTL.

Q: How do you implement real-time tracking during a trip?

Both rider and driver app send location updates every 4 seconds. The WebSocket server fans these updates to the other party. Use a dedicated "tracking channel" per trip: trip:tracking:{tripId}.

Q: How do you handle scaling location updates to 250,000/sec?

Shard the Redis cluster by geographic region. Drivers are always hashed to the same shard based on their last known location region. For the matching service, this means querying the regional shard that covers the rider's area.

Last updated on