Design Uber

Uber is a ride-hailing platform connecting riders who need transportation with drivers who have vehicles. The system must handle real-time location tracking, efficient driver matching, and seamless trip management at massive scale.

This walkthrough follows the Interview Framework and focuses on what you'd actually present in a 45-60 minute interview.

Phase 1: Requirements

Functional Requirements

1. Riders can request rides — Enter pickup and drop-off locations, select vehicle type, and request a ride
2. Drivers can accept/reject ride requests — Nearby available drivers receive ride requests and can respond
3. Real-time location tracking — Both parties see live location updates during the trip
4. ETA calculation — Show estimated arrival time for driver pickup and trip completion
5. Trip management — Track trip status from request through completion

Non-Functional Requirements

Capacity Estimation

Given:

• 20M daily active riders, 3M daily active drivers
• 20M trips per day
• Drivers send location updates every 4 seconds

Calculations:

Trips per second:
  20M trips / 86,400 sec ≈ 230 trips/sec

Location updates per second:
  3M drivers / 4 sec = 750K updates/sec

Storage per day:
  - Current driver locations (in-memory): 3M × 36 bytes ≈ 108 MB
  - Trip data: 20M × 100 bytes ≈ 2 GB
  - Location history (if stored): 750K updates/sec × 36 bytes ≈ 2.3 TB/day (raw)
  Total: trip records dominate if you don't persist every location update; otherwise location history dominates

Sensitivity check (sanity):

• 1M drivers with 5s updates ⇒ 200K updates/sec
• 5M drivers with 2s updates ⇒ 2.5M updates/sec

In interviews, call out a retention policy for location history (for example: store only active-trip traces, downsample to 15-30s, and keep 7-30 days in cold storage).

Phase 2: Data Model

Core Entities

-- User profiles (riders and drivers)
users
  id            UUID PRIMARY KEY
  name          VARCHAR(255)
  email         VARCHAR(255)
  phone         VARCHAR(20)
  type          ENUM('rider', 'driver')
  created_at    TIMESTAMP

-- Driver-specific information
drivers
  user_id       UUID PRIMARY KEY REFERENCES users(id)
  city_id       VARCHAR(64)
  vehicle_type  ENUM('economy', 'premium', 'xl')
  license_plate VARCHAR(20)
  status        ENUM('offline', 'available', 'busy')
  rating        DECIMAL(2,1)
  current_trip_id UUID

-- Real-time driver location (Redis, not SQL)
driver_locations
  driver_id     UUID
  latitude      DOUBLE
  longitude     DOUBLE
  geohash       VARCHAR(12)
  updated_at    TIMESTAMP

-- Trip records
trips
  id            UUID PRIMARY KEY
  rider_id      UUID REFERENCES users(id)
  driver_id     UUID REFERENCES drivers(user_id)
  city_id       VARCHAR(64)
  status        ENUM('requested', 'matched', 'pickup', 'in_progress', 'completed', 'cancelled')
  pickup_lat    DOUBLE
  pickup_lng    DOUBLE
  dropoff_lat   DOUBLE
  dropoff_lng   DOUBLE
  fare          DECIMAL(10,2)
  created_at    
  completed_at  

Storage Strategy

Phase 3: API Design

Protocol Choice

• WebSocket for real-time updates (location streaming, trip status)
• REST for transactional operations (request ride, complete trip)

Key Endpoints

# Rider APIs
POST   /rides/request
  Request:  { pickup: {lat, lng}, dropoff: {lat, lng}, vehicle_type }
  Response: { ride_id, status: "matching", eta_seconds }

GET    /rides/{ride_id}
  Response: { ride_id, status, driver: {...}, eta_seconds }

POST   /rides/{ride_id}/cancel
  Response: { success, cancellation_fee }

# Driver APIs
POST   /drivers/location
  Request:  { lat, lng }
  Response: { success }

POST   /drivers/status
  Request:  { status: "available" | "offline" }
  Response: { success }

POST   /rides/{ride_id}/accept
  Response: { ride_id, rider: {...}, pickup: {...} }

POST   /rides/{ride_id}/pickup
  Response: { success, trip_started_at }

POST   /rides/{ride_id}/complete
  Response: { success, fare, trip_duration }

# WebSocket subscriptions
WS /ws/rider/{rider_id}     → driver_location, trip_status updates
WS /ws/driver/{driver_id}   → ride_requests, navigation updates

Phase 4: High-Level Design

Architecture Overview

Component Deep Dive

1. Location Service

The Location Service handles 750K updates/second from drivers:

Why this two-tier approach?

• Redis hash table: O(1) writes for real-time location updates
• QuadTree: Efficient spatial queries, but expensive to update
• Batch QuadTree updates every 10-15 seconds to balance freshness vs. performance

# Redis structure for driver locations
HSET driver:123 lat 37.7749 lng -122.4194 geohash 9q8yy city_id sf updated_at 1703001234
SADD city:sf:drivers 123

# QuadTree leaf node (in-memory)
class QuadTreeNode:
    bounds: BoundingBox
    drivers: Set[DriverID]  # max 500 per leaf
    children: Optional[List[QuadTreeNode]]  # 4 children if split

2. Matching Service

When a rider requests a ride:

Matching Algorithm:

def find_best_driver(pickup_location, vehicle_type):
    # 1. Query QuadTree for nearby drivers (expands radius if needed)
    candidates = quadtree.query_radius(pickup_location, radius=2km)

    # 2. Filter by availability and vehicle type
    candidates = [d for d in candidates
                  if d.status == 'available'
                  and d.vehicle_type == vehicle_type]

    # 3. Get fresh locations from Redis
    for driver in candidates:
        driver.current_location = redis.hgetall(f"driver:{driver.id}")

    # 4. Calculate ETA for each
    for driver in candidates:
        driver.eta = eta_service.calculate(driver.current_location, pickup_location)

    # 5. Rank by composite score
    candidates.sort(key=lambda d: (d.eta, -d.rating))

    return candidates[0]

3. ETA Service

ETA calculation combines routing algorithms with real-time traffic:

Why Contraction Hierarchies?

• Dijkstra on raw road graph: O(E log V), too slow at scale
• Contraction Hierarchies: Preprocess graph into hierarchical layers
• Query time: ~1ms instead of ~100ms

4. Trip State Machine

Handling Driver Disconnection

Mobile networks are unreliable. Handle disconnections gracefully:

# Client-side: Queue location updates when offline
class LocationBuffer:
    def __init__(self):
        self.queue = []

    def add_location(self, lat, lng, timestamp):
        self.queue.append((lat, lng, timestamp))

    def flush_on_reconnect(self):
        # Send queued locations with timestamps
        api.batch_update_locations(self.queue)
        self.queue = []

# Server-side: Mark driver unavailable after timeout
def check_driver_heartbeat():
    for driver_id in get_active_drivers():
        last_update = redis.hget(f"driver:{driver_id}", "updated_at")
        if now() - last_update > 30_seconds:
            mark_driver_offline(driver_id)

Phase 5: Scaling & Deep Dives

Scaling the Location Service

Challenge: 750K location updates/second

Solution: Geographically partitioned Redis clusters

Sharding Strategy: Use geohash prefix (first 3-4 characters) to route to the appropriate cluster. Drivers in the same geographic region hit the same Redis shard.

Scaling the Matching Service

Challenge: Nearby driver queries must be fast and consistent

Solution: Replicated QuadTrees with eventual consistency

# Each city has its own QuadTree instance
class CityQuadTreeManager:
    def __init__(self, city_id):
        self.city_id = city_id
        self.quadtree = QuadTree(city_bounds[city_id])
        self.rebuild_interval = 15  # seconds

    def rebuild_from_redis(self):
        """Periodic rebuild from Redis (source of truth)"""
        drivers = redis.smembers(f"city:{self.city_id}:drivers")
        self.quadtree = QuadTree(city_bounds[self.city_id])
        for driver_id in drivers:
            driver = redis.hgetall(f"driver:{driver_id}")
            if driver.status == 'available':
                self.quadtree.insert(driver_id, driver.lat, driver.lng)

Database Sharding

Trips table: Shard by city_id + date (store city_id on trips and drivers)

-- Shard key: city_id
-- Partition: monthly
trips_sf_2024_01, trips_sf_2024_02, ...
trips_nyc_2024_01, trips_nyc_2024_02, ...

Why city-based sharding?

• Most queries are city-scoped (drivers don't cross oceans)
• Natural data locality
• Easy to scale by adding cities

Handling the "Thundering Herd"

When a popular event ends (concert, sports game), thousands of ride requests hit simultaneously:

# Rate limiting + request queuing
class SurgeManager:
    def handle_ride_request(self, request):
        city = get_city(request.pickup)

        # Check if city is in surge
        if self.get_pending_requests(city) > threshold:
            # Apply surge pricing
            request.surge_multiplier = self.calculate_surge(city)

            # Queue instead of immediate matching
            self.request_queue[city].push(request)
            return {"status": "queued", "position": queue_position}

        return self.match_immediately(request)

Consistency for Trip Assignment

Problem: Two concurrent requests could assign the same driver to different rides

Solution: Optimistic locking with database transactions (driver row)

-- Within a transaction: create trip, then claim driver
-- Attempt to assign driver (atomic)
UPDATE drivers
SET status = 'busy', current_trip_id = :trip_id
WHERE user_id = :driver_id
  AND status = 'available'
  AND current_trip_id IS NULL;

-- Check if assignment succeeded
-- (affected_rows == 1 means success)

Fault Tolerance

Common Pitfalls

Interview Checklist

Summary