Uber / Ride Matching
A real-time ride-hailing system: ingesting driver locations, indexing them geospatially (geohash/H3), matching nearby drivers to riders, and computing surge pricing.
By Ratish Jain · Updated
Problem
Design Uber's core: match a rider requesting a ride with the best nearby available driver, in real time, in every city simultaneously.
The defining problem is geospatial: millions of drivers continuously report GPS, and each ride request must answer 'which available drivers are within a few km of this point, right now?' extremely fast. This requires a specialized spatial index (geohash, quadtree, or Uber's H3 hex grid) rather than a plain database, plus real-time location ingestion and surge pricing based on live supply/demand.
Functional Requirements
- Drivers publish live location; riders request a ride from a pickup point.
- Match a rider to the nearest suitable available driver.
- Show nearby drivers and live ETA on the rider's map.
- Track trip lifecycle: requested → accepted → in-progress → completed.
- Compute surge pricing from real-time supply/demand per area.
Non-Functional Requirements
- Match latency in the low seconds; location freshness within a few seconds.
- Handle very high write volume from continuous driver pings.
- High availability per city; a region outage shouldn't affect others.
- Geospatial queries in tens of milliseconds.
- Consistency for trip state; eventual consistency acceptable for locations.
Capacity Estimation
- Active drivers
- ~5M concurrently online
- Location pings
- 1 ping/4s → ~1.25M writes/s
- Ride requests
- ~20M/day → ~250 req/s avg, higher peaks
- Geo query latency
- target < 50 ms per nearby search
- Location payload
- ~50 B (id, lat, lng, ts) per ping
- Ingest bandwidth
- ~1.25M × 50B ≈ 60 MB/s
APIs
- POST /location
- updateLocation(driverId, lat, lng, ts)
- POST /rides
- requestRide(riderId, pickup, dest) → rideId
- POST /rides/:id/accept
- accept(rideId, driverId) → tripState
- GET /nearby
- nearbyDrivers(lat, lng, radius) → Driver[]
Components
- Gateway: maintains WebSocket/long-lived connections to driver and rider apps.
- Location service: ingests high-volume pings and upserts positions into the geo index.
- Geo index (Redis + H3/geohash): in-memory spatial index mapping cell IDs → drivers for fast radius queries.
- Matching service: on a request, queries nearby available drivers and runs the assignment algorithm.
- Trip service + Trip DB: authoritative, transactional trip lifecycle state.
- Pricing/surge service: aggregates supply vs demand per cell to compute multipliers.
Request Flow
- 1Driver apps send location pings every few seconds over their connection.
- 2The location service upserts each driver's position into the geo index, keyed by spatial cell.
- 3A rider requests a ride from a pickup point; the request reaches the matching service.
- 4Matching computes the pickup's spatial cell + neighboring cells and queries available drivers within radius.
- 5It ranks candidates (ETA, rating) and offers the ride; the accepting driver is locked and a trip row is created.
- 6Both parties get live updates over their connections; surge multiplier is applied from the pricing service.
Flow Diagram
Data / Storage Design
Location is ephemeral, high-write data — stored in an in-memory geo index (Redis geo commands or a custom H3/geohash structure), not a durable DB. Each driver maps to a spatial cell; a nearby query scans the target cell plus its ring of neighbors, turning an O(n) distance scan into an O(1)-ish cell lookup.
H3 (hexagonal hierarchical index) is Uber's choice because hexagons have uniform neighbor distance, avoiding the edge distortions of square geohash cells. Trip state is the durable, transactional part — stored in a strongly-consistent DB partitioned by city/region, since a trip has clear ownership and must not be double-assigned.
Data Model
Scaling Strategy
The system shards by geography: each city/region is largely independent, so services and the geo index partition by area and scale per-market. This localizes load and blast radius — an outage in one region doesn't affect others.
The location write firehose is handled by keeping positions in memory and treating them as replaceable (last-write-wins per driver). Matching parallelizes naturally since requests only touch a small set of nearby cells. Surge is computed per cell from streaming supply/demand aggregates, often via a stream processor over the ping/request events.
Bottlenecks & Failure Scenarios
- Location write firehose: mitigated by in-memory upserts and last-write-wins; batch/throttle ping frequency.
- Hot cell in a dense downtown — sub-partition high-density cells or use finer H3 resolution there.
- Double-booking a driver: prevented with an atomic lock/compare-and-set when offering/accepting.
- Geo index node loss: locations are ephemeral and self-heal within seconds as pings resume.
- Cross-region dependency: kept minimal so a regional failure is isolated.
Design Tradeoffs
- Spatial cell indexing makes 'nearby' queries O(cells) instead of scanning all drivers.
- In-memory ephemeral location store handles the write firehose cheaply.
- Geo-sharding isolates markets and bounds failure blast radius.
- Cell boundaries mean a nearby query must check neighbor cells, adding logic.
- Ephemeral location store loses precise history unless separately logged.
- Surge and matching fairness are hard to tune and can feel opaque to users.
Common Interview Questions
Index drivers by spatial cell (geohash/H3). Map the pickup point to its cell, query that cell plus its neighbor ring, and distance-filter only those candidates — avoiding a full scan of millions of drivers.
Hexagons have uniform distance to all six neighbors, so 'nearby' is consistent in every direction, whereas square geohash cells distort near edges/poles and have non-uniform neighbor distances. Hierarchical H3 also lets you change resolution per density.
Treat driver assignment as a lock: use an atomic compare-and-set / conditional write when offering and accepting, so only one match can claim a driver; others see it's taken and pick another.
- →Index drivers by spatial cell (H3/geohash) in memory for fast nearby queries.
- →Location data is ephemeral, high-write, last-write-wins.
- →Match = query pickup cell + neighbors, rank by ETA, lock driver.
- →Trip state is durable and transactional; locations are not.
- →Shard by geography to isolate markets and scale per city.
Related
Everything on Archprimer is connected — follow the graph.