Case study: Ride-hailing and food delivery

"Design a ride-hailing app" and "design a food delivery app" are common questions. The interviewer asks: "A rider taps Book. How do you find a driver, and what stops two riders from getting the same driver? How does the rider watch the car move?" For food delivery there is a follow-up: "How does the delivery person reach the restaurant at the right time?"

A weak answer stores driver positions in a normal table and searches by distance. It uses straight-line distance as the arrival time, and it has no rule against giving one driver to two riders. A strong answer keeps drivers in memory by map cell and ranks them by road time. It uses one conditional update to give a driver to only one rider. It sends live positions only for trips that are running.

At SDE-1 level you should follow one booking. At SDE-2 level you should add the numbers and the order states. At SDE-3 level you should also handle a crowd after a match and the timing of the kitchen.

Think about a taxi stand with one dispatcher. A board shows the free taxis near each gate. A passenger asks for a taxi. The dispatcher picks a few taxis that can arrive soonest, not just those that look close on the map. Then the dispatcher phones one driver at a time. That taxi gets a "busy" tag, so no other passenger gets it. If the driver says no, or does not answer in 15 seconds, the tag goes and the next driver gets the call. For food, the dispatcher also watches the kitchen. A delivery person is sent to the restaurant just before the food is ready. Too early, and the person waits for nothing. Too late, and the food gets cold.

In ride-hailing, a rider books a trip and a driver takes it. In food delivery, a customer places an order, a restaurant cooks it, and a partner (the delivery person) brings it. Food delivery has three sides, and the kitchen takes time. A location update is a small message with the position of a phone. A driver app sends one every 4 seconds (an assumption, like every number here that is not worked out). The ETA (estimated time of arrival) is the minutes until the driver reaches the rider.

The parts

• Gateways hold one WebSocket for each driver app (lesson 75). They receive location updates and push offers to the driver.
• The geo index is in memory and split by city (lesson 43). It keeps two maps (lesson 79): the driver to its position, cell and status, and the cell to the set of drivers in it.
• The trip service owns trips, orders and driver status in a database. It makes the final choice.
• The matching service finds candidates, ranks them and makes offers.
• The routing service gives the road time between two points, using the road map and live traffic. We treat it as a box.
• Tracking servers push positions to riders and customers (lesson 75).
• A location history log keeps old points for disputes. It is never on the matching path.

Nearby

Drivers move, so they live in the memory index, not in an indexed table (lesson 79). A search reads the rider's cell and the 8 cells around it, keeps the drivers marked AVAILABLE (free to take a trip), and measures the straight-line distance to each one. That is the shortest way along the ground. If fewer than 10 drivers are found, it adds the next ring of cells. A ring is the cells just outside the block already read. The status in the index can be a few seconds old, so the index only suggests candidates. The trip service decides.

Restaurants do not move. The customer's list of restaurants uses a normal cell index and a cache (lesson 79). The partner search uses the moving index, centred on the restaurant.

ETA

Road time follows real roads and traffic. A driver 0.5 km away across a river may need 9 minutes by road. A driver 1.2 km away on the same road may need 4. So the matching service takes the 10 closest drivers by straight line (the shortlist). It asks the routing service for the road time of each, and ranks by that time.

If the routing service does not answer in 200 ms (an assumption), use a rough ETA. It is the straight distance x 1.4 / 20 km per hour (both numbers are assumptions). Show it as "about". The map screen uses this rough ETA all the time. Only the choice of a driver, and a running trip, use the routing service.

Assigning a driver

The index may be old, so the check happens in the trip service. It uses a conditional update (lesson 22). This is a statement that changes a row only if a condition is still true.

UPDATE drivers
SET status = 'OFFERED', trip_id = 981, offer_until = now() + interval '15 seconds'
WHERE id = 17 AND (status = 'AVAILABLE' OR (status = 'OFFERED' AND offer_until < now()));

If 1 row changes, this rider has won driver 17. If 0 rows change, another rider was first, so the matching service tries the next driver in the shortlist. The offer is pushed to the driver app. If the driver accepts, a second conditional update sets the status to BUSY. It works only if the offer is still this trip's and has not ended. If the driver says no or does nothing for 15 seconds, the offer is over. An old offer counts as free, as an old seat hold does (lesson 22), so no cleanup job is needed. The service then offers to the next driver, up to 5 drivers. After that it tells the rider honestly that there is no driver now.

Live tracking

While a driver is on a trip, each location update is also pushed to that trip's rider. The data goes one way, so Server-Sent Events fit (lesson 75). A lost update does not matter, because the next one comes in 4 seconds. Drivers who are not on a trip are not pushed to anyone.

The lifecycle: small state machines

Each thing has its own state machine (lesson 66), and each change is one conditional update.

• Trip: REQUESTED, MATCHED, ARRIVED, STARTED, COMPLETED. Cancel is allowed until STARTED.
• Driver or partner: OFFLINE, AVAILABLE, OFFERED, BUSY.
• Food order: PLACED, ACCEPTED, PREPARING, READY, PICKED_UP, DELIVERED, and CANCELLED (lesson 66).

Keep the order machine and the partner machine apart. One rule links them: the partner can pick up only when the order is READY. A single machine would need up to 7 x 4 = 28 states. Two machines need 7 + 4 = 11.

The third side: the kitchen

A ride can start as soon as the driver arrives. A food pickup must wait until the food is cooked. When the restaurant accepts, it gives a prep time, for example 15 minutes. The partner needs some minutes to travel to the restaurant. If the search starts at once, the partner arrives early and waits. So the order service starts the search at: prep time - travel time - 1 minute for the search itself. A loop that runs every few seconds finds orders whose start time has come. If the restaurant marks the order READY early, the search starts at once.

Assumptions (made up to teach with, except the ride-hailing scale, which follows a Tradeoff practice problem; see Sources):

• 1,000,000 drivers are online at the peak, in 50 cities. The biggest city has 10% of the load. Each driver sends a location update every 4 seconds.
• 300,000 ride requests come in one peak hour. A rider opens the map 10 times for each booking. A map stays open for 30 seconds and refreshes every 5 seconds. A trip lasts 25 minutes on average.
• One memory index server does 70,000 operations per second at our plan. A gateway holds 50,000 connections (lessons 75 and 77). One in 12 updates crosses a cell edge (lesson 79). A search reads 9 cells.
• A driver accepts 60% of offers. An offer lasts 15 seconds. A server has 8 cores, which is 5,600 ms of work per second at 70%. A partner does one order at a time.
• Food: 200,000 orders in the peak hour. Prep time 15 minutes. Travel to the restaurant 6 minutes. Delivery 10 minutes.

Step 1: the index. Updates: 1,000,000 / 4 = 250,000 per second. Memory: 1,000,000 x 100 bytes = 100 MB, which is small. A cell change is 2 operations (remove and add): 250,000 / 12 x 2 = 41,667. Bookings: 300,000 / 3,600 = 83.3 per second. Map opens: 83.3 x 10 = 833 per second, and 833 x 30 = 25,000 maps open at once. Map searches: 25,000 / 5 = 5,000 per second x 9 cells = 45,000. Booking searches: 83.3 x 9 = 750. Total: 250,000 + 41,667 + 45,000 + 750 = 337,417 per second. That is 337,417 / 70,000 = 4.8, so 5 servers. The biggest city is 10%: 33,742 per second, which is 48% of one server. So the city split is for write speed and for failure, not for size.

Step 2: connections. 1,000,000 / 50,000 = 20 gateways, plus 10% for failures = 22. Assumption: an update costs 0.1 ms of CPU. That is 250,000 x 0.1 = 25,000 ms per second, and 22 servers give 22 x 5,600 = 123,200 ms. It fits.

Step 3: ETA. Trips running at once = 83.3 per second x 1,500 seconds (25 minutes) = 125,000. Their ETA refreshes every 30 seconds: 125,000 / 30 = 4,167 per second. Each booking asks for 10 road times: 833 per second. Total 5,000 per second. Assumption: a call costs 5 ms. That is 25,000 ms per second, and 25,000 / 5,600 = 4.5, so 5 routing servers.

Step 4: the offer (the predict box). Both riders run the update for driver 17. The database lets one finish first. That rider sees 1 row changed. The other sees 0 rows, so it offers driver 22, the next on its shortlist. Nobody gets a double booking. With a 60% accept rate, the chance that all 5 drivers refuse is 0.4 to the power of 5 = 1%. The expected wait: refusals before a yes = 0.4 / 0.6 = 0.67. Assume a refusal takes 10 seconds on average and a yes takes 5. Wait = 0.67 x 10 + 5 = 11.7 seconds. Offering to 3 drivers at once is faster, but up to two drivers may then lose a trip they accepted.

Step 5: tracking. 125,000 running trips each get a point every 4 seconds: 125,000 / 4 = 31,250 pushes per second. Connections: 125,000 / 50,000 = 2.5, so 3 servers plus 1 spare.

Step 6: a crowd after a match. 5,000 riders ask in 60 seconds from one area. That is 83 per second, as much as all 50 cities together at the peak. Only 200 drivers are in the 9 cells. A hot cell is a cell with far more requests than the others (lesson 45). It does not need more servers, because the index work is small. The limit is the number of cars. Widening by 2 steps reads 5 x 5 = 25 cells: 200 x 25 / 9 = 556 drivers (if they are spread evenly). Still, 5,000 - 556 = 4,444 riders get no car now. The routing load rises by 833 calls per second, which is 17% of 5,000. So the service queues requests for the area in order of arrival, widens the ring, and shows an honest wait.

Step 7: the kitchen. Orders: 200,000 / 3,600 = 55.6 per second. Each order makes 6 writes (create plus 5 moves): 333 per second. Assumption: one database does 5,000 writes per second (lesson 77). So this uses 6.7%. Now the partner timing, where one cycle is travel + wait + delivery:

• Search at once: the partner arrives at minute 6 and waits 9 minutes (we ignore the short search time). One cycle is 6 + 9 + 10 = 25 minutes, so 60 / 25 = 2.4 orders an hour.
• Search at minute 15 - 6 - 1 = 8: the search takes 1 minute, travel 6, so the partner arrives at minute 15. One cycle is 6 + 10 = 16 minutes, so 60 / 16 = 3.75 orders an hour. That is 56% more.
• At 200,000 orders an hour: 200,000 / 2.4 = 83,333 partners against 200,000 / 3.75 = 53,333. The difference is 30,000 partners.
• The customer ETA is 15 + 10 = 25 minutes. If the search starts 3 minutes late, it is 28.

Step 8: a part fails. A memory index server dies. Every driver reports again within 4 seconds, so a new server fills its maps in a few seconds. Trips and driver status are in the database, so nothing is lost. A driver phone loses the network. The offer ends after 15 seconds. The driver leaves the index after 5 missed updates (20 seconds, an assumption).

• A memory index solves 250,000 updates per second that a table cannot take. It costs an index that is a few seconds old, so the database must make the final choice.
• One offer at a time solves double work and angry drivers. It costs a wait of 11.7 seconds on average. I would offer to 2 or 3 drivers at once when waiting hurts more than lost offers.
• Road time solves wrong ETAs. It costs 5 routing servers. I would fall back to the rough ETA when the routing service is slow.
• Starting the search by the kitchen clock solves idle partners: 3.75 orders an hour against 2.4. It costs a prep time that must be good. A late restaurant makes the partner wait, and I would learn the real prep time of each restaurant.

"Store the driver positions in the database and search with a distance query." At 5,000 writes per second for each database server, 250,000 updates need 50 servers. A position is also old after a few seconds. Use memory, keyed by cell.

"The nearest driver on the map is the best driver." A driver 0.5 km away can be 9 minutes by road, and one 1.2 km away can be 4. Rank by road time.

"Assign the partner as soon as the restaurant accepts." The partner waits 9 minutes. One partner does 2.4 orders an hour instead of 3.75, and 30,000 more partners are needed.

1. Why can the index not decide who gets a driver? What does?
2. 400,000 drivers are online and each sends an update every 5 seconds. One in 10 updates crosses a cell edge. A memory server does 70,000 operations per second. How many servers do the updates need? Count only the updates and the cell changes, with 2 operations for each cell change.
3. A restaurant gives a prep time of 20 minutes. The partner needs 8 minutes to reach it, and the search takes 1 minute. When should the search start? What does the partner do if it starts at minute 0?