Design a Ride-Hailing Service (Uber / Lyft)

TL;DR. Ride-hailing is a two-sided marketplace where physical state (moving vehicles, moving riders) collides with a globally distributed backend that must match them in under one second. Uber completed over 15 billion trips in FY2025 (up from 11.3B in FY2024) across 70+ countries ^[1][2]. The system absorbs ~1.25 million GPS updates per second, indexes them in Uber's H3 hexagonal grid ^[3], runs batched bipartite matching every 2 to 5 seconds ^[4], and orchestrates each trip through a durable Cadence workflow ^[5]. The pivotal trade-off: batched matching adds visible latency but produces documented double-digit utility gains over greedy dispatch.

Learning Objectives#

After this module, you will be able to:

• Choose a geospatial indexing scheme (H3, S2, geohash, quadtree) and defend the trade-offs for ride matching
• Design a streaming pipeline that ingests millions of driver location updates per second
• Apply batched bipartite matching under latency and supply constraints
• Justify additive surge pricing as a market-clearing mechanism with incentive-compatibility guarantees
• Model a trip as a durable workflow that survives client restarts and network partitions
• Estimate capacity for peak QPS on the geo index and downstream notification fan-out

Intuition#

Imagine you run a taxi dispatch office in the 1970s. A wall-sized map of the city hangs behind you, covered in magnets. Each magnet is a cab. Every few seconds, drivers radio in their cross-street, and you slide their magnet to the new position.

When a customer calls, you glance at the map, find the three closest magnets, and radio the nearest driver. Simple. But on New Year's Eve the phone rings 50 times a minute. You cannot keep up. You hire more dispatchers, split the map into zones, and give each dispatcher a zone. Now each person handles fewer calls, but a customer on a zone boundary might get a worse match because the dispatcher cannot see the magnet one block away in the next zone.

That is the ride-hailing problem at its core. The "magnets" are GPS pings from 5 million drivers. The "map zones" are hexagonal cells in a geospatial index. The "dispatcher" is a matching algorithm that runs every few seconds. The "New Year's Eve rush" is surge pricing. And the "zone boundary" problem is why hexagons (one neighbor class, uniform center-to-center distance) beat squares (two neighbor classes, diagonal distortion).

The engineering challenge is not dispatching one ride. It is dispatching over 40 million rides per day ^[2:1] while every magnet moves every 4 seconds ^[6], the map spans 10,000+ cities ^[7], and the dispatcher must decide in under one second.

Requirements#

Clarifying Questions#

• Q: What is the geographic scope? Assume: Global, 70+ countries, 10,000+ cities ^[7:1]. Multi-region active-active.
• Q: Human drivers only, or autonomous vehicles too? Assume: Primarily human. AVs are a driver type with geofence constraints (Waymo, Avride, and 20+ partners as of 2026) ^[8].
• Q: 1:1 rides only, or shared/pool rides? Assume: Both. Shared rides turn bipartite matching into a many-to-one variant.
• Q: What latency target for dispatch? Assume: p99 < 1 second for geo lookup + ETA scoring; 2 to 5 seconds for the batch window.
• Q: What availability target? Assume: 99.95% for the dispatch path. Degraded mode (greedy fallback) rather than refusal.
• Q: How fresh must driver locations be? Assume: 4-second update interval from driver apps ^[6:1]. Stale by at most one interval.

Functional Requirements#

• Rider requests a trip with pickup and destination; system matches to a nearby driver within seconds.
• Driver receives ride offers via push; accepts or declines within 15 seconds.
• Real-time ETA updates for both rider (pickup ETA) and driver (navigation).
• Dynamic pricing adjusts fares based on local supply-demand imbalance.
• Trip lifecycle tracking from request through payment and rating.
• Shared rides: multiple riders matched to one driver with detour optimization.

Non-Functional Requirements#

• Load: 40M+ trips/day (FY2025), ~1.25M location updates/sec peak, tens of millions of concurrent connections ^[2:2][6:2].
• Latency: p99 < 100 ms for geo index queries; p99 < 1s end-to-end dispatch (excluding batch window).
• Availability: 99.95% for the dispatch path.
• Consistency: Eventual for location index (4s staleness acceptable); strong for trip state transitions.
• Durability: Trip records must survive any single-region failure.

Capacity Estimation#

Key ratios:

• Read:write on geo index is ~4:1 (riders query, drivers write).
• Location updates dominate write bandwidth: 1.25M/sec x ~100 bytes = ~125 MB/sec ingress to Kafka.
• Hot cells (Manhattan, Bengaluru) concentrate 100x average traffic on a single partition.

API and Data Model#

API Design#

POST /v1/trips
  Body: { "pickup": {"lat": 40.7128, "lng": -74.0060}, "destination": {...}, "ride_type": "pool" }
  Returns: 201 { "trip_id": "uuid", "status": "matching", "estimated_pickup": "3min" }

GET /v1/trips/{trip_id}
  Returns: 200 { "status": "en_route", "driver": {...}, "eta_pickup": "2min", "eta_dest": "14min" }

POST /v1/drivers/{driver_id}/location
  Body: { "lat": 40.7130, "lng": -74.0055, "heading": 270, "speed_mps": 8.5 }
  Returns: 204

POST /v1/trips/{trip_id}/accept
  Idempotency-Key: <uuid>
  Returns: 200 { "trip_id": "...", "rider": {...}, "pickup": {...} }

GET /v1/surge?lat=40.7128&lng=-74.0060
  Returns: 200 { "multiplier": 1.0, "surcharge_cents": 500, "cell_id": "8928308280fffff" }

Pagination on trip history uses cursor-based ?before=<trip_id>&limit=50. Rate limiting: 1 location update per 3 seconds per driver (server-side dedup).

Data Model#

-- Trip store (Schemaless / Cassandra)
table trips (
  trip_id         uuid,
  rider_id        uuid,
  driver_id       uuid,
  status          enum(requested, offered, accepted, en_route, in_trip, completed, cancelled),
  pickup_cell     bigint,       -- H3 res 9 cell ID
  pickup_lat      double,
  pickup_lng      double,
  dest_lat        double,
  dest_lng        double,
  fare_cents      int,
  surge_cents     int,
  created_at      timestamp,
  completed_at    timestamp,
  partition_key:  trip_id
)

-- Driver location (in-memory geo index, backed by Kafka log)
table driver_locations (
  driver_id       uuid,
  cell_id         bigint,       -- H3 res 9
  lat             double,
  lng             double,
  heading         smallint,
  speed_mps       float,
  updated_at      timestamp,
  partition_key:  cell_id       -- colocates proximity queries
)

Uber's Schemaless is MySQL-backed, append-only with immutable cells keyed by (row, column, ref_key) ^[10][11]. New versions write a new cell rather than overwriting, giving an audit trail for every trip state change.

High-Level Architecture#

Driver locations stream through the mobile gateway into Kafka partitioned by H3 cell ID; Flink materializes per-cell state consumed by dispatch, surge, and ETA prediction.

Write path: Driver app pushes lat/lng every 4 seconds over a persistent gRPC connection ^[12]. The gateway computes the H3 cell ID at resolution 9 and publishes to Kafka. Flink windows the stream (1 to 5 seconds) and updates the in-memory geo index.

Read path: When a rider requests a trip, the gateway queries the geo index with a k-ring expansion (k=7 at res 9, covering ~1.3 km). Candidate drivers are scored by DeepETA (served via Michelangelo at 10M predictions/sec peak ^[7:3]), then fed into the batched bipartite matcher.

Async path: Once matched, a Cadence workflow owns the trip lifecycle. State transitions (accepted, en-route, in-trip, completed, paid) are durable events persisted to Cassandra. The workflow survives backend restarts and app crashes ^[5:1][13].

Deep Dives#

Deep dive 1: Geospatial indexing with H3#

The problem. Find all available drivers within ~1.3 km of a pickup point, updated every 4 seconds, at 1.25M writes/sec and millions of reads/sec globally.

Why generic indexes fail. A B-tree cannot answer k-NN in 2-D. A hash index cannot answer range. A quadtree adapts to density but data-dependent splits mean two replicas drift, which Uber cites as one reason they moved to H3 ^[14].

H3's design. Built on a Dymaxion-oriented spherical icosahedron with aperture-7 subdivision. Each resolution's total cells follows c(r) = 2 + 120 * 7^r, reaching 569.7 trillion cells at res 15 ^[3:1]. Resolution 9 (~201 m average edge, ~0.105 km^2 area) is used for matching; resolution 7 (~1.4 km edge, ~5.16 km^2 area) for surge zones ^[3:2].

The k-ring primitive. gridDisk(origin, k) returns all cells within grid distance k. The formula is 3k(k+1)+1 cells ^[15]. At res 9, k=7 returns 169 cells covering ~1.3 km radius, the typical urban matching radius.

At resolution 9, expanding the k-ring from 1 to 7 covers the typical urban matching radius; the matcher scores all drivers found within this disk by predicted pickup ETA.

Why not S2? S2 (Google) projects 6 cube faces to the sphere with aperture-4 quadtree subdivision and 31 levels down to ~1 cm cells ^[16]. Exact containment on subdivision is its strength. But square cells mean two neighbor classes (edge vs corner), complicating uniform radius expansion ^[17]. H3's single-distance neighbors simplify convolutions and k-ring queries.

The 12 pentagons. Hexagons cannot tile a sphere. H3 has 12 pentagons per resolution placed over ocean in the Dymaxion orientation. Code must handle E_PENTAGON errors ^[15:1]. Urban pickups never hit them.

Deep dive 2: Dispatch and matching algorithm#

The problem. Given N open ride requests and M available drivers in a region, produce assignments that maximize marketplace utility (minimize rider wait, maximize driver earnings, observe fairness constraints).

Greedy FCFS. Assign the nearest driver to each request on arrival. Simple, fair, low latency. But at rush hour, dispatching the only nearby driver to a mediocre match at t=0 leaves a high-value request unmatched at t=1 ^[4:1].

Batched bipartite matching. Lyft publicly describes dispatch as a weighted bipartite matching problem: drivers on one side, riders on the other, edge weights are a learned utility (pickup ETA, driver future earnings, detour cost). The LP relaxation gives integer solutions for bipartite graphs by Edmonds' theorem, solvable by the Hungarian algorithm in polynomial time ^[4:2].

A rider tap resolves into an H3 k-ring lookup, ETA scoring, and a batched bipartite match; the geo+ETA path targets sub-second while the batch window adds 2 to 5 seconds of visible latency.

The batching window trade-off. Longer batches give a fuller picture of supply and demand, producing better matches and lower wait times, but they delay ride assignments and risk cancellations ^[4:3]. Uber and Lyft tune this per-market: 2 seconds in low-density suburbs, 5 seconds in Manhattan at rush hour.

RL augmentation. Lyft's reinforcement learning system (deployed globally in 2021) adds driver future-earnings estimates into edge weights. After global rollout, it served millions of additional riders per year and drove more than $30M/year of incremental revenue ^[18]. DiDi uses end-to-end RL for micro-view order dispatching ^[19][20].

Shared rides (UberPool). The graph is no longer strictly bipartite when one driver serves multiple riders. The problem becomes a constrained vehicle routing problem. Uber uses ILP solvers with detour-time constraints and fairness bounds on per-rider price ^[4:4].

Deep dive 3: Surge pricing as real-time market clearing#

The problem. When demand exceeds supply in a geographic area, the system must either refuse rides or raise prices to suppress marginal demand and attract supply. Refusal is worse.

Multiplicative vs additive. Historically Uber used multiplicative surge ("3.0x"). Garg and Nazerzadeh (INFORMS Management Science, 2022) proved multiplicative surge is not incentive-compatible in dynamic settings: drivers who reason about future surge trips have a perverse incentive to reject short non-surge trips ^[21]. Their paper proposes a structured additive mechanism that Uber deployed in production ^[21:1].

The feedback loop. Surge is computed per H3 cell (res 7) using short-window supply/demand signals with exponential moving average smoothing. The loop must be damped: naive feedback without dead-time causes oscillation where surge rises, suppresses demand, rises further on stale data, and leaves the market empty.

Surge is a damped feedback loop on per-cell supply-demand imbalance; additive rather than multiplicative, with EMA smoothing and a hard cap to prevent overshoot.

Political and regulatory risk. New Year's Eve 2015 produced 9x surges and $1,114 bills ^[22]. The 2016 Chelsea bombing saw surge active at the explosion site ^[23]. NSW Australia forced Uber to cap surge during public transport failures ^[24]. Academic work shows drivers can collude to manufacture perceived supply shortages ^[25].

Joint optimization. Research shows that joint optimization of dynamic pricing and dynamic wage "mitigates price variability while increasing capacity utilization, trip throughput, and welfare" ^[26].

Deep dive 4: Trip state machine with Cadence workflow orchestration#

The problem. A trip is a long-running stateful process spanning minutes to hours. It must survive app crashes, network drops, backend restarts, and multi-step payment flows across millions of concurrent instances.

Why not a database state column? A simple UPDATE trips SET status = 'accepted' works for one trip. At 1 million concurrent trips with timeouts, retries, compensation (refunds), and multi-step sagas (charge + dispatch + navigate + complete + pay + rate), the state machine logic overwhelms application code. Every timeout needs a cron job. Every retry needs idempotency plumbing.

Cadence/Temporal. Uber built Cadence specifically for this: a durable workflow engine that persists all workflow state to Cassandra, allowing a workflow function to be paused for hours and resumed exactly where it left off ^[5:2][13:1]. Each state transition is an activity with an idempotency key. If the payment service times out, Cadence retries with the same key. If the rider cancels mid-trip, a compensation activity reverses the charge.

The fulfillment workflow owns the trip lifecycle across app restarts and network drops; each transition is a durable Cadence event with automatic retry and compensation.

Scale. Uber's Fulfillment Platform owns the end-to-end trip lifecycle across "millions of active participants" ^[5:3]. Cadence has been in production since 2017 and tagged its stable v1.0 release on June 22, 2023 ^[13:2]. Maxim Fateev later forked Cadence to create Temporal (MIT-licensed), inheriting the same feature set ^[27].

Ringpop (historical). Uber's 2015-era application-layer sharding library kept cooperating nodes in a consistent-hash ring with SWIM gossip over TCP ^[28][29]. It is no longer under active development; new services adopt Cadence/Temporal for stateful orchestration ^[28:1].

Real-World Example#

Uber Mobility, FY2025: ~15 billion trips (annualized), 202 million monthly active users, $193 billion gross bookings.

Uber reached a 15-billion annual trip run rate by Q4 2025 (3.8B trips in Q4, +22% YoY), with over 40 million trips per day and 202 million monthly active platform consumers ^[2:5]. For reference, FY2024 totaled 11.273 billion trips with 171 million MAPCs and $162.8 billion gross bookings ^[1:1]. The platform operates in 70+ countries and 10,000+ cities ^[7:4].

The ML stack. DeepETA replaced an XGBoost baseline with a deep transformer-style model that returns ETAs within milliseconds ^[30]. A companion residual network (DeeprETA) refines naive route-planner ETAs and reports both offline MAE improvements and online wins ^[31]. Both are served through Michelangelo, which as of 2024 runs ~400 active ML projects, 5,000+ models in production, and serves 10 million real-time predictions per second at peak ^[7:5].

Autonomous integration (2025-2026). Waymo launched on Uber in Austin (initially 37 square miles, expanded to ~130 square miles by early 2026) in March 2025 and expanded to Atlanta (~65 square miles) in June 2025 ^[32]. Architecturally, an AV is another driver type in the matching pipeline: AV eligibility is a driver attribute (geofence, vehicle type, opt-in). Uber has over 20 AV partnerships (including Waymo, Avride, May Mobility, Baidu Apollo Go, Lucid-Nuro, Rivian, NVIDIA) and aims for AV operations in 15 cities by end of 2026 ^[8:1]. Waymo independently runs ~500,000 paid robotaxi rides per week across 10 US cities as of early 2026 ^[33].

Trade-offs#

The single biggest meta-decision: greedy vs batched matching. Greedy is correct for sparse markets (rural, late night) where the next request may not arrive for 30 seconds. Batched is correct for dense markets (Manhattan rush hour) where 50 requests arrive in the same 3-second window. Production systems run both and switch based on real-time density signals.

Scaling and Failure Modes#

At 10x load (400M trips/day): The geo index becomes the bottleneck. Hot cells (Manhattan, Bengaluru) saturate single partitions. Mitigation: sub-shard within cells by driver ID hash; replicate hot cells across multiple nodes; increase H3 resolution to res 10 (~38,000 m^2) for finer partitioning during events.

At 100x load (4B trips/day): Kafka partitions by cell hash become insufficient. Mitigation: multi-tier partitioning (region, then city, then cell); dedicated Kafka clusters per metro; edge-local matching that only escalates to regional when local supply is exhausted.

At 1000x load: The architecture shifts to fully edge-local matching with gossip-based supply sharing between adjacent edge nodes. The central platform becomes an analytics and settlement layer, not a real-time dispatch layer.

Failure modes:

• Regional outage: Riders in the affected region fail over to the nearest healthy region. Location data is stale by the failover duration (seconds to minutes). Degraded mode: greedy matching with wider k-ring expansion until the geo index repopulates. Uber's 2020 global outage lasted 1 to 2 hours and prevented trip requests entirely ^[36].
• Surge engine failure: Freeze surge at the last computed value. Do not set surge to zero (causes demand spike that overwhelms supply). Alert on-call; manual override available per city.
• Payment service timeout: Cadence workflow retries with the same idempotency key. If payment fails after 3 retries, the trip completes but payment settles asynchronously. Uber's 2023 surge pay-split glitch (riders charged surge, drivers not paid) is a real-world example of this failure class ^[37].

Common Pitfalls#

Follow-up Questions#

Exercise#

Exercise 1: Concert surge scenario#

A concert ends and 30,000 people hit the app within 5 minutes in a 4 km^2 area. Supply in that area is 800 drivers. Design the system's response: how the matching service avoids thrashing, how surge pricing ramps without overshooting, and how you communicate ETAs honestly.

Key Takeaways#

• Geospatial indexing is the foundation. Pick H3 (hexagons, uniform neighbors, O(k^2) expansion) and commit. Mixing schemes creates seam bugs at boundaries.
• Location updates are a firehose. 5M drivers / 4s = 1.25M updates/sec. Partition by cell hash and aggregate in-stream; never query the raw stream directly.
• Batched matching beats greedy at high density. The cost is 2 to 5 seconds of visible latency; the win is documented $30M+/year at Lyft ^[18:3].
• Surge is market clearing, not revenue extraction. Additive surge is incentive-compatible; multiplicative is not ^[21:4]. Cap it, damp it, and be transparent.
• Model trips as durable workflows. Cadence/Temporal eliminates split-brain between payments and dispatch. Every transition is an activity with retry and compensation.
• Every component has a soft-fail mode. If the matcher is down, fall back to greedy. If surge is down, freeze at last value. The worst outcome is refusal to dispatch.

Further Reading#

• H3: Uber's Hexagonal Hierarchical Spatial Index. The canonical documentation for H3's cell hierarchy, resolution tables, and API; start here before implementing any geo-matching.
• Garg & Nazerzadeh, "Driver Surge Pricing" (arXiv:1905.07544). The Uber-adjacent paper proving multiplicative surge is not incentive-compatible and proposing the additive mechanism now in production.
• Azagirre et al., "A Better Match for Drivers and Riders: RL at Lyft" (arXiv:2310.13810). Online RL for matching with documented $30M+/year lift; the best public description of production matching augmentation.
• Lyft Engineering: Solving Dispatch in a Ridesharing Problem Space. Public bipartite-matching formulation with the LP relaxation argument and batching trade-offs.
• Cadence Workflow Engine (GitHub). The orchestration engine that runs Uber's trip fulfillment; read the README for the "microservice architecture beyond request-reply" motivation.
• Uber Engineering: DeepETA. How Uber replaced XGBoost with a deep model for ETA prediction, served at 10M predictions/sec via Michelangelo.
• H3 Resolution Tables. Edge lengths and areas at every resolution; the numbers you need for back-of-envelope estimation in interviews.
• Uber Q4 and Full Year 2024 Results. FY24 scale numbers: 11.3B trips, 171M MAPCs, $162.8B gross bookings. See also FY2025 results for latest: ~15B trip run rate, 202M MAPCs, $193B gross bookings.

Flashcards#

References#