Uber / Ride-Sharing

Sharpened prompt. Design a ride-hailing platform for 5M concurrent drivers and 20M daily riders, matching a request to a driver in under 2 seconds, pricing dynamically from real-time supply and demand, keeping rider and driver views of a trip consistent through cellular dead zones, and snapping noisy GPS to actual roads for fare calculation.

Everything here is a spatial-temporal problem: the data is location plus time, it is enormous in volume, individually low-value, and mostly stale within seconds. The design follows from treating location as a stream, not as state.

1. Problem framing

Functional requirements

• Drivers stream location; riders request rides from A to B.
• Match a rider to a nearby, available, suitable driver.
• Price the trip, including surge; recompute a fare from the actual route driven.
• Track the trip through its lifecycle; handle cancellations at any stage.

Non-functional requirements

Property	Target	Consequence
Match latency	P99 < 2s from request to driver offer	Candidate lookup must be an in-memory operation
Location ingest	1M writes/sec, lossy-tolerant	Never write raw pings to a durable transactional store
Trip state	Strongly consistent, single source of truth	Trips are money; they get a real database and conditional updates
Availability	Matching degrades before it fails	Fall back to simpler matching rather than returning no drivers

Back-of-the-envelope

Drivers:     5M concurrent, pinging every 4s      = 1.25M location writes/sec
Payload:     ~50 B/ping -> 62 MB/sec -> 5.4 TB/day of raw pings
             (retain 7 days for analytics, then aggregate; never keep it hot)
Rides:       20M/day = 230/sec avg, ~1,000/sec peak
Matching:    each request scans ~50-200 nearby drivers -> trivially cheap IF the
             candidate set is in memory. Impossible if it's a database query.
Trip state:  20M trips/day × ~10 transitions × 500 B = 100 GB/day

The asymmetry is the headline: location writes outnumber ride requests by ~5,000:1, so location must be cheap and ephemeral while trips are expensive and durable. Two completely different storage strategies in one system.

2. High-level architecture

3. Component inventory

Component	Concrete choice	Why this one
Location transport	gRPC bidirectional streaming into Kafka, partitioned by H3 cell	Cell partitioning means a dispatch query reads one partition's worth of state
Geo index	In-memory per-cell driver map with TTL (Redis or a sharded Go service)	Reads must be memory-speed; staleness beyond 30s is worse than useless
Supply/demand	Flink windows over the same Kafka stream	The stream you already have; no second ingest path
Trip store	CockroachDB / Spanner with optimistic concurrency	Trips need real transactions and multi-region correctness
Routing/ETA	OSRM or Valhalla over OSM, plus an ML correction layer	Graph routing gives the path; ML corrects it against reality
Map matching	HMM + Viterbi	The standard, and it handles GPS noise properly
Offers	A dedicated offer manager with per-driver locks	Prevents double-offering the same driver

4. The toughest parts

4.1 A million location writes per second that nobody will ever read

Why it's hard. 1.25M pings/sec into any durable store is a punishing write load, and 99.99% of those pings are read exactly zero times — a driver's position at 14:32:04 matters only if someone requests a ride nearby in the next few seconds. Writing them to Cassandra is an expensive way to generate garbage.

Solution — treat location as a stream with a TTL'd materialised view, not as stored state.

// Gateway: filter aggressively before anything downstream sees the ping.
func (g *Gateway) OnPing(p Ping) {
    last := g.lastSeen[p.DriverID]

    // 1. Drop pings that carry no information.
    if p.Time.Sub(last.Time) < 2*time.Second { return }
    if haversine(p, last) < 10 && p.Speed < 1 { return }   // parked driver
    if p.Accuracy > 100 { return }                          // garbage GPS fix

    // 2. Publish to the cell's partition. Ordering within a cell is what matters.
    cell := h3.LatLngToCell(p.Lat, p.Lng, 8)               // ~460 m edge
    g.kafka.Produce(topic, key(cell), encode(p))

    // 3. Update the in-memory index directly for read-your-writes on dispatch.
    g.geo.Upsert(cell, p.DriverID, p, 30*time.Second)      // TTL: no explicit deletes
    g.lastSeen[p.DriverID] = p
}

Three ideas doing the work. Filtering at the edge removes 40–60% of pings (parked drivers, redundant fixes) before they cost anything. TTL instead of deletion means a driver who goes offline, crashes, or loses signal simply ages out — you never need a reliable "driver disconnected" event, which is fortunate because you will never reliably get one. And partitioning by cell rather than driver means dispatch reads one partition instead of scattering across the fleet.

Retain raw pings in Kafka for a few days (for map matching, disputes, and model training) and let them expire. Nothing durable is needed on the hot path.

4.2 Dispatch: finding and committing a driver in two seconds

Why it's hard. "Nearest driver" is wrong in several ways at once. The nearest driver by straight-line distance may be across a river with a 15-minute drive. Offering to the nearest driver only, then waiting 15 seconds for them to decline, then offering to the next, blows the latency budget. Offering to everyone simultaneously means several drivers accept and you must renege on all but one — the worst possible driver experience.

Solution — candidate retrieval, road-aware scoring, then sequenced offers with short timeouts and hard locks.

async def dispatch(request) -> Driver | None:
    # 1. Candidates: expanding ring search over H3 cells, in memory. ~1ms.
    candidates = []
    for k in (1, 2, 3):                                   # ~0.5 km, 1 km, 1.5 km
        cells = h3.grid_disk(request.origin_cell, k)
        candidates = await geo.drivers_in(cells, status="available",
                                          vehicle=request.product)
        if len(candidates) >= 10: break

    # 2. Score by ROAD ETA, not haversine. Batch the routing call.
    etas = await osrm.table_eta(sources=[d.pos for d in candidates],
                                destination=request.origin)     # one call, N sources
    scored = sorted(zip(candidates, etas), key=lambda x: dispatch_score(*x, request))

    # 3. Sequential offers with a short timeout and an exclusive lock.
    for driver, eta in scored[:5]:
        if not await locks.acquire(f"driver:{driver.id}", ttl=12):
            continue                                       # already being offered
        try:
            accepted = await offer(driver, request, timeout=10)
            if accepted:
                return driver
        finally:
            await locks.release(f"driver:{driver.id}")
    return None                                            # expand radius or surge

def dispatch_score(driver, eta_s, req) -> float:
    return (eta_s                                          # primary: pickup time
          - 60 * driver.acceptance_rate                    # reward reliable drivers
          + 30 * driver.consecutive_declines               # rotate past decliners
          - 45 * (1 if driver.heading_toward(req.origin) else 0))

The exclusive lock with a TTL slightly longer than the offer timeout is the critical correctness detail: it guarantees a driver is never offered two rides at once, and the TTL guarantees a crashed dispatcher does not strand them.

Batch the routing call. OSRM's table service computes many-to-one ETAs in one request; making N individual routing calls is the difference between 5ms and 500ms.

Worth mentioning as a refinement: at high request density, sequential per-request dispatch is locally greedy and globally suboptimal. Batching requests into 3–5 second windows and solving a global assignment (the local delivery page covers the Hungarian algorithm and min-cost flow) measurably improves total pickup time — at the cost of adding the window's duration to every request. Uber does this in dense markets and not in sparse ones, which is exactly the kind of context-dependent answer interviewers reward.

4.3 Surge pricing without lag or oscillation

Why it's hard. Surge must reflect current supply and demand in a small area, updating every few seconds. Compute it over too large an area and it is meaningless (Midtown surges, Brooklyn doesn't). Compute it over too small an area and the sample size is tiny and the multiplier oscillates wildly — 1.0 to 2.4 to 1.2 within a minute, which enrages riders and causes drivers to chase phantom surges. And it is a feedback loop: surge attracts drivers, which reduces surge, which repels drivers.

Solution — hierarchical spatial aggregation with temporal smoothing and hysteresis.

// Flink: sliding windows over the same location stream, keyed by H3 cell.
locations
  .keyBy(e -> e.h3Res8)                                  // ~0.7 km² cells
  .window(SlidingEventTimeWindows.of(Time.minutes(2), Time.seconds(15)))
  .aggregate(new SupplyDemand())                          // available drivers, open requests
  .map(sd -> {
      // Borrow from the parent cell when the sample is too small to be meaningful.
      if (sd.requests + sd.drivers < 10) sd = sd.mergeWith(parentCell(sd.cell, 7));

      double ratio = sd.requests / Math.max(1.0, sd.drivers);
      double raw   = clamp(1.0 + 0.6 * Math.log1p(Math.max(0, ratio - 1.0)), 1.0, 3.0);

      // Exponential smoothing: no jumps from one window to the next.
      double prev  = state.value();
      double next  = 0.7 * prev + 0.3 * raw;

      // Hysteresis: require a meaningful change before moving the displayed value,
      // so the rider-facing number is stable.
      return Math.abs(next - prev) < 0.15 ? prev : round(next, 0.1);
  })
  .addSink(redisSink);                                    // read by dispatch and pricing

Four mechanisms, each fixing a specific failure: parent-cell borrowing fixes small samples, logarithmic scaling keeps the multiplier from exploding at extreme ratios, exponential smoothing removes window-to-window jitter, and hysteresis stops the displayed number from flickering.

Two product-level details worth adding. Lock the multiplier at quote time — the rider sees 1.8× and is charged 1.8× even if it moves to 2.1× while they decide. Charging a different price than quoted is a trust and regulatory problem, not an engineering one. And show drivers the surge map, since the point of surge is to reposition supply; a multiplier nobody can see does nothing.

4.4 The trip state machine and the cellular dead zone

Why it's hard. A trip moves through requested → matched → driver_arriving → arrived → in_progress → completed. Both apps hold a local view. Cellular coverage drops in tunnels, garages, and rural stretches. The driver taps "arrived" with no signal; the rider's app still shows "on the way"; the driver's retry lands three minutes later, out of order, after a "start trip" event that got through on a different network. Money depends on getting this right — wait-time fees, cancellation fees, and the fare itself.

Solution — a server-authoritative state machine with conditional transitions and client-side event queuing.

-- Optimistic concurrency: the update applies only from the expected prior state.
UPDATE trips
   SET state = 'in_progress', version = version + 1, started_at = :ts
 WHERE trip_id = :id
   AND state = 'arrived'         -- explicit legal predecessor
   AND version = :expected_version;
-- 0 rows affected -> the transition is invalid or stale. Return current state; the
-- client reconciles to the server's truth instead of forcing its own.

// Client: never assume a transition succeeded. Queue, retry, reconcile.
class TripEventQueue {
    private val pending = PersistentQueue<TripEvent>()      // survives app restart

    fun emit(e: TripEvent) {
        e.clientSeq = nextSeq()                             // per-trip ordering
        e.idempotencyKey = "${e.tripId}:${e.type}:${e.clientSeq}"
        pending.add(e)
        applyOptimistically(e)                              // UI responds instantly
        flush()
    }

    suspend fun flush() {
        while (pending.isNotEmpty()) {
            val e = pending.peek()
            when (val r = api.submit(e)) {                  // idempotent by key
                is Accepted -> { pending.pop(); reconcile(r.serverState) }
                is Conflict -> { pending.pop(); reconcile(r.serverState) } // server wins
                is NetworkError -> { delay(backoff()); }    // keep it queued
            }
        }
    }
}

The rules that make this work: the server's state is the truth and clients reconcile to it (never the reverse); transitions are conditional on the expected prior state, so out-of-order arrivals fail safely rather than corrupting the trip; every event carries an idempotency key, so a retry after a successful-but-unacknowledged call is a no-op; and the client applies optimistically so the UI stays responsive while the queue drains.

Add a timeout-based escape for each state: if a trip sits in driver_arriving for 20 minutes with no location updates, a reconciliation job flags it for support and applies a default resolution. Without it, dead-zone trips become permanent orphans that accumulate forever.

4.5 Snapping noisy GPS to actual roads

Why it's hard. Raw GPS has 5–50 m of error, worse in urban canyons where signals bounce off buildings. Naively snapping each point to its nearest road produces a path that teleports between a highway and the frontage road running parallel 20 m away, crosses buildings, and travels in physically impossible ways. Since the fare is computed from distance travelled, this is directly a billing-correctness problem.

Solution — Hidden Markov Model map matching with the Viterbi algorithm. The insight is that you should not choose each point's road independently: the sequence must be consistent with the road network's connectivity.

# Hidden states = candidate road segments. Observations = noisy GPS points.
# Emission: how likely is this GPS reading if the vehicle is really on segment s?
def emission_logp(point, seg, sigma=15.0):
    d = perpendicular_distance(point, seg)
    return -0.5 * (d / sigma) ** 2                      # Gaussian around the road

# Transition: how likely is moving from segment a to segment b between two fixes?
def transition_logp(a, b, gps_dist, beta=2.0):
    route_dist = road_network.shortest_path_length(a, b)
    if route_dist is None: return float("-inf")         # unreachable: forbidden
    # Penalise when the road distance disagrees with the straight-line distance —
    # this is what stops jumps to a parallel road.
    return -abs(route_dist - gps_dist) / beta

def map_match(points):
    V = [{s: emission_logp(points[0], s) for s in candidates(points[0])}]
    back = [{}]
    for t in range(1, len(points)):
        V.append({}); back.append({})
        for s in candidates(points[t]):
            best_prev, best_score = None, float("-inf")
            for ps, pscore in V[t-1].items():
                sc = pscore + transition_logp(ps, s, haversine(points[t-1], points[t]))
                if sc > best_score: best_prev, best_score = ps, sc
            V[t][s] = best_score + emission_logp(points[t], s)
            back[t][s] = best_prev
    return backtrack(V, back)                            # globally optimal path

Viterbi finds the globally most probable sequence in O(T·S²) where S is the small set of candidate segments per point (typically under 10 within a 50 m radius), so it runs comfortably in real time.

For production, use OSRM's /match service or Valhalla's Meili rather than writing this — but knowing that they implement HMM + Viterbi, and being able to explain the emission and transition terms, is exactly what distinguishes a real answer from a name-drop.

Run matching incrementally during the trip (a sliding window of the last ~30 points, so the rider sees an accurate live map) and again over the full trace at completion for the authoritative fare, since a full-trace match is more accurate than any incremental one.

4.6 ETA: the number everyone judges you by

Why it's hard. A routing engine gives you free-flow travel time over a graph. Reality includes traffic, signal timing, turn restrictions, the time to walk to the car, and the driver's actual behaviour. Users compare your ETA to their watch, so systematic bias is immediately visible — and an ETA that is too optimistic is much worse than one that is slightly pessimistic.

Solution — a routing baseline plus a learned residual correction.

def eta(origin, dest, t) -> float:
    # 1. Graph baseline with live traffic-adjusted edge weights.
    route = osrm.route(origin, dest, weights=traffic.current_weights())
    base = route.duration

    # 2. Learned correction on top. Predicting the RESIDUAL is far more stable
    #    than predicting absolute duration from scratch.
    feats = {
        "base_duration": base, "distance": route.distance,
        "n_turns": route.turn_count, "n_signals": route.signal_count,
        "hour": t.hour, "dow": t.weekday(), "is_holiday": cal.is_holiday(t),
        "weather": weather.at(origin), "origin_h3": h3_cell(origin),
        "recent_speed_ratio": traffic.recent_ratio(route.edges),  # live vs typical
    }
    residual = gbdt.predict(feats)                       # LightGBM, retrained daily
    return base * (1.0 + residual)

Two things to say about this that go beyond "train a model." First, predict the residual, not the absolute: the routing engine already encodes the road network, so the model only has to learn what the graph does not know, which makes it far more sample-efficient and far more robust to new geography. Second, calibrate asymmetrically: quote a higher percentile (P70 rather than P50) because arriving early is a delight and arriving late is a complaint. Optimising mean absolute error alone produces a product that feels consistently late.

Traffic edge weights come from the same location stream — drivers are the traffic sensors, which is a nice property to point out: the location firehose that seemed like pure cost in 4.1 is what makes ETAs good.

4.7 Fares, disputes, and money correctness

Why it's hard. The fare depends on distance and time, both derived from noisy GPS, both disputable. Riders contest charges; drivers contest earnings. A rounding difference between the rider's charge and the driver's payout creates an accounting hole that compounds across millions of trips.

Solution — compute the fare once, from the authoritative matched route, and store the full derivation.

{
  "trip_id": "t_8f14e",
  "fare_version": 3,
  "inputs": {
    "matched_route_hash": "sha256:9a2f...",
    "distance_m": 7431, "duration_s": 1042, "wait_s": 143,
    "surge_locked_at_quote": 1.8, "city_rate_card": "sf_2026_02"
  },
  "breakdown_cents": {
    "base": 250, "per_km": 1189, "per_min": 869, "wait": 143,
    "surge_delta": 1848, "airport_fee": 500, "tax": 231
  },
  "total_cents": 5030,
  "driver_payout_cents": 3773, "platform_cents": 1257
}

Three rules make this defensible. Integer cents, never floats — the same discipline as the payment system. Store the inputs and the rate-card version, so a fare can be recomputed identically two years later during a dispute. And derive the payout from the same computation rather than recalculating it independently, so rider charge and driver earnings can never disagree.

The trip's money flow then goes through a proper ledger with a saga (authorise at request, capture at completion, with compensating reversals on cancellation) — cross-reference the payment system rather than rebuilding it here.

5. What breaks first

Event	First failure	Mitigation
Rush hour in a dense city	Dispatch candidate scan + routing calls	Batched table-ETA; cap candidate count; degrade to haversine ordering
Stadium lets out	Surge oscillation, dispatch starvation	Parent-cell borrowing, smoothing, hysteresis; expand search radius
Kafka partition lag on one cell	Stale driver positions in that area	TTL expires stale drivers rather than dispatching to them
OSRM cluster degraded	ETA and dispatch scoring both suffer	Fall back to haversine + a historical speed factor; flag ETAs as approximate
Mass dead-zone trips	Orphaned trip states	Per-state timeouts with a reconciliation job and default resolutions
Trip DB region failover	Writes pause	Spanner/CockroachDB multi-region with quorum; clients queue events and retry

6. Cheat sheet

• The asymmetry: 1.25M location writes/sec vs 230 ride requests/sec. Location is an ephemeral stream with TTL; trips are durable transactions.
• Ingest: filter at the gateway (drop parked and redundant pings), partition Kafka by H3 cell, TTL'd in-memory index.
• Dispatch: expanding ring search → batched road ETAs → sequential offers with exclusive per-driver locks and short timeouts.
• Surge: H3 res-8 sliding windows, parent-cell borrowing for small samples, log scaling, smoothing, hysteresis, locked at quote.
• State: server-authoritative, conditional transitions on expected prior state, idempotent client event queue, per-state timeouts.
• Map matching: HMM + Viterbi (emission = distance to road, transition = route vs GPS distance). Use OSRM /match.
• ETA: routing baseline plus a learned residual; calibrate to P70, not P50.
• The one-liner: "Location is a firehose I never store and trips are a ledger I never lose — the design is the boundary between those two, plus a matching loop that fits in the two seconds a rider will wait."