Ride Matching

What is ride matching?

Ride matching selects an eligible driver for a rider's pickup while drivers continuously publish changing positions. The engineering challenge is choosing a nearby candidate quickly without allowing concurrent requests, stale GPS events, or expired offers to assign the same driver twice. This design focuses on candidate discovery, atomic claims, and short-lived driver offers.

TL;DR

A ride-matching system connects a rider's pickup request to a nearby available driver. Keep the location write path separate from the match path: ingest GPS updates through a durable event stream into a city-sharded H3 index, then search nearby cells and atomically claim a candidate with a per-driver GETDEL (or an equivalent atomic script). Send a short-lived offer, retry the next candidate on decline or timeout, and keep durable ride state in a database. The core contract is availability and low latency for matching, with exactly one successful claimant per driver.

Scope and assumptions

This article designs the matching and driver-offer pipeline from pickup coordinates to an accepted match. It treats routing, trip lifecycle, eligibility, fraud, payments, and live trip tracking as adjacent systems.

The interview scenario uses illustrative assumptions:

• 5 million registered drivers, 1 million active drivers, and a GPS update every 4 seconds, or about 250,000 location events per second at peak.
• About 2,000 ride requests per second at peak; search starts at 2 km, expands to 5 km when needed, and gives each offer a 10-second response window.
• A 200 ms target for the match service to produce an offer, with location data allowed to be a few seconds old. These are design targets, not production guarantees.
• A driver can have at most one active offer or trip. City or metro shards have a local write authority, with explicit neighbor-shard spillover at boundaries.

The design uses Redis for ephemeral indexes and claims, Kafka for replayable location events, and a durable ride store for the request and status history. A claim must be fenced against stale location events so an old available update cannot reinsert a driver who is already matched.

Functional Requirements

Core Requirements

1. A rider requests a ride at a given pickup location.
2. The system finds the nearest available driver and sends them a request.
3. If the driver accepts, both sides receive each other's contact information and ETA.
4. If the driver declines or times out, the system tries the next nearest driver.

Below the Line (out of scope)

• Routing and turn-by-turn navigation (covered in Design an ETA Service).
• Dynamic surge pricing (covered in Design a Surge Pricing System).

Non-Functional Requirements

Core Requirements

• Match latency: A matched driver is returned to the rider in under 200ms from the moment the ride request is received.
• Availability: 99.99% uptime. Availability over consistency: a driver location that is 3 seconds stale is acceptable, a failed match is not.
• Location freshness: Driver positions are current to within 5 seconds at all times. This sets the GPS update interval at 4 seconds per driver.
• Location write throughput: 1M concurrently active drivers each sending GPS updates every 4 seconds equals 250K location writes per second at peak.
• Consistency: Each driver is atomically claimed by exactly one rider. No double-booking, even under concurrent match requests.
• Scale: 5M registered drivers globally. 2K trip requests per second during peak periods.

Below the Line

• Real-time driver tracking during an active trip (separate WebSocket streaming problem)
• Trip lifecycle management and status persistence
• Fraud detection and driver eligibility filtering

Read/write ratio: Location writes dominate: 250K writes per second at peak versus roughly 2K trip-request queries per second. That is a 125:1 write-to-read ratio on the location path. Each match query is a geospatial scan (read-intensive per request) but low-rate relative to the location write firehose.

This ratio changes everything downstream. The write volume determines how the location ingestion pipeline is built; the query access pattern determines the geospatial index structure. They require separate services with separate scaling axes.

Real-time trip tracking is below the line because it does not touch the matching pipeline. To add it: open a WebSocket connection between both apps on trip acceptance and relay driver GPS updates through Redis Pub/Sub on a trip-specific channel. The Location Service publishes to that channel whenever it receives an update for a driver on an active trip.

Trip lifecycle management is below the line because it runs after the match is made. To add it: introduce a Trip Service that owns the state machine (requested, accepted, in_progress, completed) and persists each state transition to a PostgreSQL table with timestamps for audit and billing.

The hardest problem in scope: Atomically removing a driver from the available pool the moment they are matched, preventing two concurrent ride requests from being routed to the same driver. A naive SELECT-then-UPDATE is a TOCTOU race condition that fires constantly in production at this request rate. The atomic claim is where bugs hide.

30-second answer / outline

Accept the rider request and persist a RideRequest, then asynchronously search nearby H3 cells for available drivers. Location updates flow through Kafka into Redis; the match service sorts candidates by distance and atomically removes one driver's availability record with GETDEL. A 10-second offer is pushed to the driver, and decline or timeout advances the candidate queue. City-cell sharding and neighboring-cell spillover provide global scale, while the durable ride store records the outcome.

5-minute explanation

There are two independent hot paths. Drivers produce a location firehose, so the Location Service acknowledges durable Kafka publication and a consumer maintains an ephemeral H3 index. Riders produce a much smaller request stream, so the Match Service creates a durable request, queries nearby cells, and attempts an atomic claim for each candidate. The database is not on the GPS hot path, and Redis is not the durable record of the ride.

The request flow is intentionally asynchronous: POST /rides returns a ride ID, the match worker fills a candidate queue, and the driver responds through an offer endpoint. A successful claim is removed from the available set before the offer is sent. If the offer is declined, expires, or the claim is rejected as stale, the service tries the next candidate and then widens the search. A response must be fenced by an offer ID so a late response cannot confirm an already-expired offer.

H3 cells keep geographic lookups bounded, city-cell shards keep traffic local, and Kafka consumer groups absorb location bursts. The difficult correctness boundary is the claim: every candidate attempt must be one atomic state transition, not a SELECT followed by an UPDATE.

45-minute interview approach

Use this section as an interview pacing plan; it is not a promise that the article can be read in 45 minutes.

• 0-5 minutes — clarify scope: Confirm pickup-only matching, driver availability semantics, offer timeout, candidate radius, rider notification, and whether routing or surge pricing is included.
• 5-10 minutes — requirements and estimates: State the illustrative 1 million active drivers, 250,000 location events/second, 2,000 ride requests/second, 200 ms offer target, and five-second freshness allowance.
• 10-15 minutes — entities and APIs: Define RideRequest, DriverLocation, RideOffer, the request/status endpoints, and the idempotency or fencing token on driver responses.
• 15-25 minutes — baseline architecture and flows: Draw the rider request, Location Service, Kafka, H3/Redis index, Match Service, offer delivery, and durable ride store. Walk through one successful match and one timeout.
• 25-35 minutes — choose deep dives: Let the interviewer select geospatial indexing, atomic driver claims, 250K location writes/second, or city-cell sharding. Compare the naive and evolved options.
• 35-41 minutes — reliability and operations: Cover event replay, stale GPS fencing, Redis loss, offer expiry, backpressure, regional failover, authentication, and metrics for match latency and no-driver outcomes.
• 41-45 minutes — trade-offs and close: Explain H3 versus simpler geo indexes, Redis claims versus database locks, eventual location freshness versus match correctness, and what changes for multi-region active/active operation.

Core Entities

• Rider: A registered user with a rider_id who can request rides. Pickup location is captured at request time, not stored as a persistent field.
• Driver: A registered driver with driver_id, status (available, matched, on_trip, offline), and a linked vehicle record.
• DriverLocation: The current GPS snapshot for a driver: driver_id, latitude, longitude, updated_at. Ephemeral, stored in Redis, not written to the primary DB on every update.
• RideRequest: A pending match record with request_id (returned publicly as ride_id), rider_id, pickup_lat, pickup_lng, status (pending, offer_sent, matched, expired), and a candidate_queue of driver IDs to try in order.
• RideOffer: An in-flight offer from the system to a specific driver: offer_id, request_id, driver_id, sent_at, expires_at. Expires after 10 seconds if no driver response arrives.

Full schema details (indexes, partition keys, TTLs) are deferred to the deep dives. These five entities are sufficient to drive the API design and high-level architecture.

API Design

The API surface stays small: two actors (rider and driver) and four action types.

FR 1 - Rider requests a ride:

POST /rides
Body: { pickup_lat, pickup_lng }
Response: { ride_id, status: "matching" }

The rider gets a ride_id immediately and polls GET /rides/{ride_id} for a driver assignment. The server returns before a driver is found so match latency is invisible to the caller.

FR 2 - Driver broadcasts location (enables matching):

POST /drivers/location
Body: { latitude, longitude, status }
Response: 200 OK

Called every 4 seconds per active driver. The response body is empty; acknowledging receipt is sufficient. The service must sustain 250K location updates per second at peak, with up to 1M active driver clients connected.

FR 3 and FR 4 - Driver responds to an offer:

PUT /rides/{ride_id}/respond
Body: { driver_id, decision: "accept" | "decline" }
Response: { status, rider_contact? }

One endpoint handles both accept and decline. The branching logic belongs in the service, not in the URL. On accept, rider_contact carries the rider's name and phone number.

Rider polls for match status:

GET /rides/{ride_id}
Response: { ride_id, status, driver?: { driver_id, name, phone, eta_seconds } }

Polling is sufficient for the HLD. A later version could open a WebSocket after the POST response and push status changes as they occur.

High-Level Design

1. Rider requests a ride

The write path: the rider submits pickup coordinates, the Match Service creates a ride record, and returns a ride ID. Driver matching starts asynchronously.

Components:

• Rider App: Mobile client sending POST /rides.
• Match Service: Validates the request, creates the ride record, and queues the match attempt.
• Ride DB: Stores the authoritative RideRequest record. Status begins as pending.

Request walkthrough:

1. Rider app sends POST /rides with pickup lat/lng.
2. Match Service validates the coordinates (valid lat/lng range).
3. Match Service inserts { request_id, rider_id, pickup_lat, pickup_lng, status: "pending" } into Ride DB.
4. Match Service returns { ride_id, status: "matching" } to the rider.
5. Rider begins polling GET /rides/{ride_id} every 2 seconds.

This covers the write path only. The matching step that queries available drivers is in the next section.

2. Geospatial driver discovery

Drivers broadcast GPS every 4 seconds. The system must answer "which drivers are within 2km of this pickup?" in under 50ms to hold total match latency under 200ms.

A plain SQL range query can scan a large portion of the drivers table on every request. At the illustrative 1M-active-driver scale, a composite (lat, lng) index does not provide a general two-dimensional nearest-neighbor index; benchmark the query plan with representative data before relying on it.

The fix is an in-memory geospatial index, such as Redis geo commands or an H3-cell index. Query latency and capacity must be established with a workload benchmark; the specific index structure (geohash versus H3) is treated as a black box here and covered in the deep dives.

Components:

• Driver App: Mobile client calling POST /drivers/location every 4 seconds.
• Location Service: A separate service that accepts driver GPS updates and writes them to the geospatial index. Decoupled from the Match Service so location write throughput does not affect match latency.
• Redis Geo (Driver Index): Available drivers stored with geohash-encoded scores. GEORADIUS returns members within a given radius sorted by distance.

Request walkthrough (location update):

1. Driver app sends POST /drivers/location with lat, lng, status.
2. Location Service validates coordinates and checks driver status.
3. If status = available: GEOADD drivers:available <lng> <lat> <driver_id>.
4. If status = matched or offline: ZREM drivers:available <driver_id>.
5. Location Service returns 200 OK.

Request walkthrough (driver discovery on ride request):

1. Match Service receives a new RideRequest.
2. Match Service calls GEORADIUS drivers:available <pickup_lng> <pickup_lat> 2 km ASC COUNT 10.
3. Redis returns up to 10 driver IDs sorted by distance.
4. Match Service stores these as the candidate_queue for this request.