Code10x
Scale & cachingSenior

Ride matching, where the data is a moving map

Most of the writes in this system are positions that are out of date four seconds later. Treating them like database records is the first mistake and the most expensive one.

The brief

Drivers' apps report their position continuously. A rider requests a ride, and the system offers it to a nearby available driver.

A driver must never be assigned two rides at once, and a rider must not wait long for an answer.

Requirements

Functional

  • Accept frequent location updates from available drivers
  • Find available drivers near a pickup point
  • Offer a ride to a driver, who accepts or declines within a short time
  • Track the trip once matched

Non-functional

  • A driver is assigned at most one ride — the one correctness rule in the matching path
  • A position a few seconds old is acceptable; a match that takes a minute is not
  • Location data is personal data and is kept no longer than needed

Back-of-envelope

Assume

  • 500,000 drivers online at peak across all cities
  • Each sends a position every 4 seconds
  • 50,000 ride requests a minute at peak
  • A driver has 15 seconds to accept an offer; about 30% of offers are declined or time out

Therefore

  • Location writes: 500,000 / 4 = 125,000 a second. That is the dominant load, and every one of those values is superseded within 4 seconds.
  • Kept in a disk-backed database with history, that is ≈10.8 billion rows a day of mostly useless data. Kept as 'latest position per driver' in memory, it is 500,000 entries, overwritten in place.
  • Ride requests: 50,000 a minute ≈ 830 a second, each needing one nearby-driver query. The read path is 150 times smaller than the write path.
  • With a 15-second offer window and a 30% decline rate, a rider whose first two offers fail waits 30 seconds or more before a third driver is even asked. The offer timeout, not the query, dominates time-to-match.

Halve the reporting interval and the write load doubles while the position error only halves — at typical city speeds, a car moves roughly 40 metres in 4 seconds. The interval is a cost-versus-accuracy dial, worth setting on purpose.

The interface

POST /drivers/me/location { lat, lng, heading, at } → 204 (or a stream over a persistent connection)Fire-and-forget. A lost update is replaced 4 seconds later, so it is never retried; retrying stale positions only delivers them out of order.
POST /rides { pickup, dropoff } → 202 { rideId, status: SEARCHING }202, because matching takes seconds and involves a human accepting. The rider's app follows status changes rather than holding a request open.
POST /offers/{offerId}/accept → 200 { rideId } | 409 offer no longer valid409 covers the case where the offer expired, or where the driver accepted another ride on a second device a moment earlier. The accept is the moment the one-ride rule is enforced.

What is stored

live positions (in memory, per city)geospatial index: driverId → (lat, lng), plus driverId → { status, updatedAt }
The query is 'available drivers within radius r of a point', answered from a geospatial index — geohash cells or a sorted-set geo structure. updatedAt lets the query ignore drivers whose app went silent a minute ago.
driversdriver_id · status (OFFLINE | AVAILABLE | OFFERED | ON_TRIP) · current_ride_id · version
Status changes are conditional updates — AVAILABLE → OFFERED only if still AVAILABLE — which is what makes double assignment impossible even when two matchers pick the same driver.
tripsride_id · rider_id · driver_id · state · route samples (downsampled)
The durable record of what happened, for fares and disputes. The route is stored downsampled after the trip rather than as every 4-second ping.

The design

Location ingestAccepts position updates over persistent connections and writes them to the in-memory geospatial index for the driver's city. It does not touch the relational database.
The matcherFor a request, queries nearby available drivers, ranks them by estimated time to pickup rather than straight-line distance, and offers the ride to the best one.
The offer managerMoves the driver to OFFERED with a conditional update, starts the acceptance timer, and on decline or timeout returns the driver to AVAILABLE and asks the matcher for the next candidate.
Trip trackingOnce matched, positions for that driver are also sent to the rider's app and sampled into the trip record.

The decisions

Each of these could go the other way. The choice, the reason, and what it costs — a design that lists only what it chose teaches the choice; one that lists what it gave up teaches the judgement.

Offer to one driver at a time, or to several at once?Chose — One at a time, with a short timeoutBecause — Offering to several and taking the first acceptance means every other driver who tapped accept is told no, repeatedly, and learns to distrust offers. Sequential offers keep an offer meaningful.Time-to-match grows with every decline, as the estimate shows. Shorter timeouts help riders and pressure drivers, and that trade-off is felt by both sides of the market.
Where do live positions live?Chose — In memory, latest value only, partitioned by cityBecause — The value of a position expires in seconds, and the only query is spatial and local. A durable store would spend most of its capacity persisting data nobody reads.A node failure loses current positions for its city. They are rebuilt within one reporting interval as apps report again, but matching in that city is blind for those seconds.
Search a radius around the pickup, or the cells that cover it?Chose — The pickup's cell plus its neighbours, widening if too few driversBecause — Grid cells make the lookup a key read. Searching only the pickup's own cell misses a driver 50 metres away across a cell boundary — the neighbours are what make the grid correct.Cell size is a fixed choice that suits dense centres or sparse suburbs, not both, and widening the search in a sparse area costs extra queries exactly where there are fewest drivers.

What breaks first

In order. Each names what you would actually observe, and each fix carries its cost.

Hot cellsSymptom — At an airport or after a stadium event, one cell holds hundreds of drivers and receives thousands of requests; queries on that shard slow while the rest of the city is idle.Fix — Smaller cells in dense areas, or a dedicated pickup queue for known hotspots where drivers wait in order.Variable cell sizes complicate neighbour lookup, and a hotspot queue is a separate product with its own fairness rules.
Location ingestSymptom — Ingest CPU and network saturate at peak while the matcher is comfortable; positions start arriving late, and matched drivers appear further away than they are.Fix — Adaptive reporting: less often when the driver is stationary or on a trip far from any pickup, more often near a pickup.More logic in the driver app, and position accuracy that varies by situation — which must be accounted for in time-to-pickup estimates.
DeclinesSymptom — Time-to-match rises with no rise in query latency; the offer manager's timeout counter is what moves.Fix — Rank candidates using their recent acceptance behaviour, not only distance.A ranking that learns from behaviour can quietly penalise drivers for reasons they cannot see, which is a fairness problem as much as a technical one.

When something fails

Two matchers pick the same driver at the same momentBoth attempt the AVAILABLE → OFFERED update; one affects a row and the other affects none. The loser moves to its next candidate. The rider never knows.
A driver's app goes silent mid-offerThe offer times out, the driver returns to AVAILABLE — and, because their position has stopped updating, the matcher's staleness filter keeps them out of future results until the app reports again.
The in-memory index for a city is lostMatching in that city returns no drivers until apps report again, a few seconds. Requests arriving in that window should wait and retry rather than be told no drivers are available.

Scaling it

Each step is triggered by a number, not a feeling — and carries what it costs.

10× drivers in one cityMove — Shard the city's index by cell ranges rather than one node per city.A search near a shard boundary must query two shards, and moving drivers cross shard boundaries continuously.
Hundreds of citiesMove — Nothing changes in the matching path: cities are independent, so each is its own partition.Rides that cross city boundaries, like airport runs, need a rule for which city owns them.
Shared ridesMove — Match a request against drivers already on a trip whose route passes nearby.The query is no longer 'available drivers near a point' but 'routes passing near two points in the right order' — a different and far more expensive search.

What gets probed

The design is the easy half. These are where the conversation goes, and each has a defensible answer above.

  • 125,000 location updates a second arrive. Where do they go, and why not the database?
  • Two riders' requests select the same driver. Show exactly what prevents a double assignment.
  • A driver is 50 metres from the pickup but in the next grid cell. Does your query find them?
  • Time-to-match has doubled, and query latency has not changed. Where do you look?