Designing a Ride-Sharing Service
High Level Design·advanced·~25 min read
- system-design
- ride-sharing
- uber
- quadtree
- distributed-systems
- hld
What you'll learn
Problem Statement
Design a ride-sharing service that connects riders with nearby drivers in real-time. A rider requests a ride by specifying pickup and destination locations. The system finds suitable drivers nearby, dispatches the request, and manages th…
Requirements
Functional Requirements
1. Riders can request a ride by providing pickup and destination locations 2. System matches riders with nearby available drivers in real-time 3. Drivers can accept/decline ride requests 4. Both rider and driver see each other's real-tim…
Non-Functional Requirements
1. Low latency matching — rider should be matched within seconds 2. High availability — service must be operational 24/7 3. Real-time updates — location tracking with minimal lag 4. Scalability — handle millions of concurrent users acros…
Extended Requirements
1. Surge pricing during high-demand periods 2. Trip history and receipts 3. Driver ratings and feedback 4. Multiple ride types (economy, premium, shared) ---
Capacity Estimation
Scale
| Metric | Value | |--------|-------| | Total customers | 300 Million | | Total drivers | 1 Million | | Daily active customers | 1 Million | | Daily active drivers | 500K | | Daily rides | 1 Million | | Driver location update interval |…
Location Update Traffic
| Metric | Calculation | Value | |--------|-------------|-------| | Updates per driver per day | 8 hrs × 3600 / 3 sec | ~9,600 | | Total updates per day | 500K drivers × 9,600 | ~4.8 Billion | | Updates per second | 500K / 3 | ~166,000/s |
Storage for Active Driver Locations
| Metric | Calculation | Value | |--------|-------------|-------| | Per-driver entry | DriverID (3B) + OldLat (8B) + OldLong (8B) + NewLat (8B) + NewLong (8B) | 35 bytes | | Total for all drivers | 1M × 35 bytes | 35 MB | This is trivial…
Bandwidth Estimation
| Metric | Calculation | Value | |--------|-------------|-------| | Ingestion (driver → server) | 19 bytes × 500K drivers / 3 sec | ~3.2 MB/s (19 MB per 3-sec window) | | Broadcast (server → subscribers) | 2.5M subscribers × 19 bytes/sec…
Spike Handling
| Load Level | Requests per second | |------------|-------------------| | Baseline (steady state) | ~25K rps | | 2× spike (concert ending, etc.) | ~50K rps | | 4× spike (major event) | ~100K rps | | 10× spike (New Year's Eve) | ~250K rps…
Pub/Sub Memory for "Drivers Around Me"
When customers open the app (before requesting a ride), they see nearby drivers on the map. This uses a subscriber model: | Metric | Calculation | Value | |--------|-------------|-------| | Subscriber list (customer → subscribed drivers)…
Pull vs Push for "Drivers Around Me"
| Approach | How it works | Verdict | |----------|-------------|---------| | Push | Server maintains subscriber lists, broadcasts every driver move to subscribed customers | Complex — must manage subscriptions, handle churn as customers…
Design Evolution & Trade-offs
How this system grew from an MVP to what a production version looks like — and the choices you'd defend in an interview.
Stage 1 — MVP: One box, one database
The simplest thing that could possibly work for a ride-sharing service. - A single API server (monolith) that owns rider requests, driver registration, matching, and trip lifecycle. - A single relational database (Postgres) storing rider…
Stage 2 — Scale-out: Multiple pods behind a load balancer
- API layer becomes stateless; N replicas behind an L7 load balancer. - Rider sessions moved out of process memory into Redis (rider JWT + last-known ride state). - Driver WebSocket connections are sticky per pod (via consistent-hash rou…
Stage 3 — Bottleneck: Geospatial matching at 166K updates/sec
This is the single most characteristic problem of a ride-sharing service. You have a fleet of hundreds of thousands of moving points, each emitting a new coordinate every 3 seconds, and you must answer "give me the 10 nearest available d…
Stage 4 — Second bottleneck: Race conditions on driver acceptance
Matching returns "top 3 nearest drivers," and the design fires ride offers to all three in parallel. The moment two riders' matching workflows both select driver D1234 in the same 200 ms window — or two drivers simultaneously tap "Accept…
Stage 5 — Third bottleneck: Real-time location fan-out during active trips
Once a ride is matched, both rider and driver want each other's live position. The driver's location updates every 3 seconds. If the rider polls every 3 seconds too, that's fine for one trip — but with 1M concurrent trips, you're doing 3…
Stage 6 — Mature architecture
A diagram showing the full system with all the additions from stages 2-5. ---
Cost vs Complexity — When to Pick What
A summary table cross-cutting every decision by scale tier. | Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Compute | Single VM running monolith | Kubernetes depl…
Migration Path (MVP → Enterprise)
Stepped list — how you'd migrate a live ride-sharing service without downtime, and which steps unlock which. 1. Move driver locations out of Postgres into Redis GEO. Dual-write from the Location Service to both stores for 24-48 hours, ve…
Core Data Structures
DriverLocationHT (Hash Table)
The central in-memory data structure storing all active driver locations: Why store both old and new positions? - Track movement direction and speed - Predict where driver will be by the time rider is picked up - Detect stationary vs. mo…
QuadTree for Spatial Indexing
The QuadTree enables "find drivers near point X" queries: Key difference from static proximity service: Drivers move constantly, so the QuadTree must handle dynamic updates. Why QuadTree is NOT suitable for frequent updates (pivotal insi…
Alternative: Redis Geospatial Commands (Simpler for Interviews)
Redis provides native geospatial indexing using geohashing internally: Why this works for ride-sharing: - Each GEOADD overwrites the previous position — always current, no stale data - 2M writes/sec (10M drivers × every 5s) is within Red…
H3 Hexagonal Grid (Modern Alternative)
A modern approach to spatial partitioning that avoids QuadTree pitfalls: How it works: - The Earth's surface is tiled with equal-area hexagons at multiple resolution levels - A Locator Service maps each hexagon to a physical shard - Give…
Durable Execution for Matching Workflow
The matching process (find drivers → notify → wait for response → retry next driver) involves multiple steps with timeouts. A durable execution framework provides: Why durable execution? If the matching service crashes mid-workflow, the…
Database Schema (Core Entities)
Object Storage Usage
| Content | Why Object Storage | |---------|-------------------| | Driver identification documents (PAN, national ID scans) | Large binary files, infrequent access after verification | | Trip invoices (PDF with route map + payment detail…
High-Level Architecture
Gateway & Protocol Design
The system uses distinct gateway types for riders and drivers based on their communication patterns: Protocol rationale: - Riders use REST + polling — simpler client, interactions are request-response in nature (request ride, check statu…
System Component Diagram
Architecture Components
| Component | Role | |-----------|------| | Ride Service | Handles ride requests, matching, lifecycle | | Location Service | Receives driver location updates, maintains DriverLocationHT | | QuadTree Service | Spatial index for finding ne…
Core Flows
Ride Request Flow
Detailed steps: 1. Rider requests ride with pickup (lat/long) and destination (lat/long) 2. System locates rider's QuadTree cell 3. Search that cell + adjacent cells for available drivers 4. If not enough drivers found → expand search ra…
Driver Location Update Flow
1. Driver's phone sends (driverID, lat, long) every 3 seconds 2. Location Service updates DriverLocationHT with new position 3. If ride is in progress: notify subscribed rider about driver's new position 4. Periodically sync to QuadTree…
Pub/Sub for Location Broadcasting
When a ride is in progress, the rider needs real-time driver location: Design decisions: - Topic per active ride (not per driver) — limits scope and fan-out - Rider subscribes when match is confirmed, unsubscribes when trip ends - Every…
Fault Tolerance
| Failure | Recovery Strategy | |---------|-------------------| | DriverLocationHT server dies | Replicate to multiple servers (only 35 MB — trivial) | | QuadTree server dies | Primary-secondary replication; rebuild from DriverLocationHT…
ETA Calculation
ETA is not just straight-line distance: - Use Dijkstra/A on road graph with traffic-weighted edges - Precompute cell-to-cell travel times for fast rough estimates - Refine with ML models trained on millions of historical trips ---
Key Design Decisions Summary
| Decision | Rationale | |----------|-----------| | Separate DriverLocationHT from QuadTree | HT is always fresh (O(1) updates); QuadTree is slightly stale but enables spatial queries (O(log N)) | | Notify top 3 drivers simultaneously |…
Trip State Machine
---