Ride Sharing System

June 26, 2022 6:00 PM PDT

---

This document summarizes a mock system design interview focused on a ride-sharing system. The discussion covered functional and scaling requirements, system design, database models, and various technical considerations. The interview aimed to evaluate the candidate's understanding of system architecture and their ability to design scalable and efficient solutions.

Requirements

Functional Requirements

• Customer (Driver) Capabilities:
  • Request a ride.
  • View all nearby drivers.
  • Send location to the server.
  • After accepting a ride, both driver and rider can see each other.

Scaling Requirements

• User Base:
  • 300 million customers and 1 million drivers.
• Daily Active Users (DAU):
  • 1 million active riders: approximately 2,000 transactions per second (TPS).
  • 500,000 active drivers: approximately 1,000 TPS (notifications every 3 seconds).

System Design

External APIs

• API Types:

  • RESTful API for external communication.
  • gRPC for internal communication.

• Endpoints:

  • POST /domain/RideRequest
    • Payload: { customerId, Latitude, longitude }
  • GET /domain/nearByCars?longitude={}&latitude={}
  • POST /domain/driverLocation
    • Payload: { driverId, Latitude, Longitude }
  • GET /domain/getMyDriverLocation/{customerId}
    • Response: { Latitude, Longitude }

Database Models

• Data Structures:
  • QuadTree Index: Used for finding the nearest driver by dividing the map into grid cells.
    • Structure: TraTree: gridId, startLat, endLat, startLong, endLong
  • Location Table (In-memory):
    • Structure: driverId, curLongitude, curLatitude, preLongitude, preLatitude
    • driverInGrid(gridId, driverId)
  • Ride Table:
    • Structure: Ride, customerId, driverId

System Flow

1. Client sends a ride request to the Load Balancer (LB).
2. LB forwards the request to the ride request API.
3. The API queries driverInGrid to find available drivers in the grid.
4. Notifications are sent to matched drivers based on:
   • Rating
   • Preferences (e.g., car type)

Driver Lookup

• Grid Lookup:
  • Use binary search to identify the appropriate grid based on longitude and latitude.
  • If a grid has more than 500 drivers, it can be subdivided; if too few, grids can be merged.

Message Queue

• The system can choose between push or pull mechanisms for delivering requests, with a preference for push to enhance efficiency.
• If no driver responds within a specified timeout (10 seconds to 1 minute), the system can notify multiple drivers sequentially to avoid concurrency issues.

Audience Feedback

• Functional requirements were deemed good, but scaling requirements needed improvement regarding reliability and latency.
• Suggestions included using websockets for notifications and discussing trade-offs in more depth.
• The interviewee was encouraged to manage time better and focus on high-level design before drilling down into specifics.

Interviewee Self-Reflection

• Acknowledged the need for better time management during the interview.
• Identified two main challenges: finding nearby drivers and implementing the QuadTree structure.
• Recognized the importance of discussing trade-offs, sharding, and message queues.

Conclusion

The interview provided valuable insights into the design of a ride-sharing system, highlighting key functional and scaling requirements, as well as the importance of efficient data structures and communication protocols. Further exploration of trade-offs and system reliability is recommended for a more robust design.