Design a Real-Time Ride-Sharing Dispatch Service (Uber/Lyft)

1. Problem Statement & Scope

System Mission

Design a real-time, highly available, low-latency ride-matching and dispatch platform (similar to Uber or Lyft) capable of tracking millions of active drivers sending continuous GPS coordinates, matching rider requests with the nearest available drivers in under 2 seconds, calculating dynamic surge pricing, and handling atomic ride acceptances under high concurrency.

Functional Requirements

1. Real-Time Driver Location Ingestion: Ingest live GPS coordinates (lat, lng, bearing, status) from 1 Million active drivers every 4 seconds.
2. Ride Request & Driver Discovery: Riders request a ride specifying pickup and dropoff coordinates; system discovers top $N$ nearby available drivers within a $5\text{ km}$ radius in $< 500\text{ ms}$.
3. Atomic Ride Dispatch & Match Acceptance: Dispatch ride offers sequentially or in batched rings to drivers; ensure exactly one driver accepts the ride without race conditions.
4. Dynamic Surge Pricing: Calculate real-time supply vs. demand multiplier per spatial grid cell (e.g. $1.5\times$ surge).
5. Trip State Machine: Track trip lifecycle states (REQUESTED, MATCHED, ARRIVING, IN_TRIP, COMPLETED, CANCELLED).

Non-Functional Requirements (SLAs/SLOs)

• High Availability: $99.999\%$ uptime SLA for location ingestion and dispatch pipelines.
• Ultra-Low Latency: P99 Location Ingestion Latency $< 50\text{ ms}$; P99 Driver Matching Latency $< 1\text{ s}$.
• Consistency: Strong consistency on driver acceptance (atomic lock) to prevent double-booking.
• Scalability: Support $1\text{M}$ active drivers and $10\text{M}$ daily completed trips.

2. Capacity & Scale Estimation

Traffic Calculations

• Active Driver Count: 1 Million active drivers ($10^6$).
• GPS Ingestion Rate: Each driver emits a location ping every 4 seconds ($0.25\text{ updates/sec/driver}$).
• Global Ingestion QPS: $\text{Location Write QPS} = \frac{1,000,000}{4} = \mathbf{250,000\text{ QPS}}$
  • Peak Ingestion QPS ($2\times$ rush hour): $\mathbf{500,000\text{ QPS}}$.
• Rider Demand & Search QPS:
  • $10\text{ Million}$ ride requests per day.
  • Active rider search QPS: $\approx 2,000\text{ search QPS}$ (Peak $5,000\text{ QPS}$).

Storage & Bandwidth Estimation

• Location Payload Size:
  • driver_id (16 Bytes), lat (8 Bytes), lng (8 Bytes), bearing (4 Bytes), timestamp (8 Bytes), status (4 Bytes) $\approx \mathbf{48\text{ Bytes}}$ (with JSON/Protobuf envelope $\approx 100\text{ Bytes}$).
• Ingestion Network Bandwidth: $250,000\text{ writes/sec} \times 100\text{ Bytes} = 25\text{ MB/s} = \mathbf{200\text{ Mbps}}$
• Active Driver Ephemeral Location Cache (Redis Geospatial / In-Memory MemoryDB): $1,000,000\text{ drivers} \times 200\text{ Bytes} \approx \mathbf{200\text{ MB RAM}}$ (Easily stored in memory with sub-millisecond query latency).
• Historical Location Audit Log (30-Day Retention in S3): $25\text{ MB/s} \times 86,400\text{ s/day} \times 30\text{ days} \approx \mathbf{64.8\text{ TB/month}}$

3. AWS-First High-Level Architecture

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...