Matching supply and demand

A different system: ride-hailing

Snip doesn't match anything to anything, so this lesson uses the classic example, a ride-hailing app, because the same shape appears in food delivery, freelance marketplaces and ad auctions. In one city at rush hour: 40,000 drivers sending their position every 4 seconds, and 2,000 ride requests a minute. Each request should get a nearby driver within a few seconds, and no driver should ever be sent to two riders.

Positions live in memory

10,000 position updates a second per city, each superseding the last, is a poor fit for a disk-based database. The dispatch service keeps a cell index in memory (12.06 Nearby search): each update moves a driver from one cell's set to another, along with their status (free, en route, on a trip). A lost position is replaced 4 seconds later, so this state can be rebuilt after a crash rather than made durable.

Cities are independent, so the natural shard is the city or region (05.01 Sharding: range, hash, directory): each region's dispatch runs on its own servers with its own in-memory index.

Greedy or batched?

Greedy: when a request arrives, give it the nearest free driver, now. Simple and immediate, but each decision ignores the next. Two riders on the same street can end up with one getting a car 1 minute away and the other a car 9 minutes away, when swapping would have made it 3 and 4.

Batched: collect requests for a few seconds, then choose the assignment of drivers to riders that minimises total pickup time (a classic assignment problem with efficient algorithms). Each rider waits a few seconds longer to be matched, and overall pickups get shorter.

Tested on 200 random batches of 6 riders and 6 drivers: greedy assignment gave a total pickup distance of 4,284, the best assignment 3,720, 13% less, for the cost of collecting requests for a moment.

Two refinements real systems use:

• ETA, not straight-line distance. A driver 300 m away across a river may be 10 minutes away. Candidates are found by distance, then ranked by estimated time from a routing service.
• Look ahead: a driver finishing a trip nearby in 1 minute may be a better match than a free driver 6 minutes away.

Never two jobs for one driver

The race: two dispatch decisions, made a moment apart, both pick driver 812. The fix is the same as any exclusive claim (08.08 Distributed locks and fencing tokens): claim the driver atomically before telling anyone.

• Change the driver's status from free to offered:ride-5521 only if it's still free (a compare-and-set in the dispatch store). The loser of the race picks another driver.
• The offer is a lease (08.07 Leader election and leases): if the driver doesn't accept within 15 seconds, the claim expires, the driver is free again, and the ride is re-matched.
• Keep a region's dispatch decisions on one owner (a leader per region), so most races never happen at all.

Steering supply and demand

Matching handles the next few minutes. Over longer periods, the system nudges supply and demand towards each other: measure requests and free drivers per area, often per H3 hexagon (12.05 Geospatial indexes). Where demand outstrips supply, prices rise (encouraging drivers to move there and some riders to wait), and drivers are shown where demand is high. Uber describes calculating surge pricing exactly this way: by measuring supply and demand in hexagons across each city.

Recap

Interview questions