System Design: Designing Uber

Introduction

• Second system design problem breakdown, first was Ticket Master.
• Positive reception for initial video.
• Plan to release videos bi-weekly, focusing on system design.
• Current focus: Designing Uber, a complex proximity search problem.
• Relevant for interviews at top tech companies like Google and Meta.

About the Presenter

• Former staff engineer and interviewer at Meta.
• Co-founder of Hello Interview, a site for interview preparation.
• Extensive experience asking and evaluating system design questions.

Roadmap for Designing Uber

1. Requirements
   • Functional requirements: Core features of the system.
   • Non-functional requirements: Qualities of the system.
2. Core Entities and API
   • Determine key entities and design APIs.
3. High-Level Design
   • Satisfy core functional requirements.
4. Deep Dives
   • Ensure system satisfies all non-functional requirements.

Functional Requirements

• Users should be able to:
  • Input a start location and destination to get an estimated fare.
  • Request a ride based on the estimate and be matched with a nearby driver in real-time.
  • Drivers should be able to accept/deny requests and navigate to pick up and drop off locations.
• Out of scope: Multiple car types, ratings, scheduling rides in advance.

Non-Functional Requirements

• Key Characteristics
  • Low latency matching (<1 min).
  • Consistency: One-to-one ride and driver matching.
  • High availability outside matching.
  • Handle high throughput during peak events.
• Out of Scope: GDPR, privacy, resilience, monitoring, deployment pipelines.

Core Entities

• Ride
• Driver
• Rider
• Location: Maintains the latest location of drivers.

API Design

• Get fare estimate: Post request with source/destination returning partial ride details.
• Request ride: Patch request with ride ID to initiate matching.
• Update location: Drivers update their location every few seconds.
• Driver accepts request: Patch request for drivers to accept/deny.
• Navigation update: Drivers update status during a ride.

High-Level Design

• Frontend: Separate clients for drivers and riders.
• Backend Services: Managed via AWS API Gateway with routing, load balancing, and scalability.
• Core Services:
  • Ride Service: Manages fare estimates via third-party mapping.
  • Ride Matching Service: Matches drivers to riders using real-time location data.
  • Location Service: Updates and retrieves driver locations.
  • Notification Service: Sends push notifications to drivers.
• Database: Stores ride details and driver statuses.
  • Primary DB for persistent data.
  • Location DB for real-time driver locations.

Deep Dives

Low Latency Matching

• Location Service:
  • High TPS requirement (~600k TPS) for driver updates.
  • Use Redis for in-memory data storage with geohashing for spatial data efficiency.
  • Optimize for high-frequency updates without reindexing.

Consistency of Matching

• Ensure ride requests are not sent to more than one driver simultaneously.
• Use a distributed lock (e.g., Redis) to manage driver status.
• Avoid Cron job delays by using TTLs on locks for dynamic availability.

High Throughput Handling

• Introduce a queue for ride requests to manage surges.
• Partition queues by region to optimize matching speed.

High Availability

• Horizontally scale services and partition by geographic region.
• Consider DynamoDB with TTLs for consistency across distributed instances.

Conclusion

• Summary of key points for various candidate levels (mid-level, senior, staff).
• Encouragement to practice these concepts for system design interviews.
• Engagement: Comments and feedback welcome for further improvement.