Designing Uber: Ride Matching, Live Location, and Surge Pricing

Uber inverts the usual read/write ratio. A typical app is read-heavy with rare writes; here, a million drivers write their GPS position every 4 seconds whether or not anyone is looking, and the hardest query — "nearest available drivers, now" — runs against data that is stale the moment it lands. Design decisions that are obvious for a CRUD system (persist writes durably, index in the database) are exactly wrong here, which is what makes this interview discriminating.

Requirements

Functional: riders request trips, system matches a nearby available driver, both parties track each other live, price responds to supply/demand imbalance. Non-functional: match in under 10s end-to-end, location freshness within seconds, ~1M location updates/sec at peak, a lost location ping is fine, a lost trip state transition is not.

Location ingestion: embrace the ephemerality

The first fork in the road: driver pings are high-volume, tiny, and individually worthless 5 seconds later. So: WebSocket/UDP-ish ingestion into an in-memory geospatial index, not synchronous durable writes. Kafka tees the stream off to analytics and ETA-model training (history matters in bulk), but the live index is memory, updated in place.

Index shape: the world divided into cells — H3 hexagons in Uber's case, geohash/S2 elsewhere — with a mapping cell → set of (driver_id, position, status).

driver ping -> gateway -> shard(cell) -> update cell set + driver record
nearby query -> cover rider's radius with ~1 ring of cells -> union sets -> rank

Two classic follow-ups live here. Why hexagons? Uniform neighbor distances (squares have diagonal-neighbor distortion) make ring expansion cleaner for "widen the search." Boundary problem: a rider near a cell edge must query the neighbor ring, not just their own cell — otherwise the nearest driver 50m away in the adjacent cell is invisible.

Sharding is geographic: each shard owns a set of cells (city or region). Load skew is brutal — downtown Friday night vs rural Tuesday — so hot regions get split (finer cell-to-shard mapping), the same hot-partition medicine as everywhere else. City-level sharding also matches the failure domain you want: a bad deploy takes out one metro, not the planet.

Matching: a distributed transaction wearing a trench coat

Naive matching — query nearby, pick nearest, assign — double-books drivers the moment two riders request simultaneously: both queries return driver D, both assign. The invariant "a driver has at most one active trip" needs an atomic claim:

def match(ride):
    candidates = geo_index.nearby(ride.pickup, ring=1)      # stale-ish, fine
    ranked = rank(candidates, eta_model, driver_rating)     # ETA, not distance
    for d in ranked:
        # atomic compare-and-set on the driver's status record
        if driver_state.cas(d.id, from_="AVAILABLE", to="OFFERED", ttl=15):
            if offer_to_driver(d, ride):                     # push, 15s to accept
                return assign(d, ride)                       # OFFERED -> ON_TRIP
            driver_state.cas(d.id, "OFFERED", "AVAILABLE")   # declined/timeout
    escalate(ride)   # widen ring, relax ranking, or queue

The pattern to name: read from the fast stale index, enforce on a small strongly-consistent core. The geo index proposes; the driver-state store (the only strongly consistent, tiny, per-driver record) disposes. Offers carry TTLs because drivers are humans holding phones in cars — every state that depends on a human has a timeout and a compensation path.

Ranking is ETA-based, not distance-based — a driver 800m away across a divided highway is worse than one 2km down the same road — which is why the road-network ETA model sits inside the matching loop, not just the app display.

Trip state: the part that must not lose writes

Once matched, the trip becomes a durable state machine (REQUESTED → MATCHED → PICKUP → ON_TRIP → COMPLETED/CANCELED) in a replicated transactional store, transitions idempotent (clients retry over flaky mobile networks — every transition carries a request ID). Note the storage split the design has quietly produced, and say it explicitly in the interview: ephemeral high-volume data in memory; low-volume monetary state machine fully durable. Getting these reversed is the failure mode — durable GPS pings melt your database while in-memory trip state loses revenue.

Live trip tracking (rider watching the car approach) is a pub/sub channel per trip fed by the same location stream, filtered to the matched driver — cheap fan-out of one driver's pings to one rider.

Surge: pricing as a control loop

Per cell (coarser than matching cells), compute supply (available drivers) vs demand (open requests + recent unfulfilled) over a sliding window; when the ratio crosses thresholds, apply a multiplier. Design points that show maturity: smooth it (hysteresis/decay — flickering 1.0→2.1→1.0 destroys trust), precompute per-cell multipliers on a tick (pricing reads a table; it is not a per-request computation), and acknowledge the feedback loop — surge changes both rider demand and driver supply, which is the point, but it means thresholds need damping or the system oscillates. Surge is a rate limiter implemented in prices.

Interview probe	Answer sketch
Driver's app dies mid-trip?	Trip state is server-side durable; app reattaches by trip ID; missed pings ≠ lost trip
Two riders, one driver?	CAS on driver status — the geo index is advisory, never authoritative
City-scale hot spot (stadium)?	Cell splitting + surge damping + expand-ring matching; admission control on requests as last resort
Why not PostGIS for live positions?	1M writes/sec of 4-second-lifetime data through WAL + B-tree/GiST maintenance buys durability nobody needs

The transferable shape: a fast lossy read path proposing, a small consistent core deciding, a durable state machine recording — three tiers with three different consistency budgets, chosen per invariant instead of one-size-fits-all.