Uber and ride matching

What you are designing

A rider requests a trip. You find a driver who is online, nearby, and not already committed, offer them the trip, and record it if they accept. Locations update every few seconds. A stadium letting out is a localized spike. Assume a large city has tens of thousands of online drivers.

Requirements

• Rider requests a pickup and sees a driver within a few seconds if one is available.
• Drivers stream location while online.
• A driver is offered at most one trip at a time.
• Both sides see trip state (accepted, arriving, started, finished) and can cancel under rules you state.

Matching latency matters. Historical pings do not need to be queryable for the match.

Entities and API

Driver(id, status, cell, lat, lng, updated_at), Rider, Trip(id, rider, driver, state), Offer(trip, driver, lease_until).

POST /v1/trips                 { pickup, dropoff } -> trip or searching
POST /v1/drivers/location      { lat, lng }
POST /v1/offers/{id}/accept
POST /v1/offers/{id}/decline

High-level design

flowchart LR
  Phone[Driver phone] --> Loc[Location ingest]
  Loc --> Geo[(Geo index)]
  Rider --> Match[Matcher]
  Match --> Geo
  Match --> DB[(Trips)]
  Match --> Push[Offer push]
  ETA[Routing] --> Match

Location ingest writes Redis (hash + GEO set) and nothing else on the hot path. The matcher reads candidates, asks routing for ETA on the top K, and claims a driver in Postgres or with a conditional Redis/DB update. The offer goes out through the real-time path. Accept flips the trip to assigned.

Data model

CREATE TABLE trips (
  id          BIGSERIAL PRIMARY KEY,
  rider_id    BIGINT NOT NULL,
  driver_id   BIGINT,
  state       TEXT NOT NULL, -- searching | offered | assigned | started | done | canceled
  pickup_lat  DOUBLE PRECISION NOT NULL,
  pickup_lng  DOUBLE PRECISION NOT NULL,
  offered_to  BIGINT,
  offer_until TIMESTAMPTZ
);
CREATE INDEX trips_driver_active ON trips (driver_id) WHERE state IN ('offered','assigned','started');

The partial index is what you use to answer “is this driver busy?” if the Redis status is lost. Redis is the live index. Postgres is the trip ledger.

Deep dives

Candidate search. Geohash or Redis GEO on the driver’s latest point. Query the cell and neighbors, filter status=free, take a few dozen. Expand the radius if the set is empty, up to a cap, then tell the rider no one is close. See the geo page for boundary cells.

The claim. Sort candidates by ETA, then try:

UPDATE trips SET state='offered', offered_to=:driver, offer_until=now()+interval '15 seconds'
WHERE id=:trip AND state='searching';

And a driver-side condition so a driver with an active trip is not selected. If the driver declines or the lease expires, a worker tries the next candidate. The offer push uses the real-time pattern with a cursor so a flaky phone can still accept.

Spike and fairness. A concert is one hot cell. Cache the candidate id list briefly and isolate matching workers for that cell so one neighborhood cannot fill the global queue. Rotate which free driver you try first among similar ETAs so the nearest driver is not always the one who works.

Money and state. Fare estimation can be approximate. The fare charge is a saga after the trip completes, idempotent on trip id. Do not block matching on the payment discussion.

Levels

• Mid-level. Geo index, a durable trip, an offer that a second rider cannot also take.
• Senior. Lease and decline loop, ETA versus distance, location ingest split from durable state, hot-cell behavior.
• Staff. Fairness, surge as a supply signal (even if you do not fully design pricing), multi-modal fallbacks, and what you degrade if routing is down (fall back to straight-line and say so).