Code a ride-hailing service with driver matching

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Two state machines meet in one service: the driver (available, offered, on trip) and the trip (offering, driver assigned, in progress, completed, cancelled, no drivers). Most design bugs come from changing one without the other.
Matching is a sequence of exclusive offers. Offer a trip to one driver at a time, hold that driver so no other trip can grab them, and move on when they decline or the offer times out. Double dispatch is the bug to design against.
Time drives the protocol: offer timeouts, cancellation grace periods and fare duration all read the same injected clock. A matcher that sleeps or reads the wall clock directly cannot be tested.
Pricing is a pure function of facts recorded on the trip: distance, duration and the surge multiplier snapshotted when the rider requested. Never reprice a trip with the current surge.
The shape is contention over a scarce pool with a hold: the same offer, hold and expire loop runs a restaurant table waitlist, a support queue that offers chats to agents, and a job queue's visibility timeout.

Requirements

Functional:

Drivers go online with a location and update it as they move.
A rider requests a trip from a pickup point. The system offers the trip to the nearest available driver; the driver accepts or declines within a fixed time, and otherwise the offer moves to the next nearest driver. When no driver is left, the trip ends as "no drivers".
The assigned driver starts the trip at pickup and finishes it at drop-off with the distance travelled. The fare is charged from base, distance, time, surge and a minimum.
The rider may cancel before the trip starts. Cancelling more than two minutes after a driver was assigned costs a fee, since the driver is already on the way.
A rider has at most one active trip; a driver is offered or carries at most one trip.

Non-functional:

No driver is ever offered two trips at once, and no trip is ever assigned two drivers.
Fares are reproducible from the trip record.
Offers resolve within seconds, and the matcher keeps up with a busy city's request rate.

Out of scope: the geospatial index at city scale, ETA prediction, payments, ratings and shared rides. The Design Uber system design lesson covers the location firehose, geo-sharding and the real-time connections. This lesson is the object model and the in-process logic of one matching cell.

Entities and relationships

RideService is the façade that rider and driver apps call: request, respond, start, finish, cancel, plus a tick the scheduler calls to expire stale offers.
Driver has an id, a location and a state (available, offered, on trip). The state is what makes the hold explicit: an offered driver is invisible to every other trip.
Trip has an id, the rider, the pickup point, the surge multiplier at request time, the set of drivers already tried, the driver currently offered and when, the assigned driver, the assignment and start times, the fare and a status.
Location is a value (x, y here; latitude and longitude in production).
DriverLocator answers "available drivers near this point, nearest first". In the practice it is a sort over all drivers; in production it is a geohash or H3 cell index. Hiding it behind an interface lets the matcher stay the same as the index changes.
PricingPolicy turns a completed trip into money. Clock supplies time.
Rider appears only as an id with one rule attached: at most one active trip.

Relationships: the service owns drivers and trips. A trip references drivers by id: one current offer, one assignment, many already tried. A driver does not point back to the trip in the model; the service keeps that index, so there is one source of truth for "who holds whom".

Class diagram

classDiagram
    class RideService {
      -drivers: Map~DriverId, Driver~
      -trips: Map~TripId, Trip~
      -clock: Clock
      +request(rider, pickup, surge) TripId
      +respond(driver, trip, accept) Result
      +tick()
      +start(trip, driver)
      +finish(trip, driver, meters) Money
      +cancel(trip, rider) Money
    }
    class Driver {
      +id: DriverId
      +location: Location
      +state: DriverState
    }
    class Trip {
      +id: TripId
      +rider: RiderId
      +pickup: Location
      +surgePct: int
      -tried: Set~DriverId~
      -offeredTo: DriverId
      -offeredAt: int
      +driver: DriverId
      +status: TripStatus
    }
    class DriverLocator {
      <<interface>>
      +nearestAvailable(point, exclude) DriverId[]
    }
    class PricingPolicy {
      <<interface>>
      +fare(meters, seconds, surgePct) Money
      +cancelFee(sinceAssigned) Money
    }
    class Clock {
      <<interface>>
      +now() int
    }
    RideService "1" *-- "many" Driver
    RideService "1" *-- "many" Trip
    Trip --> Driver : offered or assigned
    RideService --> DriverLocator
    RideService --> PricingPolicy
    RideService --> Clock
    GridLocator ..|> DriverLocator
    MeteredPricing ..|> PricingPolicy

Key flows

A request where the nearest driver declines, the second lets the offer time out, and the third accepts.

sequenceDiagram
    participant R as Rider
    participant S as RideService
    participant L as DriverLocator
    participant A as Driver A
    participant B as Driver B
    participant C as Driver C
    R->>S: request(pickup, surge 150)
    S->>L: nearestAvailable(pickup, tried)
    L-->>S: A, B, C
    S->>A: offer (A held)
    A->>S: decline
    S->>B: offer (A released, B held)
    Note over S,B: 15 s pass, tick expires offer
    S->>C: offer (B released, C held)
    C->>S: accept
    S-->>R: driver C assigned
    C->>S: start, then finish(4300 m)
    S-->>R: fare 1599

Design patterns used and why

State, as enums with guarded transitions. Both machines are small, and their states differ in which operations are legal, not in rich behaviour. Each operation checks the current state of the trip and of the driver together, under one lock.
Strategy for the driver locator and the pricing policy. The locator changes as the city grows (sort, then grid, then H3 cells with ring search); pricing changes by market (airport flat fares, minimum fares, time-of-day rates). The matcher depends only on the interfaces.
Snapshot of volatile inputs. Surge is read once, when the rider requests and sees the price, and stored on the trip. The same idea applies to the rate card version. Anything that feeds the fare is copied onto the trip.
Observer for side effects: the rider app hears "driver assigned", the driver app hears "offer", analytics hears everything. Publishing happens after the state change commits.
Façade for the two apps, with idempotent operations: a repeated "accept" from a flaky phone finds the trip already assigned and returns a stable answer instead of corrupting state.
Singleton, avoided. Each city or cell needs its own matcher with its own clock and locator; that is wiring in main, not a property of the class.

Concurrency and edge cases

Two trips, one driver. Rider P and rider Q request from the same corner. Without a hold, both offers go to driver A, A accepts both, and one rider waits forever. The hold (driver state "offered") is set in the same critical section that picks the driver, so the second request sees A as unavailable and goes to B.
Late accept. Driver B taps accept 200 ms after the timeout. If tick already moved the offer on, B is "not offered". If tick has not run yet, respond itself checks the deadline and treats the answer as expired. Either way, the decision depends only on the clock and the offer time, not on which code path ran first.
Decline loops. A driver who declined must not be offered the same trip again, or two nearby drivers ping-pong until the rider gives up. The trip keeps a set of drivers already tried.
Rider cancels during an offer. Release the held driver in the same step, or that driver is stuck in "offered" and silently out of the pool.
Duplicate requests. A double-tapped "request" hits the one-active-trip rule; with an idempotency key the client gets the first trip id back instead.
Rounding. Do fare arithmetic in integer cents and define the order: compute each component with floor division, sum them, apply surge, then apply the minimum. Write it down, because support will ask.

Down the stack

Layer 1The contract

request returns a trip that is either offered to exactly one available driver (now held) or ended as no drivers. respond from the offered driver within the timeout either assigns the trip or moves the offer to the next nearest untried driver; any other response changes nothing visible to that driver. After tick, no offer older than the timeout is outstanding. finish returns max(minimum, (base + per_km × meters / 1000 + per_min × seconds / 60) × surge / 100) with floor division at each step. cancel releases any held or assigned driver and returns the fee that the grace rule implies.

Layer 2The mechanism

In one process: a hash map of drivers, a hash map of trips and one mutex around both, because every interesting operation touches a trip and a driver together. Picking the next driver sorts available, untried drivers by distance then id. At city scale this becomes a grid or H3 index: the pickup's cell and its rings are scanned outwards until enough candidates are found, which is the Design Uber lesson's core. Offer expiry is a min-heap keyed by offeredAt + timeout, with stale entries skipped on pop because the trip may already have moved on; a hierarchical timing wheel does the same with O(1) inserts when there are millions of timers. When the state lives in a database, the hold is a conditional update, UPDATE drivers SET state = 'offered', trip_id = $1 WHERE id = $2 AND state = 'available', and a zero row count means another matcher got that driver first; try the next candidate.

Layer 3The machine

The mutex is never the bottleneck. A busy city might see 50 requests per second and a few hundred driver responses; each critical section is microseconds of work (sorting a few dozen nearby candidates and flipping two enums), against a lock cost of roughly 20 ns uncontended. The real latency is the network to the driver's phone: a push over a mobile connection takes 100 ms to several seconds, which is why the offer timeout is measured in seconds, not milliseconds. One more machine-level fact matters for fairness: timeouts must use a monotonic clock, because an NTP step on the server could otherwise expire every outstanding offer at once.

Why it's built this way

Drivers are scarce and riders wait in real time, so a driver must not be offered two trips at once.
Drivers answer through slow, unreliable phones, so each offer needs a hold with a deadline rather than a blocking call.
Deadlines and fares must be testable and reproducible, so time comes from an injected clock and fare inputs are snapshotted on the trip.
The nearest-driver query changes with scale while the offer protocol does not, so the locator sits behind an interface.
Matching decisions touch a trip and a driver together, so they share one serialisation point per matching cell, and cells scale out by geography.

Extensibility

Batch offers: offer to the top three drivers at once and assign the first acceptor. The trip holds a set of offered drivers; acceptance releases the others. The driver state machine stays the same.
Vehicle classes (XL, premium, accessible): a VehicleType on driver and trip, and a locator filter. Pricing becomes a table per vehicle type.
Scheduled rides: a trip created in a scheduled state that enters offering at pickup time minus the expected driver ETA, reusing the same timer heap.
Shared rides: a driver can hold a small number of compatible trips, and the hold becomes capacity rather than a single flag. This is a large change in the matcher, which is the right place for it.

Leadership lens

Build first: the hold-and-offer loop with timeouts, plus a test where two riders request in the same instant near one driver. Fare rules can be corrected and refunded; a double dispatch strands a rider at night.
Ask in review: where is the single point that decides a driver is held; what happens to a held driver when the rider cancels or the server restarts; which clock measures the offer timeout; what is snapshotted on the trip.
Pricing is regulated in many cities (fare caps, surge limits during emergencies). Keep the policy as data with an owner, log the rule version on every trip, and make the minimum and cancellation fee configurable per market.
Operationally, watch offer-to-accept ratio and time-to-assign by area. A rising expire rate usually means a broken push channel or a bad app release, not a lack of drivers.

Check yourself

Why must choosing a driver and marking them "offered" happen in one critical section?
Show answer
Otherwise two concurrent requests can both read the same driver as available and both offer to them. Combining the read and the hold (a lock or a conditional update) makes one request win and the other move on.
A driver answers "accept" one second after the offer timeout, before the expiry job has run. What should happen?
Show answer
The response handler checks the deadline itself and treats the offer as expired, moving to the next driver. The result must not depend on whether the sweep ran first.
Why snapshot surge on the trip instead of reading it at drop-off?
Show answer
The rider agreed to a price at request time, and surge can change during the ride. Recording it makes the fare reproducible and fair.
Why keep a set of drivers already tried on the trip?
Show answer
Without it, a decline or timeout can return the trip to the same driver, who is still the nearest, producing a loop that never reaches other drivers.

Watch

Design Uber (LLD): Fare Calculation, Driver Matching, Real-time ETA, GeoHashing (Shubh Patel): class-level design covering fare strategies and matching.
Ride Sharing Application Low Level Design in Python (Code and Debug): a complete coded solution to the machine-coding version of the problem.
Live Uber / Ride Sharing App Low Level Design, Part 2 (Elegant Engineer): a live walkthrough that spends time on the trip lifecycle and classes.

Free resources

H3 documentation: the hexagonal grid index used for nearest-driver queries at city scale.
State pattern (Refactoring.Guru): the pattern behind the driver and trip lifecycles, and when enums are enough.
Strategy pattern (Refactoring.Guru): how pricing and driver location become pluggable policies.
Assignment problem (Wikipedia): the optimisation behind batch matching of many riders to many drivers.
Explicit locking (PostgreSQL docs): row locks and conditional updates, the database form of the driver hold.

Open in the interactive app: practice, quiz, mock interview →