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.
On this page
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.
| Phase | Time in a 45-min interview | What you produce |
|---|---|---|
| 1. Clarify requirements | 5 min | Functional list, non-functional targets, what's out of scope |
| 2. Estimate | 5 min | Location updates/s, trips/s, memory for live positions |
| 3. API | 5 min | Estimate, request, location, accept, status, live tracking |
| 4. Data model | 5 min | Live locations vs trips vs history, and where each lives |
| 5. High-level design | 10 min | The hot location path and the transactional trip path |
| 6. Deep dives | 10–15 min | Geo index, matching, one driver per trip, state machine, hot cells, surge |
| 7. Wrap up | 2–3 min | Bottlenecks, 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
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
| Quality | Target | Why |
|---|---|---|
| Matching latency | A driver offered in < 10 s | Riders cancel if nothing happens |
| Location freshness | Positions no older than a few seconds | |
| Consistency | A driver can only accept one trip; a trip has one driver | Strong consistency here |
| Availability | 99.99% | People get stranded otherwise |
| Scale | ~2 M drivers online at peak; ~25 M trips a day | Spiky: rush hour, concerts, rain |
2. Back-of-the-envelope estimates
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.
| Number | Estimate | Why it matters |
|---|---|---|
| Location updates per second | 500 K / s | ≈ 500 K/s: the biggest load in the system. |
| Location ingest bandwidth | 50 MB/s | |
| Trip requests per second (avg) | 289 / s | ≈ 300/s average, several times more at peak. |
| Memory for latest positions | 400 MB | Tiny: the live index easily fits in memory. |
| Location history per day | 2.2 TB | Stored 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
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.
| Call | Request | Response | Notes |
|---|---|---|---|
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 } | 204 | Every 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 } | 200 | Trip state machine transitions |
WS /v1/trips/{id}/live | – | driver position, ETA, status | Live 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
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_idsdriver_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_idstatus: matching | accepted | arrived | started | completed | cancelledpickup, dropoff, fareversion
Money and state transitions need transactions; conditional updates prevent double assignment.
drivers and riders SQL + cache
driver_id, vehicle, statusrider_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
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
- 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.
- 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.
| Component | What it does |
|---|---|
| Location service | Ingests ~500 K updates/s; updates the geo index |
| Geo index | Drivers bucketed by map cell (geohash/H3), in memory |
| Matching / dispatch | Finds candidates, ranks by ETA, offers, handles timeouts |
| Trip service | The trip state machine; conditional updates |
| ETA / maps | Road-network routing and traffic-aware ETAs |
| Pricing | Estimates, surge multipliers, final fares |
| Payments | Idempotent charges via a payment provider |
| Location stream | Kafka feed for history, analytics and ML |
A ride request becomes a match
- 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:
- The rider taps Request with an idempotency key and the estimate ID. The trip service creates the trip with status
matching. - 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.
- It asks the ETA service for road travel times for the best 10–20 candidates and ranks them.
- 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.
- 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
- 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
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
- 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.
| Option | How | Good at | Catch |
|---|---|---|---|
| Geohash | Interleave latitude and longitude bits into a base-32 string; nearby points share a prefix. 6 characters ≈ 1.2 × 0.6 km | Simple; any key-value store or Redis GEOSEARCH can use it | Rectangles that distort with latitude; two points across a cell edge can have very different strings, so you always search the 8 neighbours |
| Quadtree | Split a square into four whenever it holds more than N points | Adapts to density: small cells downtown, huge ones in the desert | Built 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 demand | Children 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?
| Option | How | Catch |
|---|---|---|
| Nearest in a straight line | Sort candidates by distance | The nearest driver may be across a river or on a motorway going the other way |
| Best road ETA, offered one at a time | Rank by routed ETA (plus acceptance likelihood); offer with a ~15 s timeout, then the next | Each decline adds 15 s; needs a fast routing service |
| Broadcast to several | Offer to the top 3; first accept wins | Faster, but drivers see offers vanish, and you need the same race protection anyway |
| Batch matching | Collect requests for 2–5 s, then solve an assignment problem over all riders and drivers in the area | Slightly 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
- 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.
| Option | How | Catch |
|---|---|---|
| Shard by driver ID | Hash the driver; each shard holds random drivers | Every nearby search must ask every shard |
| Shard by city | One shard per city | Big cities overload one shard; trips cross city lines |
| Shard by current cell, move on crossing | Route each update by its cell's parent; when the parent changes, add the driver to the new shard and remove them from the old one | Needs 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
| Bottleneck | Fix |
|---|---|
| Location ingest (~500 K/s) | Partition by city/cell; stateless ingest; in-memory index sharded by region |
| Rush-hour spikes | Autoscale matching; queue requests briefly; surge to rebalance supply |
| Trip DB writes | Shard by city/region; trips are independent |
| Map / ETA calls | Cache routes; precomputed road graphs; batch ETA requests |
When things fail
| Failure | What happens |
|---|---|
| Location service node dies | Drivers’ next update (4 s later) goes to another node; index rebuilds within seconds |
| Driver doesn’t answer the offer | Timeout → offer the next driver |
| Payment provider down | Trip completes; charge retried later with the same idempotency key |
| Rider app double-taps Request | Idempotency 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
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:
- 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.
- 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.
- 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.
- 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', driverofferedfor 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.
1. A design stores every driver location update as a new row in the trips SQL database. What is the main problem?
Only the newest position matters for matching, so it belongs in memory, overwritten in place. History can be streamed to cheap storage asynchronously.
2. Why are fixed cells (H3 or geohash) usually preferred over a quadtree for live driver positions?
Quadtrees shine for mostly static points such as places. With 500 K moves a second, fixed cells keep every update cheap and uniform.
3. Matching finds the nearest driver by straight-line distance, but pickups are often slow. What is the most likely cause?
Riders wait for road travel time, not distance. Rank candidates by a routed ETA.
4. Two matchers offer the same driver two different trips, and the driver accepts both within a second. What prevents a double assignment?
The driver's row records which trip they were offered, and accept is a conditional write on it (plus on the trip row), so only one can commit. Client-side rules don't survive retries and races.
5. A driver's accept commits, but the response is lost and the app retries. What should the retry return?
A conditional write must distinguish "someone else won" from "you already won". Otherwise drivers think they lost trips they won.
6. 30,000 people leave a stadium and request rides from three cells. Which change helps the most with matching quality?
Greedy, one-at-a-time offers collide when everyone sees the same drivers. A batch solver avoids collisions and long pickups; queues and surge help too.
7. How should surge pricing avoid confusing riders when the multiplier changes during booking?
A locked quote makes the price predictable; surge itself is smoothed and capped per cell.
Score 60% or more and the lesson is marked complete.