CodeBrewerz“Find the nearest driver” sounds like a query. It is not, and the reason is in the verb tense: by the time you have found them, they have moved.
A ride-hailing system’s defining property is that its index is under constant write pressure. A hundred thousand active drivers reporting position every four seconds is twenty-five thousand writes a second, forever, against the exact structure you are also reading from on every ride request. Almost every design decision in this system is downstream of that one number.
Why the obvious index does not work
The textbook answer is a spatial index — an R-tree, or PostGIS on top of one. These are excellent structures and they are built on an assumption you have just violated: that reads vastly outnumber writes. A tree index rebalances on insert, and rebalancing under a sustained twenty-five thousand writes per second is where this design dies.
So the working answer is not a tree. It is a grid.
Divide the world into cells with a fixed scheme — geohash, S2, H3, or a plain latitude and longitude grid — and make the cell id a string. A driver’s position update becomes “remove from old cell, add to new cell”, which is two hash operations rather than a rebalance. A query becomes “give me everyone in these cells”, which is a key lookup. The whole thing fits in memory in something like Redis, and it degrades gracefully because every operation is O(1).
The price of that simplicity is that a grid does not know about distance.
A rider at the edge of a cell
—
The rider is near a cell boundary — which, with any grid, a large fraction of riders always are — and the closest driver is in the next cell. Query only the rider’s own cell and that driver is invisible. Nothing fails. A driver is still dispatched, just a worse one, and the only symptom is a pickup time a little higher than it should have been. This is the most common bug in a first geospatial implementation precisely because it never announces itself.
The fix is to always query the ring of nine cells, and the cost is that you now examine nine times as many candidates. Which sets up the real parameter: cell size. Too large and you scan thousands of irrelevant drivers downtown at rush hour; too small and the ring of nine still is not wide enough in a suburb where the nearest car is three kilometres away. Every serious implementation ends up with variable resolution — smaller cells where density is high — which is exactly what S2 and H3 give you, and it is why people use them instead of a plain grid.
Assignment is not the same as search
Once you have candidates, there is a second decision that most designs skip entirely.
Four riders, four drivers, two ways to assign them
—
Greedy dispatch — each rider takes the nearest free driver at the moment they ask — is unarguable per rider and measurably worse for the group. Early riders consume drivers that later ones needed, and nothing in the system can observe that happening, because every individual decision was correct when it was made.
Batching a few seconds of requests and solving the assignment together does better. It will sometimes hand a rider a driver who is not their closest, and everyone still waits less on average. The cost is honest and bounded: nobody is matched until the window closes, so the window is a few seconds, not a minute.
Straight-line distance is also the wrong ranking function, and it is worth being explicit about why. The driver 200 metres away across a river with no bridge is twenty minutes away. The correct ranking is estimated time of arrival on the road network, which means the candidate set from the grid is a shortlist that gets re-scored by a routing engine, not an answer. Grid first because it is cheap, routing second because it is not.
And the assignment must survive the driver saying no. A dispatch is an offer with a timeout, which means the driver is provisionally held, then released if unaccepted — the same reservation-with-expiry shape as any inventory system, and the same failure if the release does not happen.
Two riders, one car
The concurrency bug here is the same one from the rate limiter, wearing different clothes.
Read the nearby drivers, pick the best, mark them as assigned. Two riders whose requests overlap both read the same driver as free, both pick them, and both write. One rider is now waiting for a car that is going somewhere else. This is check-then-act, it is invisible under light load, and it gets worse exactly at the times you most care about.
The fix is the same too: make claiming a driver a single conditional operation. A compare-and-set
on the driver’s state — set to assigned only if currently free — and the loser gets
nothing back and moves to the next candidate. Not a lock, not a transaction across two
stores, just one atomic write that can fail.
The related trap is that the driver’s location index and the driver’s assignment state are usually two different stores, and they will disagree. Treat the index as a hint: it tells you who to try, and the conditional claim tells you who you got. Any design where the index is authoritative about availability will dispatch cars that are already busy.
The parts nobody mentions
Location updates do not all need to be durable. A position that will be superseded in four seconds does not belong in a write-ahead log. Keep the live index in memory, and write the historical trail — which you do need, for billing, disputes and analysis — to a separate append-only store on a different path. Conflating them makes the live path as slow as the durable one.
A stale driver is worse than a missing one. Drivers lose signal, and a driver whose last update was ninety seconds ago is somewhere unknown. Expire index entries aggressively — a TTL a few multiples of the update interval — so the index self-cleans without a sweeper. Dispatching to a ghost costs a rider several minutes.
Supply and demand are the same map. The same grid that answers “who is near this rider” answers “where are riders asking and no drivers exist”, which is what surge pricing and driver repositioning are built from. It is one of the few places where the operational index is also the business intelligence.
Airports and stadiums break every assumption. Thousands of drivers in one cell, a queue discipline that is first-in-first-out rather than nearest-first, and a demand spike that arrives on a timetable. These are handled as special-cased zones, not by making the general algorithm cleverer.
Test with real movement traces. A simulation of drivers on straight lines at constant speed will not produce the boundary churn — drivers oscillating between two cells at a junction, generating two index writes each time — that dominates your write load in practice.
The short version
The workload is write-dominated, so the index is a grid of cell ids in memory, not a tree. Position updates are a remove and an add; queries are key lookups; everything is O(1) and nothing rebalances.
Always query the ring of nine cells, because a grid has no notion of distance and the driver just over a boundary is invisible otherwise — a failure that produces slightly worse matches and no errors. Use a variable-resolution scheme so cell size can follow density instead of being one compromise for the whole map.
Treat the grid result as a shortlist to be re-scored by road-network ETA, not as an answer. Batch a few seconds of requests and solve the assignment together, accepting that one rider gets their second-best driver so that everyone waits less. And claim the driver with a single conditional write, because two riders reading the same free driver and both writing is the same check-then-act race that shows up in every system in this series — invisible in testing, worse at scale, silent when it fires.