Design Uber

Design a ride-hailing platform. A rider opens the app, sees nearby cars and a price, requests a ride and watches the assigned car approach on the map. Drivers keep the app open while they work, sending their position every few seconds and accepting or declining trip offers.

What makes it hard: millions of moving drivers produce a constant flood of location updates, matching must find a good nearby driver in a couple of seconds, no driver may be assigned to two riders, prices react to local supply and demand, and a trip must never get stuck in a strange state when phones lose signal or retry requests.

In 45 minutes, cover location ingestion, how you find and assign drivers, how prices are computed, and how a trip moves from request to payment.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Location & Marketplaces · problem 25 of 70

Ask before you design. Try answering each yourself, then compare.

  1. What scale should we design for?
    Typical answer

    About 5 M drivers online at peak worldwide, 25 M trips per day, and city-level peaks during rush hour and events.

  2. How often do drivers send location?
    Typical answer

    Every 4 seconds while online, more often during an active trip is fine.

  3. How quickly must a rider be matched?
    Typical answer

    A driver offer should go out within about 2 seconds of the request; the whole match usually completes within 30 s including driver acceptance.

  4. Can a driver decline?
    Typical answer

    Yes. An offer times out after ~15 s and the next candidate is tried.

  5. Do we need pooled or shared rides?
    Typical answer

    No, single-rider trips only. Pooling is a follow-up.

  6. What does pricing depend on?
    Typical answer

    Base fare plus estimated distance and time, multiplied by a surge factor per area that reflects current demand versus supply. The quoted price is honoured for a few minutes.

  7. Is payment in scope?
    Typical answer

    Only as the final step: the trip service triggers a charge; the payment system itself is external.

Do location pings need to be durable before you can use them for matching?
How would you find drivers within 2 km without scanning every driver in the city?
Two dispatch servers pick the same driver for two riders at the same moment. What prevents a double assignment?
A trip goes through clearly defined stages. What happens when the 'start trip' request is retried?
Surge pricing needs supply and demand per area per minute. Where do those numbers come from?

Requirements

Functional

  • Drivers go online/offline and stream their location.
  • Riders see nearby cars and an upfront price, then request a ride.
  • Match the request to a nearby available driver who accepts; show live driver location to the rider.
  • Track trip state from request to completion or cancellation, then trigger payment.
  • Compute dynamic pricing per area from current supply and demand.

Non-functional

  • Driver offer sent within 2 s at p95 of a ride request.
  • Location ingestion of ~1 M updates/s at peak; positions visible to matching within 1 s.
  • A driver is never assigned to two active trips; trip state changes are exactly-once in effect.
  • 99.99% availability for requests and trips in progress; region-local operation if a cloud region fails.

Out of scope

  • Payment processing internals, ratings, driver onboarding.
  • Routing/ETA engine internals (treat as a service).
  • Pooled rides and food delivery.

Back-of-the-envelope estimates

  • Location updates: 5 M drivers × 8 online hours ÷ 4 s ≈ 36 B pings/day, ~420,000/s on average and ~1 M/s at peak. Each is ~100 bytes, so ~40–100 MB/s of ingest.
  • Live index: 5 M drivers × ~100 bytes = 500 MB, small enough to keep every city's index in memory on a few machines.
  • Trips: 25 M/day ≈ 300/s average, ~1,000/s at peak, each with ~6 state changes. Trip storage is ~25 M × 2 KB = 50 GB/day.
  • Rider tracking: during a trip the rider receives the driver's position every few seconds, roughly 1 M active trips × 0.25/s = 250,000 pushes/s.
  • History: keeping all pings for a year is ~1.3 PB with replication, so it goes to cheap columnar storage, not the hot path.

Location write volume dominates, but it is ephemeral; the trip path is small but must be strictly correct.

API

WS   /v1/driver/stream     driver -> {lat, lng, heading, ts}   server -> {offer | trip update}
POST /v1/quotes            {pickup, dropoff}             -> {quoteId, price, surge, expiresAt}
POST /v1/trips             {quoteId, idempotencyKey}     -> {tripId, state: REQUESTED}
POST /v1/offers/{id}/accept {driverId}                   -> {tripId} | 409 already taken
POST /v1/trips/{id}/events {type, expectedVersion}       -> {state, version}
WS   /v1/rider/trips/{id}  server -> {driverLocation, eta, state}

Trip transitions send the version the client last saw, so retries and races are rejected by a compare-and-set rather than applied twice.

Data model

Live locations: an in-memory index per city shard, cell_id -> {driver_id: (lat, lng, status, ts)}, using a hierarchical cell system (geohash, S2 or H3). It is rebuilt from pings within seconds after a restart, so it needs no durability.

Trips: trips(trip_id PK, rider_id, driver_id, state, version, quote_id, pickup, dropoff, timestamps, fare) in a strongly consistent, sharded relational store (by city or trip_id), with a unique constraint on (driver_id) among active trips. quotes(quote_id, price, surge, expires_at) in a TTL key-value store.

Supply/demand: surge(cell_id, multiplier, updated_at) in a cache, recomputed every minute. Raw pings go to a log and then a columnar store for analytics and fraud review.

High-level design

Location path: each driver app holds a WebSocket to the edge gateway and sends a ping every 4 s. The location service validates it, updates the driver's cell in the in-memory geo index for that city, and publishes the ping to a location stream. Stream consumers archive pings to history and feed the surge aggregator, and during a trip forward the driver's position to the rider's socket.

Quote and request: the rider app asks the trip service for a quote; the pricing service combines an ETA/distance estimate with the current surge multiplier for the pickup cell and stores a quote valid for a few minutes. When the rider confirms, the trip service writes a REQUESTED trip with an idempotency key and hands it to dispatch.

Matching: the dispatcher for that city queries the geo index for idle drivers in rings of cells around the pickup, ranks them by ETA, and sends an offer to the best one through the gateway, holding a short reservation on that driver. On accept, the trip service moves the trip to MATCHED with a conditional write that also asserts the driver has no other active trip. On decline or timeout, the next candidate gets the offer.

Trip: arrive, start and complete events move the state machine via versioned transitions; completion triggers payment asynchronously.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Indexing millions of moving drivers

A database index rewritten a million times per second is the wrong tool. Divide the map into cells (around 1 km at the matching level) and keep, in memory, which idle drivers are in each cell. A ping moves a driver between two sets at most, which is O(1). Nearby search reads the pickup cell and expanding rings of neighbours until enough candidates appear, then ranks them by road ETA rather than straight-line distance. Shard by city or region so a dispatcher only talks to its local index, and replicate each shard so a failed node is replaced by a warm copy. Pings older than ~15 s mark a driver stale, so a phone that loses signal stops receiving offers.

Assigning without double booking

Dispatchers for one city may run in parallel, so two can choose the same driver. Use two layers. First, a short reservation: when sending an offer the dispatcher atomically sets the driver's status from IDLE to OFFERED with a TTL in the index shard, which only one dispatcher can win. Second, the source of truth: accepting writes MATCHED to the trip with a conditional update and a uniqueness constraint on the driver's active trip, so even a bug in the reservation layer cannot produce two active trips. Offer timeouts release the reservation. Batching requests every second or two and solving a small assignment problem per area improves global ETAs during rush hour, at the cost of a little latency.

Trip state machine and idempotency

A trip moves REQUESTED → MATCHED → DRIVER_ARRIVED → IN_PROGRESS → COMPLETED, with CANCELLED allowed from early states. Each transition is a compare-and-set on (trip_id, version), so a retried 'start trip' after a dropped response finds the version already advanced and returns the current state instead of acting twice. Side effects such as charging the rider are emitted as events through an outbox in the same transaction and processed by consumers keyed on trip id, so payment runs once even if the service crashes mid-way. A sweeper resolves trips stuck in one state too long, for example an offer that no driver ever answered.

Dynamic pricing

A stream job counts open requests and idle drivers per cell per minute from the request and location streams, smooths them over a few minutes and across neighbouring cells to avoid jumpy prices at cell borders, and maps the demand/supply ratio to a capped multiplier. Multipliers go to a cache read by the pricing service. The rider gets a quote with an id and expiry, and the trip is billed at the quoted price, so a surge change between quote and request never surprises them.

Failure modes

  • If a geo index node dies, its replica takes over; if all copies are lost, the index refills from pings within one or two update intervals.
  • If the location stream lags, matching is unaffected because it reads the in-memory index; only surge and history fall behind, and surge keeps its last values.
  • If a driver's phone loses connectivity mid-offer, the offer times out and the reservation expires so the next candidate is tried.
  • If the trip DB primary fails, a synchronous replica is promoted; in-flight transitions are retried idempotently by version.
  • If an entire region fails, cities fail over to another region; drivers reconnect and the live index rebuilds from fresh pings, while trips in progress are read from the replicated trip DB.

Core algorithm in code

import math
from collections import defaultdict

CELL_DEG = 0.01   # ~1.1 km cells at the equator


def cell(lat, lng):
    return (math.floor(lat / CELL_DEG), math.floor(lng / CELL_DEG))


def km(a_lat, a_lng, b_lat, b_lng):
    x = math.radians(b_lng - a_lng) * math.cos(math.radians((a_lat + b_lat) / 2))
    y = math.radians(b_lat - a_lat)
    return 6371 * math.hypot(x, y)


class DriverIndex:
    def __init__(self):
        self.cells = defaultdict(set)
        self.where = {}

    def update(self, driver_id, lat, lng, idle):
        old = self.where.pop(driver_id, None)
        if old:
            self.cells[old[0]].discard(driver_id)
        if idle:                                   # only idle drivers are matchable
            c = cell(lat, lng)
            self.cells[c].add(driver_id)
            self.where[driver_id] = (c, lat, lng)

    def nearby(self, lat, lng, k, max_ring=5):
        cx, cy = cell(lat, lng)
        found = []
        for ring in range(max_ring + 1):
            for dx in range(-ring, ring + 1):
                for dy in range(-ring, ring + 1):
                    if max(abs(dx), abs(dy)) != ring:
                        continue                   # only the new outer ring
                    for d in self.cells.get((cx + dx, cy + dy), ()):
                        _, dlat, dlng = self.where[d]
                        found.append((round(km(lat, lng, dlat, dlng), 2), d))
            if len(found) >= k:                    # one more ring could hold closer ones at the corners,
                break                              # good enough for a candidate list
        return sorted(found)[:k]


TRANSITIONS = {
    "REQUESTED": {"MATCHED", "CANCELLED"},
    "MATCHED": {"DRIVER_ARRIVED", "CANCELLED"},
    "DRIVER_ARRIVED": {"IN_PROGRESS", "CANCELLED"},
    "IN_PROGRESS": {"COMPLETED"},
}


class Trip:
    def __init__(self, trip_id):
        self.trip_id, self.state, self.version = trip_id, "REQUESTED", 0

    def transition(self, new_state, expected_version):
        if expected_version != self.version:           # stale or duplicate request
            return False
        if new_state not in TRANSITIONS.get(self.state, ()):
            return False
        self.state, self.version = new_state, self.version + 1
        return True


idx = DriverIndex()
drivers = {"d1": (37.7749, -122.4194), "d2": (37.7790, -122.4170), "d3": (37.7600, -122.4400),
           "d4": (37.8044, -122.2712), "d5": (37.7755, -122.4180)}
for d, (lat, lng) in drivers.items():
    idx.update(d, lat, lng, idle=True)
idx.update("d5", 37.7756, -122.4181, idle=False)       # d5 just started a trip
print("candidates:", idx.nearby(37.7752, -122.4190, k=3))

trip = Trip("t42")
print("match:", trip.transition("MATCHED", expected_version=0))
print("duplicate match retry:", trip.transition("MATCHED", expected_version=0))
print("arrive:", trip.transition("DRIVER_ARRIVED", 1), " start:", trip.transition("IN_PROGRESS", 2))
print("cancel mid-trip:", trip.transition("CANCELLED", 3), " final state:", trip.state)

Trade-offs

  • Keeping live locations only in memory gives huge write throughput and low latency but loses them on a crash; they are rebuilt from the next pings, which is acceptable because they expire anyway.
  • Greedy nearest-driver matching is fast and simple but globally worse at rush hour than batched assignment, which adds a second or two of delay.
  • Sharding by city keeps matching local and fast but makes trips that cross shard borders (airports, metro areas) need special handling.
  • Smaller cells give more precise surge and search but more cells to scan and noisier counts per cell.
  • Quoting a fixed price protects riders from surprises but leaves the platform carrying the risk when the trip runs long.

What a strong answer shows

  • Treats location pings as high-volume, ephemeral data held in an in-memory spatial index, not a transactional DB.
  • Explains a concrete spatial index (grid, geohash, S2/H3) and ring search for nearby drivers.
  • Prevents double assignment with reservations plus a constraint-backed source of truth.
  • Models the trip as a state machine with idempotent, versioned transitions and reliable side effects.
  • Derives surge from streamed supply and demand and honours quotes.
  • Partitions by geography and explains regional failure handling.

Mistakes to avoid

  • Writing every location ping to a relational table and running radius queries on it.
  • Matching purely by straight-line distance and ignoring ETA and stale drivers.
  • No protection against two riders being matched to the same driver.
  • Handling retries with plain updates so a trip can be started or charged twice.
  • Pushing driver positions to riders by having riders poll the database.

Follow-ups to expect

  • How would you add pooled rides? (Match requests along compatible routes; detours bounded; trip has multiple riders.)
  • How would you compute ETAs fast? (Precomputed road graph with contraction hierarchies plus live traffic speeds per segment.)
  • How do you detect GPS spoofing? (Speed and jump checks on the stream, compare with network location, flag accounts.)
  • How would you run the system in a new country with data residency laws? (Region-pinned shards for trips and history.)

Practice next

Next Post Previous Post
No Comment
Add Comment
comment url