Location · Design 23

Design Uber

Design Uber in a 45-minute interview: location updates, geo indexes compared (geohash, quadtree, H3), matching, the trip state machine, hot cells, one driver per trip and surge.

AdvancedInterview priority: High65 min
On this page
  1. How to use this page
  2. 1. Clarify the requirements
  3. 2. Back-of-the-envelope estimates
  4. 3. API
  5. 4. Data model
  6. 5. High-level design
  7. 6. Deep dives
  8. 7. Bottlenecks, failures and monitoring
  9. 8. Follow-up questions
  10. Quiz

How to use this page

This page follows the order of a real system design interview. At each step there is a Your turn box: write your own answer first (it stays in your browser), then open ours and compare. Reading a finished design feels easy; producing one under time pressure is the skill you are practising.

PhaseTime in a 45-min interviewWhat you produce
1. Clarify requirements5 minFunctional list, non-functional targets, what's out of scope
2. Estimate5 minLocation updates/s, trips/s, memory for live positions
3. API5 minEstimate, request, location, accept, status, live tracking
4. Data model5 minLive locations vs trips vs history, and where each lives
5. High-level design10 minThe hot location path and the transactional trip path
6. Deep dives10–15 minGeo index, matching, one driver per trip, state machine, hot cells, surge
7. Wrap up2–3 minBottlenecks, failures, what you would monitor

Riders request a ride from A to B and see a price estimate. Nearby drivers get the offer; one accepts. Rider and driver see each other live on the map. At the end, the fare is calculated and charged. Skip pooling (shared rides), food delivery, driver onboarding and ratings.

1. Clarify the requirements

Your turn: scope it

The interviewer says: "Design Uber." Write down your questions, then 4–6 functional requirements, 4–5 non-functional requirements with targets, and what you'd leave out.

Compare with our answer

The questions that matter most: One ride type or pooling too? Do we quote a price before the ride? How fast must matching be? How many drivers are online at peak? Is payment in scope? Pooling is the one to push out: it turns matching into a route-planning problem.

A strong answer mentions: request with a price estimate · match a nearby driver · live tracking both ways · the trip lifecycle · automatic payment · strong consistency for assignment and money, freshness (not durability) for locations.

Functional: what it must do

  • Request a ride: Pickup and destination, price estimate first
  • Match a nearby driver: Offer to drivers; one accepts
  • Live tracking: Both see each other on the map
  • Trip lifecycle: Driver arrives, trip starts, trip ends
  • Fare and payment: Charged automatically at the end

Out of scope

Shared rides (pooling)Uber EatsDriver onboardingRatings

Non-functional: how well it must work

QualityTargetWhy
Matching latencyA driver offered in < 10 sRiders cancel if nothing happens
Location freshnessPositions no older than a few seconds
ConsistencyA driver can only accept one trip; a trip has one driverStrong consistency here
Availability99.99%People get stranded otherwise
Scale~2 M drivers online at peak; ~25 M trips a daySpiky: rush hour, concerts, rain

2. Back-of-the-envelope estimates

Your turn: the numbers

2 M drivers online at peak each send a ~100-byte position every 4 s. There are 25 M trips a day. Work out location updates per second, ingest bandwidth, memory for the latest positions, and trip requests per second.

Compare with our answer
  • Location updates: 2 M ÷ 4 s = 500 K/s. Ingest: 500 K × 100 B = 50 MB/s.
  • Latest positions: 2 M × 100 B = 200 MB, call it 400 MB with index overhead. Fits in memory on one machine; we shard for throughput and availability, not size.
  • Trips: 25 M ÷ 86,400 ≈ 300/s on average, perhaps 1,000–1,500/s at a Friday-night peak.
  • History, if kept: 500 K/s × 100 B × 86,400 s is about 4 TB/day at peak rate, roughly half that averaged over the day. Bulk storage, not the hot path.
  • How far a car moves between updates: at 50 km/h (14 m/s), 4 s ≈ 55 m. That's the accuracy budget, and why 4 s is a reasonable rate.

A strong answer mentions: 500 K writes/s as the biggest load · that the live set fits in memory · trips as a small, careful workload · the distance moved per update · peak factors.

Assumptions: drivers online at peak 2 M; seconds between location updates 4; trips per day 25 M; size of one location update 100 B.

NumberEstimateWhy it matters
Location updates per second500 K / s≈ 500 K/s: the biggest load in the system.
Location ingest bandwidth50 MB/s
Trip requests per second (avg)289 / s≈ 300/s average, several times more at peak.
Memory for latest positions400 MBTiny: the live index easily fits in memory.
Location history per day2.2 TBStored cheaply for trip receipts and analytics, not in the hot path.
  • Half a million location writes a second, but only the latest position per driver matters for matching: keep it in memory.
  • Trips are far fewer (hundreds a second) but each one must be handled carefully.

The key insight: 500 K writes a second of data that is stale in 4 seconds does not belong in a database. Write it to memory, overwrite in place, and stream a copy to cheap storage for history. The trip table sees a few hundred writes a second, which a sharded SQL database handles with ease, so it can afford strong consistency.

Choosing the update rate

The rate is a trade-off between freshness, battery, mobile data and server load. 4 s gives about 55 m of error in town, fine for matching. Real apps adapt: an idle driver parked in a lot can report every 10–15 s, a driver on a trip or approaching a pickup every 1–4 s, and the app sends immediately on a big heading change. Halving the interval doubles the 500 K/s firehose, so "every second for everyone" is an expensive answer.

3. API

Your turn: the API

List the calls for: getting a price, requesting a ride, a driver reporting location, a driver accepting, and moving the trip forward. Which ones must be idempotent, and which one can return "already taken"?

Compare with our answer

A strong answer mentions: an estimate that returns an ID and expiry so the price is locked · a request with an idempotency key · locations over a persistent connection or a cheap fire-and-forget call · accept returning 409 if someone else won · status transitions that name the state they expect · a WebSocket or push channel for live tracking.

CallRequestResponseNotes
POST /v1/estimates{ pickup, dropoff }{ fare, eta, surge }Price quote, valid for a few minutes
POST /v1/trips{ estimateId, pickup, dropoff }201 { tripId, status: "matching" }Idempotency-Key header so a double tap books once
POST /v1/drivers/me/location{ lat, lng, heading, ts }204Every 4 s (or over the driver’s WebSocket)
POST /v1/trips/{id}/accept–200 or 409 (already taken)Driver accepts an offer
POST /v1/trips/{id}/status{ status: arrived | started | completed }200Trip state machine transitions
WS /v1/trips/{id}/live–driver position, ETA, statusLive updates to the rider

The Idempotency-Key on POST /v1/trips means a rider who taps twice, or whose app retries after a timeout, gets the same trip back instead of booking two cars. The pattern is covered in depth in duplicates and idempotency.

4. Data model

Your turn: the tables

Where do the live driver positions go, where do trips go, and where does the full location history go? Pick a store for each and say why.

Compare with our answer

A strong answer mentions: live positions in an in-memory geo index keyed by cell, with a last-seen time · trips in a strongly consistent store with a status and version, sharded by city · drivers and riders in SQL with a cache · history appended to a stream and stored in a wide-column store or data lake.

live driver locations In-memory geospatial index (Redis GEO / H3 cells)

  • cell_id → set of driver_ids
  • driver_id → lat, lng, status, updated_at

Overwritten every few seconds; only “who is near here, right now?” matters.

trips Strongly consistent SQL (sharded by city)

  • trip_id, rider_id, driver_id
  • status: matching | accepted | arrived | started | completed | cancelled
  • pickup, dropoff, fare
  • version

Money and state transitions need transactions; conditional updates prevent double assignment.

drivers and riders SQL + cache

  • driver_id, vehicle, status
  • rider_id, payment_method_id

Profiles, vehicles, payment methods.

location history Wide-column / data lake

  • driver_id, ts, lat, lng

Route for receipts, disputes, ETA model training; written in bulk.

One detail interviewers probe: the live index needs two maps, cell → drivers (to search) and driver → cell, position, status (to know which cell to remove a driver from when they move). Every update is "remove from old cell if it changed, add to new cell, overwrite position". Entries that haven't been updated for, say, 30 seconds are treated as offline, which handles drivers whose phones die without saying goodbye.

5. High-level design

Your turn: draw it

Sketch two paths: how a driver's position reaches the index, and how a ride request becomes an assigned driver. Where are they connected?

Compare with our answer

Compare with the figure below. The pieces people forget: the stream that feeds history, ETAs and surge, the ETA service (matching needs road time, not distance), and the conditional update at the moment of acceptance.

The architecture, then drivers reporting their position

  1. The architecture splits the hot location path from the transactional trip path. Locations go to an in-memory geo index and a stream. Trips live in a strongly consistent database, and a matching service combines the geo index with ETA estimates to pick drivers. Pricing and payments sit on the trip path.
  2. Every driver’s phone sends its position every few seconds. The location service updates the in-memory geo index, which files each driver under a small map cell, and also streams positions to analytics and ETA models.
ComponentWhat it does
Location serviceIngests ~500 K updates/s; updates the geo index
Geo indexDrivers bucketed by map cell (geohash/H3), in memory
Matching / dispatchFinds candidates, ranks by ETA, offers, handles timeouts
Trip serviceThe trip state machine; conditional updates
ETA / mapsRoad-network routing and traffic-aware ETAs
PricingEstimates, surge multipliers, final fares
PaymentsIdempotent charges via a payment provider
Location streamKafka feed for history, analytics and ML

A ride request becomes a match

  1. A rider requests a trip. Matching looks up drivers in the pickup cell and its neighbours, ranks them by real driving ETA, and offers the trip to the best one. When the driver accepts, a conditional update in the trips database makes sure nobody else can claim it.

Trace the match out loud:

  1. The rider taps Request with an idempotency key and the estimate ID. The trip service creates the trip with status matching.
  2. Matching asks the geo index for available drivers in the pickup cell and the ring of cells around it, widening the ring if there are too few.
  3. It asks the ETA service for road travel times for the best 10–20 candidates and ranks them.
  4. It offers the trip to the top driver for about 15 seconds. If the driver declines or the timer runs out, it offers the next.
  5. The driver accepts; the trip service assigns them with a conditional update and the rider is told a car is coming.

The trip and the payment

  1. During the trip, the driver’s positions are pushed to the rider live. When the driver ends the trip, the fare is calculated from the actual route and the payment is charged once, using an idempotency key.

6. Deep dives

Your turn: the hard parts

Before reading on: how do you find nearby drivers in milliseconds, how do you stop one driver being assigned two trips, and what happens at a stadium when 60,000 people leave at once?

Compare with our answer

A strong answer mentions:

  • Cells (geohash, quadtree or H3) in memory; search the pickup cell plus neighbours; then rank by road ETA.
  • A conditional update on the trip (and driver) row, inside one transaction, so only one accept wins.
  • Hot cells: finer cells or splitting a hot shard, queues for venues and airports, surge to move supply.
  • A trip state machine where every transition names the state it expects.

Finding nearby drivers: geohash vs quadtree vs H3

Cells in memory: search the pickup cell and its neighbours

  1. Deep dive: finding nearby drivers. The map is cut into cells, each driver is filed under one cell in memory, and a search checks only the pickup cell and its neighbours.

All three cut the map into cells so that "who is near here" becomes "who is in these few cells". They differ in cell shape and in how they cope with moving points.

OptionHowGood atCatch
GeohashInterleave latitude and longitude bits into a base-32 string; nearby points share a prefix. 6 characters ≈ 1.2 × 0.6 kmSimple; any key-value store or Redis GEOSEARCH can use itRectangles that distort with latitude; two points across a cell edge can have very different strings, so you always search the 8 neighbours
QuadtreeSplit a square into four whenever it holds more than N pointsAdapts to density: small cells downtown, huge ones in the desertBuilt for points that rarely move; 500 K moves/s means constant splitting and merging, and it's an in-memory structure that is awkward to shard
H3 (Uber's hexagonal grid)The earth tiled with hexagons at 16 resolutions; resolution 9 cells are about 0.1 km²All 6 neighbours are the same distance away, so "rings" of cells approximate a circle well; good for aggregating supply and demandChildren don't tile a parent exactly; a library dependency

Choice: fixed cells (H3 or geohash) for the live index, because a driver moving is just "change one cell ID", which costs the same everywhere. Quadtrees suit mostly static data such as restaurants or places (nearby places uses that trade-off). Uber's own dispatch historically used Google's S2 cells and moved to H3 for analytics and pricing; either is a fine interview answer.

The search is: take the pickup's cell, read it and its first ring of neighbours (7 hexagons or 9 squares), filter by status = available, and if there are fewer than, say, 10 candidates, widen to the next ring.

H3's 12 pentagons

You cannot tile a sphere with hexagons alone. H3 starts from an icosahedron (20 triangular faces, 12 corners), and at every resolution the cell at each of the 12 corners is a pentagon, with 5 neighbours instead of 6. Near a pentagon, "ring k" is not a clean hexagonal ring, distances between cell centres are uneven, and some fast-path library functions fail and need the slower, safe variant (in the current API, gridDisk handles pentagons for you; the "unsafe" variants may return an error).

For a ride-hailing app this almost never matters: H3's icosahedron is oriented so that all 12 corners fall in the ocean, far from any road. The practical rules are to call the safe neighbour functions and not to assume "every cell has exactly 6 neighbours" in code that might one day run on global data, such as shipping or flight tracking.

Matching: who gets the offer?

OptionHowCatch
Nearest in a straight lineSort candidates by distanceThe nearest driver may be across a river or on a motorway going the other way
Best road ETA, offered one at a timeRank by routed ETA (plus acceptance likelihood); offer with a ~15 s timeout, then the nextEach decline adds 15 s; needs a fast routing service
Broadcast to severalOffer to the top 3; first accept winsFaster, but drivers see offers vanish, and you need the same race protection anyway
Batch matchingCollect requests for 2–5 s, then solve an assignment problem over all riders and drivers in the areaSlightly slower per request, better overall (fewer long pickups); more complex

Choice: ETA ranking with sequential offers for the interview; mention batch matching as the senior improvement. Two riders near one driver is exactly where greedy "closest driver to each rider, in order of arrival" goes wrong and a batch solver wins.

One driver, one trip: conditional writes

Two races exist: one trip accepted by two drivers (if offers overlap), and one driver accepted onto two trips (if two matchers offer to the same driver). Both are classic check-then-act bugs: "is it free? yes. Assign." run twice in parallel.

Accepting is a conditional update

  1. Accepting a trip is a conditional update: it only succeeds if the trip is still unassigned, so two accepts can never both win.

The fix (see contention and double booking for the general pattern) is to make the check and the write one atomic step, and to cover both rows in one transaction on the city's shard:

BEGIN;
UPDATE trips   SET driver_id = 'd42', status = 'accepted', version = version + 1
 WHERE trip_id = 't9' AND status = 'matching';          -- must affect 1 row
UPDATE drivers SET status = 'on_trip', trip_id = 't9'
 WHERE driver_id = 'd42' AND status = 'offered' AND trip_id = 't9';  -- must affect 1 row
COMMIT;   -- if either affected 0 rows: ROLLBACK and return 409 "already taken"

Marking the driver offered (with the trip ID) when the offer is sent also stops a second matcher offering them another trip in the meantime; the offer's timeout moves them back to available.

The trip state machine

A trip moves matching → accepted → arrived → started → completed, with cancelled reachable from the first three states (and no_driver from matching). Each transition is allowed for one actor and is written as UPDATE … WHERE status = <expected>, so duplicate or out-of-order events (a "driver arrived" retry after "trip started") are rejected instead of moving the trip backwards. Each transition is also published as an event, which drives notifications, ETAs and billing.

Hot cells: stadiums and airports

A concert ends and 30,000 requests come from three cells in ten minutes, while 2,000 drivers converge on them. Problems: the geo-index shard that owns those cells gets most of the city's updates and searches, and every rider's search returns the same few drivers, so offers collide.

Fixes, in the order to mention them:

  • Shard the index by cell, not by city, and use finer cells (a higher H3 resolution) where density is high, so a hot area spreads over several shards.
  • Venue and airport queues: drivers wait in a designated lot and are matched first-in, first-out, which replaces the geo search entirely. Uber does this at airports.
  • Batch matching in hot areas, so one solver assigns drivers to many riders at once instead of thousands of colliding greedy offers.
  • Surge, which brings in more drivers and spreads demand over time.

Routing a moving driver to the right shard

Once the index is sharded by cell, every update must reach the shard that owns the driver's current cell, and drivers keep driving across shard boundaries. A typical layout assigns coarse parent cells (say H3 resolution 5, about 250 km² each) to shards through a small shard map, while drivers are indexed at resolution 9. Finding a cell's parent is a pure function (cellToParent), so any server can route without a lookup service.

OptionHowCatch
Shard by driver IDHash the driver; each shard holds random driversEvery nearby search must ask every shard
Shard by cityOne shard per cityBig cities overload one shard; trips cross city lines
Shard by current cell, move on crossingRoute each update by its cell's parent; when the parent changes, add the driver to the new shard and remove them from the old oneNeeds to know the previous cell; boundary queries touch two or three shards

Choice: route by current cell. The gateway holding the driver's connection remembers the last cell it sent. When an update lands in a cell owned by another shard, it sends add (with position, status and timestamp) to the new shard, then remove to the old one. If the remove is lost, the stale entry is harmless: it expires after 30 seconds without updates, and matching drops duplicates by keeping the entry with the newest timestamp per driver. A driver parked exactly on a boundary may flip shards every update; that is two cheap writes, or you add hysteresis (move only once they are, say, 100 m inside the new parent).

Queries across shards: matching computes the pickup cell plus its ring, groups those cells by owning shard, asks each shard in parallel and merges. With 250 km² shard regions and a search radius of about 1 km, nearly all searches hit one shard; those near an edge hit two or three. That scatter-gather costs one extra in-memory call, well under a millisecond inside a datacenter.

Live tracking: sizing the WebSocket gateways

Drivers send positions and riders watch their car move, both over persistent connections (WebSockets, or MQTT on mobile) held by a fleet of gateway servers. The worked numbers:

  • Connections: 2 M drivers, plus riders on a trip or waiting for pickup. At about 1,000 trip requests/s at peak, each lasting roughly 1,000 s from request to drop-off (a 5-minute wait and a 12-minute ride), Little's law gives 1,000 × 1,000 ≈ 1 M riders watching. About 3 M connections.
  • Messages: 500 K/s in from drivers, and one push to each watching rider per update: 1 M ÷ 4 s = 250 K/s out.
  • Per node: a tuned gateway can hold several hundred thousand mostly idle connections, but plan conservatively at 100 K connections (a few GB of memory for TLS and socket buffers). 3 M ÷ 100 K = 30 nodes; double it to survive losing an availability zone and a reconnect surge: about 60 nodes across three zones, each handling roughly 750 K ÷ 60 ≈ 12.5 K messages/s.

The rider's connection and the driver's connection usually sit on different gateways, so the location service publishes each position to a per-trip channel (Redis pub/sub or a similar fan-out layer), and the gateway holding the rider is subscribed to it. When a gateway dies, its 50 K to 100 K clients reconnect at once; clients must use exponential backoff with jitter, and deploys must drain nodes gradually rather than restart them together.

Surge pricing at a high level

The pricing service aggregates, per cell and per minute or two, demand (requests and app opens) and supply (available drivers, from the location stream), usually with a stream processor. When demand exceeds supply, it applies a multiplier, smoothed over time and across neighbouring cells so prices don't flicker, and capped. The quote is stored with an estimate ID and honoured for a few minutes, so the rider pays what they were shown even if the multiplier moves.

Payment once

Authorise (hold) an amount on the card when the trip is requested, then charge the final fare when it completes, sending an idempotency key derived from the trip ID to the payment provider. If the provider is down at the end of a trip, the trip still completes and the charge is retried later with the same key.

7. Bottlenecks, failures and monitoring

Scaling bottlenecks

BottleneckFix
Location ingest (~500 K/s)Partition by city/cell; stateless ingest; in-memory index sharded by region
Rush-hour spikesAutoscale matching; queue requests briefly; surge to rebalance supply
Trip DB writesShard by city/region; trips are independent
Map / ETA callsCache routes; precomputed road graphs; batch ETA requests

When things fail

FailureWhat happens
Location service node diesDrivers’ next update (4 s later) goes to another node; index rebuilds within seconds
Driver doesn’t answer the offerTimeout → offer the next driver
Payment provider downTrip completes; charge retried later with the same idempotency key
Rider app double-taps RequestIdempotency key returns the same trip

What to monitor

Time to match (p50, p95)Offer acceptance rateLocation update lagCancellation rateSupply vs demand per cityPayment failures

8. Follow-up questions

Your turn: the interviewer pushes

Answer in order: 1) A whole city's matching runs in one region. That region fails. What happens to trips in progress? 2) Add shared rides (two riders, one car). What changes in matching? 3) Riders complain that ETAs shown at request time are wrong by 5 minutes. Where would you look?

Compare with our answer

A strong answer mentions:

  1. Trips are persisted and replicated to another region; apps keep the trip state locally and reconnect; positions rebuild in seconds; in-flight accepts retry idempotently.
  2. Matching becomes route insertion: add a rider to an existing trip only if the detour for current riders stays under a limit; state machine per rider, not per car.
  3. Compare predicted vs actual ETAs per city and time; stale or missing traffic data; pickup-point snapping; the offer/decline delay that isn't in the ETA.
How would you add shared rides?

Matching becomes route-aware: insert a new rider into an existing trip only if the detour for current riders stays under a threshold.

How do you compute ETAs?

Road graph + live traffic from the location stream, with contraction hierarchies or similar for fast routing; ML corrections on top.

How do you handle a city where the network is poor?

Offline-tolerant apps: queue status changes locally, send SMS fallbacks, accept slightly stale locations.

Uber on one page
  • Numbers: 2 M drivers / 4 s = 500 K location updates/s (~50 MB/s); live set ~400 MB in memory; ~300 trips/s average.
  • Two paths: locations (soft state, memory, overwrite, stream to history) vs trips (strongly consistent SQL, sharded by city).
  • Geo index: fixed cells (H3/geohash) for moving drivers; search pickup cell + ring; quadtrees suit static points.
  • Matching: rank by road ETA, offer one at a time with ~15 s timeout; batch matching for global efficiency.
  • One driver, one trip: one transaction with two conditional updates (status = 'matching', driver offered for this trip); accept idempotent per driver.
  • State machine: matching → accepted → arrived → started → completed; transitions name the expected state.
  • Hot cells: shard by cell, finer cells, venue/airport FIFO queues, batch matching, surge.
  • Surge: supply/demand per cell, smoothed and capped; quote locked by estimate ID.
  • Payment: hold at request, charge at completion with an idempotency key.
  • Shard crossing: route updates by the current cell's parent; on crossing, add to the new shard, remove from the old (30 s TTL as backstop); boundary searches scatter-gather 2–3 shards.
  • Gateways: ~3 M connections (2 M drivers + ~1 M riders), 500 K/s in, 250 K/s out; ~100 K connections per node → ~60 nodes with headroom; reconnect with jitter.
Mock interviewPractise it as a mock interview: scope, size and the big decisionsOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A design stores every driver location update as a new row in the trips SQL database. What is the main problem?

2. Why are fixed cells (H3 or geohash) usually preferred over a quadtree for live driver positions?

3. Matching finds the nearest driver by straight-line distance, but pickups are often slow. What is the most likely cause?

4. Two matchers offer the same driver two different trips, and the driver accepts both within a second. What prevents a double assignment?

5. A driver's accept commits, but the response is lost and the app retries. What should the retry return?

6. 30,000 people leave a stadium and request rides from three cells. Which change helps the most with matching quality?

7. How should surge pricing avoid confusing riders when the multiplier changes during booking?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.