Design ride matching

Ride matching inverts the read/write ratio that almost every other design in this course assumes. A million drivers publishing their position every four seconds produce 250,000 writes per second; the riders those positions exist to serve produce a few hundred requests per second. Every decision below falls out of that inversion and out of one question the writes make expensive: given a point, find the nearby drivers — when no ordinary index can answer a two-dimensional range query.

Step 1 — Requirements

In scope:

• A driver publishes location continuously while online.
• A rider requests a ride from a pickup point.
• The system matches that request to one nearby available driver.
• Both sides track the trip until it completes.

Out of scope: pricing and surge, payments, and the internals of routing and ETA. Routing is a service we call and treat as a black box that returns travel time for a pair of points.

Non-functional targets, stated as numbers rather than adjectives, in the habit from gathering requirements:

• A match decision within 5 seconds of the request, p99. The rider is staring at a spinner.
• Driver position no more than 8 seconds stale when it enters a candidate set: one ping interval plus propagation.
• One driver is never assigned to two rides. This is the only hard correctness constraint in the system.

Those last two point in opposite directions, and saying so early is worth marks. When a partition occurs, the location index stays available and serves possibly-stale positions — a driver who was at that corner 10 seconds ago is still a useful candidate. The ride-state store makes the opposite choice: it refuses the write rather than risk a double assignment. PACELC covers the rest of the time, when there is no partition: location reads take latency over consistency, ride-state reads take consistency over latency. The consistency models lesson has the full framing.

Step 2 — Estimates

Assume 1M drivers online at peak and 20M completed rides per day.

Driver pings. This is the number that defines the system.

1,000,000 drivers ÷ 4 s per ping = 250,000 writes/second
250,000 × 86,400 s             ≈ 21.6 billion location writes/day

Rider requests.

20,000,000 rides/day ÷ 86,400 s ≈ 230 requests/second average
peak at 3×                      ≈ 700 requests/second

The ratio is 250,000 : 230, or roughly 1,000 writes for every read. Most systems in this course run the other way — a feed or a shortener is read-heavy by 100:1 — and that matters because the standard answer to read pressure does not apply. You cannot cache a value that is invalidated every 4 seconds; the cache would miss on essentially every lookup and add a round trip for the privilege.

Payload and storage.

driver id 8 B + lat 8 + lon 8 + timestamp 8 + heading/speed 8 = 40 bytes
with framing and headers, ~100 bytes on the wire
21.6B pings × 100 B ≈ 2.2 TB/day of raw location payload

Persist that as rows and it is worse: at roughly 200 bytes with row headers and index entries, 4.3 TB/day and 1.6 PB/year, to store data whose value expires in seconds.

The relational sanity check. A commodity Postgres box handles about 5,000 simple QPS.

250,000 QPS ÷ 5,000 QPS per box = 50 boxes

Fifty machines doing nothing but updating one hot table, before any query runs. And these are not cheap appends: each update writes a WAL record, rewrites index entries on every indexed column, and leaves a dead row version behind — 21.6 billion of them a day for autovacuum to clean up. The conclusion is not "shard it". The conclusion is that current driver position does not belong in a relational database at all. Work that arithmetic out loud; it is the fastest way to justify the architecture that follows. The method is in back-of-the-envelope estimation.

Step 3 — Why the obvious query cannot work

The query everyone writes first:

SELECT driver_id FROM drivers
WHERE status = 'available'
  AND lat BETWEEN 12.90 AND 13.00
  AND lon BETWEEN 77.55 AND 77.65;

Add CREATE INDEX ON drivers (lat, lon) and it looks solved. It is not, and the reason is structural rather than a tuning problem.

A B-tree indexes one ordered sequence of keys. A composite index on (lat, lon) sorts by latitude first and only breaks ties by longitude. The latitude predicate is therefore a real range seek; the longitude predicate is applied afterwards, to whatever that seek returned. It filters, it does not seek.

Put numbers on the waste. A 0.1° latitude band is about 11 km tall and wraps the entire planet, roughly 40,000 km wide. The seek narrows the search to 1 of 1,800 latitude bands (180° ÷ 0.1°). The query actually wants 1 of 1,800 × 3,600 = 6.5 million cells. So the index does 1/1,800 of the elimination and leaves the scan to discard the other 3,600× by hand. Swapping the column order moves the problem to the other axis. Two separate single-column indexes are worse — the planner either picks one, or bitmap-ANDs two enormous row sets.

R-tree indexes (PostGIS GiST) genuinely index two dimensions and are the correct answer for spatial data that mostly sits still. They are the wrong answer here for the reason the estimate already exposed: an R-tree rebalances on insert, and at 250,000 moving points per second the rebalancing, not the query, is the bottleneck.

The fix is to stop trying to index two dimensions. Reduce 2D to 1D, then use the ordinary structures that are excellent at one dimension.

Geohash

Interleave the bits of longitude and latitude into a single number, then base32-encode it. Each character carries 5 bits, alternating between the axes: longitude, latitude, longitude, and so on. Read it as recursive halving — the first bit answers "east or west half of the world", the second "north or south half", and each pair of bits quarters the remaining box.

Length	Bits	Cell size near the equator
4	20	39 km × 20 km
5	25	4.9 km × 4.9 km
6	30	1.2 km × 0.6 km
7	35	153 m × 153 m

Derive one to show the mechanism rather than the table: at length 6 there are 30 bits, 15 to each axis. Longitude spans 360°, so a cell is 360 ÷ 32,768 = 0.011° ≈ 1.22 km wide. Latitude spans 180°, so 180 ÷ 32,768 = 0.0055° ≈ 0.61 km tall.

The property that earns the technique its place: two nearby points usually share a long prefix, so a proximity query becomes a prefix match, and a prefix match on a sorted string is exactly what a B-tree does well. WHERE geohash LIKE 'tdr1v%' is an O(log N) seek followed by a sequential read of contiguous entries — the access pattern the two-dimensional version could never produce.

In practice you do better than scanning. Bucket by cell instead: a set per cell, cell:tdr1v holding driver ids, so a lookup is a single hash operation with no scan at all. Redis does this natively — GEOADD stores a 52-bit geohash integer as a sorted-set score and GEOSEARCH performs the neighbour expansion internally.

Precision is chosen against density, not fixed. Take a city with 50,000 online drivers spread over 1,500 km², about 33 drivers per km². A precision-6 cell is 0.72 km², so roughly 24 drivers per cell, and a 3×3 block of cells yields about 220 candidates — a good working size. Precision 5 in the same city gives 24 km² cells, about 800 drivers each and 7,200 per block, far more than any ranker needs. A sparse suburb wants the opposite adjustment.

Quadtrees

A quadtree performs the same recursive quartering, but adaptively: a node splits only when it exceeds a bucket capacity, say 100 drivers. Downtown ends up fourteen levels deep, a rural highway six. Every leaf then holds a bounded number of points, so query cost is bounded regardless of how skewed the density is — precisely the property a fixed geohash grid lacks.

The cost lands on writes. A driver crossing a boundary is a delete from one leaf and an insert into another, and a leaf that overflows or empties triggers a split or merge that must be coordinated with every concurrent reader. The tree is one shared mutable structure. At 250,000 moves per second, restructuring is the expensive part, and it needs locking that a grid never does: a geohash cell key is pure arithmetic on the coordinates, and moving a driver touches two independent keys with nothing in between.

So: quadtree when the data is skewed and reads dominate; geohash grid when writes dominate. Here writes dominate by 1,000:1, and the grid wins on the axis that matters.

H3 and S2

Two production variants worth naming.

H3 (Uber) tiles with hexagons. On a square grid the four edge-neighbours sit one cell-width away while the four corner-neighbours sit 1.41× farther, so "expand the search by one ring" grows the area unevenly. A hexagon's six neighbours are all equidistant, which makes ring expansion behave like a widening circle. Hexagons cannot tile a sphere perfectly — H3 carries twelve pentagons — but they were placed over ocean.

S2 (Google) projects the sphere onto the six faces of a cube and runs a Hilbert curve over each face, yielding 64-bit cell ids. The Hilbert curve preserves locality better than the Z-order curve geohash uses, and the cube projection keeps cell areas far more uniform than a lat/lon grid, where a geohash cell at 60° latitude is half the width of one at the equator.

Both are libraries: coordinates in, cell id out. Name them in an interview, but the mechanism to explain is still 2D to 1D.

The boundary problem

Prefix similarity is a heuristic, not a guarantee. Two drivers 50 metres apart on opposite sides of a cell edge get different cell ids, and if that edge sits high in the recursion their ids differ in the first character. The pathological cases sit on the meridians and parallels where the Z-order curve jumps. A rider standing 30 m from a cell boundary, served by a single-cell query, would never be shown the driver parked across the street.

The fix is unglamorous and universal: query the cell plus its eight neighbours. Neighbour computation is arithmetic on the cell — decode, step, re-encode — and every library exposes it (geohash_neighbors, H3's k_ring, S2CellId neighbours). Nine hash lookups against nine independent keys issue in parallel and cost one 0.5 ms datacenter round trip in total.

Then always re-filter exactly. A 9-cell block is a rectangle, not a circle: it over-covers the corners and returns drivers up to 1.5 cell-widths away. Take the ~220 candidates and compute a real haversine distance on each, in the application process, in memory — 220 distance computations is microseconds of arithmetic. The index's job is reducing a million to a few hundred. Exact geometry finishes the job.

Step 4 — The write path

Ride matching: the driver location write path and the rider dispatch path100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

The location gateway holds one persistent connection per driver — a WebSocket or a long-lived gRPC stream, never a fresh HTTPS request every four seconds. A TCP plus TLS handshake per ping would add two round trips of latency and multiply CPU cost by an order of magnitude for a 100-byte payload. One million concurrent connections at roughly 10,000 per node is about 100 gateway nodes.

Little's Law sizes the gateway: 250,000 pings/second × 1 ms of handling = 250 updates in flight. That is comfortable — and it stays at 1 ms only because the write is in memory. A single 10 ms disk seek in that path turns 250 concurrent into 2,500 and the gateway falls over.

The ping fans out to two destinations, split by durability:

Current position goes to the in-memory geo index, and that is the only copy matching ever reads. One write, ~100 ns of real work, dominated by the 0.5 ms round trip. Prefer the single-sorted-set form (GEOADD region driver_id lon lat) over hand-rolled per-cell sets: overwriting a member's score is one idempotent operation, whereas per-cell sets require knowing the driver's previous cell to remove them from it, which makes the update two operations with a window between them. The index is disposable — lose the whole thing and every driver repopulates it within 4 seconds. That property is exactly what licenses keeping it in memory with modest persistence and no cross-region replication.

The historical trail goes to a queue, asynchronously and downsampled. Persisting 21.6 billion points a day to answer occasional questions is indefensible. Emit one point per 20 seconds — every fifth ping — and only for drivers on an active trip, which excludes the idle majority entirely:

20M trips/day, ~15 min each = 900 s per trip
900 s ÷ 20 s                = 45 points per trip
45 points × 16 bytes        ≈ 720 B, call it 1 KB per trip with a header
20M trips × 1 KB            = 20 GB/day

2.2 TB/day of pings becomes 20 GB/day of trails, a 100× reduction, and none of it touches the matching path. The queue is at-least-once, so duplicate points are guaranteed; the writer keys each point on (trip_id, sequence) and overwrites, which is the at-least-once implies duplicates implies idempotency-required chain from message queues.

Matching

Dispatch: read nearby cells, claim one driver with a TTL, offer, and handle the answer100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Dispatch, on a rider request: resolve the pickup point to a precision-6 cell; read that cell plus its eight neighbours for ~220 driver ids and positions, one 0.5 ms round trip; drop drivers already on a trip (an availability flag inside the index beats a second lookup); compute exact haversine and drop anything past the radius; then rank.

Rank on travel time, not straight-line distance. A driver 400 m away across a river is twelve minutes out; a driver 1.5 km away on the same road is four. Send the top twenty by straight-line distance to the routing service and rank on what comes back. The geo index produces candidates; it does not produce a decision.

The offer lock

Two riders 200 m apart request at the same instant. Both dispatch workers read the same nine cells, both see driver D at the top of their ranking, both offer. D accepts one; the other rider waits on a driver who is already gone.

Pessimistic locking — take a lock on every candidate before ranking — serialises dispatch and locks 220 drivers in order to use one. Optimistic is the right shape here: let a driver appear in as many candidate lists as they like, and resolve the conflict with a single conditional write at the moment of the offer.

SET lock:driver:<driver_id> <ride_id> NX EX 15

NX succeeds only if no lock exists, which is the compare-and-set. Exactly one worker gets OK; the loser gets nil and moves to its next candidate in the same millisecond, having wasted no round trip.

EX 15 is not decoration. A lock without expiry means a crashed dispatch worker, a dropped connection, or a driver whose phone dies removes that driver from the marketplace permanently — and manual intervention is the only way back. The TTL bounds the damage to one offer window. It also introduces the classic hazard: if the offer overruns 15 seconds, the lock expires, a second ride claims the driver, and the first worker's release then deletes a lock it no longer owns. Release must be a compare-and-delete — delete only if the value is still my ride id — which is the fencing argument in the locking lesson.

Decline and timeout are the same code path: compare-and-delete the lock, record (ride_id, driver_id) in a declined set so the driver is not re-offered this ride, offer to the next candidate. Bound the loop at five candidates or 60 seconds. Then widen the search ring one level and retry; if that fails too, tell the rider no driver is available rather than leaving the request pending forever. Every retry is another opportunity to double-book, which is why the conditional claim — not the loop — is the correctness mechanism.

Idempotency

Duplicates arrive from three directions: the rider double-taps, the mobile client retries a request whose response was lost on a flaky network, and the dispatch job is redelivered by an at-least-once queue. Any one of them creates two rides and locks two drivers for one rider.

The client generates a UUID per request attempt and sends it as Idempotency-Key. Dispatch stores the mapping from key to ride id with a conditional insert; a repeat with the same key returns the existing ride rather than creating another. The key must survive the client's retry — regenerate it on retry and the whole mechanism is decorative. Idempotency covers the general pattern.

Ride state is where consistency beats availability. Acceptance is a single-row conditional update — accept only if the state is still offered — in a store that refuses the write during a partition rather than accepting both sides. Location can be stale. Assignment cannot be double.

Trip tracking

After acceptance the ride moves through accepted → arriving → in_progress → completed, and the driver is removed from the available index. Their pings continue, now also forwarded to the rider's connection so the map moves; that is a fan-out of one, not a broadcast, so it costs nothing structural. On completion the driver is re-added at their current position and the trail buffer flushes to the queue.

Trade-offs

Dimension	B-tree on (lat, lon)	Geohash grid in memory	Quadtree	H3 / S2
Query cost	Scans a full latitude band; ~3,600× over-read	9 hash lookups, ~220 candidates	Bounded by bucket capacity	9–19 cell lookups
Write cost at 250k/s	~50 Postgres boxes plus index and vacuum churn	One in-memory overwrite per ping	Splits and merges under a lock	One overwrite per ping
Handles density skew	No	No — precision tuned per region	Yes, adaptively	Partly; resolution chosen per region
Neighbour expansion	Not applicable	8 neighbours; corners 1.41× farther	Tree walk across parents	H3: 6 equidistant. S2: Hilbert locality
Durability posture	Full ACID, none of it needed	Disposable, rebuilt in 4 s	Disposable	Disposable
Effort	Trivial to write, does not scale	A library plus ~50 lines	Real code, real concurrency control	Import a library

Note that ACID's C and CAP's C are unrelated here, and the row above trades on the first: the relational option offers transactional invariants we do not need for a value overwritten every four seconds. The invariant we do need — one driver, one ride — is enforced by a conditional write in the lock store, not by the location table. Choosing the store per workload rather than per system is the SQL versus NoSQL decision made properly.

In an interview

What is being tested is whether you recognise a spatial-index problem and whether you notice the read/write inversion. Most candidates arrive with read-heavy reflexes — add a cache, add read replicas, shard by user — and none of that helps when writes outnumber reads 1,000 to 1.

Say it in this order:

1. Lead with the arithmetic. "One million drivers at one ping per four seconds is 250,000 writes a second, against roughly 230 ride requests a second. This is write-heavy by three orders of magnitude." That single sentence reframes the whole problem and it takes ten seconds.
2. Kill the naive query explicitly. Write the BETWEEN clause, then explain that a B-tree seeks on latitude and merely filters on longitude, so the scan reads a band that circles the planet.
3. Reduce 2D to 1D. Geohash as interleaved bits and recursive quartering; prefix match as proximity query.
4. Raise the boundary problem before you are asked, and give the nine-cell fix plus the exact haversine re-filter.
5. Handle dispatch: optimistic claim with NX, a TTL sized to the offer window, compare-and-delete on release, and an idempotency key on the request.
6. State that the geo index is in memory and disposable, and that the trail is downsampled and written asynchronously.

The mistakes that lose points:

• Putting driver location in Postgres with an index on (lat, lon). It is the single most common answer and it is the thing the question exists to catch.
• Saying "geohash" without saying why. Naming a technique is recall. Deriving the prefix property from interleaved bits is understanding, and the interviewer can tell within one sentence which one you have.
• Ignoring the boundary problem. A design that queries one cell has a bug demonstrable with two drivers standing 50 m apart, and being shown it is much worse than raising it yourself.
• A lock with no expiry. It means a crashed worker permanently removes a driver from the marketplace.
• Ranking on straight-line distance and stopping there. Geometry is the filter; travel time is the ranking.
• Treating the geo index as a source of truth. Say out loud that it is disposable and rebuilds in four seconds — that is what licenses the entire in-memory design, and it is the same argument used for derived stores elsewhere in scaling.
• Calling this read-heavy. It announces that you did not do the arithmetic.

If pressed on precision, do not defend a constant: "I would start at 6 in dense cities and 5 in sparse regions, watch the candidate count per query, and target roughly 200. Precision is a knob against local density, not a global setting."

Check yourself

1. A festival puts 4,000 online drivers into one square kilometre for six hours. At precision 6, what does the nine-cell query return, and what do you change?

A 3×3 block of precision-6 cells covers 3.6 km × 1.8 km = 6.5 km², so it contains the entire crowd: the query returns roughly 4,000 candidates instead of the normal ~220. That is an 18× increase in bytes moved and haversine computations per request, arriving at exactly the moment request volume also spikes. Widening the ring makes it worse; the fix is to go deeper. Precision 7 cells are 153 m × 153 m = 0.023 km², so at 4,000 drivers/km² each holds about 93, and a nine-cell block covers 0.21 km² for roughly 840 candidates. Add a per-cell read cap — stop after 50 — and the candidate set is bounded at ~450 regardless of density. The general lesson is that precision must be selected per query from a rolling density estimate, not fixed at deploy time.

2. Rider requests peak at 700/second and a dispatch decision takes 800 ms of compute and network. Size the concurrency. Now assume the first offered driver lets the 15-second window time out. What changes, and what does that force in the design?

concurrency = arrival rate × latency. At peak, 700/s × 0.8 s = 560 concurrent dispatches — trivial for a stateless pool. The number that matters is the one with a human in it: a 15-second offer window makes each attempt 700/s × 15 s = 10,500 outstanding offers, and three sequential attempts pushes the tail past 45 seconds. Ten thousand five hundred held threads and connections exhausts any pool, so dispatch cannot be a blocking request. It must be a state machine: persist the offer, schedule a 15-second timer as a delayed message, and let any worker pick it up on expiry. The server holds a row, not a connection, and the rider's client waits on its own WebSocket. This is the general shape of every design where latency is set by a person rather than a machine.

3. Product asks to replay any driver's exact path over the last 30 days for dispute resolution. Decide what you store and defend the cost.

Full fidelity is 21.6B pings/day × 100 B ≈ 2.2 TB/day, so 66 TB for 30 days before replication — to serve a query run a few thousand times a day. The 20-second downsample is 20 GB/day, 600 GB for 30 days, and reconstructs a path well enough to answer "did the driver take the long route" but not "which lane was the driver in". Size the actual need: if disputes touch 0.1% of 20M trips, that is 20,000 trips a day. So keep the downsampled trail for everyone for 30 days at 600 GB, and hold the full-rate stream in a rolling 24-hour buffer costing 2.2 TB — long enough for a dispute raised the same day to promote its trip to permanent full-fidelity storage. You pay full fidelity for 0.1% of trips and one-hundredth the storage for the other 99.9%, and the decision is defensible because both numbers were derived rather than asserted.