Design Interviews · lesson 7 of 15 · about 30 min
A ride-hailing system end to end: the constant stream of locations, how to find nearby drivers fast, how to spread the map over machines, how to match well, how surge balances supply and demand, and what ghost drivers do to waiting times. Tap any for a plain-language card.
A million dots that never stop moving
Frequency is a trade-off between accuracy and cost: update more often and matches are better but the firehose, battery and bandwidth grow; update less and the dot on the map lags. Many apps adapt: fast when moving or on a trip, slow when idle. Size yours.
1 million online drivers reporting every 4 seconds is 250,000 location writes a second (200 Mbps at 100 bytes each), against 230 ride requests a second for 20 million trips a day.
1000K drivers reporting every 4 s make 250K location writes a second (200 Mbps) for just 231 ride requests a second: 1080 writes per request. The latest position of every driver is only 0.10 GB, which fits easily in memory.
Arithmetic. History is written asynchronously to cheap storage for analytics and safety; the live index keeps only the latest point.
Who is within 2 km of this rider?
Cell size is the tuning knob. Too small and a query must visit hundreds of empty cells; too large and each cell holds so many drivers that you are nearly scanning everything again. The best size is around the search radius divided by a small number. The simulation runs real queries over real positions, with hotspots if you want them.
50,000 drivers, a 2 km radius and 1 km cells: a query examines about 730 drivers in 23 cells instead of 50,000. With 20 km cells it examines about 15,000; with 0.1 km cells it visits 1,600 cells.
With 1 km cells, a 2 km search visits 23 cells and examines 734 of 50,000 drivers to find 377 inside the circle: 66× less work than scanning everyone.
Real queries (200 random points) over seeded driver positions; the circle test is exact, the grid only narrows what is examined. Hotspots are five Gaussian clusters.
Downtown at rush hour
It is the usual trade between balance and locality, here with a spatial twist. Real systems start with regions and then split hot regions finer (more shards where there are more drivers), or keep cells small and assign them to shards by load, with a mapping table. The simulation shows both numbers for the same drivers: how much hotter the busiest shard is than average, and how many shards a search has to ask.
50,000 drivers with 60% in hotspots over 16 shards: by region the busiest shard carries 2.5× the average but a search touches 1.7 shards; by cell hash it carries 1.3× but a search touches 12.5 shards.
Sharding by region over 16 shards, the busiest shard holds 2.5× the average and a 2 km search asks 1.7 shards. The other scheme would give 1.3× and 12.5: you cannot have both balance and locality for free.
50,000 seeded drivers on 1-km cells; region shards are square blocks of the 40 × 40 km city. Fan-out is the mean number of distinct shards covering a search circle (100 random searches).
Nearest is not the same as best
Real dispatch goes further: it considers the driver's direction, predicted travel time (not straight-line distance), ride type, driver rating and fairness, and may re-match or pool rides. Each assignment then needs an offer to the driver, who can decline or time out, so matching is a loop with an claim on the driver so two riders are never given the same one. This simulation compares sequential-nearest with closest-pair batching on random positions.
With 60 requests and only 40 free drivers in a 10 km square, sequential nearest-first averages 2.0 km pickups and batching averages 1.1 km. With 100 riders and 100 drivers: 1.5 km versus 1.2 km.
With 60 requests and 40 free drivers, 40 riders were matched. Sequential nearest-first averaged 2.00 km to pick up; batching the closest pairs averaged 1.07 km, 47% shorter, for a wait of a second or two to collect the batch.
Random positions in a 10 × 10 km square, straight-line distance. Closest-pair batching is a greedy heuristic, not the optimal assignment, so the real gain from proper assignment is at least this.
When there are more riders than cars
The numbers below use an illustrative model: demand shrinks and supply grows as a power of the multiplier, with elasticities you choose. Real systems estimate these per area and time, update every minute, smooth the changes, cap the multiplier in emergencies, and publish the price before the rider accepts it. Whether surge is fair is a product and policy question; the engineering question is making it fast, local and stable, not oscillating.
Demand for 1,000 rides and supply of 600, with elasticities 0.8 (demand) and 0.5 (supply): the price rises about 1.48× and both settle at about 730 rides.
With 1,000 wanting rides and 600 available, a 1.48× price makes demand fall to 730 and supply rise to 730: they meet, and 400 riders who would have been stranded are reduced to those unwilling to pay.
Illustrative constant-elasticity model: demand = D0 × m^(−e_d), supply = S0 × m^(e_s); equilibrium m = (D0 ÷ S0)^(1 ÷ (e_d + e_s)). Not an estimate of any real market.
Pick the fix
Each problem has one fix that fits best. Each answer is worth 20 XP.
Match the symptom: slow search, a hot shard, poor pickups, or unanswered offers?
Every ride request scans all 50,000 drivers' positions.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Published tools and designs from ride-hailing and mapping.
hierarchical hexagonal grid
Uber open-sourced H3, a hexagonal hierarchical geospatial index, in 2018; hexagons have equal-distance neighbours, which makes smoothing and neighbour searches (such as for surge pricing and supply counts) behave better than with square cells.
spherical geometry library
Google's S2 library divides the sphere into hierarchical cells identified by 64-bit ids, so a region can be covered by a small set of ranges of cell ids and stored in an ordinary sorted key-value store.
geohash-based commands
Redis added GEOADD and radius-search commands that store members in a sorted set keyed by geohash, a simple way to answer nearby queries entirely from memory.
consistent-hash sharded dispatch
Uber described its dispatch service as sharded geographically with consistent hashing across nodes using Ringpop, so that all the requests and drivers of an area are handled together without a central database.
Interview angle
Six questions, each worth 20 XP. Strong answers separate the location stream from the ride requests.
Name the index, the sharding, the matching rule and how stale data is handled.
What dominates the traffic of a ride-hailing system?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
The cure is a on each location: an entry expires unless refreshed by the next ping, so a ghost lives only as long as the TTL (set it to a few missed updates). Add connection health from the channel to remove a driver immediately when the socket drops, and prefer drivers whose last ping is very recent. Shorter TTLs mean fewer ghosts but risk dropping drivers with a patchy connection. By Little's law the ghosts present are the vanish rate × the TTL.
10,000 active drivers with 600 vanishing a minute and a 120-second TTL: 1,200 ghosts are in the index, 11% of first offers go to a ghost, and each such offer wastes 10 s, an average of 1.2 s extra wait for everyone.
600 drivers vanishing a minute with a 120 s location TTL leave about 1,200 ghosts among 10,000 real drivers: 10.7% of first offers go to a ghost and each wastes 10 s, an average 1.2 s extra wait. Halve the TTL and the ghosts halve.
Little's law: ghosts = vanishing rate × TTL. Share of ghosts among candidates p = ghosts ÷ (active + ghosts); expected extra wait = p ÷ (1 − p) × timeout (repeated ghost offers).