Loading...
MVP features:
The system should be able to track the location of rider and driver
Rider can request a rider that takes them from current location to the destination
Driver can get notified when there is a nearby rider request. Driver can accept/decline the request
For each trip, the system should be able to calculate the cost, persist the trip info so riders/drivers can pull trip history
Non MVP feature:
Users can filter the ride by car models, or other criteria
Scalability: should be easy to scale up
Reliability: system should behave reliable, the dispatch workflow should work as expected
Available: Users/drivers should always have access to our service anytime/anywhere.
Security: the PII data should be safeguarded when stored in our system. The system should have authN/authZ to grant access to valid users
1000 Million DAU for riders (1 billion)
100 Million concurrent riders
100 Million DAU for drivers
10 Million active drivers
Riders send their location every 20 sec (usually on foot, move slow)
1/20 * 100 000 000 => 5 Million QPS
Peak QPS = QPS * 5 => 25 million QPS
Drivers send their location every 10 sec (move fast)
1/10 * 10 000 000 => 1 million QPS
Peak QPS = QPS * 5 => 5 million QPS
Location update: 30 million QPS
Assume each trip will generate ~1kb data, and each rider will book take one trip
1000 000 000 * 1 kb = 1 TB /day new data per day
Request_trip(user_id, src_longitude, src_latitude, dst_longitude, dst_latitude):
Response: trip_id
We will use WebSocket to push notifications to rider for trip status changes (pending-> accepted->picking up->enroute->finished, cancelled).
But users can also manually check the trip status at anytime (for ex. look up past trips)
Get_trip_status(trip_id, user_id)
Response: trip_details
Cancel_trip_request(user_id, trip_request_id): 200 OK, 400/500 error
Accept_trip_order(driver_id, trip_request_id): 200 OK, 400/500 error
Decline_trip_order(driver_id, trip_request_id): 200 OK, 400/500 error
Users
User_id
creation_timestamp
last_active_timestamp
name,
phone,
Drivers
driver_id
User_id
creation_timestamp
last_active_timestamp
name,
phone,
car_id,
status, available, not available
Cars
driver_id
car_id
model
year
make
license_plate
color
Driver_location table (high read and high write, not need long-term durable storage)
location (geo_hash, or longitude&latitude ) *partition_key
driver_ids: (stored in a collection data type like set)
last_seen_timestamp
Discussion:
geohash vs (longitude&latitude)
join between longitude & latitude
select * from table where longitude = x and latitude = y;
discussion for driver_location table:
1) We maintain two tables, one for location -> driver_id, the other one for driver_id -> location
when a ride_request comes in, we will search the available drivers in first table
when drivers moves between different location grids, we use table 2 to update data in table 1
drawback:
we may keep updating same row for a hot location
update two tables, consistence issue, double the traffic
Not a good design
2) the second option is to have a single table but use global secondary index feature like DynamoDB
So the primary key is driver_id, global secondary_index is geohash
But since we frequently update the table, which means the secondary_index will be frequently updated too, which might not be scalable
3) Another option is to maintain a single table for driver location. We set TTL for each location data. We allow driver to be present in different blocks for a short time, and we apply dedupe logic at the application level. We will keep the driver location data with the newer timestamp
Drawback:
Extra dedupe logic
4) Since those traffic pattern to this table will be read and write frequently, and there is no need to put them in the long-term durable storage, we can put those data in cache.
Can we put them in cache?
Based on a Redis' blog, Redis supports 200 Million QPS with 40 instances.
QPS side -> ok
Lets say our geohash uses 6 digits (1km * 1km)
32^6 keys in total (2^30, ~ 1 billion keys), a single instance can support up to 2^32 keys
but we can reduce the number of keys per instance by sharding based on regions (us-west vs us-east or like by states/cities)
So we should be able to fit the driver_location table in cache.
We can use similar table design for user_location table
Trip table
trip_id
driver_id
rider_id
started_timestamp
last_updated_timestamp
start_location
dest_location
status
Driver workflow.
When waiting for orders, the driver sends their location to our server every 10 sec via websocket connection.
We will store the data in driver location table with a TTL. The driver location table is implemented with cache, partitioned by geohash. In this way we can quickly retrieve all drivers with a given location.
We can maintain several location tables with different location precision (for ex. geohash with 6 digits, 5 digits, etc.)
When dispatch service sends an order to the driver, driver can choose to accept or decline the order.
If driver accepts the order, the dispatch service will update trip table with driver id, sends a notification to user for the updates. The notification should contain the information about the driver and vehicle.
Bonus, non MVP feature:
If we want to show driver real-time time location to the user. We can create a Pub/sub channel in cache. Once the driver accept the order, it will start to send location messages with an extra flag like tracking: enabled. In that way, the location service can start to push driver location information to the Pub/Sub cache, and stop to push location information to the driver location cache.
The rider side will subscribe to this Pub/sub channel. If using Redis, it can deliver all messages in the channel to the subscribers.
Once the driver picks up the rider, driver can manually click the button like "start trip", so we can change the status in trip table from picking up to enroute, and also update the trip table with locations.
Similarly, when driver arrive at the the destination, the driver needs to manually click the button like "end trip", so we can end the trip
Rider workflow
Rider maintain a WebSocket connection with our servers. When the user request for a trip, the request will firstly go to our dispatch service which will trigger several calls.
First, it will look up the driver_location datastore, and get the list of available drivers nearby. If the number of driver is not enough, it can expand the search range to nearby grids (with user at the center). After gathering the results, the service can apply some filters (for ex. if the user asks for a SUV), and dedupe (in case driver's old location data has not expired yet).
To ensure the driver is indeed available for accepting orders, we should have a field in driver table telling us the driver's status
The dispatch service will also call Billing Service to calculate the fees and call Route planning service to calculate the route details.
Apart from that, dispatch will create an entry in trip details table, so we can start to track the trip.
After that, the dispatch can send the request to top driver. Things after that will go through the driver route
Most of our services are staleless, meaning we can horizatonal scale the fleet by adding more instances
for WebSocket node, it should maintain fixed connection with clients. In case of failures, we can use connection service with connection table to recreate the connections. For new connections, we can add more websocket nodes
Trip table can be sharded by trip_id
Driver_location table can be sharded by geohash. For hot partitions (like area around airport), we can further split the grid to smaller regions, so the data in one grid will be smaller
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?