Understanding the Ride Matching Problem
A ride-matching service (like Uber or Lyft) is one of the most popular real-time geospatial system design case studies. At its core, the system takes a pickup request, finds eligible drivers nearby, and turns a driver's acceptance into a matched assignment. The map and real-time geospatial data help choose whom to ask.
The complexity comes from the scale and the real-time nature of the requirements. The system must track millions of active drivers moving constantly, update their locations every few seconds, and query for nearest neighbors within milliseconds to fulfill rider requests.
Geospatial Indexing
To match riders with drivers, we cannot simply iterate through a database of all active drivers and calculate the distance to the rider using the Haversine formula. That approach would require O(N) operations per request, which is prohibitively expensive when N is millions of drivers.
Instead, we use a geospatial index. Common approaches include:
- Geohash: Divides the world into a grid and represents each grid cell as a short string. Searching for nearby drivers becomes a prefix match search. Redis has built-in support for Geohashing and radius queries.
- Quadtrees: A tree data structure where each node represents a bounding box and has four children representing the four quadrants of the box. Quadtrees allow for efficient spatial partitioning and searching, particularly when driver density varies drastically between urban and rural areas.
- Google S2 or Uber H3: S2 uses hierarchical quadrilateral cells; H3 uses mostly hexagonal cells plus required pentagons. Both discretize the sphere for candidate lookup, but cell areas and center distances vary with location and resolution, so final radius eligibility still needs an exact distance calculation.
The Architecture
A standard architecture involves a few key services:
The Location Service receives ping updates from drivers every 4 seconds via WebSockets or long polling. It updates the driver's current position in a distributed Redis cluster using geospatial indexes. To handle the high write volume, we can shard the Redis cluster based on regions or cities, since ride requests are fundamentally local (a rider in New York won't need a driver in Tokyo).
The Matching Algorithm
When a rider requests a car, the Matching Service kicks in:
- It queries the Location Service to get a list of active, available drivers within a certain radius (e.g., 2 miles).
- It filters out drivers who are already on a trip or have opted out of that specific ride type (e.g., UberX vs. UberXL).
- It ranks the drivers based on factors like distance, ETA, and driver ratings. ETA is usually calculated by a dedicated Routing Service that uses real-time traffic data, rather than just simple "as the crow flies" distance.
- It sends a dispatch request to the top-ranked driver. If the driver accepts, the match is made. If they decline or let the request timeout, the system moves to the next driver on the list.
Real-time Communication
HTTP request-response is not suitable for this real-time interaction. Instead, WebSockets or Server-Sent Events (SSE) are used. The Driver app maintains a persistent connection with a Dispatch/Gateway service. This allows the server to push ride requests instantly without the app needing to constantly poll.
Handling Concurrency and Race Conditions
What happens if two riders request a ride simultaneously, and the system tries to match both of them with the same nearby driver? This is a classic distributed systems race condition.
We must use distributed locks or atomic database operations to ensure that a driver can only accept one ride at a time. For instance, when a driver accepts a ride, the system can perform a conditional update (Optimistic Concurrency Control) on the driver's status in the database: UPDATE driver SET status = 'busy', ride_id = 123 WHERE driver_id = 456 AND status = 'available'. If this update fails (returns 0 rows affected), it means the driver accepted another ride a millisecond earlier, and the current rider's request must be routed to the next best driver.
Worked example: location ingestion
- 1.5 million drivers online at global peak, pinging every 4 s, is about 375,000 writes per second. Each ping is about 100 B (driver ID, latitude, longitude, heading, speed, timestamp), so about 37 MB/s of payload.
- Shard by city or region, since a request in Mumbai never needs drivers in London. A large city at peak might have 50,000 drivers producing 12,500 writes per second, which is comfortable for one in-memory shard plus a replica.
- Keep only the latest position in the hot index. Append the full stream to Kafka for trip replay, ETA model training and fraud detection.
- Drop drivers whose last ping is more than about 30 s old from the index, so a phone that loses signal does not keep receiving offers.
Matching strategies
| Strategy | How it works | Pro | Con |
|---|---|---|---|
| Greedy nearest ETA | Each request takes the best available driver immediately | Lowest latency, simple | Poor overall results at peak (a driver taken for one rider may have been the only option for another) |
| Batched assignment | Collect requests for 1 to 2 s, then solve a bipartite assignment that minimises total ETA | Better overall pickup times and utilisation | Adds a small delay; needs a solver |
| Sequential offers | Offer to driver 1, wait up to about 15 s, then driver 2 | Respects driver choice | Slow when drivers decline |
| Broadcast offers | Offer to N drivers at once; first to accept wins | Fast acceptance | Drivers get frustrated when they lose races; needs strict locking |
Uber and Lyft have both described batched or global matching for dense markets. Greedy matching is still reasonable for sparse areas.
Driver state machine with locking
The move to OFFERED is a conditional write: SET status = 'OFFERED', offer_id = :o WHERE driver_id = :d AND status = 'AVAILABLE'. The driver's accept must quote the same offer_id, so a late accept for an expired offer is rejected and cannot steal the driver from a newer match.