Requirements

Functional Requirements:

1. Rider can send request with origin and destination
2. Driver can upload position to the system
3. Driver can accept the request
4. System needs to match driver based on the position of rider

Non-Functional Requirements:

1. Availability, 99.99% up time
2. Scalability, can support 1m concurrent online users
3. Low latency, rider can find near drivers within 1min
4. Reliability, rider can find best matched driver, e.g. least arrival time

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

API Design

Client can use REST API to send request:

POST v1/findDriver body: {origin: (latitude, longitude), destination: (latitude, longitude), timestamp: time}

Driver can use REST API to accept request:

POST v1/acceptOrder body: {order_id: id, rider: user_id, origin, destination, timestamp}

Driver can use WebSocket to upload position, because it needs to upload position every 5 seconds, using WebSocket has less overhead.

Request body: {driver: user_id, position: (latitude, longitude), timestamp}

High-Level Design

Rider send request with origin and destination to the system, system store the ride information and status in a SQL database, because we need ACID. The ride table schema looks like:

{

ride_id: int

rider: user_id

driver: driver_id

origin: (latitude, longitude)

destination: (latitude, longitude)

status: {pending, assigned, transportation, done, cancelled}

timestamp: time

}

Transport service send a RPC call to match service to find drivers based on arrival ETA. Match service retrieve all available drivers around the origin and sort by ETA from short to long. Match service send a ride request to the first driver, if the driver rejected the request, the service send the request to the second driver, etc. until on driver accepted the order. Once the driver accepted the order, the match service updates the ride table, e.g. fill the driver column, change the status. Duplicate acceptance will be rejected because of the ride table has already a driver assigned.

Driver use WebSocket to connect with location service and upload its position every 5 seconds, the payload is:

{latitude, longitude, timestamp}

The location service update the record in the in-memory database:

dirver_id -> {latitude, longitude, timestamp}

Once a driver accepted the order, the location service push the driver's location to rider via WebSocket connection.

If the driver is offline then the record will be removed from the in-memory database. So match service can use the record to retrieve online drivers.

The in-memory database is replicated into 3 pieces, which increase availability.

API gateway is to do authentication, load balance.

We can put a queue between transport service and match service, so that we can support high volume traffic. When the request from transport service is large, we can increase the instance number of match service.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Detailed Component Design

1. To increase availability, each single service instance can increase independently when traffic is large. Also the in-memory database and the SQL database are replicated.
2. To lower latency, match service cannot retrieve all available drivers and sort them by ETA, that would need a long time. Instead it only retrieve around drivers say within 5 miles. In order to retrieve them very fast, we can index the driver location based on the position cell, that means a city is divided into m*n metrics and each cell is responsible for an area say 5 miles range. So that match service only needs to get the all drivers that are located in the same cell with the origin. That may be inaccurate for the case where origin is location on the edge of a cell, in this scenario, we can also include surrounding cells as well to increase accuracy.