Engineering Atlas › System Design Interviews

Design a ride-hailing app

18 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional:

Non-functional:

Out of scope: surge pricing models, ETA and routing engines (treated as services), fraud, driver onboarding, pooled rides, and food delivery.

Back-of-envelope

Use round planning numbers rather than Uber's published figures: 5 million drivers online at peak worldwide and 30 million trips per day.

Location updates: each online driver's app sends a position every 4 seconds. 5M / 4 = 1.25 million updates per second at peak. Each update is about 100 bytes on the wire after framing (driver ID, lat, lng, heading, speed, timestamp, status), so ingress is about 125 MB/s, or roughly 1 Gbit/s. That is modest bandwidth but a very high message rate, so per-message CPU matters more than bytes.

Trip requests: 30M per day / 86,400 is about 350 per second on average. Rush hour and weekend nights concentrate demand, so plan for 5x peaks, about 1,750 requests per second, plus 10x that in "show nearby cars" map queries from riders with the app open: say 20,000 nearest-driver queries per second.

Index memory: 5M drivers x about 64 bytes per entry (ID, coordinates, cell, status, timestamp) is 320 MB. The whole live index fits in memory on a single machine; we shard it for throughput and fault isolation, not for capacity.

Location history (for trip receipts, disputes and analytics): 1.25M updates per second x 100 bytes x 86,400 seconds is about 10.8 TB per day if everything is kept. Keep only on-trip points at full resolution and downsample the rest: perhaps 2 to 3 TB per day, roughly 1 PB per year, and 5 PB over five years in compressed columnar storage. These are rough, and compression ratios on GPS tracks can be large.

Trips: 30M per day x about 2 KB per trip record = 60 GB per day, around 110 TB over five years. Small compared to location data, but it is the data that must never be lost.

API

// Driver app, over a persistent connection (WebSocket or gRPC stream)
DriverUpdate { driver_id, lat, lng, heading, speed, status, client_ts }
<- OfferTrip { trip_id, pickup, dropoff_hint, expires_at }
-> RespondOffer { trip_id, accept: bool }

// Rider app
POST /v1/trips        body: { pickup, dropoff, product, idempotency_key }
  -> 202 { trip_id, state: "MATCHING" }
GET  /v1/nearby?lat&lng&product -> { drivers: [ { id, lat, lng, heading } ] }
<- TripEvent { trip_id, state, driver_location, eta } (pushed)
POST /v1/trips/{id}/cancel -> 200 { state }

Data model

High-level design

flowchart LR
  D["Driver app"] --> GW["Connection gateway"]
  R["Rider app"] --> API["API gateway"]
  GW --> LOC["Location service"]
  LOC --> IDX["Geo index shards"]
  LOC --> LOG["Location log"]
  LOG --> HIST["History store"]
  API --> TRIP["Trip service"]
  TRIP --> TDB["Trips DB"]
  TRIP --> DISP["Dispatch"]
  DISP --> IDX
  DISP --> ETA["ETA service"]
  DISP --> GW
  TRIP --> PAY["Payments"]
  GW --> R

Write path for locations: the driver app keeps one long-lived connection to a gateway node. Each update goes to the location service, which validates it (drops out-of-order or impossible jumps), routes it to the index shard that owns the driver's new cell, and, if the cell changed, removes the driver from the old cell's set. The same update is appended asynchronously to a location log for history and analytics; that path can lag or drop without affecting matching.

Read path for a trip request: the trip service creates a trip in MATCHING with the rider's idempotency key, then asks dispatch for a driver. Dispatch queries the index shard for the pickup cell and its neighbours, gets the K nearest available drivers by straight-line distance, re-ranks the top few by road ETA from the ETA service, and attempts to hold the best one with a conditional update on driver_state (available to offered). If the hold succeeds, it sends an offer over the driver's connection with a 10 to 15 second expiry. Accept moves the trip to DRIVER_ASSIGNED and the driver to on_trip; decline or timeout releases the hold and dispatch tries the next candidate.

Deep dives

The spatial index: geohash, quadtree or hexagons

A geohash interleaves latitude and longitude bits into a string, so nearby points usually share a prefix. It is easy to compute and store, but cells near a boundary can be close in space and far apart in prefix, so you always search the cell plus its 8 neighbours. A quadtree adapts to density (split a node when it holds too many drivers), which is attractive for cities with a dense core, but every split and merge under a 1.25M-per-second update stream is coordination you have to get right. A hexagonal grid such as Uber's open-source H3 gives cells whose neighbours are all at the same distance from the centre, which makes ring searches and surge zones cleaner, at the cost of a less familiar library. H3 has 16 resolutions, each cell about one seventh the area of its parent, but a hexagon cannot be split exactly into seven smaller hexagons, so a child is only approximately inside its parent (Uber Engineering, 2018). Rolling cells up to a coarser level is therefore lossy in a way geohash and S2 prefixes are not.

This is not hypothetical history. Uber's dispatch system as described in 2015 sharded its supply index on Google S2 level-12 cells (roughly 3.3 to 6.4 km² each), wrote each driver location to its cell's shard plus a few replicas, and answered a pickup query by computing the cells that cover a circle around the rider (High Scalability, from Uber's talk).

The choice for the interview: a fixed-resolution grid of cells (geohash or H3) with ring expansion. Pick a cell size of roughly 1 to 2 km so a typical query touches the centre cell plus one ring (H3 resolution 8 averages 0.74 km² with edges of about 0.53 km; resolution 7 averages 5.2 km² (H3 cell statistics)), and expand rings outward until K drivers are found and the next ring is provably farther than the K-th result. Dense areas are handled by using a finer resolution there, not by dynamic tree splits.

Matching without double dispatch

Two riders a block apart can both see the same nearest driver. If two dispatch workers each send that driver an offer, one rider gets a phantom match. The fix is that every offer is preceded by an atomic hold on the driver's state: UPDATE driver_state SET status='offered', trip_id=? WHERE driver_id=? AND status='available', or the in-memory equivalent on the shard that owns the driver. Only the winner sends the offer. Holds carry an expiry so a crashed dispatcher does not strand a driver. Expiry creates its own race: a dispatcher that stalls past the deadline (a GC pause, a slow network) may still send its offer after another worker has re-held the driver. Give every hold a monotonically increasing version and make the accept path check it, the fencing-token idea (Kleppmann), so a stale offer cannot be accepted.

An alternative is to route all dispatch for a geographic region to a single-threaded owner (one actor per city or per cell group), which serialises decisions without locks and lets you do batch matching: collect requests for one or two seconds and solve a small assignment problem that minimises total pickup time rather than greedily serving each rider. Batching gives better global outcomes in dense areas at the cost of a short wait. A staff answer mentions both and picks per-region serialisation with a short batching window in busy cities and greedy matching elsewhere.

Ingesting 1.25 million updates per second

The update path must be cheap per message. Keep connections on gateway nodes that only frame and forward, batch updates per destination shard every few hundred milliseconds, and make the index update an in-memory hash-set move. Drop stale updates by comparing client_ts to the stored timestamp, since mobile networks reorder and replay. Expire drivers whose last update is older than a TTL (say 30 seconds) so a phone that lost signal does not keep receiving offers. Persistence of the live index is unnecessary: on shard restart, drivers repopulate it within one update interval. Uber's driver apps send a location every 4 seconds, and the geo index was designed for about a million writes per second (High Scalability). Shard ownership among index nodes can be handled with a gossip-based consistent-hash ring; Uber's open-source Ringpop was first used for exactly this geospatial service (Uber Engineering, 2016).

Down the stack

Layer 1The contract

A nearest-driver query returns up to K available drivers within radius R, each with a position no older than the TTL, sorted by distance, in a few milliseconds of server time. It may miss a driver who moved in the last few seconds. A hold on a driver is linearizable per driver: at most one active offer exists for a driver at any time. Trip state transitions are durable and ordered; a client retrying a request with the same idempotency key gets the same trip.

Layer 2The mechanism

Each shard holds a hash map from cell ID to a set of driver IDs and a second map from driver ID to its record. An update computes the new cell (a few floating-point operations and bit interleaving for a geohash, or the H3 index function), compares it with the stored cell, and does at most one set removal and one insertion. A query computes the centre cell, iterates ring by ring, computes exact distances (haversine, or planar distance in a local projection) for drivers in those cells, and keeps the best K in a bounded max-heap. Termination uses the rule that every cell in ring r+1 is at least r cell widths from the query point. Offers and holds are a small state machine per driver: available, offered (with deadline), on_trip, offline.

Layer 3The machine

A driver update is about 100 bytes, which fits in a single TCP segment and a single TLS record. At 1.25M messages per second, the cost is dominated by syscalls and wake-ups, so gateways read many messages per epoll_wait cycle and batch forwards. An index entry of 64 bytes is one CPU cache line; a ring-1 query on a 1 km cell in a dense city might touch a few hundred entries, which is tens of microseconds of CPU, mostly cache misses at around 100 ns each. Long-lived mobile connections cost memory per socket (kernel buffers of tens of KB), so a gateway holding 500,000 connections needs tens of GB just for socket state, which is why buffer sizes are tuned down. For scale, Uber's push platform (RAMEN) started on Server-Sent Events with acknowledgements and retries layered on top, peaked at over 70,000 messages a second on its first generation, and after a rebuild held more than 1.5 million concurrent connections and pushed over 250,000 messages a second, with a bidirectional gRPC protocol in beta (Uber Engineering, 2020). Cellular round trips are 50 to 300 ms and radios sleep between sends, so the 4-second interval is a battery trade-off, not a server one.

Why it's built this way

  • Positions change every few seconds, so durable storage of the live index is wasted work; keep it in memory and rebuild from the stream.
  • Queries start from a location, so shard and key by location cell, not driver ID.
  • Drivers cluster in city centres, so cell size and shard ownership must follow density, not area.
  • Two riders can race for one driver, so offers require an atomic per-driver hold.
  • Mobile networks are slow and lossy, so use persistent connections, sequence numbers and TTL expiry instead of request-per-update.

Failure modes

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Fixed grid or geohashSimple, cheap updates, easy shardingBoundary effects, uneven densityDefault for live driver index
QuadtreeAdapts to densitySplit/merge churn under heavy writesMostly static points of interest
H3 hexagonsUniform neighbour distance, good for zonesLibrary dependency, less familiarSurge zones, analytics, ring search
Greedy nearest matchLowest latency, simpleGlobally suboptimal in dense areasSparse markets
Batched assignmentBetter total pickup timeAdds 1 to 2 s wait, more computeDense city centres at peak

Leadership lens

Check yourself

  1. Two riders a block apart both see the same nearest driver. How does the design stop that driver from being dispatched twice?

    Show answer

    Every offer is preceded by an atomic hold, a conditional update that moves driver_state from available to offered only if it is still available, so only the winner sends an offer. Holds carry an expiry so a crashed dispatcher does not strand the driver.

  2. With 5M drivers online, why is the live driver index sharded at all, and why is it not persisted?

    Show answer

    At about 64 bytes per entry it is only 320 MB and fits on one machine, so it is sharded for throughput (1.25M updates a second) and fault isolation, not capacity. Positions change every few seconds, so on a shard restart drivers repopulate it within one update interval and durable storage would be wasted work.

  3. When would you choose batched assignment over greedy nearest matching?

    Show answer

    In dense city centres at peak, where collecting requests for one or two seconds and solving a small assignment problem minimises total pickup time. Greedy matching has the lowest latency and suits sparse markets, while batching adds a 1 to 2 second wait and more compute.

  4. Why does the design use a fixed-resolution grid with ring expansion instead of a quadtree for the live driver index?

    Show answer

    A quadtree adapts to density, but every split and merge under a 1.25M-per-second update stream is coordination that has to be right. A fixed grid keeps each update a cheap in-memory set move, and dense areas are handled by a finer resolution rather than dynamic tree splits.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →