Requirements & Scope
Functional Requirements
- Request Ride: Rider specifies pickup location and destination, sees fare estimate
- Match Driver: System finds and assigns nearest available driver
- Track Location: Real-time driver location updates visible to rider
- Fare Estimation: Upfront fare estimate based on distance, time, demand
- Payment: Automatic payment processing (credit card, wallet)
- Rating: Both rider and driver rate each other after trip
- Trip History: View past trips with details and receipts
Non-Functional Requirements
- Low Latency Matching: Match driver within 15-30 seconds of request
- Real-Time Location: Driver location updates every 3-4 seconds
- High Availability: 99.99% uptime (ride requests anytime)
- Scalability: Handle 1M+ concurrent drivers, 10M+ daily trips
- Consistency: Trip state must be consistent (no double-booking)
Capacity Estimation
Assumptions:
- 1M concurrent drivers
- 10M daily trips
- Average trip: 20 minutes, 8km
- Location updates: every 3 seconds per driver
Write QPS:
- Location updates: 1M * (1/3) ≈ 333,000 QPS
- Trip requests: 10M / 86400 ≈ 115 QPS
- Trip state updates: ~500 QPS
Read QPS:
- Location reads (rider tracking): 333,000 * 2 = 666,000 QPS
- Trip status reads: ~1,000 QPS
Storage:
- Driver locations: 1M * 50 bytes * 3600 * 24 ≈ 4TB/day
- Trip data: 10M * 1KB = 10GB/day
- Historical: ~100TB/year
Location & Matching
Geospatial Indexing
Geohash
Divide world into grid cells using hierarchical geohash:
┌─────────────────────────────────────────────┐
│ GEOHASH GRID EXAMPLE │
├─────────────────────────────────────────────┤
│ │
│ Level 0: 1 cell covers entire world │
│ ┌────────────────────────────────────────┐ │
│ │ World │ │
│ └────────────────────────────────────────┘ │
│ │
│ Level 2: 32x32 grid │
│ ┌──────┬──────┬──────┬──────┐ │
│ │ 9q8y │ 9q8z │ 9q90 │ 9q91 │ ... │
│ ├──────┼──────┼──────┼──────┤ │
│ │ 9q8u │ 9q8v │ 9q8w │ 9q8x │ ... │
│ └──────┴──────┴──────┴──────┘ │
│ │
│ Level 6: Fine-grained (city block) │
│ Each cell: ~1.2km x 0.6km │
│ ┌────┬────┬────┬────┐ │
│ │9q8y│9q8y│9q8y│9q8y│ ... │
│ │u23 │u24 │u25 │u26 │ │
│ └────┴────┴────┴────┘ │
│ │
└─────────────────────────────────────────────┘
Quadtree (Alternative)
Recursive spatial partitioning:
┌───────────────────────────┐
│ ┌─────────┬─────────┐ │
│ │ Drivers │ Drivers │ │
│ │ 0-50 │ 51-100 │ │
│ ├─────────┼─────────┤ │
│ │ Drivers │ Drivers │ │
│ │ 101-150 │ 151-200 │ │
│ └─────────┴─────────┘ │
│ │ │
│ Split if > threshold │
│ (e.g., 100 drivers) │
└───────────────────────────┘
Driver Availability Service
import redis
import geohash
class DriverLocationService:
def __init__(self):
self.redis = redis.Redis()
def update_driver_location(self, driver_id: str, lat: float, lng: float):
"""Update driver location every 3-4 seconds."""
# Store in Redis sorted set by geohash
gh = geohash.encode(lat, lng, precision=7) # ~150m accuracy
self.redis.zadd(
f"drivers:geo:{gh[:4]}", # Group by geohash prefix
{driver_id: self._to_score(lat, lng)}
)
# Store driver details
self.redis.hset(f"driver:{driver_id}", mapping={
"lat": lat,
"lng": lng,
"geohash": gh,
"updated_at": time.time(),
"status": "available"
})
def find_nearby_drivers(self, lat: float, lng: float, radius_km: float = 5):
"""Find drivers within radius using geohash neighbors."""
center_gh = geohash.encode(lat, lng, precision=7)
# Get neighboring geohash cells
neighbors = geohash.neighbors(center_gh)
candidates = []
for cell in [center_gh[:4]] + [n[:4] for n in neighbors]:
drivers = self.redis.zrangebyscore(
f"drivers:geo:{cell}",
min=self._to_score(lat - radius_km/111, lng - radius_km/111),
max=self._to_score(lat + radius_km/111, lng + radius_km/111)
)
candidates.extend(drivers)
# Filter by actual distance
nearby = []
for driver_id in candidates:
driver = self.redis.hgetall(f"driver:{driver_id}")
dist = self._haversine(lat, lng, float(driver[b'lat']), float(driver[b'lng']))
if dist <= radius_km:
nearby.append({
"driver_id": driver_id,
"distance": dist,
"lat": float(driver[b'lat']),
"lng": float(driver[b'lng'])
})
# Sort by distance
return sorted(nearby, key=lambda x: x['distance'])
Matching Algorithm
┌─────────────────────────────────────────────────────┐
│ MATCHING FLOW │
├─────────────────────────────────────────────────────┤
│ │
│ Rider Request │
│ ┌────────────────────────────────────────────────┐ │
│ │ pickup_lat: 37.7749 │ │
│ │ pickup_lng: -122.4194 │ │
│ │ destination: SFO Airport │ │
│ └────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────┐ │
│ │ 1. Find nearby drivers (geohash query) │ │
│ │ Result: 15 drivers within 5km │ │
│ └────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────┐ │
│ │ 2. Filter: available, no current trip │ │
│ │ Result: 10 drivers │ │
│ └────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────┐ │
│ │ 3. Rank by score: │ │
│ │ score = w1*distance + w2*eta + w3*rating │ │
│ │ + w4*acceptance_rate │ │
│ └────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────┐ │
│ │ 4. Send request to top 3 drivers │ │
│ │ (first-come, first-served with timeout) │ │
│ └────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────┐ │
│ │ 5. Driver accepts → Trip confirmed │ │
│ │ All reject/timeout → Expand search │ │
│ └────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────┘
Matching Score Calculation
def calculate_match_score(driver: dict, pickup: tuple, destination: tuple) -> float:
"""Calculate driver match score (lower is better)."""
# Distance to pickup (km)
distance = haversine(
pickup[0], pickup[1],
driver['lat'], driver['lng']
)
# ETA to pickup (minutes) - based on road network
eta = get_eta(driver['lat'], driver['lng'], pickup[0], pickup[1])
# Driver rating (0-5)
rating = driver['rating']
# Acceptance rate (0-1)
acceptance_rate = driver['acceptance_rate']
# Weighted score (lower is better)
score = (
0.3 * distance + # Closer is better
0.4 * eta + # Faster arrival is better
0.2 * (5 - rating) + # Higher rating is better
0.1 * (1 - acceptance_rate) # Higher acceptance is better
)
return score
Request-Response Flow
┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐
│ Rider │ │ Matching │ │ Driver │ │ Location │
│ App │ │ Service │ │ App │ │ Service │
└────┬─────┘ └────┬─────┘ └────┬─────┘ └────┬─────┘
│ │ │ │
│ 1. Request │ │ │
│ ride │ │ │
│───────────────>│ │ │
│ │ │ │
│ │ 2. Query nearby│ │
│ │ drivers │ │
│ │───────────────>│ │
│ │ │ │
│ │ 3. Return │ │
│ │ nearby drivers │ │
│ │<───────────────│ │
│ │ │ │
│ │ 4. Rank & │ │
│ │ select │ │
│ │ │ │
│ │ 5. Send match │ │
│ │ request │ │
│ │─────────────────────────────── >│
│ │ │ │
│ │ │ 6. Accept │
│ │<─────────────────────────────── │
│ │ │ │
│ 7. Trip │ │ │
│ confirmed │ │ │
│<───────────────│ │ │
│ │ │ │
Driver Location Updates
WebSocket connection for real-time location streaming:
class DriverLocationWebSocket:
def on_connect(self, driver_id: str):
"""Driver app connects and starts streaming location."""
self.driver_id = driver_id
self.start_location_streaming()
def on_location_update(self, lat: float, lng: float, speed: float):
"""Receive location update every 3-4 seconds."""
# Update in Redis for real-time queries
self.location_service.update_driver_location(
self.driver_id, lat, lng
)
# Broadcast to rider if trip is active
trip = self.get_active_trip()
if trip:
self.send_to_rider(trip.rider_id, {
"type": "location_update",
"driver_lat": lat,
"driver_lng": lng,
"eta_minutes": self.calculate_eta(lat, lng, trip.pickup)
})
def on_trip_complete(self, trip_id: str):
"""Trip completed, update driver status."""
self.location_service.update_driver_status(
self.driver_id, "available"
)
Route & Pricing
Road Network Graph
class RoadNetwork:
def __init__(self):
# Graph: nodes = intersections, edges = road segments
self.graph = defaultdict(list)
def add_edge(self, from_node: int, to_node: int,
distance: float, speed_limit: float):
self.graph[from_node].append({
"to": to_node,
"distance": distance,
"speed_limit": speed_limit,
"current_speed": speed_limit # Updated with traffic
})
def update_traffic(self, from_node: int, to_node: int,
current_speed: float):
"""Update edge with real-time traffic data."""
for edge in self.graph[from_node]:
if edge["to"] == to_node:
edge["current_speed"] = current_speed
Dijkstra's Algorithm for ETA
import heapq
def find_shortest_path(graph: dict, start: int, end: int) -> tuple:
"""Find shortest path using Dijkstra's algorithm."""
distances = {node: float('inf') for node in graph}
distances[start] = 0
previous = {node: None for node in graph}
pq = [(0, start)] # (distance, node)
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_node == end:
break
if current_dist > distances[current_node]:
continue
for edge in graph[current_node]:
neighbor = edge["to"]
# Weight = distance / current_speed (time)
weight = edge["distance"] / edge["current_speed"]
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current_node
heapq.heappush(pq, (distance, neighbor))
# Reconstruct path
path = []
current = end
while current is not None:
path.append(current)
current = previous[current]
return path[::-1], distances[end]
A* Algorithm (Optimized)
def a_star_search(graph: dict, start: int, end: int,
coords: dict) -> tuple:
"""A* algorithm with heuristic for faster routing."""
def heuristic(node: int) -> float:
"""Euclidean distance to goal (admissible heuristic)."""
return haversine(
coords[node][0], coords[node][1],
coords[end][0], coords[end][1]
)
g_score = {node: float('inf') for node in graph}
g_score[start] = 0
f_score = {node: float('inf') for node in graph}
f_score[start] = heuristic(start)
pq = [(f_score[start], start)]
previous = {node: None for node in graph}
while pq:
_, current = heapq.heappop(pq)
if current == end:
break
for edge in graph[current]:
neighbor = edge["to"]
tentative_g = g_score[current] + edge["distance"] / edge["current_speed"]
if tentative_g < g_score[neighbor]:
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + heuristic(neighbor)
previous[neighbor] = current
heapq.heappush(pq, (f_score[neighbor], neighbor))
# Reconstruct path
path = []
current = end
while current is not None:
path.append(current)
current = previous[current]
return path[::-1], g_score[end]
Dynamic Pricing (Surge)
┌─────────────────────────────────────────────────────────────┐
│ SURGE PRICING MODEL │
├─────────────────────────────────────────────────────────────┤
│ │
│ Surge Multiplier = f(supply, demand, time, location) │
│ │
│ Supply: Available drivers in area │
│ Demand: Pending ride requests in area │
│ │
│ ┌───────────────────────────────────────────────────────┐ │
│ │ Supply/Demand Ratio │ Surge Multiplier │ │
│ ├───────────────────────┼───────────────────────────────┤ │
│ │ > 0.8 │ 1.0x (no surge) │ │
│ │ 0.6 - 0.8 │ 1.2x │ │
│ │ 0.4 - 0.6 │ 1.5x │ │
│ │ 0.2 - 0.4 │ 2.0x │ │
│ │ < 0.2 │ 3.0x │ │
│ └───────────────────────┴───────────────────────────────┘ │
│ │
│ Additional factors: │
│ - Weather (rain: +20-50%) │
│ - Events (concerts, games: +30-100%) │
│ - Time of day (rush hour: +10-30%) │
│ - Holidays (+10-50%) │
│ │
└─────────────────────────────────────────────────────────────┘
Fare Calculation
def calculate_fare(trip: dict, surge_multiplier: float = 1.0) -> dict:
"""Calculate trip fare with all components."""
# Base fare
base_fare = 2.50
# Distance fare (per km)
distance_km = trip['distance_km']
distance_fare = distance_km * 1.50
# Time fare (per minute)
duration_min = trip['duration_min']
time_fare = duration_min * 0.25
# Apply surge
subtotal = (base_fare + distance_fare + time_fare) * surge_multiplier
# Platform fee (25%)
platform_fee = subtotal * 0.25
# Driver earnings
driver_earnings = subtotal - platform_fee
# Total fare
total_fare = subtotal + platform_fee
return {
"base_fare": base_fare,
"distance_fare": distance_fare,
"time_fare": time_fare,
"surge_multiplier": surge_multiplier,
"platform_fee": platform_fee,
"driver_earnings": driver_earnings,
"total_fare": round(total_fare, 2)
}
Real-Time Traffic Integration
class TrafficService:
def __init__(self):
self.traffic_db = redis.Redis()
def update_traffic(self, road_segment: str, speed: float):
"""Update traffic speed from driver GPS data."""
self.traffic_db.hset(f"traffic:{road_segment}", mapping={
"current_speed": speed,
"updated_at": time.time()
})
def get_eta(self, from_lat, from_lng, to_lat, to_lng) -> int:
"""Calculate ETA considering real-time traffic."""
# Get route from routing service
route = self.routing_service.find_route(
from_lat, from_lng, to_lat, to_lng
)
total_time = 0
for segment in route['segments']:
# Get current traffic speed
current_speed = self.traffic_db.hget(
f"traffic:{segment['road_id']}",
"current_speed"
)
if current_speed:
speed = float(current_speed)
else:
speed = segment['speed_limit']
total_time += segment['distance'] / speed * 60 # Convert to minutes
return int(total_time)
Trip Management
Trip State Machine
┌─────────────────────────────────────────────────────────────┐
│ TRIP STATE MACHINE │
├─────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ REQUESTED│───>│ MATCHED │───>│ACCEPTED │ │
│ └──────────┘ └──────────┘ └──────────┘ │
│ │ │ │ │
│ │ │ ▼ │
│ │ │ ┌──────────┐ │
│ │ │ │ ARRIVING │ │
│ │ │ └──────────┘ │
│ │ │ │ │
│ │ │ ▼ │
│ │ │ ┌──────────┐ │
│ │ │ │IN_PROGRESS│ │
│ │ │ └──────────┘ │
│ │ │ │ │
│ │ │ ▼ │
│ │ │ ┌──────────┐ │
│ │ │ │COMPLETED │ │
│ │ │ └──────────┘ │
│ │ │ │ │
│ │ │ ▼ │
│ │ │ ┌──────────┐ │
│ │ │ │ RATED │ │
│ │ │ └──────────┘ │
│ │ │ │
│ │ ▼ │
│ │ ┌──────────┐ │
│ │ │CANCELLED │ │
│ │ └──────────┘ │
│ │ │ │
│ │ ▼ │
│ │ ┌──────────┐ │
│ └────────>│ FAILED │ │
│ └──────────┘ │
│ │
└─────────────────────────────────────────────────────────────┘
Trip Data Model
CREATE TABLE trips (
trip_id UUID PRIMARY KEY,
rider_id UUID NOT NULL,
driver_id UUID,
status VARCHAR(20) NOT NULL,
pickup_lat DECIMAL(10, 8) NOT NULL,
pickup_lng DECIMAL(11, 8) NOT NULL,
dest_lat DECIMAL(10, 8) NOT NULL,
dest_lng DECIMAL(11, 8) NOT NULL,
pickup_address TEXT,
dest_address TEXT,
distance_km DECIMAL(6, 2),
duration_min INTEGER,
fare_estimate DECIMAL(8, 2),
fare_actual DECIMAL(8, 2),
surge_multiplier DECIMAL(4, 2) DEFAULT 1.0,
payment_method VARCHAR(20),
payment_status VARCHAR(20),
created_at TIMESTAMP DEFAULT NOW(),
matched_at TIMESTAMP,
started_at TIMESTAMP,
completed_at TIMESTAMP,
cancelled_at TIMESTAMP
);
CREATE TABLE trip_updates (
update_id UUID PRIMARY KEY,
trip_id UUID REFERENCES trips(trip_id),
status VARCHAR(20) NOT NULL,
lat DECIMAL(10, 8),
lng DECIMAL(11, 8),
event_data JSONB,
created_at TIMESTAMP DEFAULT NOW()
);
CREATE TABLE ratings (
rating_id UUID PRIMARY KEY,
trip_id UUID REFERENCES trips(trip_id),
rater_id UUID NOT NULL,
ratee_id UUID NOT NULL,
score INTEGER CHECK (score BETWEEN 1 AND 5),
comment TEXT,
created_at TIMESTAMP DEFAULT NOW()
);
Trip Service Implementation
class TripService:
def __init__(self):
self.db = PostgresDB()
self.matching_service = MatchingService()
self.payment_service = PaymentService()
self.notification_service = NotificationService()
async def request_trip(self, rider_id: str, pickup: dict, destination: dict) -> dict:
"""Create new trip request and find driver."""
# Create trip record
trip = await self.db.execute("""
INSERT INTO trips (rider_id, status, pickup_lat, pickup_lng,
dest_lat, dest_lng)
VALUES (%s, 'REQUESTED', %s, %s, %s, %s)
RETURNING trip_id
""", [rider_id, pickup['lat'], pickup['lng'],
destination['lat'], destination['lng']])
# Calculate fare estimate
fare = await self.calculate_fare_estimate(pickup, destination)
await self.db.execute("""
UPDATE trips SET fare_estimate = %s WHERE trip_id = %s
""", [fare['total_fare'], trip['trip_id']])
# Find matching driver
match = await self.matching_service.find_driver(
pickup['lat'], pickup['lng'],
destination['lat'], destination['lng']
)
if match:
await self.assign_driver(trip['trip_id'], match['driver_id'])
return {
"trip_id": trip['trip_id'],
"fare_estimate": fare['total_fare'],
"driver": match
}
async def assign_driver(self, trip_id: str, driver_id: str):
"""Assign driver to trip and notify both parties."""
# Update trip status
await self.db.execute("""
UPDATE trips
SET driver_id = %s, status = 'MATCHED', matched_at = NOW()
WHERE trip_id = %s
""", [driver_id, trip_id])
# Send notifications
await self.notification_service.send(trip_id, {
"type": "trip_matched",
"driver_id": driver_id,
"eta_minutes": await self.calculate_eta(driver_id, trip_id)
})
async def update_trip_status(self, trip_id: str, new_status: str,
location: dict = None):
"""Update trip status with location tracking."""
# Validate state transition
valid_transitions = {
"REQUESTED": ["MATCHED", "CANCELLED", "FAILED"],
"MATCHED": ["ACCEPTED", "CANCELLED", "FAILED"],
"ACCEPTED": ["ARRIVING", "CANCELLED", "FAILED"],
"ARRIVING": ["IN_PROGRESS", "CANCELLED", "FAILED"],
"IN_PROGRESS": ["COMPLETED", "FAILED"],
"COMPLETED": ["RATED"],
"CANCELLED": [],
"FAILED": []
}
current = await self.get_trip_status(trip_id)
if new_status not in valid_transitions.get(current, []):
raise ValueError(f"Invalid transition: {current} -> {new_status}")
# Update status
await self.db.execute("""
UPDATE trips SET status = %s WHERE trip_id = %s
""", [new_status, trip_id])
# Log update
await self.db.execute("""
INSERT INTO trip_updates (trip_id, status, lat, lng)
VALUES (%s, %s, %s, %s)
""", [trip_id, new_status,
location['lat'] if location else None,
location['lng'] if location else None])
# Notify rider
await self.notification_service.send_to_rider(trip_id, {
"type": "status_update",
"status": new_status,
"location": location
})
Real-Time Communication Architecture
┌─────────────────────────────────────────────────────────────┐
│ REAL-TIME COMMUNICATION ARCHITECTURE │
├─────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────┐ ┌──────────┐ │
│ │ Driver │◄─────────────────>│ WebSocket│ │
│ │ App │ Location updates │ Server │ │
│ └────┬─────┘ (every 3s) └────┬─────┘ │
│ │ │ │
│ │ │ │
│ │ │ │
│ │ │ │
│ ┌────┴─────┐ ┌────┴─────┐ │
│ │ Rider │◄─────────────────>│ WebSocket│ │
│ │ App │ Trip updates │ Server │ │
│ └──────────┘ └──────────┘ │
│ │
│ WebSocket Connections: │
│ - Driver: Location streaming, trip requests │
│ - Rider: Trip status, driver location tracking │
│ │
│ Message Types: │
│ - driver.location_update │
│ - trip.requested │
│ - trip.matched │
│ - trip.status_update │
│ - trip.driver_arriving │
│ - trip.completed │
│ │
└─────────────────────────────────────────────────────────────┘
Data Model Summary
┌─────────────────────────────────────────────────────────────┐
│ DATA MODEL │
├─────────────────────────────────────────────────────────────┤
│ │
│ Users │
│ ├── user_id (PK) │
│ ├── name, email, phone │
│ ├── role (rider/driver/both) │
│ ├── rating (avg) │
│ └── payment_methods │
│ │
│ Drivers │
│ ├── driver_id (PK) │
│ ├── user_id (FK) │
│ ├── vehicle_type │
│ ├── license_plate │
│ ├── status (available/busy/offline) │
│ └── current_location (lat, lng) │
│ │
│ Trips │
│ ├── trip_id (PK) │
│ ├── rider_id (FK) │
│ ├── driver_id (FK) │
│ ├── status │
│ ├── pickup_location, destination │
│ ├── fare_estimate, fare_actual │
│ └── timestamps (created, matched, started, completed) │
│ │
│ Payments │
│ ├── payment_id (PK) │
│ ├── trip_id (FK) │
│ ├── amount │
│ ├── method │
│ └── status (pending/completed/refunded) │
│ │
│ Ratings │
│ ├── rating_id (PK) │
│ ├── trip_id (FK) │
│ ├── rater_id, ratee_id │
│ ├── score (1-5) │
│ └── comment │
│ │
└─────────────────────────────────────────────────────────────┘
Payment Flow
class PaymentService:
async def process_payment(self, trip_id: str) -> dict:
"""Process payment after trip completion."""
trip = await self.get_trip(trip_id)
# Calculate final fare
fare = self.calculate_fare(
trip['distance_km'],
trip['duration_min'],
trip['surge_multiplier']
)
# Process payment
payment = await self.stripe.charge(
amount=fare['total_fare'],
currency='usd',
customer=trip['rider_payment_method'],
metadata={'trip_id': trip_id}
)
# Update trip with actual fare
await self.db.execute("""
UPDATE trips
SET fare_actual = %s, payment_status = 'completed'
WHERE trip_id = %s
""", [fare['total_fare'], trip_id])
# Pay driver (minus platform fee)
await self.payout_service.payout(
driver_id=trip['driver_id'],
amount=fare['driver_earnings']
)
return {
"payment_id": payment['id'],
"total_fare": fare['total_fare'],
"driver_earnings": fare['driver_earnings']
}
Practice Problems
0/3solved
Design Ride Sharing (Design Uber/Lyft) System
Design a scalable Ride Sharing (Design Uber/Lyft) system. Cover high-level architecture, data model, and API design.
Solution
// Complete system design:
// - Functional + Non-functional requirements
// - Capacity estimation
// - Data model (SQL/NoSQL choice)
// - API endpoints
// - Component architecture
// - Scaling strategy
// - Monitoring & reliabilityRide Sharing (Design Uber/Lyft) Scaling
How would you scale Ride Sharing (Design Uber/Lyft) to handle 10x the current load? Identify bottlenecks and solutions.
Solution
// Scaling approach:
// 1. Load balancing
// 2. Database sharding/replication
// 3. Cache layer (Redis)
// 4. CDN for static assets
// 5. Async processing (queues)
// 6. Microservices decompositionRide Sharing (Design Uber/Lyft) Failure Modes
Analyze potential failure modes for Ride Sharing (Design Uber/Lyft) and design mitigation strategies.
Solution
// Failure mitigation:
// 1. Redundancy (multi-AZ)
// 2. Circuit breakers
// 3. Retry with backoff
// 4. Dead letter queues
// 5. Health checks
// 6. Graceful degradationQuiz
1. Why use geohash for driver location indexing?
2. What is the typical driver location update frequency?
3. How does surge pricing work?
4. What algorithm is used for ETA calculation?
5. What is the trip state after driver accepts the request?
Flashcards
Question
What is geohash and why use it for driver locations?
Click to reveal answer
Answer
Geohash encodes geographic coordinates into a string prefix. Nearby locations share prefixes, enabling efficient range queries. Used to find drivers within a radius by querying adjacent geohash cells.
Question
How does the matching algorithm work?
Click to reveal answer
Answer
1) Find nearby drivers using geohash, 2) Filter by availability, 3) Rank by score (distance, ETA, rating), 4) Send request to top 3 drivers, 5) First to accept gets the trip.
Question
What factors affect surge pricing?
Click to reveal answer
Answer
Supply/demand ratio in area, weather conditions, special events, time of day, holidays. Surge multiplier increases when demand exceeds supply to balance the market.
Question
What are the trip states in a ride-sharing system?
Click to reveal answer
Answer
REQUESTED → MATCHED → ACCEPTED → ARRIVING → IN_PROGRESS → COMPLETED → RATED. Also: CANCELLED (from any state before COMPLETED) and FAILED.
Question
Why use WebSocket for driver location updates?
Click to reveal answer
Answer
WebSocket provides persistent, bidirectional connection for real-time updates. Drivers stream location every 3-4 seconds; riders receive live tracking. More efficient than polling for high-frequency updates.
Revision Notes
Key Takeaways
- 1.Geohash enables efficient proximity queries for driver matching
- 2.Driver location updates every 3-4 seconds via WebSocket
- 3.Matching algorithm: find → filter → rank → request → accept
- 4.Trip state machine ensures consistent lifecycle management
- 5.Dynamic pricing balances supply and demand in real-time
- 6.Real-time communication essential for rider tracking
- 7.Dijkstra/A* algorithms for ETA calculation on road network
Interview Tips
- •Start with requirements: clarify scale (drivers, trips/day), latency needs
- •Explain geospatial indexing with a diagram showing geohash grid
- •Discuss matching algorithm: how to find and rank drivers efficiently
- •Address surge pricing: explain it's dynamic, not fixed, based on supply/demand
- •Walk through trip state machine: show all states and valid transitions
- •Discuss real-time updates: WebSocket for driver location, notifications for rider
- •Address scalability: Redis for location, partitioning by region, CDN for maps
Cheat Sheet
Ride Sharing Cheat Sheet
Architecture Components
- Location Service: Geohash-based driver indexing in Redis
- Matching Service: Find and rank nearby drivers
- Trip Service: State machine, trip lifecycle
- Payment Service: Fare calculation, payment processing
- Notification Service: WebSocket/SSE for real-time updates
Key Design Decisions
- Geohash precision: Level 7 (~150m) for driver locations
- Update frequency: Every 3-4 seconds for driver GPS
- Matching radius: 5km default, expand if no drivers
- Surge pricing: Dynamic based on supply/demand ratio
- Trip state machine: REQUESTED → MATCHED → ACCEPTED → ARRIVING → IN_PROGRESS → COMPLETED → RATED
Location Service
- Redis sorted set by geohash prefix
- Haversine formula for distance calculation
- Neighbor geohash cells for nearby search
Matching Algorithm
- Find drivers within radius (geohash query)
- Filter: available, no current trip
- Rank: score = w1distance + w2eta + w3*rating
- Send to top 3 drivers (first-come)
- Timeout: expand search if no accept
Pricing Model
- Base fare + distance (per km) + time (per min)
- Surge multiplier: f(supply/demand, weather, events)
- Platform fee: 25% of fare
- Driver earnings: fare - platform fee
Data Model
- Users: rider/driver profiles, ratings
- Drivers: vehicle info, current location, status
- Trips: full lifecycle with timestamps
- Payments: transaction records, status
- Ratings: bidirectional after trip
Scalability
- Redis for real-time location (in-memory)
- Partition drivers by geohash region
- CDN for static map data
- Event sourcing for trip updates