Design Uber: Dispatch, Spatial Indexing, and Real-Time Location

"Design Uber" looks like a maps problem and is really a matching problem under a clock. Five million drivers report their location every few seconds, riders expect a car assigned in under a second, and the one thing that must never happen is two riders being sent the same driver.

The reward is separating the fast, ephemeral world — driver locations, worthless three seconds later — from the durable, transactional world where a paid trip must be recorded correctly. Those two halves want opposite datastores, consistency guarantees, and failure policies. Walk the standard rubric — requirements, capacity, architecture, deep dives — and the non-obvious calls fall out naturally.

What does Uber actually have to do?#

Strip the app down to the operations a client can request:

• Track drivers. A driver's phone streams its location every ~4 seconds.
• Match a rider to a driver. Given a pickup point, find nearby available drivers, rank by ETA, and offer the trip to the best one.
• Run the trip lifecycle. Request through pickup, ride, drop-off, and payment — surviving crashes at every step.
• Price the trip. Compute a fare including surge, and freeze a quote the rider can trust.

The non-functional bounds make this interview-worthy: matching must return in well under a second, a driver must never be double-offered, location data can be lossy and eventually consistent while trip and payment data cannot lose a single write, and it all must absorb a location-update firehose without touching a relational database.

Capacity estimation: the firehose vs the trickle#

Assume 5M active drivers globally, each pinging every 4 seconds, plus 50 major cities generating ~100 rider-dispatch requests per second each — two workloads that size completely differently.

Each ping carries driver_id, lat, lng, heading, speed, and a timestamp — roughly 200 bytes. The global aggregate looks scary, but it shards cleanly: a dense city like San Francisco has maybe 20K drivers, only ~5K pings/sec, trivial for a single in-memory node.

The asymmetry drives everything. Location is enormous but throwaway — a dropped ping self-heals in 4 seconds. Dispatch, at ~5K requests/sec, is two orders of magnitude smaller but must be correct every time. The bottleneck is ingress bandwidth, not compute.

Spatial indexing: geohash vs quadtree vs H3#

"Find drivers near this point" is a geospatial range query, and the index choice is the classic Uber follow-up.

Geohash's fatal flaw: a driver 10 meters from a rider can land in a cell whose prefix looks nothing like the rider's, so a naive prefix scan misses them. Uber built H3 because hex cells have uniform distance to every neighbor while keeping geohash's flat, shardable addressing. A "nearby" query becomes expanding outward in concentric H3 rings from the pickup cell until there are enough candidates.

High-level architecture#

Two loops run at different tempos behind an API gateway:

The location loop is high-volume and best-effort; the trip loop is low-volume and transactional. They're decoupled on purpose — a spike in location pings must never slow a payment capture, and a slow payment gateway must never stall the location index.

Ingesting the location firehose without a database#

Each driver's phone holds open a long-lived connection — a WebSocket or gRPC stream — to a location service in its region, which keeps that driver's current position in memory only, sharded by driver_id with consistent hashing so the mapping stays stable as nodes come and go.

The current location never touches a persistent database — it's ephemeral, the driver republishes in 4 seconds anyway, and a relational write per ping at 1.25M/sec would melt any cluster. Instead pings flow through Kafka into a streaming job that updates the H3 index, while historical trails batch into columnar blob storage (Parquet) for analytics and fraud review. Heartbeats catch staleness: a shard that hasn't heard from a driver in time marks them offline so the matcher never offers a trip to a dead phone.

Dispatch: never offer one driver to two riders#

This is the correctness core. The matcher queries candidate drivers in concentric H3 rings, scores each by ETA plus driver preferences, and picks the best. The danger: two matchers, serving two different riders, both pick the same idle driver at once.

The fix: a driver's availability lives as a single entry in a per-driver KV store, and a matcher must win an atomic compare-and-set against it before sending an offer:

Only one matcher's CAS succeeds; the loser sees the state already flipped and moves to its next candidate. The winner's offer carries a short TTL (~10 seconds); acceptance advances state to assigned, while a decline or timeout flips it back for the next-best candidate.

Sharding the dispatcher by geographic region keeps contention low — two riders in different cities never touch the same driver keys, so the CAS almost always succeeds on the first try. At the ~5K dispatches/sec computed above, each CAS is a single in-memory operation, not a distributed transaction.

Deep dives: ETA, surge, and trip integrity#

Two-stage ETA under 100ms#

Running a full routing engine for every candidate is far too slow, so the trick is two stages. First, a cheap filter: Haversine (straight-line) distance adjusted by a per-region factor trained on historical trip data, split out by hour-of-day and H3 cell pair — an O(1) estimate under 1ms, cheap enough to score all ~50 candidates in a ring. Then, only for the top handful of finalists, a true routing call (OSRM or Valhalla) at ~10–30ms each decides the displayed ETA; the heuristic only ranks candidates. Models retrain nightly on real trip data.

Surge pricing that doesn't oscillate#

A Flink job consumes ride-request and driver-supply events, computing a demand/supply ratio per H3 cell over a rolling 1–5 minute window. Feeding that raw ratio straight into a price would flap the multiplier between 1.0x and 1.5x every minute, so two safeguards intervene: the ratio is smoothed with an EWMA (exponentially weighted moving average) and mapped to a multiplier through a step function with hysteresis, so price only moves when demand crosses a real threshold. The result lands in a surge KV store keyed by (cell, minute). A rider's quote freezes the multiplier in the trip object for ~2 minutes, so they're charged what they were shown even if surge shifts mid-booking.

Trip lifecycle that survives crashes#

Taking payment but never recording the ride is the nightmare outcome, so the trip is a finite state machine — requested → offered → accepted → in_progress → completed → paid — persisted in a strongly-consistent store (Spanner, CockroachDB, or MySQL with Raft). Transitions run through an idempotent saga: each step (reserve payment, dispatch driver, start ride, capture payment) is a durable activity with its own retry and compensation handler, and idempotency keys on every external call keep effects exactly-once so a retried capture never double-charges. A background job checks for trips stuck mid-transition and forces them to a clean end state — pushing them forward or unwinding them through those handlers.

How this shows up in interviews#

Interviewers use Uber to see whether you keep the ephemeral and durable worlds separate. The strongest signals: refusing to write location pings to a database and explaining why in-memory plus Kafka is correct; naming an atomic CAS as the answer to double-dispatch instead of hand-waving "the matcher picks one"; and an honest account of the geohash boundary problem when justifying H3. Common traps: a relational row-per-ping, surge as a raw ratio with no smoothing, and a trip modeled as a single mutable row instead of an idempotent state machine. If time is short, spend it on dispatch correctness and location ingestion — that's where the non-obvious decisions live.

Uber shares DNA with other real-time and geospatial designs: the routing side compares to Design Google Maps, the read/write contrast to Design Netflix and Design Spotify, and the persistent-connection fan-out to Design Discord.

Further learning#

• Design Uber w/ Ex-Meta Staff Engineer — Hello Interview's end-to-end walkthrough of matching, spatial indexing, and trip state, a strong companion to the rubric above.
• Practice this topic on YeetCode — step through the requirements, capacity math, and deep dives interactively.

FAQ#

Why does Uber use H3 instead of a geohash for finding nearby drivers?#

Geohash encodes location as a prefix string, which shards easily, but has a boundary problem: two points a few meters apart can fall into cells with completely different prefixes, so a prefix scan misses them. H3 is a hexagonal grid where every cell has uniform distance to its neighbors, removing that discontinuity while keeping geohash's flat, shardable addressing. A nearby-drivers query becomes expanding outward in concentric hex rings from the pickup cell.

How does dispatch avoid offering the same driver to two riders?#

Each driver's availability is a single key in a KV store. Before making an offer, a matcher must win an atomic compare-and-set against that key — flipping it from available to offered:riderX — and only the winner proceeds; every other matcher sees the state already changed and moves on. Offers carry a ~10-second TTL, so a declined or timed-out offer reverts the key and the next-best candidate is tried. Sharding the dispatcher by region keeps two matchers from contending on the same key.

How does surge pricing stay stable instead of flickering every minute?#

The demand/supply ratio per H3 cell is never fed straight into the price — it's smoothed with an exponentially weighted moving average and mapped through a step function with hysteresis, so price only moves when demand crosses a genuine threshold. When a rider requests a quote, that multiplier is frozen into the trip for about two minutes, so the fare shown is the fare charged even if surge shifts during booking.

How is a trip kept consistent if the system crashes mid-ride?#

The trip is a finite state machine — requested, offered, accepted, in progress, completed, paid — stored in a strongly-consistent database. Each transition runs as a step in an idempotent saga (reserve payment, dispatch, start ride, capture payment) with its own retry and compensation logic, and idempotency keys on every external call guarantee a retried payment never double-charges. A background job checks for trips stuck between states and pushes them to completion or unwinds them.