Uber / Ride Dispatch

Requirements

The approach

Ingest locations via WS/queue into a geo-indexed store (geohash/QuadTree/H3 cells) with a hot cache; a ride request queries the rider's cell + neighbors; matching runs async via workers.

Key components

Driver app → ingestion (WS/queue) → geo store + cache · matching workers · trip service

Numbers that matter

• Millions of location pings/sec — drivers report every few seconds; this write volume, not the matching, is the real scaling challenge.
• Don't durably store every ping — keep only the latest location per driver in a hot store (Redis); historical tracks, if needed, go to a separate async pipeline.
• Match target <1s — so matching reads a small set (the rider's cell + neighbors), never a global scan; the geo index turns O(drivers) into O(cell).
• Cell size is a tuning knob — too big scans too many drivers, too small queries too many neighbor cells; pick it for your local driver density.

Senior deep-dive

Nearest-neighbor at scale needs spatial indexing — you must scan one geo cell, not the planet.

Index locations with geohash / QuadTree / H3 so a ride request queries the rider's cell plus its neighbors; cell-boundary cases (a driver just across the line) are why you always check neighbor cells.

Location writes dwarf reads — keep them in a fast, possibly-lossy hot store, not a durable DB.

Spatial indexing turns the planet into a cell

Scanning every driver is O(drivers) — impossible at scale. Geohash, QuadTree, or H3 bucket the map into cells, so you fetch just the rider's cell. Hierarchical indexes (H3) let you widen the radius by stepping up a level when a cell is sparse. This trick is the core of the question.

Always query neighbor cells

A driver 200m away but just across a cell boundary is missed by a single-cell lookup. Query the rider's cell plus adjacent cells and rank by true distance. Hex grids (H3) make neighbors uniform — every cell has six equidistant neighbors, unlike square grids.

Writes dwarf reads — design for the firehose

Location updates (millions/sec) vastly outnumber ride requests. Ingest via WebSocket/queue into an in-memory geo store keyed by cell, keeping only the latest position per driver. It is fine for this store to be lossy — a one-ping-stale location is acceptable; durability here would crush throughput.

Matching is async and stateful

A request queries nearby drivers, then matching workers score and assign (ETA, rating, surge, heading) off the request path. The trip lifecycle — requested → matched → en route → complete — is a state machine in a durable store, kept separate from the volatile location data.

Surge and supply/demand

Surge is computed per cell from the local supply/demand ratio — a streaming aggregation over the same geo grid. It both rations scarce drivers and pulls supply toward demand. Compute it per cell on a short interval, not globally.

What breaks at scale

Bottlenecks are location-write throughput, hot cells (downtown at rush hour), and match latency under contention (two riders, one nearby driver). Shard by cell, keep the geo store in memory, and resolve the double-assignment race with an atomic claim. Storage is trivial; the write firehose and geo queries are the hard parts.

In production

Uber built H3 (a hexagonal hierarchical geo-index) for exactly this; Lyft and DoorDash solve the same nearest-driver problem with geohash/QuadTree variants. The shared shape: ingest a firehose of locations into a sharded in-memory geo store, query a few cells on demand, run matching asynchronously. Dispatch is a geo-indexing + write-throughput problem.

Common mistakes

• Scanning all drivers per request
• Storing every ping durably (write overload)
• Ignoring cell-boundary neighbors

Related System Design Library