Ride Matching (Uber / Lyft)

Functional

• Drivers continuously report their location while online.
• A rider requests a ride from pickup to destination and sees nearby drivers and an ETA.
• The system matches the rider with one available driver within a few seconds; the driver can accept or decline.
• Both parties track the trip in real time: en route to pickup, in progress, completed.
• Fare estimate before the request; final fare after the trip.

Non-functional

• Matching latency: an offer reaches a driver within ~2–3 s of the request; a match is confirmed within ~15 s including driver response time.
• Location freshness: driver positions shown to riders are no more than ~5 s stale.
• Correctness: a driver is never assigned to two riders at once; a trip, once accepted, is never lost.
• Availability: location ingestion must keep working during partial outages; it is acceptable to degrade matching to a single region.
• Scale: millions of concurrent drivers worldwide, with hot cities and sharp demand spikes (events, rain, New Year's Eve).

Out of scope

• Payments and fraud, driver onboarding, pricing models beyond a simple surge multiplier, pooled rides.

Assumptions

• 5M drivers online at peak worldwide; 20M ride requests per day.
• Drivers send location every 4 s while online.
• A location update is ~50 bytes (driver_id, lat, lng, heading, timestamp, status).

Location ingestion

• 5M drivers / 4 s = 1.25M updates/s at peak. With adaptive frequency (idle or stationary drivers every 30 s) the active fleet is perhaps 40%, so ≈ 0.5M + 0.1M ≈ 600K updates/s.
• 600K × 50 B ≈ 30 MB/s. Kafka handles this on a handful of brokers; the hard part is the per-driver write into the geo index.
• We keep only the latest position per driver in the index (5M entries × ~100 B ≈ 500 MB in memory), and stream the history to cold storage for analytics and ETA models.

Matching

• 20M requests/day ≈ 230/s average; peak in a single hot city on a bad night ≈ 100× its average, so design a city shard for ~2–5K matches/s.
• Each match queries ~9 geohash cells and scores perhaps 50–200 candidate drivers by ETA. That is a few thousand ETA lookups per second per hot city, cheap against a precomputed road graph or a cached ETA service.

Trips

• 20M trips/day × ~2 KB (states, timestamps, route summary, fare) ≈ 40 GB/day, ≈ 73 TB over 5 years. Relational-shaped data; shard by region or trip id.
• GPS breadcrumbs per trip: a 20-minute trip at 4 s intervals is 300 points × 30 B ≈ 9 KB → 180 GB/day. Store compressed in object storage, not the transactional DB.

Bandwidth

• Riders polling or streaming nearby-driver positions: 1M active riders × 1 update/3 s × ~1 KB ≈ 330 MB/s outbound. Larger than ingestion; push deltas, not full lists.

Driver side

• POST /v1/drivers/{id}/location { lat, lng, heading, speed, ts } at an adaptive interval; batched in one request when the app was offline. Often done over a persistent gRPC stream or WebSocket rather than HTTP to save handshakes.
• POST /v1/drivers/{id}/status { available | busy | offline }.
• Offer push (server → driver): { offer_id, trip_id, pickup, eta_to_pickup, expires_at }.
• POST /v1/offers/{offer_id}/accept or /decline. Accept returns 409 if the offer expired or the rider cancelled.

Rider side

• GET /v1/estimate?pickup=&dropoff= → { fare_range, eta_pickup, surge_multiplier }.
• POST /v1/rides { pickup, dropoff, product } → 202 { ride_id, status: matching }. Idempotent on a client-generated request id.
• GET /v1/rides/{id} or a WebSocket subscription → { status, driver, vehicle, driver_location, eta }.
• POST /v1/rides/{id}/cancel.
• GET /v1/nearby?lat=&lng= → driver positions for the map (anonymised, rate limited, approximate).

Internal

• LocationService.Nearby(cell_ids[], radius, limit) → candidate drivers with last position.
• EtaService.Batch(origin, destinations[]) → road-network ETAs.
• MatchingService.Request(ride_id) consumed from a queue; publishes match / no-match events.

Errors

• 404 no drivers nearby (after a bounded retry window), 409 driver already busy, 410 offer expired, 429 too many requests per rider.

Entity: driver_location (hot, in memory)

• driver_id → lat, lng, heading, updated_at, status, geohash / H3 cell id
• Only the latest position is kept. Indexed by cell so "drivers in cell X" is a set lookup.

Entity: ride_request

• ride_id (PK), rider_id, pickup, dropoff, product, requested_at, status (matching | matched | cancelled | expired)

Entity: offer

• offer_id (PK), ride_id, driver_id, sent_at, expires_at, response (pending | accepted | declined | expired)

Entity: trip

• trip_id (PK), ride_id, driver_id, rider_id, state (assigned | arriving | in_progress | completed | cancelled), timestamps per transition, route_summary, fare, region

Entity: driver (reference data)

• driver_id, vehicle, rating, home_region, current_trip_id

Storage choice

• Driver locations: Redis with geo commands (GEOADD/GEOSEARCH) or a custom in-memory service sharded by region. Volatile data; losing it means drivers re-report within seconds.
• Location history: Kafka → object storage (Parquet) for ETA model training and dispute resolution.
• Ride requests, offers, trips: a relational database (Postgres) sharded by region. Trip state transitions need transactions and the data is small.
• Trip breadcrumbs: appended to a time-series or wide-column store keyed by trip_id, or batched into object storage after completion.

Components

• Driver gateway: terminates driver connections and publishes location updates to a Kafka topic partitioned by region.
• Location service: consumes the stream and maintains the latest position per driver in a region-sharded geo index. Answers "nearby drivers" queries.
• Rider gateway / ride service: creates ride requests, exposes trip status, pushes updates to the rider.
• Matching service: one logical matcher per region. Pulls requests off a queue, finds candidates, ranks by ETA, sends offers, and confirms the match atomically.
• ETA service: road-graph routing with a cache of recent origin/destination ETAs.
• Pricing service: fare estimate and surge multiplier from supply/demand per cell.
• Trip service: owns the trip state machine and the durable trip store; emits events for notifications, payments and analytics.

Why region shards?

• A match only needs drivers near the pickup. Sharding everything (locations, matching, trips) by region keeps each shard's working set in memory and contains a bad night in one city to that city.

1. Geospatial index: geohash or H3 cells with neighbour search

• Geohash encodes a lat/lng into a string whose prefix identifies a rectangular cell; precision 6 is about 1.2 km × 0.6 km, precision 5 about 5 km × 5 km. H3 gives uniform hexagons with cleaner neighbour relationships (every neighbour shares an edge of the same length) and is what Uber uses.
• Index: one set per cell, members = driver ids with their last position. Redis GEO does this for you: GEOADD region:{r} lng lat driver_id, then GEOSEARCH ... BYRADIUS 2 km.
• Edge effect: a rider near a cell boundary has close drivers in the adjacent cell. Always query the pickup cell plus its 8 neighbours (hexagons: 6), then filter by real distance or ETA.
• Density: Manhattan and rural Montana cannot use the same cell size. Start with a coarse cell and refine (or expand the ring) until you have at least N candidates or hit a radius cap.
• Quadtrees adapt to density but are expensive to rebalance with points that move every few seconds; they suit static points like restaurants.

2. Location ingestion at hundreds of thousands of writes per second

• Kafka as the shock absorber between driver gateways and the location service; consumers can lag during a spike without dropping data.
• Partition by region so each location service shard consumes only its region, and the geo index for a region fits in one process's memory with a replica.
• Adaptive frequency on the client: every 4 s while moving or on a trip, every 30 s when stationary, nothing when offline. Cuts write volume by more than half.
• Last-write-wins keyed by driver_id and timestamp; out-of-order updates (mobile retries) are discarded if older than the stored one.
• Eviction: a background sweep removes drivers whose last update is older than 60 s so the index never offers a driver whose app died.

3. Matching under contention

• Two riders in the same block request at the same second and the same driver is the best candidate for both. Without coordination both get offered, and both accept.
• Option A: a single matcher process per region consumes requests sequentially (or in small batches) and keeps an in-memory set of drivers with a pending offer. Simple and correct; throughput of thousands of matches/s per region is enough.
• Option B: distributed matchers with a short lock per driver in Redis (SET driver:{id}:lock NX PX 20000). The offer expires with the lock.
• Offer/accept protocol: offer carries expires_at; accept is validated against the request still being in "matching" state and the lock being held by this offer. The match commit is one transaction on the trip store. Late accepts get 409 and the driver sees "ride no longer available".
• Batch matching: when demand is high, collect requests for ~2 s and solve a small assignment problem (Hungarian algorithm or greedy by ETA) rather than first-come-first-served; it raises overall ETA quality.

4. ETA, not straight-line distance

• Across a river or a highway, the nearest driver by crow-flies distance may be ten minutes away. Rank candidates by road-network ETA.
• Precompute contraction hierarchies for the road graph so point-to-point queries take milliseconds; keep a cache keyed by (origin cell, destination cell, 5-min time bucket) since many lookups repeat.
• Use a batch ETA call: one origin (pickup) to up to 200 driver positions in one request. Fall back to haversine distance if the ETA service is slow, and say so out loud as a graceful degradation.
• Live traffic feeds from driver breadcrumbs improve the edge weights; this is the same Kafka stream, consumed by a separate pipeline.

5. Demand spikes and surge

• Pricing service counts open requests versus available drivers per cell over a sliding 5-minute window; surge multiplier rises when the ratio exceeds thresholds, which both throttles demand and pulls drivers in.
• Back-pressure: the matcher queue per region is bounded; when it grows, widen the search radius and extend the batching window rather than failing. Riders see "finding a driver" longer instead of an error.
• Protect the location path first: ingestion and the geo index must stay up even if matching is slow, because stale locations make every later match worse.

6. Trip state machine and durability

• States: requested → matching → matched (offer accepted) → arriving → in_progress → completed, with cancelled reachable from requested through arriving, and no_drivers from matching.
• Each transition is a conditional update (UPDATE trip SET state='arriving' WHERE id=? AND state='matched') so retries and duplicate events are harmless. Transitions emit events to a trips topic for notifications, receipts and analytics.
• The trip store is the source of truth; the geo index and matcher state can be rebuilt from driver reports and the trip table after a crash.

Summary of decisions

• Geohash/H3 cell index in a region-sharded in-memory service, queried with the pickup cell plus its neighbours.
• Kafka between driver gateways and the location service; adaptive client update frequency.
• One matcher per region with offer locks and a 15 s offer timeout; short batching window under load.
• Candidates ranked by road-network ETA with a cache, falling back to distance when degraded.
• Relational trip store with conditional state transitions; everything else is rebuildable.

What was given up

• Global optimality: regional, near-greedy matching is not the mathematically best assignment.
• Exact freshness: positions can be a few seconds stale and we accept that.
• Simplicity: three distinct data planes (stream, in-memory index, transactional store).

With more time

• Pooled rides (multi-rider assignment), predictive positioning of idle drivers, fraud detection on GPS spoofing, multi-region failover for the matcher, and an ETA model trained on breadcrumb history.