Ride matching - the nearest car is the wrong car

Two sides of a market that can both walk away, on a map, in real time. The design question underneath every requirement below is which geospatial index the matcher reads.

Ask these before designing

• Is this dispatch or is this a marketplace? If drivers can decline, matching produces offers and the assignment is provisional. If they cannot, it is allocation and the whole board simplifies. The answer changes the data model, not just a policy.
• What is the index actually for - radius queries or cell aggregates? "Drivers within 2 km" and "supply divided by demand in this cell" are different questions. The second is what drives pricing, and it is the one that makes hexagons worth the trouble.
• How stale may a driver position be at match time? 4 seconds is a smooth map and 150,000 writes/s. 10 seconds is 60,000 writes/s and a matcher that regularly offers a ride to a driver who has already turned off the road it assumed.
• May the rider be shown a car before a driver has accepted? If yes, the ETA is a promise made on somebody else’s behalf. If no, the rider stares at a spinner for eight seconds.
• Is the pickup ETA road-aware or straight-line? Straight-line is one multiplication. Road-aware is a routing call per candidate driver, which at 370 requests/s and 12 candidates each is 4,400 routing calls/s.
• What happens to a rider nobody accepts? Widen the ring, raise the fare, or fail honestly. All three ship; only one of them is usually designed.

Functional

• A rider requests a ride from a pickup point and is quoted a fare and an ETA.
• Drivers report position continuously while online and are indexed by H3 cell.
• The matcher assigns open requests to available drivers and offers each assignment to its driver.
• A driver accepts or declines; a declined or expired offer returns the request to the next batch.
• Exactly one driver is ever assigned to one request, and one driver to at most one request.
• Surge multiplier per cell, from the supply/demand ratio over a rolling window.
• Track the trip from acceptance to completion.

Non-functional

• Request to assignment p95 under 5 s end to end, of which the batch window is 2 s and is spent on purpose.
• No double assignment, ever. A driver claim is a compare-and-set, not an UPDATE. This is a correctness requirement and not a performance one.
• Cell aggregates fresh within 60 s. Surge computed on a stale ratio is a price charged for a shortage that has already ended.
• Matching availability 99.95%, degrading to greedy nearest-driver rather than failing.
• Location writes are lossy by design: a dropped ping costs 4 seconds of freshness for one driver and nothing else.
• Demand is not a curve but two spikes and a stadium: 08:00-09:30, 17:30-19:00, and an unpredictable third that is somebody’s concert ending.

Explicitly out of scope

Payments and driver payouts, identity and background checks, in-trip navigation (that is the routing board), ratings and disputes, pooled/shared rides - which changes matching from an assignment to a much harder routing problem.

From 12M rider DAU, 1.5M registered drivers and 8M completed rides/day. As in every board in this category, the ride rate is not the load - the moving dots are.

Requests

• 8,000,000 / 86,400 = 92.6 requests/s average
• Morning and evening peaks carry 35% of the day in 3 hours: 2,800,000 / 10,800 s = 259/s
• Friday 23:00 city peak, measured rather than derived: 370 requests/s
• Each request is retried into roughly 1.35 batches (declines and expiries), so the matcher sees 500 request-slots/s at peak

Driver location - the arithmetic that decides the architecture

• A device reporting every 4 seconds is 86,400 / 4 = 21,600 writes per device per day
• A driver is online about 8 h, so 7,200 writes/driver/day
• 1,500,000 drivers x 7,200 = 10.8 billion location writes/day
• At peak 600,000 drivers online: 600,000 / 4 = 150,000 writes/s
• That is 405x the peak request rate. The system is a location system that happens to dispatch cars.

What the matcher reads

• A batch runs every 2 s per active cell. At peak roughly 9,000 cells are active in the fleet
• Each batch reads its own cell and its 6-neighbour ring = 7 cell reads, plus one ring-2 expansion for sparse cells (18 more cells) in about 20% of batches
• 9,000 cells / 2 s x (7 + 0.2 x 18) = 47,700 cell reads/s
• Each read is one Redis sorted-set range: the index is the only thing standing between this and 150,000 rows scanned per batch

Surge aggregates

• Supply and demand counters per cell, 60-second tumbling window: 9,000 cells x 1 write/60 s = 150 writes/s. Trivial, and it is the number that sets the price.

Read : write ratio

• Writes: 10,800,000,000 pings + 8,000,000 rides x ~14 state and offer rows = 10.9 billion/day
• Reads: 47,700 cell reads/s x 86,400 = 4,120,000,000, plus rider polling 8,000,000 x 180 = 1,440,000,000 = 5.6 billion/day
• Read : write = 1 : 1.9 - write-heavy, and every bit of that is one number that changes four times a minute per car.

The location stream, which is 99% of the bytes and 0% of the durable data

• One ping: vehicle id 16 B + lat/lon 16 B + heading 2 B + speed 2 B + accuracy 2 B + timestamp 8 B + overhead ~12 B = 58 B
• 10,800,000,000 pings/day x 58 B = 626 GB/day if every point were written
• Live position is held, not stored. One key per online driver, overwritten: 600,000 x 120 B (position, H3 cell, state, vehicle) = 72 MB total, and it fits in a single Redis node with room left over.
• The durable track is downsampled to one point per 30 s before anything touches a disk: 626 GB / 7.5 = 83 GB/day, kept 90 days = 7.5 TB, for disputes and pickup-quality analysis only.

The transactional data

• ride_requests: 1 x 420 B (with the pickup/dropoff cells and the quoted fare)
• match_offers: 1.35 x 160 B = 216 B
• trips: 0.82 x 560 B = 459 B (18% of requests never become a trip)
• driver state transitions: 6 x 90 B = 540 B
• Total 1,635 B per request x 8,000,000 = 13.1 GB/day
• Indexes x1.7 = 22.3 GB/day = 8.1 TB/year, five years = 40.7 TB
• Requests older than 18 months go to columnar object storage at ~8x, so the live cluster stays near 12 TB

The index itself

• The H3 index is derived, not stored durably: cell id is a function of lat/lon, so the sorted sets are rebuilt from the next ping within one ping interval
• 9,000 active cells x ~70 drivers x 30 B = 19 MB. The entire geospatial index of a national fleet is smaller than one photograph.
• surge_cells: 9,000 rows, rewritten every 60 s, with a 24 h history for pricing audits: 9,000 x 1,440 x 60 B = 778 MB/day, kept 30 days = 23 GB

Five-year total

About 41 TB of rides and offers, 7.5 TB of rolling downsampled tracks, 23 GB x 12 of surge history, and 72 MB of live state. The part of this system that dispatch actually reasons about would fit on a phone.

Targets

• Ride request accepted: 99.95%
• Matching: 99.95%, degrading to greedy nearest-driver rather than failing
• Driver claim (the compare-and-set): 99.99% and failing closed - a claim that is not certain must be refused, because the failure mode is two riders in one car
• Live map: 99.9%, degrading to a static pickup pin and a text ETA
• Measured weighted by request volume, so an outage at 18:00 counts roughly 3x one at 04:00

Single points of failure, named

• The matcher for a city. It is stateful for two seconds at a time and deliberately single-writer per cell group: two matchers running the same cells would assign the same driver twice, which is worse than a two-second gap. Leader election per city, restart from open requests in about 8 s, and open requests simply wait one extra batch.
• The driver location cache. In-memory, unreplicated for writes, and not durable on purpose. Losing it loses at most 4 seconds of freshness per driver; the index refills from the next ping.
• The requests primary for a city shard. The claim is a compare-and-set, which needs one writer per driver row. Primary plus synchronous replica; failover RTO 30-40 s, during which new requests in that city are refused rather than matched optimistically.
• The H3 library version. A cell id is a pure function of a library, so an upgrade that changes a boundary re-partitions the index. Pinned, and rolled out by rebuilding the index rather than by deploying.

Replication and failover

• Requests, offers and trips: Postgres sharded by city, primary plus synchronous replica in a second AZ. The matcher never reads an async replica - a stale read here assigns a driver who is already on a trip.
• Location: Redis Cluster, sharded by H3 cell prefix so a cell and its neighbours land on few nodes, no persistence, replica for failover only.
• Trip events: 3x replicated, 7-day retention, partitioned by trip id.

What degrades rather than dies

• Assignment solver slow or down: fall back to greedy nearest-available-driver per request. Measurably worse pickup times at peak, no correctness loss, and it is the same code path the board describes as the wrong answer - kept precisely because it is a safe wrong answer.
• Ring-2 expansion too slow: stop expanding and fail sparse cells to "no cars available" rather than holding a rider for eleven seconds to find one 6 km away.
• Surge pipeline down: freeze the multiplier at its last value and stop it from rising. A frozen price is a business decision; a price computed from a stale ratio is a refund.
• Routing service down: pickup ETA falls back to straight-line distance x 1.4. Less accurate, and the matcher’s ranking changes slightly, which is acceptable for minutes.
• Offer push down: drivers poll every 3 s instead. Battery cost, no lost rides.

Every online driver’s phone sends a position every four seconds. The location gateway does one thing with it that matters: it computes the H3 cell at resolution 8 - a hexagon about 460 m across - and writes the driver into that cell’s sorted set, removing them from the previous one. Nothing here is persisted. A position that is worthless in four seconds does not deserve a disk, and the index is a pure function of the position, so it rebuilds itself continuously.

Why hexagons and not a geohash. A geohash is easier: it is a string, prefixes nest, and "nearby" is a prefix scan. But its cells are rectangles that get narrower as you go north, its eight neighbours sit at two different distances, and its boundaries fall wherever the binary interleave happens to put them. For a radius query none of that matters much. For this system it does, because the matcher’s primary question is not "who is within 2 km" but "what is the ratio of supply to demand in this cell compared with the six around it" - and that is a comparison between cells, which needs cells that are comparable. H3 hexagons have six neighbours all the same distance away and near-equal area within a region. S2 would be the other defensible answer, with better global area uniformity and a proper cell hierarchy; it loses on the ring being eight cells rather than six. PostGIS with a GiST index is the right answer for a system with a hundredth of this write rate, and the wrong one at 150,000 writes a second.

A rider requests a ride. The request service quotes a fare - base plus distance plus the current multiplier for the pickup cell - and writes the request as OPEN with its pickup cell. It does not look for a driver.

Instead, every two seconds a matcher wakes up per active cell and takes every open request in that cell together. It reads the cell and its six neighbours, and expands to a second ring only if the first one is thin. Then it scores each (request, driver) pair: pickup ETA, the driver’s direction of travel, how long the rider has waited, whether the driver is about to finish a trip nearby, and how scarce supply is in the cell the driver would be leaving. It solves the assignment over the whole batch.

This is the part worth arguing about. The reflex is to hand each rider the nearest car. Nearest by straight line is not nearest by road - a river is 200 m wide and 4 km around. Nearest now is not nearest in ninety seconds. And taking the only car in a cell to serve a rider 900 m away leaves the next request in that cell with nothing. Greedy dispatch is a local optimum that gets worse exactly when the system is busiest. A batch of two seconds is enough to turn a lookup into an assignment, and it costs every rider two seconds including the one at 03:00 who was the only request in the city.

The assignment is then claimed, one driver at a time: UPDATE drivers SET state = 'OFFERED' WHERE id = $1 AND state = 'AVAILABLE'. Batches run per cell and independently, so two adjacent batches can both see the same driver standing on their shared boundary, and exactly one of them may win. The loser’s request goes back into the next batch. Without that compare-and-set, one car is dispatched to two people and both of them are watching it on a map.

The winning driver gets an offer with a twelve-second expiry. Accept and the trip begins; decline or let it lapse and the request re-enters the next batch, with its waiting time now weighing more heavily in the score. Meanwhile counters per cell feed the supply/demand ratio that sets the multiplier, on a sixty-second window - which is why a stadium emptying registers as a shortage in one hexagon and nothing at all in the six around it.

Regions

• Sharded by city. A city is a closed marketplace: its riders, drivers and cells never interact with another city’s, which makes the shard key, the deploy unit and the blast radius the same thing.
• Three regions hosting city shards by geography; a city never spans regions.
• The location cache is regional and never cross-replicated. A driver in Lisbon is of no interest in Toronto.

What is stateful, and how it moves

• ride_requests / match_offers / trips (Postgres): expand-contract only. Offers and trips are append-mostly; the one hot mutable column is the driver state the claim writes.
• The matcher: stateful for the length of one batch. A deploy drains it - finish the current batch, stop taking new ones, restart, resume from OPEN requests. Disruption is one batch, 2 seconds, per cell group.
• The location cache (Redis): never migrated. Stand up an empty cluster, point the gateway at it, and it is complete within one ping interval - 4 seconds. The only stateful component here that genuinely needs no migration plan.
• The H3 index: derived, so it is not migrated either. A resolution change (8 to 9, say) is a config flag that is rolled forward by letting the new cells fill and the old ones expire; both are written for one ping interval during the flip.
• Surge windows: in-memory counters, rebuilt from the event stream in 60 s. A deploy loses at most one window, which freezes the multiplier rather than resetting it.

Rollout

1. Deploy by city, in local off-peak - 13:00 to 15:00 local. Because cities are independent this is a real blast-radius limit, not a percentage spread evenly over everybody.
2. Three smallest cities in a region first, soak 2 hours.
3. Gates: double assignments = 0 (this one is absolute), p95 request-to-assignment within 400 ms of baseline, offer acceptance rate within 2 points, unmatched-request rate within 1 point, surge multiplier distribution unchanged.
4. Then 10 cities, then the region, then the next region. Three days for a full rollout, and that is the intended speed.
5. Hard freeze Friday and Saturday evenings in any timezone the release touches, and around any event the demand forecaster has flagged.

Rollback

• Application: previous image per city in under 3 minutes.
• Matching policy - batch window, ring size, score weights, offer TTL - is runtime configuration. Retuning it is the first response to a supply incident and must never need a deploy. The greedy fallback is reachable by flipping one flag.
• Schema: expand-contract with tested down scripts.
• Not rollback-able: a trip that happened, a fare that was quoted at a multiplier the new code would not have produced, and a driver who declined an offer they should never have been sent. All three are handled forward - refund, adjustment, an apology in the driver app - and none of them is fixed by redeploying yesterday’s binary.