Design Uber / Ride-Sharing

Design Uber / Ride-Sharing

Why this one separates seniors from staff: the whiteboard-friendly answer — "store drivers in a table, find the nearest one, assign it" — hides two distinct systems fighting each other. One is a write firehose (millions of drivers streaming GPS every few seconds), the other is a latency-critical read + a correctness-critical claim (find nearby drivers in tens of milliseconds, then hand exactly one of them to exactly one rider). Get the geo-index wrong and location writes melt your database; get the dispatch wrong and you offer the same driver to two riders during surge. This lab makes you feel both failures, then build the design that survives New Year's Eve. It is the archetype for every "real-time matching over moving objects" question (food delivery, on-call routing, logistics).

Scope it like a senior (ask before you design)

Never start drawing boxes. A staff candidate spends the first two minutes pinning the problem down, because the answers change the architecture:

• Matching objective — nearest, or lowest-ETA, or global-optimal? "Nearest by straight-line distance" is a lie the instant a river or a one-way street exists. Real matching ranks by ETA (road-network travel time), and mature systems optimise fleet-wide (don't strand a driver who's better for the next request 200m away). Assume ETA-ranked, greedy per-request for v1; flag fleet-optimisation as the follow-up.
• How fresh must driver location be, and how often do drivers ping? Every 4–5s is typical. This single number sets the entire write load — it is the most important question you can ask.
• Matching-latency SLA? A rider staring at a spinner tolerates ~1–2s end to end, which means the nearby-driver lookup must be tens of ms. That rules out a scan.
• Scale? Assume ~5M concurrent drivers at peak, ~30M rides/day. We will derive the rest.
• Surge / hotspots? Demand is wildly non-uniform — a stadium letting out concentrates thousands of requests into a few cells. The design must survive geographic skew, not just aggregate load.

Reason to the design (derive it, don't recite it)

Attempt 1 — a drivers table, query on read. SELECT * FROM drivers WHERE status='available' ORDER BY dist(:lat,:lng, lat,lng) LIMIT 10. Two things kill it. First, that query cannot use an index — dist() is computed per row, so it is a full scan of millions of rows on every request. Second, and worse, each of 5M drivers is rewriting its (lat,lng) row every 4s — a relentless hot-row update storm that has nothing to do with matching and will saturate the database on its own.

Attempt 2 — add a spatial index (2D / R-tree / PostGIS). Now the read is fast. But the write firehose is untouched: a spatial index that must be re-balanced on 1M+ updates/s is more expensive to write, not less. We've optimised the 2,000-reads/s path and ignored the 1,250,000-writes/s path. Wrong bottleneck.

Attempt 3 — separate the two systems. The insight: location updates and matching want opposite things, so stop forcing them through one store.

• Geo-index in memory, keyed by cell. Divide the map into geohash / quadtree / S2 cells. The index is a map cellId → {driverIds}. A driver ping is an in-place update: remove from old cell, add to new cell — O(1), no disk, no lock, no index rebalance. A nearby query reads the rider's cell plus its 8 neighbours (a 3×3 block) and ranks that small candidate set. Both operations touch a handful of cells, never the whole map.
• Atomic dispatch as its own step. Ranking gives you candidates; claiming a driver must be atomic so the same driver is never handed to two riders. That is a compare-and-set on the driver's state, not a byproduct of the query.

The two cruxes — an in-memory moving-object geo-index and an atomic claim — are what the rest of the lab builds and defends.

Build it — the design worksheet

Functional: drivers publish location; riders request a ride; the system returns one matched driver quickly; a driver is offered to at most one rider at a time; handle decline/timeout by re-dispatch.
Non-functional: match latency < ~1s; location freshness ~5s; high availability (a region outage must not stop a neighbouring region); survive geographic skew.

Back-of-the-envelope (show the arithmetic):

• Location write load (the real driver of the design): 5M drivers ÷ 4s = 1.25M location writes/s average, call it ~2.5M/s at peak. A single durable DB node handles maybe 5–10K row-writes/s — you'd need ~250 nodes and they'd be rewriting the same hot rows. This number alone forces the in-memory grid.
• Match load: 30M rides/day ÷ 86,400 ≈ ~350 matches/s average, ~2,000/s at peak. Five orders of magnitude below the write load — confirming reads and writes must scale independently.
• Geo-index memory: 5M drivers × ~100 bytes (id + lat/lng + cell key + overhead) ≈ ~500 MB. Trivially fits in RAM on one machine; we shard by region anyway, for locality and blast-radius, not for capacity.
• Candidates per query: at geohash precision-6 (≈1.2km × 0.6km cells), a 3×3 block = 9 cells. A dense-city cell holds ~100 available drivers → ~900 candidates to rank by ETA — a tiny in-memory sort, not a table scan.

API sketch: updateLocation(driverId, lat, lng) (fire-and-forget, high volume); requestRide(riderId, lat, lng) → matchId; internally findCandidates(cell) → [driverId] and claim(driverId) → bool.

Data model / partitioning: the geo-index is sharded by region (e.g. top-level geohash prefix) so a city's drivers and the riders searching for them live on the same node — a nearby query never fans out across shards. Driver state (AVAILABLE / OFFERED / ON_TRIP) lives in a fast store (Redis or an in-memory partition) that supports the atomic claim. Trip history and billing go to a separate durable store off the hot path.

Break it — the naive design's three concrete failures

1. The location write storm (Attempt 1/2's silent killer). 5M drivers × a ping every 4s = 1.25M writes/s hammering one hot row each. Traced: even at a generous 10K writes/s per DB node, that's 125 nodes doing nothing but absorbing GPS, and every write invalidates a cache and (with a spatial index) triggers a rebalance. The fix is structural, not a bigger box: keep live location in an in-memory geo-index with in-place cell moves, batch/sample updates, and never put the ping on the durable write path.

2. The double-dispatch race. Two riders request simultaneously near the same idle driver. Both matchers run findCandidates, both see driver D as AVAILABLE, both offer D. Interleaving: R1 reads D=AVAILABLE → R2 reads D=AVAILABLE → R1 offers D → R2 offers D. Now one car, two riders. The fix is an atomic compare-and-set: UPDATE driver SET state=OFFERED WHERE id=D AND state=AVAILABLE — exactly one update returns "1 row changed"; the loser re-queries for the next-best driver. (This is the same shape as the dispatch double-booking race.)

3. The cell-boundary miss + stale location. The closest driver may sit just across a cell edge, so querying only the rider's cell misses them — hence the 3×3 neighbour scan. And a driver who pinged 30s ago may have moved a kilometre; matching on stale coordinates offers a car that's already gone. Fix: always scan neighbour cells, and treat location as soft state with a freshness TTL — drop or de-rank drivers whose last ping is too old.

Optimise — with trade-offs

Decision	Option A	Option B	When to pick which
Spatial index	Geohash (string prefix = cell; dead simple, range-scannable)	Quadtree / S2 / H3 (adaptive depth, no boundary distortion near poles, hex neighbours)	Geohash for a straightforward v1 and easy sharding by prefix; S2/H3 when you need uniform cell area globally or cleaner neighbour math. Both beat a uniform grid, which dies on density skew.
Location store	In-memory grid, update-in-place	Durable DB / spatial index	In-memory always, for live location — it's soft state you can rebuild from the next round of pings. Durable store only for trip records, never the ping firehose.
Dispatch concurrency	Optimistic CAS on driver state	Lock-based (distributed lock per driver)	Optimistic wins: contention on a single driver is rare, the loser just picks the next candidate, and there's no lock to leak on a crash. A distributed lock only earns its keep if a claim is expensive/multi-step.
Matching policy	Greedy nearest-ETA per request	Batched / fleet-optimal (hold a window, solve assignment)	Greedy for low latency and simplicity; batched when fleet efficiency matters (surge, pooling) and riders tolerate a few seconds — it's the assignment-optimisation upgrade.
Location update path	Every ping updates the index	Sample / batch / dead-reckon between pings	Update every ping at moderate scale; batch and interpolate at extreme scale to cut write amplification — you trade a little freshness for a lot of headroom.

Defend under pushback

"How do you prevent the same driver being matched to two riders?" An atomic compare-and-set on driver state: UPDATE driver SET state=OFFERED WHERE id=? AND state=AVAILABLE. Exactly one concurrent claim flips the row; every other claim sees 0 rows affected and moves to its next-best candidate. State lives in a single-writer-per-driver store (Redis / an in-memory partition), so the claim is a fast, linearizable operation. No lock to leak, no two-phase anything.

"How do you handle the location write storm?" Never put pings on the durable write path. Live location is soft state in an in-memory, region-sharded geo-index updated in place (remove-from-old-cell, add-to-new-cell). At extreme scale, sample/batch pings and dead-reckon between them. If the whole index is lost, it self-heals within one ping interval (~4s) as drivers report again — so we don't pay for durability we don't need.

"Straight-line distance is wrong — a driver across the river is 'near' but 20 minutes away." Correct — the geo-index only produces candidates cheaply. We then rank the ~900 candidates by true ETA from a road-network/ETA service. The grid narrows the set; the ETA model orders it.

"A stadium empties — 100× the requests, all in a few cells. What breaks first?" Not storage (500MB is nothing) and not aggregate compute — it's the hot region shard and contention on the few AVAILABLE drivers in those cells. Mitigations: split hot cells at finer geohash precision to spread them; scale the region's matcher independently; apply surge pricing (which is partly a load-shedding lever — it throttles demand to what supply can serve); and queue requests with a bounded wait rather than failing them.

"A matched driver declines or doesn't respond." The OFFERED state carries a short TTL. On decline or timeout, an expiry worker resets the driver to AVAILABLE and the matcher re-dispatches to the next candidate — the same claim protocol, so no double-offer even during re-dispatch.

"Two riders, and the only nearby driver just went ON_TRIP." The CAS naturally handles it: the claim's WHERE state=AVAILABLE fails, the rider falls through to the next candidate or widens the search radius (more neighbour cells). Freshness TTL plus the atomic guard mean we never match a car that isn't actually free.

What you've mastered when this is done

• Recognising a "real-time matching over moving objects" problem as two decoupled systems — a write firehose and a latency-critical read+claim — and refusing to force them through one store.
• Designing an in-memory, region-sharded geo-index (geohash/quadtree/S2) with in-place cell moves, and explaining why live location is soft state that needs no durability.
• Guaranteeing exactly-one dispatch with an optimistic compare-and-set on driver state, and defending it against the double-dispatch interleaving, declines, and TTL expiry.
• Reasoning about geographic skew (hot cells, surge) as the true scaling limit rather than aggregate throughput — and naming the levers (finer cells, independent region scaling, surge-as-load-shedding).

Related: Designing Uber (backend) · Uber geospatial matching, traced · the dispatch double-booking race · Geohashing & Quadtrees · Geospatial indexing (Geohash/S2/H3).

I just read a lesson on **Design Uber / Ride-Sharing** (Hands-On Builds) and want to truly understand it. Explain Design Uber / Ride-Sharing from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Design Uber / Ride-Sharing** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Design Uber / Ride-Sharing** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Design Uber / Ride-Sharing** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.