Design a Ride-Sharing Service (Uber)

The canonical "moving objects" system

Ride-sharing is the canonical "moving objects" system. The defining property is that hundreds of thousands of drivers each emit a location update every 4 to 5 seconds, and riders ask "who is near me right now" against that constantly-changing set. Both the write rate and the spatial query are the hard parts, and a naive SELECT ... WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? full scan collapses immediately: a bounding-box scan over millions of rows with no spatial index is O(n) per query, and you have thousands of queries per second.

The spatial index

The fix maps 2D coordinates to a 1D sortable key so "nearby" becomes a range or key lookup:

• Geohash: interleaves lat/lng bits into a base-32 string; a shared prefix means spatial proximity. Simple and stringy, but has edge effects (two close points can straddle a cell boundary and share no prefix), so you always query the cell plus its 8 neighbors.
• Quadtree: recursively splits space into 4 quadrants, adapting depth to density. Great for skewed distributions (dense downtown, empty suburbs) but is a tree you must maintain in memory.
• S2 (Google) and H3 (Uber): project onto a space-filling curve (S2 uses a Hilbert curve on a sphere; H3 uses hexagons). Hexagons matter because every neighbor is equidistant, which makes "expand the search ring" uniform. Uber built and open-sourced H3 for exactly this.

Writes as overwrites, sharded by geography

For writes, the trick is to not treat driver locations as durable database rows. Locations are ephemeral: you only ever care about the latest one. Keep the live index in memory (Redis geospatial commands, or a sharded in-memory service) and treat the write as an overwrite, not an append. Shard the index by geography (city or region), because a rider in Chicago never needs a driver in Miami. Regional sharding keeps each shard's write volume and index size bounded and lets you scale cities independently.

driver app --loc every 4s--> location ingest --> in-memory geo index (Redis/H3), sharded by city
rider request --> matching engine --> query index (cell + neighbor ring) --> rank candidates --> offer --> trip FSM

Dispatch, matching, and the trip FSM

The dispatch/matching engine does candidate generation (query the rider's H3 cell and its neighbor rings until it has enough drivers), then ranks by ETA (not raw distance, because a driver across a river is far by road), driver acceptance likelihood, and supply-demand balance. Surge is a pricing signal computed per cell from the ratio of open requests to available drivers. Once a driver accepts, a trip state machine (requested -> accepted -> arrived -> in-progress -> completed) becomes the source of truth, and this part does need durable, strongly consistent storage because it maps to money.

Interview nuance: the assignment must be exclusive. If you offer the same driver to two riders you double-book. Use a short lock or conditional write on the driver's state so only one match wins, and expire the offer if the driver does not accept in a few seconds so the driver returns to the pool. And hot cities (New Year's Eve downtown) concentrate load on one shard: degrade gracefully by lowering location-update frequency (QoS) and widening the matching radius under load rather than dropping updates blindly.

Recap: index moving drivers with a space-filling spatial index (H3/S2/geohash) sharded by geography, keep locations in memory as overwrites, and rank matches by ETA under an exclusive-assignment lock, with the trip state machine as the one strongly consistent part.