Ride Matching: Spatial Search and Safe Assignment

Ride matching: nearby is a candidate, not an assignment

This exercise designs a dispatch service for a hypothetical city. H3 is an open-source spatial index originally developed at Uber; its documentation explains a hierarchical global grid with hexagonal cells and pentagons. It does not prove that a particular Redis schema or trip-assignment protocol is Uber's current architecture. H3 documentation.

Separate fast-changing location from ownership

The location path accepts frequent approximate updates: driver ID, coordinates, observation time, sequence number, and location accuracy. The trip path decides whether a driver can accept a ride. A stale map dot is tolerable for a short period; two active trips for the same driver violate a business invariant.

Assume 30,000 active drivers reporting every three seconds. That is 10,000 updates per second on average. At an assumed 200 bytes per stored event, raw historical ingestion is about 2 MB/s or 172.8 GB/day before compression, indexes, and replication. Keeping only the latest location has a different storage profile from retaining every event.

Start with one city's measured traffic and retention needs. Spatially indexed SQL, an in-memory index, or a dedicated geo service can all be candidates. A latitude/longitude query does not inherently require a full scan when a suitable spatial index exists.

Search cells, then calculate the route

Map each fresh driver location into a cell. For a pickup point, search its cell and neighboring cells until enough candidates are found or a maximum radius is reached. Deduplicate drivers returned from overlap while updates move between cells.

The visualization illustrates spatial grouping; it is not evidence of a company's deployment. In real geographic grids, boundary behavior matters. Nearby positions can have different prefixes, and H3 cells do not have perfectly uniform geometry everywhere. Never rely on prefix similarity alone as a distance test.

Filter candidates by freshness, availability, vehicle requirements, and pickup constraints. Then compute road-network ETAs for a bounded shortlist. A driver 300 meters away across a river may be slower than one a kilometer away on the correct road. Sending every driver's position to a routing API wastes both time and quota.

Staleness is per driver

If Redis is used, GEOADD updates members in a geospatial sorted set. Expiring the entire key expires the entire set; it does not give each driver an independent timeout. Keep a last-seen record or time-ordered index, filter stale members on reads, and remove them in a cleanup job. Redis's command documentation describes the underlying sorted-set behavior. Redis GEOADD.

Reject older sequence numbers from the same device session so delayed packets cannot move a driver backward. Reconnection needs a new session identity or a controlled reset rule. Location freshness should use trusted server receipt time plus validated observation time; a device clock alone is not reliable.

If a driver crosses a cell boundary, update old and new membership with a defined ordering. Brief duplicate membership is usually safer than temporary disappearance, provided reads deduplicate and consult the latest location record.

Two riders request the same driver

Riders A and B both receive driver D in their candidate list. The assignment service attempts a conditional transition from available to offered, storing an offer token and expiry in the authoritative driver record. Only one succeeds.

An acceptance must contain that token. When an offer expires, a later offer receives a newer version. A delayed acceptance for the old offer is rejected even if the old process resumes. A cache lock by itself cannot enforce this after lease expiry; the final assignment checks the current version.

Commit the accepted driver and trip relationship together where possible, with uniqueness constraints on active assignments. If services use separate stores, represent the workflow as explicit pending states with retries and reconciliation. The rider must see “finding a driver” until the assignment is actually established.

Matching has a product objective

Nearest-driver-first minimizes a local distance, not necessarily fleet-wide wait time. Consider two riders: A can use drivers X or Y, while B can reasonably use only X. Assigning X to A first can leave B waiting despite Y being idle. Small batch matching can improve allocation, at the cost of waiting briefly to assemble the batch.

Choose the objective—pickup time, fairness, acceptance probability, or some constrained combination—and measure its consequences. Do not label a heuristic “optimal” without specifying the problem it optimizes.

Test stale GPS, out-of-order updates, a cell-boundary crossing, simultaneous offers, and an acceptance arriving after expiry. Track pickup ETA error, location age, rejected stale offers, unmatched requests, and duplicate active assignments. These metrics connect the map, the dispatch algorithm, and the ownership invariant.