Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

System Design HLD-19.13

Design a ride-hailing service (Uber)

Design ride hailing: high-rate driver location ingestion, an in-memory geo index, matching with offers, a trip state machine, surge input and payments.

Advanced 25 min Last reviewed

The problem

A rider taps "request" and within seconds a nearby driver is on the way, with a moving car on the map and a reliable arrival time. To do that, the system must know where every available driver is right now, find the best few near the rider, offer the trip to one without offering the same driver two trips, track the trip from pickup to drop-off, and charge the right amount at the end.

The unusual part is the write rate. Most systems are read-heavy. Here, a million phones each report their position every few seconds, and that data is stale almost as soon as it arrives. The location pipeline is built for a firehose of tiny, short-lived writes, which is the opposite of what a normal database is good at.

Requirements

Functional

  • Drivers go online and stream their location; riders see nearby cars.
  • A rider requests a trip with pickup and destination and gets a price estimate.
  • The system matches the rider to a nearby available driver, who accepts or declines.
  • Both see each other's live position; the trip moves through pickup, ride and drop-off.
  • Payment is charged after the trip; both parties rate each other.

Non-functional

  • Scale: 1 million drivers online at peak, 20 million trips a day.
  • Matching: a driver offer within a few seconds of the request.
  • Consistency: a driver is never assigned two trips at once; a trip is charged exactly once.
  • Availability: a failed data center must not strand riders mid-trip.

Out of scope

  • Routing and ETA computation internals, fraud detection, shared rides and food delivery.

Estimates

  • Location writes: 1M drivers x 1 update every 4 seconds = 250,000 writes per second at peak. At about 100 bytes each, 25 MB/s.
  • Location history: if kept for analytics, 250,000 x 86,400 = 21.6 billion updates a day at the peak rate, about 2 TB a day at 100 bytes. This goes to a log and cheap storage, not to the matching index.
  • Current positions: 1M drivers x about 100 bytes = 100 MB. The live index fits in memory on one machine; it is partitioned by city or region for locality and fault isolation, not for size.
  • Trips: 20M a day is about 230 per second on average, maybe 3x at peaks, so around 700 trip requests per second. Matching reads are tiny next to the location writes.

API

WS   /v1/driver/stream            # driver -> { lat, lng, heading, ts } every 4 s
                                  # server -> trip offers
POST /v1/trips/estimate  { pickup, dropoff }        -> { price, quote_id, expires_in }
POST /v1/trips           { quote_id, pickup, dropoff, idempotency_key } -> { trip_id }
POST /v1/trips/{id}/accept   (driver)                -> 200 or 409 if the offer expired
POST /v1/trips/{id}/events   { type: arrived | started | completed | cancelled }
WS   /v1/trips/{id}/live     # both apps: the other party's position

The driver app keeps one persistent connection ( Real-time: polling, long polling, SSE and WebSockets ) for both directions: location up, trip offers down. Trip creation takes an idempotency key so a retried tap does not create two trips ( Idempotency and safe retries ).

Data model

  • Live driver index (in memory, per region): driver_id -> lat, lng, status (available, offered, on_trip), updated_at, plus a geospatial index from cell to drivers. Entries expire if a driver stops reporting.
  • Location log (event stream): every update, consumed by the index, surge computation and history storage ( Stream processing ).
  • Trips (relational database, partitioned by region or trip id): trip_id, rider_id, driver_id, state, pickup, dropoff, quote_id, price, timestamps. The state column is the source of truth for the trip lifecycle.
  • Quotes: quote_id -> price, surge multiplier, expires_at, so the price the rider accepted is the price charged.

High-level design

Ride hailing: location, matching and trip paths Location path: driver apps stream positions over persistent connections to location gateways, which publish them to a log; an indexer updates the in-memory geo index and a surge job counts supply and demand per cell. Matching path: a rider's request reaches the trip service, which asks the matcher; the matcher queries the geo index for nearby available drivers, ranks them by ETA, and offers the trip to one driver through the gateway. Trip path: the trip service records state changes in the trip database and, when the trip completes, hands payment to the payment service asynchronously. upsert request claim candidates offer state completed Driver apps every 4 s Location gateways WebSockets Location log partitioned stream Geo index in memory, per city Surge job supply, demand per cell Rider app Trip service state machine Matcher rank by ETA Trip DB Payments after drop-off ETA service road network Figure 1. The location firehose (top) never touches the trip database. The matcher reads the in-memory index; the trip service owns the state machine and starts payment after drop-off.
  1. Location path Driver apps send a position every few seconds over a persistent connection. Gateways publish updates to a partitioned log. An indexer keeps the latest position per driver in an in-memory geo index; a surge job counts supply and demand per cell.
  2. Matching path The rider's request goes to the trip service, which asks the matcher. The matcher finds nearby available drivers in the geo index, asks the ETA service for road travel times, atomically claims the best driver and sends the offer through the driver's gateway.
  3. Trip path Every step of the trip is a state transition written to the trip database. When the trip completes, payment is requested asynchronously, using the trip id as the idempotency key.

Deep dives

Deep dive 1: Ingesting locations

A position is only useful for a few seconds, so treat updates as a stream, not as rows to keep. Gateways terminate the persistent connections and publish each update to a log partitioned by region ( Message queues vs pub/sub vs event streams ). Consumers each keep what they need:

  • The indexer overwrites the driver's latest position in memory. Losing one update is harmless; the next arrives in 4 seconds.
  • The surge job counts available drivers and open requests per cell per minute.
  • The history writer batches updates into cheap storage for trip receipts, disputes and analytics.

The phone also helps: it can send less often when the driver is parked, and batch points when the signal is poor. Because positions overwrite each other, a write-heavy key-value store or plain process memory is the right tool, not a relational table with an index on location.

Deep dive 2: Finding nearby drivers

Divide the map into cells ( Geospatial indexing ), keep a set of drivers per cell, and on a driver's update move it between cells only when it crosses a boundary. To find drivers near a rider, look in the rider's cell, then expand ring by ring until you have enough candidates and no unsearched cell could hold a closer one:

nearby.pyruns with python3 (standard library)
# In-memory geo index for drivers: a grid of 500 m cells. Find the 5 nearest
# available drivers by searching rings of cells outward from the rider.
import math, random
from collections import defaultdict

rnd = random.Random(42)
CELL = 500                                    # metres
drivers = {f"d{i}": (rnd.uniform(0, 20000), rnd.uniform(0, 20000))
           for i in range(10000)}             # a 20 km x 20 km city
grid = defaultdict(set)
cell_of = lambda x, y: (int(x // CELL), int(y // CELL))
for d, (x, y) in drivers.items():
    grid[cell_of(x, y)].add(d)

def update(d, x, y):                          # a ping every 4 s
    old, new = cell_of(*drivers[d]), cell_of(x, y)
    if old != new:
        grid[old].discard(d)
        grid[new].add(d)
    drivers[d] = (x, y)

def nearest(x, y, k=5):
    cx, cy = cell_of(x, y)
    found, checked, r = [], 0, 0
    while True:
        for i in range(cx - r, cx + r + 1):
            for j in range(cy - r, cy + r + 1):
                if max(abs(i - cx), abs(j - cy)) != r:
                    continue                  # only the new outer ring
                for d in grid.get((i, j), ()):
                    checked += 1
                    found.append((math.dist((x, y), drivers[d]), d))
        found.sort()
        # stop once k drivers are closer than any unsearched cell can be
        if len(found) >= k and found[k - 1][0] <= r * CELL:
            return found[:k], checked, r
        r += 1

update("d7", 10100, 10050)                    # d7 drives next to the rider
top, checked, rings = nearest(10000, 10000)
print("nearest:", ", ".join(f"{d} {m:.0f} m" for m, d in top))
print(f"checked {checked} drivers in {(2 * rings + 1) ** 2} cells "
      f"instead of all {len(drivers)}")

Output

nearest: d6855 63 m, d7 112 m, d1215 148 m, d7770 188 m, d9802 206 m
checked 54 drivers in 9 cells instead of all 10000

Ten thousand drivers, but the search checked 54 of them in 9 cells. The index answers "who is close in a straight line"; the matcher then asks an ETA service for road travel times for those few candidates, because a driver 200 m away across a river or a motorway may be ten minutes out. Square grids, geohashes, quadtrees and hexagonal grids all work here; hexagons have the advantage that every neighbour is the same distance away.

Deep dive 3: Matching without double booking

Two riders near the same driver may be matched at the same moment. The matcher must claim the driver atomically: a compare-and-set that changes the status from available to offered only if it is still available, with an expiry of about 15 seconds. If the claim fails, take the next candidate. If the driver declines or the offer expires, the status returns to available and the trip is offered to the next driver. Because each region's index has a single owner, the compare-and-set is a local operation in memory, not a distributed lock.

The trip itself moves through a strict state machine, and every transition is a conditional update in the trip database (UPDATE ... WHERE state = 'accepted'), so a duplicated or late event cannot move a trip backwards:

Trip state machine States from left to right: requested, matching, accepted, arriving, in progress, completed and paid. Cancelled can be reached from requested, matching, accepted and arriving. If no driver accepts, matching loops back to try the next driver. declined: next charge requested matching accepted arriving in progress completed paid cancelled Figure 2. Each arrow is a conditional update, so events that arrive twice or out of order are rejected rather than corrupting the trip.

Payment is a separate step after completed. The trip service publishes a completed-trip event and the payment service charges the card using the trip id as the idempotency key; if the charge fails, the trip stays completed and payment is retried or handled by a support flow, which is the saga pattern ( Sagas: choreography and orchestration ).

Deep dive 4: Surge pricing input

Prices rise where demand outruns supply, which pulls drivers toward busy areas. The surge job consumes the location log and the request stream, counts open requests and available drivers per cell per minute, and smooths the ratio across neighbouring cells so prices do not jump between adjacent streets. The output is a multiplier per cell with a short lifetime. The estimate endpoint attaches the multiplier to a quote with an expiry, so the rider pays the price they saw even if surge changes a minute later.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Find a precision where a cell is roughly the size of a few city blocks. How many drivers would a busy city have per cell?
  2. Put the two points close together but on opposite sides of a cell boundary. Why must the driver search include neighbouring cells?
  3. With 250,000 updates per second, how many of them actually move a driver into a different cell at this precision? (Think about how far a car moves in 4 seconds.)

Bottlenecks and failure modes

FailureImpactMitigation
Location firehose overloads storageLag in positionsOverwrite in memory; history in batched, cheap storage
Geo index node diesNo matching in that regionRebuild from the log within seconds; replicas per region
Two riders claim one driverDouble bookingAtomic compare-and-set on driver status with an expiry
Driver ignores the offerRider waitsOffer timeout, then the next candidate
Duplicate or late trip eventsCorrupted trip stateConditional state transitions in the trip database
Payment provider downTrip unpaidAsync payment with idempotency key and retries

Trade-offs we made

OptionWins whenLoses when
In-memory index rebuilt from a log (chosen) Handles 250,000 writes per second cheaply Recovery depends on replaying recent updates
Geospatial queries in a database Durable and familiar Index churn at this write rate is expensive
Offer to one driver at a time (chosen) No wasted driver attention; simple claims Slower when drivers decline
Partition by region (chosen) Locality and fault isolation; most trips stay in one region Trips near region borders need cross-region lookups

Extensions

  • Batch matching: collect requests for a second or two and assign drivers to riders together for better overall pickup times.
  • Shared rides: match riders whose routes overlap.
  • Driver positioning: predict demand per cell and suggest where idle drivers should wait.
  • Multi-region failover for in-progress trips.

In the wild

Uber

H3: Uber's Hexagonal Hierarchical Spatial Index (opens in a new tab)

Uber built H3, a grid system that divides the world into hexagonal cells, for optimizing ride pricing and dispatch and for exploring spatial data, and open-sourced it in 2018. Hexagons were chosen because a hexagon has only one distance between its centre and its neighbours' centres, unlike squares or triangles, which simplifies analysis and smoothing over gradients. H3 has sixteen resolutions, each finer cell having one seventh the area of the coarser one, and cell ids can be truncated to find their ancestor at a coarser resolution. The post says Uber uses it to compute surge pricing by measuring supply and demand in hexagons.

Check yourself

  1. Why are driver locations kept in memory rather than written to a relational table?

    Show answer

    B. Updates arrive at very high rates and are stale within seconds, so overwriting in memory is cheap and sufficient The live index only needs the latest position; history goes to a log and cheap storage.

  2. Why does a nearby search look at neighbouring cells?

    Show answer

    B. A driver just across a cell boundary can be closer than drivers inside the rider's cell Cell membership is not distance; the search expands until no unsearched cell could be closer.

  3. How does the matcher stop two riders getting the same driver?

    Show answer

    B. An atomic compare-and-set changes the driver from available to offered, with an expiry Only one claim can succeed; the losing match moves to its next candidate.

  4. Why does the matcher call an ETA service after the geo query?

    Show answer

    B. Straight-line distance ignores roads, rivers and one-way streets The geo index narrows candidates cheaply; road ETA ranks the few that remain.

Recap

  • Driver locations are a firehose: stream them through a log and keep only the latest in memory.
  • Find nearby drivers by cell, expanding ring by ring, then rank candidates by road ETA.
  • Claim a driver with an atomic compare-and-set and an offer expiry to prevent double booking.
  • The trip is a state machine of conditional updates; payment runs afterwards with an idempotency key.
  • Surge counts supply and demand per cell, and quotes lock the price the rider saw.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up