Design: ride matching

The full lesson, with a worked example: Design: ride matching. The rider's side is in How a cab app finds your ride.

Requirements

Functional

• Quote: riders enter pickup and drop and see a fare before booking.
• Match: find a nearby free driver and offer them the trip.
• Offer: drivers accept or let it pass; then the next driver is tried.
• Track: rider and driver see each other move until the trip ends.

Non-functional

• Fast: a driver found within seconds; the search itself well under a second.
• Fresh: map positions no more than a few seconds old.
• Never double-booked: a driver holds at most one trip, always.
• Survives peaks: office hours, heavy rain, a match ending.
• Out of scope (say so): payments, ratings, driver onboarding.

Estimates

• Location writes: 10 lakh drivers online at peak, a GPS ping every 4 s: 10 lakh ÷ 4 = 2.5 lakh writes a second.
• Live state: about 200 bytes per driver (id, position, status, time) × 10 lakh ≈ 200 MB. Fits in one machine's memory.
• Ride requests: 1 crore rides a day ≈ 115 a second, about 600 at the evening peak. Fare checks run several times higher.
• Tracking pushes: 2 lakh trips in progress, a position every 4 s = 50,000 pushes a second.
• Naive search cost: 600 requests × 10 lakh drivers = 60 crore distance sums a second. That is why you index by area.
• Trip history: a 55-minute trip at one ping per 4 s is about 800 pings, sent to cheap storage.

The shape: small data, changing constantly. The hard part is a huge rate of tiny updates plus a fast "who's near here?" on data that never sits still. An ordinary database writing every change to disk and re-indexing would choke.

API

• POST /v1/quotes: pickup, drop, ride type. Returns a price quote id, fare and expiry (a few minutes).
• POST /v1/trips: quote id plus an idempotency key. Returns the trip in searching. A repeat key returns the same trip.
• POST /v1/drivers/me/location: lat, lng, heading, speed, timestamp. Every 4 s; fire and forget.
• POST /v1/offers/:id/accept and /decline: the driver's answer, valid only before the offer expires.
• POST /v1/trips/:id/cancel: by rider or driver, with a reason.
• A WebSocket per app: offers pushed to drivers, driver positions and trip status pushed to riders.

Data model

• Live cell index (memory): cellId → set of free driver ids. Updated only when a driver crosses a cell border.
• Driver state (memory): driverId → position, status (free, offered:t-501, on_trip:t-501, offline), version, lastPingAt. Expires after about 30 s of silence, like a TTL.
• trips (database): tripId, riderId, driverId, quoteId, idempotencyKey (unique), state, pickup, drop, fare, timestamps.
• offers: offerId, tripId, driverId, expiresAt, result.
• supply and demand per area: requests and free drivers in the last few minutes, read by pricing.
• ping history: raw pings through a queue to cheap storage, for ETA models and disputes. Never the main database.

High-level design

1. 1

   Driver appLocation service

   Ping: here I am (every 4 s)

2. 2

   Rider appTrip service

   Book, quote q-17, key r-88

3. 3

   Trip serviceMatching

   Trip t-501 is searching

4. 4

   MatchingLocation service

   Free drivers in this cell + ring?

5. 5

   Location serviceMatching

   14 drivers, in about 3 ms

6. 6

   MatchingDriver app

   Offer to best ETA, 15 s countdown

7. 7

   Driver appTrip service

   Accept: claim if still offered t-501

8. 8

   Trip serviceRider app

   Suresh, 6 minutes away

• Location service: takes pings and keeps only each driver's latest position in memory, organised by map cell, a geospatial index.
• Trip service: owns each trip as a state machine: searching → driver assigned → arriving → on trip → completed, or cancelled.
• Matching: finds candidates, ranks them by driving time, sends offers with a countdown.
• Pricing: quotes from distance, time and current demand.
• Tracking: pings for a live trip go to a channel for that trip and on to the rider's open connection.

Deep dives

Map cells and the nearby search

• Cut the map into cells of about a square kilometre in a city. A geohash is one naming scheme; hexagons are popular because every neighbour is the same distance away.
• Each cell holds the set of free drivers inside it, in an in-memory key-value store. A ping that crosses a border moves the driver from the old set to the new.
• Search: the rider's cell plus the ring of 6 around it (a driver 50 m away may be just over the border). In a busy city that gives 10 to 30 drivers in a few milliseconds. Too few? Widen to the next ring.
• Rank by driving time, not distance: a routing engine knows one-ways, flyovers and rivers. A driver 600 m away across a flyover may be 11 minutes off; one 1.8 km away on the right side may be 4.

Claiming a driver exactly once

Two riders a street apart can both pick Suresh in the same millisecond. "Read free, then write mine" lets both reads happen before either write: a race condition.

• Make the check and the change one step: a compare-and-set, "set Suresh to t-501 only if he is still offered t-501", usually with a version number.
• Exactly one request wins; the other gets "already taken" and moves to its next candidate in milliseconds.
• A short lock also works, but compare-and-set needs no clean-up if a server dies mid-request.
• While an offer stands, the driver is offered and no other trip can offer them anything. Offers carry an expiry, so a crashed matcher cannot leave a driver stuck.

Offers: one at a time, several, or batched

• One at a time (about 15 s each): fair and simple, but every ignored offer costs the rider 15 s.
• Several at once: faster for riders, but annoys the drivers who lose.
• Batch matching: collect a second or two of requests and pair the whole batch with drivers together, lowering total waiting time across everyone. It adds a short delay and is best in busy areas.

Scaling the location service

• Shard by area, with the cell as the shard key. Bengaluru's cells live on different machines from Delhi's; a search touches only its own neighbourhood.
• Hot spots: a stadium emptying puts 30,000 requests into two or three cells. Give busy areas finer cells over more machines, and switch them to batch matching.
• Crash recovery: the index is soft state. A standby takes over and every driver pings again within 4 s, so cells refill almost at once. Assigned trips are safe in the trips database. A warm replica shortens the gap.
• Silent drivers: an entry with no ping for about 30 s drops out of its cell. On a live trip, the rider sees "updating location" instead of a reassignment.

Live tracking and pricing

• Each ping on a live trip is snapped to the road (map matching) and published to the trip's channel by publish–subscribe. The rider gets it within about a second over a persistent connection; no polling.
• The app glides the car between pings by interpolation.
• Every minute or so, pricing compares requests and free drivers per area. When demand far outruns supply, surge pricing raises the fare, pulling drivers in and cooling demand.

Trade-offs

• Smaller cells: precise searches, but more cells to read near borders and more border crossings per driver.
• Faster pings: fresher maps, but more writes and more battery and data on drivers' phones.
• Batching: better matches overall, but a second or two before anyone is matched.
• Memory over disk: fast, but lost on a crash. Acceptable, because the next round of pings rebuilds it.
• Push vs polling for tracking: push needs lakhs of open connections; polling every second would be 2 lakh requests a second for data that changes every 4.

Interview talking points

• State "never assign a driver twice" and "positions a few seconds fresh" up front.
• The sum: drivers ÷ ping interval = lakhs of writes a second, yet the live state is only about 200 MB.
• In-memory index by map cell, sharded by area, with expiry for silent drivers.
• Search the cell plus a ring; rank the shortlist by ETA from a routing engine.
• Trip state machine, offers with a timeout, compare-and-set to claim, idempotency key on booking.
• Live tracking through a channel per trip and an open connection.
• Hot spots and surge as deep dives; raw pings to cheap storage for ETA models.

Follow-up questions

Why not use a database with built-in location search? It works at small scale, but updating an on-disk index 2.5 lakh times a second is far beyond it. Latest positions are small, change constantly and can be rebuilt, so memory is the right home.

What about a driver right on the edge of a cell? That's why every search reads the rider's cell and the ring around it, and widens the ring if too few drivers turn up.

The rider taps Book twice on a slow network. What happens? The app sends the same idempotency key with every retry, and the trip service returns the existing trip for a repeat key, so ten taps make one booking.

A location server holding south Bengaluru dies at 7 pm. What do riders see? A gap of a few seconds. A standby takes the shard, every driver pings again within 4 s, and assigned trips are untouched because they live in the trips database.

Offer to one driver or several at once? One at a time is fair but slow when drivers ignore offers; several is faster but wastes drivers' attention. Many systems start with one and go wider, or batch, when an area is busy.