The short answer
Quick answer: Drivers' phones send their GPS position to the server every few seconds. The server stores each position in a geospatial index, which divides the map into cells so that "who is near this point?" becomes a quick lookup of a few cells instead of a scan of every driver. When you request a ride, the system finds candidate drivers in the cells around you, estimates how long each would take to reach you by road, picks the best match, and sends an offer to that driver. If they decline or time out, it moves on to the next.
This article explains the general design of ride-hailing systems. Uber has published a good deal about its approach, including its open-source H3 grid; the full details of its current dispatch system are not public.
The core problem
The naive solution is to compute the distance from the rider to every online driver and sort. With hundreds of thousands of drivers moving constantly and thousands of requests per second, that is far too slow.
Ordinary database indexes do not help much either. A B-tree index works on one dimension. You could index latitude, but "latitude between X and Y" still returns a band stretching around the whole planet. Location is two-dimensional, and it needs a different kind of index.
Step 1: Collecting locations
Each driver's app sends its position every few seconds over a persistent connection; see how WebSockets work. That is a very large volume of small writes, with two useful properties:
- Only the latest position matters for matching.
- Losing one update is harmless, because another arrives seconds later.
So current positions are typically kept in a fast in-memory store, updated in place, and partitioned by region. A separate stream of the same updates flows through a message queue into long-term storage for trip records, analytics and machine learning.
Step 2: Turning two dimensions into cells
The trick is to cut the map into cells and give each cell an ID. Then "nearby" means "in the same or neighbouring cells", and cell IDs can be indexed like any other key.
Geohash
A geohash divides the world into a grid recursively and encodes each square as a short string. Longer strings mean smaller squares, and squares that share a prefix are close together.
- Simple and supported by many databases.
- Edge problem: two points a few metres apart can sit either side of a cell boundary and have completely different codes, so searches must always include neighbouring cells.
- Cells are rectangles whose shape distorts with latitude.
Quadtrees
A quadtree splits a square into four, and splits busy squares again. Dense city centres get many small cells and empty countryside gets a few large ones, so each cell holds a similar number of points.
S2 and H3
Google's S2 library projects the Earth onto a cube and uses a space-filling curve to number cells. Uber developed H3, a hierarchical grid of hexagons, described in its engineering blog and at h3geo.org.
Why hexagons? In a square grid, a cell's eight neighbours are at two different distances: edge neighbours are closer than corner neighbours. A hexagon's six neighbours are all the same distance from its centre. That makes "everything within k rings of this cell" a clean approximation of a circle, and makes smoothing and movement analysis more uniform.
| Geohash | Quadtree | H3 | |
|---|---|---|---|
| Cell shape | Rectangle | Square | Hexagon |
| Adapts to density | No | Yes | Fixed resolutions |
| Neighbour distances | Uneven | Uneven | Uniform |
| Typical use | Simple proximity search | In-memory spatial indexes | Ride-hailing, supply and demand analysis |
Step 3: Finding candidates
With a cell index, a nearby search is:
- Convert the rider's position to a cell ID.
- Get that cell and its ring of neighbours.
- Look up the drivers currently in those cells.
- If there are too few, widen the ring.
The index is essentially a map from cell ID to the set of drivers in it. In-memory stores handle this well; Redis, for example, has built-in geospatial commands. See why Redis is fast.
When a driver moves from one cell to another, they are removed from the old set and added to the new one.
Step 4: Choosing the best driver
The closest driver in a straight line is often not the best choice.
- Use travel time, not distance. A driver 300 metres away across a river or on the wrong side of a motorway may take longer than one a kilometre down the road. A routing service estimates the ETA for each candidate using the road network, traffic and turn restrictions.
- Consider drivers finishing nearby trips. Someone about to drop a passenger around the corner may be the fastest option.
- Batch requests. Matching each request to its nearest driver the instant it arrives is "greedy" and can leave other riders worse off. Collecting requests and available drivers for a few seconds and solving the assignment together produces lower total waiting time. Uber has described using this kind of batched matching.
- Apply filters: vehicle type, accessibility needs, driver preferences and ratings.
Step 5: Dispatch
Once a driver is chosen:
- The trip offer is pushed to the driver's app.
- The driver has a short window to accept.
- On acceptance, both apps receive each other's details and live location.
- On decline or timeout, the system offers the trip to the next best candidate.
A trip is a state machine: requested, matched, driver arriving, in progress, completed or cancelled. Two guarantees are essential and require careful concurrency control: one driver must never be assigned two riders at once, and one request must never be assigned to two drivers. See how database transactions handle concurrent users.
Surge pricing
The same grid is used to balance supply and demand. For each cell, the system compares open requests with available drivers. Where demand outstrips supply, prices rise. The intent is to nudge some riders to wait and attract more drivers to the area. Hexagonal cells make it natural to smooth these values across neighbouring cells so prices do not jump sharply at a boundary.
Scaling it
- Partition by geography. A request in Karachi never needs data about drivers in London. Cities or regions map to separate shards, which keeps each one small and isolates failures. See sharding explained.
- Keep hot data in memory. Current positions and cell membership change every few seconds and do not need durable storage.
- Use streams for everything else. Location history, trip events and pricing signals flow through message queues to the systems that need them.
- Degrade gracefully. If the routing service is slow, fall back to simpler estimates rather than failing the request.
Frequently asked questions
How does an app find the nearest driver so fast?
It indexes drivers by map cell. A search only looks at drivers in the rider's cell and its neighbours, not at every driver in the city.
What is a geohash?
A short string that encodes a rectangular area of the map. Longer strings are smaller areas, and nearby places usually share a prefix.
Why does Uber use hexagons?
All six neighbours of a hexagon are the same distance away, which makes radius searches, smoothing and movement analysis more uniform than with squares.
Why was I not matched with the closest car?
Matching uses estimated travel time, driver availability and overall efficiency across several requests, not straight-line distance alone.
Conclusion
Ride matching is a geospatial search problem wrapped in a real-time system. Dividing the map into indexed cells makes "who is nearby" cheap, road-based ETAs make the choice sensible, and batching makes it efficient for everyone. The same pattern underlies food delivery, bike sharing and any other "find the nearest" service.
Related articles
- How WebSockets Enable Real-Time Apps Like Chat and Live Scores
- How Redis Is So Fast
- How Message Queues Like Kafka Decouple Systems
- Sharding Explained: How Databases Scale Beyond One Machine
Sources and further reading
