Design Uber

Clarify the problem

The interview question is to design Uber, a ride-sharing service.

A rider asks for a trip from where they stand to a destination. A driver nearby accepts, drives to the rider, and completes the trip.

The service must quote a price before the trip starts. It must also show the rider where the driver is while the driver approaches.

Charging the rider happens through a payment service next door to this design. This design names that seam and does not build the payment system itself.

Estimate the scale

The scale decides the design. The service handles 20,000,000 trips a day.

20,000,000 / 86,400 = 231 trips per second on average.

Drivers are the heavier load. 5,000,000 drivers are online at busy times, and each driver sends a location update every 4 seconds.

5,000,000 / 4 = 1,250,000 location updates per second.

The write load from locations dwarfs the trip load. A design that treats location as ordinary profile data breaks at this rate.

What makes the problem hard

The core data moves. A driver's stored position is wrong within seconds, so the design must accept constant rewriting and slightly stale reads.

Demand is uneven across a city. A stadium at closing time can hold thousands of riders and very few drivers, while a suburb nearby sits quiet.

A match must feel instant to the rider. The stated budget for this design is a driver accepted in about 30 seconds from the request.

Each trip is also a shared record. Rider, driver and service must agree on the trip's state at every moment, even when a phone loses signal.

The high-level shape

The high-level design has four parts. A rider app and a driver app talk to app servers behind a load balancer.

A location service receives the driver updates and keeps current positions ready to search. A matching service picks a driver for each request.

A trip service owns each trip record from request to completion. The location search, the matching, the trip record, and pricing each need a deep dive.

The shape is simple on purpose. The depth of this problem lives inside the location service and the matcher, not in the number of boxes.

Scope and success

In scope are finding drivers nearby, matching, the trip record, and pricing at scale. Out of scope are the payment system itself and the road routing that a maps service provides.

Success means a rider in a busy area gets a suitable driver inside the match budget. It also means no driver is ever promised to two riders at once.

The location service keeps millions of moving drivers searchable through its index.

The location index

A geospatial index is an index that organises places by where they are, so a search can find what is near a point without scanning everything. Uber uses one to turn millions of moving drivers into a short list of nearby candidates for each request.

The location index is the heart of the Uber design. Every match starts with one question. Which drivers are near this rider right now?

A geospatial index answers that question. It stores each driver's position in a structure shaped by geography, not by driver name or account number.

The index takes the constant location writes. 5,000,000 drivers sending every 4 seconds give 1,250,000 updates per second.

1,250,000 x 86,400 = 108,000,000,000 updates arrive in a day. The index keeps only the latest position per driver, so old updates are overwritten, never stored.

Why a plain index fails

A position is a pair of numbers. One number gives distance north or south, and the other gives distance east or west.

An ordinary database index sorts by one value well. Sorting by the first number scatters drivers who share the second, so a nearby search still scans a long strip of the map.

Scanning is far too slow at this scale. The search must jump straight to the rider's small area and read only the drivers inside it.

Geohash, a code for a square

Geohash divides space as a fixed grid, coded as text, and it treats busy and empty cells alike.

A geohash is a short text code that names one square of a fixed grid laid over the map. Nearby places share a long common start to their codes, because they fall in the same or neighbouring squares.

A longer code names a smaller square. The design picks a code length whose square holds a useful search area for a city street.

Each driver's current code is stored as a key in a key-value store. Finding candidates means reading the keys that start with the rider's code, a prefix search the store does well.

Edges are the known weakness. A driver across the border of the rider's square may be the closest of all, so the search also reads the neighbouring squares.

3 x 3 = 9 squares are read in total, the rider's own square and the ring around it. Exact distance is then checked for each driver found, and only true nearby drivers pass on to matching.

Quadtree, squares that split

Quadtree divides space as squares that split when full, and its cost is rebuilding as drivers move.

A quadtree is a tree that divides a map area into four squares, and divides any square again when it holds too many drivers. Busy city centres end up as many small squares, and empty countryside stays as a few large ones.

In this design a square splits when it passes 100 drivers. A city area holding 50,000 drivers then needs at least 50,000 / 100 = 500 leaf squares.

A search walks down the tree to the rider's square, then reads that square and its neighbours. The work stays small because the tree points straight at the right leaves.

The cost is upkeep. Drivers move between squares constantly, so the tree is always being rebalanced, and a very busy square can churn as drivers cross its borders.

Keeping the index fresh

The index lives in memory, where overwriting a position is cheap. Durability matters little here, because a lost position is replaced by the driver's next update seconds later.

Each entry carries the time it was written. Entries older than a short limit are treated as gone, so a driver whose phone died stops being offered to riders.

The index is sharded by area, one shard per city region. A request only ever touches the shard that holds the rider's area, and a failure in one region leaves the others matching normally.

Geohash and quadtree both serve this design. Geohash is simpler and fits a key-value store directly, while the quadtree adapts its effort to how crowded each area is.

Matching and dispatch

Matching is the step that picks one driver for one rider request from the nearby candidates the index returns. Good matching weighs arrival time, fairness to drivers and the next few minutes of demand, not just raw distance.

The index returns nearby drivers, and the matcher must choose exactly one for each rider.

The choice matters beyond one trip. A poor pairing leaves the next rider with nobody nearby and leaves a driver driving empty across town.

Matching runs against the clock. The design budget is a driver accepted in about 30 seconds from the request, and every choice inside matching spends part of that budget.

Build the candidate list

The matcher asks the geospatial index for drivers around the rider. It then filters that list before ranking it.

Drivers already on a trip are removed, unless their trip ends close to the rider. Drivers with the wrong vehicle type for the request are removed too.

Straight-line distance misleads in a city with rivers and one-way streets. The matcher ranks by estimated driving time to the rider, using road travel times supplied by a maps service.

The ranked list is short. Only the best few drivers are ever offered the trip, which keeps offers rare enough that drivers trust them.

Greedy matching and batched matching

The simplest matcher is greedy. Each request takes the best available driver the moment it arrives.

Greedy matching has a flaw. The first rider can take the only driver who could also have served a second rider a street away, and the second rider then waits far longer.

This design instead collects requests for a short window of 5 seconds, then pairs riders and drivers together. At the average load, one window holds 231 x 5 = 1,155 requests.

Inside the window the matcher picks the set of pairings with the lowest total arrival time. The cost is a few seconds of waiting before an offer goes out, well inside the match budget.

Offer, accept, reserve

Dispatch sends an offer to the chosen driver's phone. In this design the driver has 10 seconds to accept before the offer moves to the next driver on the list.

Three offers at 10 seconds each give 3 x 10 = 30 seconds, the whole match budget. The batch window and the candidate ranking exist to make the first offer succeed almost every time.

Acceptance reserves the driver with one atomic update that flips the driver from available to reserved. If two matchers race for the same driver, only the first update succeeds, and the other matcher picks its next candidate.

Every request carries a unique request identifier, so a retried request is recognised as a duplicate. Idempotency here means one rider can never end up with two drivers by accident.

When matching fails

Sometimes no driver accepts. The matcher widens the search area once, then tells the rider honestly that no driver is available and invites a later retry.

A failed matching service must not lose requests. Requests wait briefly in a queue while a standby matcher takes over, and the rider sees a searching state rather than an error.

Fairness is checked over days, not seconds. The design tracks how offers spread across drivers in an area, so the same few drivers are not fed every trip while others starve.

The trip data model

A trip lifecycle is the ordered set of states one trip passes through, from the first request to completion or cancellation. One shared trip record, moving through those states in order, is what rider, driver and service all agree on.

A trip is one record that many actors read and a few actors change.

The record holds the rider, the driver, the pickup point and the destination. It also holds the quoted price, the current state, and the time each state began.

One record per trip keeps agreement simple. Every screen the rider and driver see is a view of this same record.

The states of a trip

A trip begins as requested, before any driver is chosen. Matching moves it to driver assigned, and the driver's journey to the pickup moves it to driver arriving.

Pickup moves the trip to in progress. Arrival at the destination moves it to completed, which is a final state.

Either side can cancel before pickup, which moves the trip to cancelled, also final. A trip can never move backwards, and a final state can never change again.

Illegal moves are rejected by the trip service. A completion event for a cancelled trip is refused, which keeps billing and ratings attached to exactly one outcome.

The operations, in plain text

Requesting a trip takes the rider, the pickup point, the destination and the vehicle type. The response gives the trip identifier, the quoted price and the first state.

Reading a trip takes its identifier and returns the current state, the driver's position and the estimated arrival time. Both apps poll or subscribe to this read during the trip.

Cancelling takes the trip identifier and who cancelled. The trip service checks the state allows cancellation, applies any cancellation rule for late cancels, and closes the trip.

State changes are sent as events with a sequence number for that trip. The trip service applies events in sequence and ignores repeats, so retries from a flaky phone are safe.

Live progress during the trip

The driver keeps sending a location every 4 seconds throughout the trip. A trip of 20 minutes lasts 1,200 seconds, so it produces 1,200 / 4 = 300 location updates.

Those updates feed the rider's view of the approaching car. The rider's app holds a connection open, by long polling or a WebSocket, so each new position appears without the rider refreshing.

Live positions are not written into the trip record itself. The record stores the route summary at the end, while the stream of positions flows past it and is kept only briefly.

Ending the trip and failure

At completion the trip service fixes the final distance, the duration and the fare from the quoted price. It then invites both sides to rate each other and passes the fare to the payment service at the payment seam.

Trip records are small. At 1 KB per record, a day of trips needs 20,000,000 x 1,000 / 1,000,000,000 = 20 GB of new storage a day, which ordinary database storage absorbs easily.

If a driver's app dies mid-trip, the last recorded state stands. On reconnect the app reads the record and resumes, or support reassigns the rider from the same record.

The record is the recovery plan. Because every actor trusts it over any phone's memory, a crash loses seconds, never the trip.

Pricing

Surge pricing is a fare multiplier that rises when trip requests in an area outnumber the drivers available there. It balances the two sides of the market, pulling more drivers toward busy areas and asking riders who can wait to wait.

Pricing and the scale of the location pipeline belong together. Pricing depends on the pipeline, because a price set from stale driver counts is wrong on arrival.

The base fare comes from distance and time, priced by fixed rates for the city. Surge pricing is a multiplier applied on top of that base fare, and only while the imbalance lasts.

Surge pricing has two jobs. It encourages drivers to head toward the busy area, and it encourages riders with flexible plans to wait a few minutes.

How the multiplier is set

Requests outnumber drivers in an area, and the multiplier rises.

Drivers outnumber requests in an area, and the multiplier returns to normal.

An event ending nearby makes the multiplier rise before the rush.

For each small area, the pricing service counts open requests and available drivers over a short recent window. The ratio of the two counts drives the multiplier.

Take one busy area with 1,200 requests and 600 available drivers. The ratio is 1,200 / 600 = 2, so demand is double supply, and the multiplier rises toward that signal.

The design caps the multiplier at a stated maximum and smooths its steps. A price that jumps wildly between one minute and the next destroys rider trust, even when the ratio is real.

Prices are recalculated every 5 minutes in this design. That gives 60 / 5 = 12 fresh prices an hour for each area, frequent enough to follow an event crowd, calm enough to quote from.

Quote first, then lock

The rider sees the price, including any multiplier, before confirming the request. A rider who dislikes the price can wait or choose another way to travel.

Once a driver accepts, the quoted price is locked for that trip. Traffic delays on the road do not reopen the quote, and a falling multiplier nearby does not discount it.

Locking the price keeps the trip record simple. The fare at completion is the quote, checked against the final distance and duration, with any difference explained in the receipt.

The pipeline at full scale

Pricing and matching both read the same location pipeline. That pipeline carries 5,000,000 drivers sending every 4 seconds, which is 1,250,000 updates per second.

The pipeline is sharded by region, so each region handles its own drivers. Split across 50 regions in this design, one region carries 5,000,000 / 50 = 100,000 drivers.

Evening peaks stress trips more than locations, because the driver count changes little while requests surge. At a peak of three times the average, trips reach 231 x 3 = 693 per second.

Queues absorb short bursts between pipeline stages, and rate limiting protects the request operation from accidental or hostile floods. Matching is protected first, because a matched trip can tolerate a slightly older price better than no match at all.

Keeping surge honest

Fake requests could inflate a multiplier, so only confirmed requests from real accounts count toward demand. Cancelled requests leave the count at once.

Every multiplier decision is logged with the counts that caused it. The log lets the service explain any price afterwards and audit whether the rules were followed.

Under overload the design degrades gracefully. Prices refresh more slowly and search areas grow more slowly, while requesting and matching keep working at full quality.

Evaluation

A trade-off review tests a finished design against freshness, fairness and failure, and names what each choice gave up. The Uber design trades constant write load and a few seconds of matching delay for trips that feel instant and fair.

Evaluation revisits the whole Uber design and states what each major choice costs.

The design in one line is this. A memory-based geospatial index feeds a batching matcher, one ordered trip record carries each trip, and area pricing balances demand against supply.

Evaluation is not a victory lap. Each strength below is paired with the weakness the same choice created.

Freshness against write load

Drivers report every 4 seconds, which produces 1,250,000 updates per second. That write load is the price of positions fresh enough to match on.

Reporting less often would halve the load at a stroke, and matches would then be made on positions a street or two out of date. The design keeps the load and spends engineering on making writes cheap, in memory and overwritten in place.

The same logic protects the trip record in the opposite direction. Trip writes are rare and precious, so they go to durable storage with ordered, once-only changes.

Speed against pairing quality

Batching delays every offer by a few seconds. In return it pairs riders and drivers as a set, which shortens total waiting across the city.

Geohash gives simple, fast lookups and awkward edges. The quadtree adapts to density and costs constant upkeep. Many real designs run the simple grid first and reach for the tree only where density varies sharply.

Surge pricing balances the market and annoys riders in equal measure. Showing the price before the request, capping the multiplier and logging every decision are the mitigations the design chose.

Where the design breaks

Lose one region's index shard and that region cannot match until the shard recovers. It recovers quickly by design, because drivers keep sending updates and the index rebuilds itself from the fresh stream.

A sudden event crowd overwhelms matching before it overwhelms storage. Queues hold the burst, prices rise to spread demand, and honest no-driver answers beat false promises.

A network partition between regions is survivable because trips are local. A trip begins and ends inside one region, so regions keep serving their own cities while cut off from each other.

Wrap up the answer

Close the interview answer by walking the method back. Clarify the actors, estimate the location load, sketch the services, then dive into the index, the matcher, the trip states and pricing.

Name the seams honestly. Road routing belongs to a maps design, and charging belongs to a payment design, and both were named rather than built.

That honesty is part of the evaluation. A design that states its boundaries and its costs reads as stronger than one that claims to solve everything.

The ask in numbers