Design a ride-hailing dispatch system

"Design Uber/Lyft dispatch" is the case study that introduces geospatial systems, and it's worth doing precisely because the naive instincts from every other prompt fail here. This isn't read-heavy like a feed or a shortener; it's write-heavy in an unusual way, and its core query — "which drivers are near this rider?" — is one a normal B-tree index fundamentally cannot answer efficiently. Run it through the framework.

Requirements

Functional: drivers continuously report their location; a rider requests a ride from a pickup point; the system finds nearby available drivers and matches one; both sides track the trip in real time. Defer: pricing, routing/ETA, payments (that's the ledger).

Non-functional: very high write volume (every active driver pushes a location every few seconds), low-latency proximity search ("find drivers near this point" must return in milliseconds), real-time tracking (rider watches the driver approach), and geographic locality (a query in Mumbai shouldn't touch data in London). The write firehose and the proximity query are the two hard parts, and they pull in different directions.

Estimates

Say 1M drivers online, each sending a location update every 4 seconds → ~250,000 location writes per second. That's the number that dominates, and it's the opposite of the shortener: writes, not reads, are the firehose here. Ride requests are far rarer (thousands/sec at most). Storage of the current location is tiny (1M drivers × a few dozen bytes = megabytes — it fits in memory); it's the update rate, not the volume, that's the challenge. Immediately this says: the hot location data wants an in-memory, write-optimized store, not a disk-based relational table taking 250k writes/sec.

The core problem: "find drivers near me" is not a B-tree query

Here's why this prompt is special. You have driver locations as (latitude, longitude) pairs, and you need "all drivers within 2 km of this point." A B-tree index on latitude and one on longitude cannot answer this well: indexing each dimension separately lets you find drivers in a latitude band or a longitude band, but "near this point" is the intersection of two ranges in 2D, and B-trees index one ordered dimension at a time. You'd scan a huge band and filter — far too slow at this scale. Proximity in two dimensions needs a spatial index, and the whole design hinges on choosing one.

The trick every spatial index shares: map 2D space onto something 1-dimensional (or hierarchical) so that points close in space are close in the index.

• Geohash — encode a lat/long into a short string where shared prefixes mean spatial proximity (nearby points share a longer prefix). "Find drivers near me" becomes "find drivers whose geohash shares my prefix" — a prefix lookup, which a plain B-tree can do (prefixes are ordered ranges). Elegant because it reduces the 2D problem to the 1D string-prefix problem your existing tools already handle. (Edge case: points across a geohash boundary can be physically close but share no prefix, so you check neighboring cells too.)
• Quadtree — recursively subdivide space into four quadrants, deeper where drivers are denser. "Near me" walks down to the relevant leaf cells. Adapts to density (a busy downtown cell subdivides finely; empty countryside stays coarse).
• S2 / H3 cells — Google's S2 and Uber's own H3 map the globe to a hierarchy of cells with a single integer id per cell; "near me" is "these cell ids," a set of point lookups. (Uber built H3 for exactly this.)

Naming one — "I'd geohash driver locations so proximity becomes a prefix/cell lookup, checking neighboring cells at boundaries" — is the move that shows you know geospatial systems aren't just "index lat and long."

High-level design: split the write path from the match path

The write firehose and the proximity query want different stores, so you separate them:

• Location ingest (the 250k writes/sec path). Driver location updates go to an in-memory, spatially-indexed store — think Redis with geospatial commands (GEOADD/GEOSEARCH, which use geohashing internally), or a purpose-built in-memory service sharded by region. It holds only the current location per driver (overwrite, not append — you don't need every historical ping on the hot path), so it stays small and fast. This absorbs the firehose without touching the disk-based database.
• Matching (the rare, latency-critical path). A ride request hits the geospatial store with a proximity search ("available drivers in these cells near the pickup"), gets a candidate set, and runs the dispatch decision — pick the best driver by ETA, rating, direction, and fairness — then offers the ride (with a timeout; if declined, offer the next). This is a small, infrequent, but latency-sensitive operation on top of the fast index.
• Durable/trip state lives in the regular database: trips, driver profiles, history. The ephemeral high-write location goes to the in-memory store; the durable low-write trip data goes to Postgres. That split — ephemeral-fast-write vs durable-truth — is the same instinct as caching and the chat persist-then-deliver split, applied to location.

And regional sharding falls out of the "geographic locality" requirement: shard the location data by city/region so a Mumbai proximity search only touches Mumbai's shard — the shard key is geography itself, which is a naturally good shard key because queries are inherently local (you never match a Mumbai rider with a London driver).

Real-time tracking

Once matched, the rider watches the driver approach — which is the WebSocket / realtime problem from the chat design: the driver's location updates stream to the rider's app over a persistent connection, and the same persist-the-trip-state, stream-the-live-position split applies. Dispatch reuses the realtime machinery; it doesn't reinvent it.

Go deeper

• Uber Engineering — "H3: A Hexagonal Hierarchical Geospatial Indexing System" — Uber's own account of the geospatial index they built for exactly this dispatch problem — why cells, why hexagons, and how "near me" becomes a set of cell ids.
• Redis — geospatial indexing (GEOADD/GEOSEARCH) — The concrete in-memory store for the location firehose: geohash-backed proximity search commands that instantiate the "map 2D to a prefix" trick, ready to use.
• Proximity-service / "nearby" design walkthrough — A full worked design of the geospatial-search problem (geohash vs quadtree, cell sizing, boundary handling) that the dispatch design is built on.

Check yourself

Answer out loud, as if an interviewer asked. If you hand-wave, reread that section.

1. What is the dominant scaling number for ride dispatch, and why is this prompt write-heavy in an unusual way compared to a feed or a shortener?
2. Explain why two B-tree indexes (one on latitude, one on longitude) cannot efficiently answer "drivers within 2 km of this point," and the core trick every spatial index uses to fix it.
3. How does a geohash turn a 2D proximity query into something a plain B-tree can serve? What boundary edge case must you handle, and how?
4. Why must the 250k-writes/sec location firehose NOT go into your relational database? Where does current location belong, and what durable data still goes to Postgres?
5. Describe the double-dispatch race and the reserve-with-timeout fix. Which earlier concurrency pattern is it the same as?
6. Why is geography a naturally good shard key here, and how does Fable's location-sharing feature face the ingest half of this problem (but not the matching half)?