Design rider matching
How do you match moving riders to pickups every few seconds?
Why did one rider get two pickups and one customer none?
The delivery service now promises a lunch in 30 minutes if you order before 12:30. Lunch boxes on the old fixed routes still travel the way they always have. The new orders are different: nobody knows in the morning which kitchen will cook them or where they go. They need a rider found on the spot.
Today that is done by hand, from a desk: three dispatchers, a screen showing every rider’s last position, and a WhatsApp group for each area. With 80 riders it worked. This month there are 300.
At 12:31 one Tuesday, two dispatchers look at the same screen and see the same idle rider near one kitchen. Each sends him a pickup, from two different kitchens. He takes the first message and never sees the second. The second kitchen waits 25 minutes with a sealed box on the counter. It is a low-sugar lunch for a diabetic customer who eats on a schedule his doctor set.
The same hour shows a second fault. A rider from Kothrud is sent to Aundh because he is nearest to the first order. Two minutes later an order comes from Kothrud and the nearest rider is eight kilometres away.
The obvious fix is to let the app do it: when a kitchen presses “ready”, find the nearest idle rider and mark him busy, with no people or WhatsApp groups involved. A geo index finds the nearest rider in a millisecond. The best human dispatchers do something different at 12:30. They do not send the first rider they see. They wait a few seconds, look at the whole board, and send the riders out together.
Finding which riders are near a kitchen is the easy part. Two harder questions remain: who decides which rider goes to which order, and what stops two decisions from giving away the same rider? Good matching looks at many orders at once, and each decision must be recorded in one place, so that a rider can be claimed by only one order. Before reading on, guess how much riding the nearest-first rule wastes at the peak.
Pause and predict Two dispatchers sent the same rider to two different kitchens. What would stop one rider from being given two pickups at once?
What must never go wrong?
Dispatch sits between riders, kitchens and the ordering platform. The ordering platform keeps track of orders; dispatch keeps track of riders and which rider is going where.
The first non-functional requirement is that a rider has at most one pickup at a time. The second follows from the sealed box on the counter: no order may wait for a rider who is not coming.
Core entities, in two minutes
A Rider (status: idle, offered, on a pickup), a Location (only the latest one is kept for matching), an Order that is ready, an Offer (one rider, one order, an expiry), and an Assignment once an offer is accepted.
The estimate that changes the design
Each rider’s phone sends its position every 4 seconds. Pune today: 300 / 4 = 75 writes a second. Three cities at 1,000 riders each: 750 a second. Only the latest position matters for matching, about 100 bytes a rider: 3,000 x 100 B = 300 KB. The whole live picture fits in the memory of one small machine many times over.
The matching work is small too. At the peak, Pune has about 60 orders ready a minute and about 150 idle riders. A batch every 20 seconds holds about 20 orders. What the estimate saves: there is no need for a sharded location index or for matching spread across machines. One dispatcher per city can see every order and every idle rider of that city at once, which is exactly what good matching needs. (The full history of positions still flows to the location store of lesson 2.5, for disputes and analytics; matching never reads it.)
The obvious version, and how it breaks
The first version lives in the ordering app. When a kitchen presses “ready”, the app server that receives the request reads the nearest idle rider from a riders table and then marks him busy. It is stateless, so all six app servers can do it (lesson 1.1).
It has two faults, and they are different kinds of fault.
Pause and predict Two app servers handle two ready orders a few milliseconds apart. Each reads rider 117 as idle, then marks him busy. What happens?
A quality fault. Nearest first is greedy: each order takes the best rider for itself, without asking whether a later order needed that rider more.
Run it. Start with “Nearest rider, at once”, then switch on two dispatchers without a conditional write, then try batching with few and with many idle riders.
With 150 idle riders and 60 orders a minute, nearest first rides 285.5 km to pickups in three minutes. Two dispatchers without a conditional write leave 7 kitchens waiting for a rider who is not coming when they assign at once, and 46 when they batch.
A mental model
- The assignment problem
- Given some orders, some riders, and the cost of sending each rider to each order, choose who goes where so that the total cost is as small as possible, with each rider used at most once.
- For example: Two orders, two riders. Order A is 1 km from rider X and 2 km from Y; order B is 1.2 km from X and 6 km from Y. Nearest first gives A to X (1 km) and leaves Y for B (6 km): 7 km. Giving B to X and A to Y costs 1.2 + 2 = 3.2 km.
Assign at once, or batch?
Batching is the human dispatchers’ habit, waiting a few seconds and looking at the whole board, done in software. The question is whether it is worth the delay.
Both are right, at different times of day. When riders are plentiful, the nearest rider is nearly always the best match, and waiting costs a tenth of a minute for nothing. When riders are scarce, the batch saves 9% of the riding and gets riders to kitchens sooner on average, even after the 10-second wait. The lunch peak is when most orders arrive and riders are scarcest, so the choice is made for the peak.
A later refinement could shorten the window when idle riders are plentiful. Until the numbers show a need for that, the window stays one fixed setting.
What to remember
- Matching is a decision over many orders and many riders at once: the assignment problem. Nearest first is greedy and spends scarce riders badly at the peak.
- Batching trades a few seconds of decision delay for less riding. It pays when riders are scarce and buys almost nothing when they are plentiful.
- Claim a rider with a conditional write and back it with a constraint (one open offer per rider). Correctness must not depend on only one dispatcher running.
- An offer is a hold with an expiry: unanswered offers return the rider and the order to the next batch, and late accepts are refused.
- Keep only the latest position for matching; it is small, fits in memory, and rebuilds itself from the next pings.
Match the whole batch at once, and claim each rider with a conditional write that fails if he is already taken.
In the real world
Real dispatch systems add what our toy leaves out: travel-time estimates from road graphs, riders who become free again at the place they delivered, several orders on one trip, predictions of where riders will be needed next, fairness so that no rider waits an hour while others ride constantly, and acceptance rates learned per rider. Large platforms describe solving batches city by city, much as here, but their exact algorithms are rarely published; nothing here claims to describe any particular company’s system.
The core stays what you built: see the whole board, decide together, and claim each rider exactly once. In booking, the scarce thing is a festival thali, and the hold with an expiry becomes the centre of the design.