Loading...
Driver
Rider
We assume pricing is statically calculated based on start and end distance, and we'll not focus on pricing in this design due to limit of time.
Drivers and riders' locations shall be updated near real-time.
Trip info shall be highly consistent.
Location service shall be generally available.
Assume the entire platform has 10 M drivers and 200 M riders. At any given time, averagely there's 1 M drivers and 10 M riders being active. For peak hours, 3 M drivers and 30 M riders.
Assume we use geohash for location service.
Driver data:
uid 8 bytes
location 12 bytes
Rider data:
uid 8 bytes
location 12 bytes
Trip data:
from: 12 bytes + metadata
to: 12 bytes + metadata
request time: 8 bytes
ETA: 8 bytes
total: say 100 bytes
Assume location is updated every 5 seconds.
Avg: 1M * 20 + 10M * 20 + 1M*100 = 320MB / 5 seconds
Peak: 960MB / 5 seconds
Data size may be easily fit into one single machine. However, due to users being globally distributed, we need multiple servers to ensure minimum latency for every geographic locations.
The APIs are called by client app to report location, request trip, etc.
POST /locations/
payload contains user id, location geohash
GET /locations/
for riders to get nearby drivers' locations by passing the rider's geohash location
GET /locations/
for drivers to get nearby riders' locations
PUT /trips/
payload: rider id, location, trip begin and end locations, action type = new. For rider to request a new trip
payload: driver id, location, action type = accept. For driver to accept a rider's trip request
payload: driver id, location, action type = ready. For driver to indicate ready to start trip
payload: driver id, location, action type = start. For driver to mark trip as started
payload: driver id, action type = end. For driver to mark trip as completed.
DELETE /trips/
payload: rider id, trip id. for rider to cancel a trip request
payload: driver id, trip id. for driver to cancel a not-yet-started-but-accepted trip
As location is updated in short period of time and shall be almost always available, and that users are distributed geographically, and each piece of location data is small, we use in-memory KV store, e.g., Redis.
We partition the service nodes by geo locations. If a small geo area becomes too hot, we further split the traffic into two nodes.
User profiles are small, highly relational data, and does not require continuous updates and is not frequently accessed, we use SQL to store them.
Trip data are partially relational (rider and driver, start and end points, timestamp, duration) and partially document style (directions). They're accessed and updated during the trip lifetime, yet rarely accessed after trip is completed. We may choose document DB, e.g., MongoDB to store them.
See diagram
Rider:
Driver:
We'll discuss how driver gets riders requests later.
Moving users between location service nodes:
When a user moves from one geohash grid to another which causes moving to a different partition node, we will move this user if the user's move has been persistent, i.e. stayed in the new grid for long enough time, e.g., 10 seconds. This is to avoid unnecessary traffic is a user is moving on the boundaries back and forth.
Location update: Pull vs Push vs WebSocket
Similar handling for rider and driver. Take rider as an example. Rider's app reports their location every 5 seconds, this is a push request to the location service. In the same period, the app client could pull nearby drivers locations from the service. This reduces complexity of design, but in cost of having up to 5 seconds of driver location delay when network condition is good. This tradeoff is ok in most cases. Another option is let the location service to push driver locations to client app when it's updated. This adds more work and stress on the location service side, but client side will see more close to real-time driver location update. Another option is to have a websocket connection between server and client, such that any location update can happen nearly real-time. This is expensive in wireless data cost on client side; also, server needs lot of network bandwidth, which means that we'll need much more nodes/partitions, each of which handle a smaller geo area. As a result, we choose the pull other side of party method.
See "Detailed component design".
A location service node may be down. We can apply consistent hashing on how we distribute nearby geohash grids. If one node is down, then all drivers and riders in this node can be rehashed to its next adjacent node on the hash ring. If this causes overload on the next node, we could use the similar overloading handling algorithm to redistribute some traffic to the further next adjacent node. We need a orchestration service, such as zookeeper, to track the traffic distribution, such that if the dead node becomes online again, we have the capability of returning certain traffic back.
There may be race condition that multiple drivers see the same rider's trip request and they all try to accept it. One alternative is to have the trip service to only send trip request to one driver at a time, e.g., based on the distance of driver and rider. If the driver does not accept after timeout, the request goes to the next driver. This round robin approach avoids race condition, but will likely let the rider wait longer time, especially at off-peak hours when not many drivers are available. Another alternative is to have the trip service to respond with confirmation status back to driver app. This is actually easier to implement and only adds a minimal latency on driver side.
Other improvements may be: