Designing Uber — Geospatial Matching, Traced
Real-time matching over a moving map
Uber must match a rider to nearby drivers in well under a second, while millions of drivers stream location updates. A naive "compute distance to every driver" is O(drivers) per request — hopeless. The key is a spatial index: geohashing / quadtrees turn "near me" into a cheap cell lookup.
Traced: a driver location update (write-heavy)
- Driver app sends GPS every few seconds.
- Compute the driver's geohash cell; write to a geo index (Redis GEO, or a geohash → driver-set bucket). High write rate — this is the demanding path.
- Old location expires (TTL) so stale drivers drop out.
Traced: a rider requests a ride
- Compute the rider's geohash cell.
- Query that cell + its 8 neighbours for candidate drivers — the neighbours matter because a driver one metre away can be just across a cell boundary (the boundary problem from Geohashing & Quadtrees).
- Rank candidates by ETA (road distance, not straight line), offer to the nearest; on decline, offer the next.
- On accept, atomically assign the driver so two riders can't grab the same one (a lost-update race — lock/CAS the driver's status).
Pitfalls
- Hot cells (downtown at rush hour) overload one shard — use finer cells where dense, or a quadtree that subdivides by density.
- Stale locations → offers to drivers who left; enforce TTL + heartbeats.
- Dispatch race: the accept step must be atomic, or two riders double-book a driver.
Takeaways
- Spatial index (geohash/quadtree) makes "nearest drivers" a cell + neighbours lookup, not a full scan.
- Writes (locations) dominate; reads query cell+8; assignment must be atomic.
- Hot cells and stale data are the real-world failure modes.
Re-authored for this guide; geohash-grid diagram hand-authored as SVG. See also: Geohashing & Quadtrees, Caching, Replication. (Complements the existing "Designing Uber" problem page with a traced flow.)
🔨 Practice this hands-on — Design Uber / Ride-Sharing →
Attempt it from an empty file, break it to feel the failure, then defend it under pushback.
🤖 Don't fully get this? Learn it with Claude
Stuck on Designing Uber — Geospatial Matching, Traced? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
🎨 Explain it visually
Build the mental picture, not memorization.
I just read a lesson on **Designing Uber — Geospatial Matching, Traced** (System Design) and want to truly understand it. Explain Designing Uber — Geospatial Matching, Traced 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.
🤔 Walk me through it (interactive)
Socratic — adapts to where you're stuck.
Teach me **Designing Uber — Geospatial Matching, Traced** 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 & fix my gaps
Active recall exposes what you missed.
Quiz me on **Designing Uber — Geospatial Matching, Traced** 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.
🧠 Make it stick
Intuition + hook + flashcards for long-term memory.
Help me remember **Designing Uber — Geospatial Matching, Traced** 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.