Design ride-hailing matching

Match a rider to a nearby driver in seconds, while tens of thousands of drivers send their location. The core pieces are a geo index built for fast writes, a protocol for offering rides to drivers, and a trip state machine that never assigns one driver twice.

Design the core of a ride-hailing app for Indian cities. Riders request a ride. The system finds a nearby available driver and offers the ride, and one driver accepts. At peak about 50,000 drivers are online, each sending their location every 5 seconds.

Requirements

Functional

Drivers send their location continuously while online.
A rider requests a ride with pickup and drop points, and sees a matched driver and ETA.
The system offers the ride to nearby available drivers until one accepts, or reports "no drivers".
Rider and driver both see live trip status and the driver's position until the trip ends.
Either side can cancel before pickup.

Non-functional

Location ingest: about 10,000 writes per second at peak.
Nearby-driver lookup p99 under 50 ms (99 out of 100 lookups are faster). A match, or "no drivers", within about 30 seconds.
Never assign one driver to two trips, or two drivers to one trip.
Trip state is durable: an accepted trip is never lost. The ride request path is 99.99% available.

Out of scope

Surge pricing and fare calculation.
Routing and ETA engine internals (we call a maps service).
Payments, ratings and driver onboarding.

Estimate

Location writes: 50,000 drivers x 1 ping / 5 s = 10,000 writes/s.
Hot index size: 50,000 drivers x ~100 bytes (id, lat, lng, status, timestamp) = 5 MB. It fits in memory easily; the challenge is the write rate and freshness, not size.
Ping history: 10,000/s x 100 bytes = 1 MB/s = ~86 GB a day. That goes to a stream and cold storage, never into the hot index.
Ride requests: say 2M rides a day = ~23/s average; peak (office hours, rain) ~5x = ~120/s. Each does one nearby query plus up to 3 sequential offers.
Live tracking: 120 new trips/s x 20 min average trip = 120 x 1,200 = ~144,000 trips in progress; each rider gets a driver position every 5 s = ~29,000 pushes/s over persistent connections.

API

WS /ws/driver (authenticated) -> client sends {lat, lng, heading, ts} every 5 s; server sends offers
POST /rides {pickup, drop, idempotencyKey} -> 201 {rideId, state: "MATCHING"}
POST /rides/{id}/accept {offerId} (driver) -> 200 {ride} | 409 offer expired or taken
POST /rides/{id}/events {event: ARRIVED | STARTED | COMPLETED} -> 200 {state}
POST /rides/{id}/cancel {reason} -> 200 {state: "CANCELLED"}
WS /ws/rides/{id} -> stream of {state, driverLocation, eta}

Data model

Geo index (in memory): cell_id -> set of driver_id; driver_id -> {lat, lng, status, ts} with a ~30 s TTL so silent drivers vanish
drivers(driver_id PK, status AVAILABLE | OFFERED | ON_TRIP | OFFLINE, current_ride_id, version)
rides(ride_id PK, rider_id, driver_id NULL, state, pickup, drop, idempotency_key UNIQUE, created_at, version)
offers(offer_id PK, ride_id, driver_id, expires_at, outcome)
ride_events(ride_id, seq, from_state, to_state, actor, at): append-only audit of transitions

A request, step by step

A driver app keeps a WebSocket (a connection that stays open both ways) to the realtime gateway and sends a ping every 5 seconds. The location service moves the driver to the right geo cell in the in-memory index, with a TTL (an expiry time). It also adds the ping to the location stream.
A rider calls POST /rides with an idempotency key, a unique id that makes a retried request safe. The ride service creates the ride in the MATCHING state and asks the matching service for a driver.
Matching asks the geo index for AVAILABLE drivers in the pickup cell and the rings of cells around it. It ranks a short list by road ETA and makes an offer to the best driver. A conditional update flips that driver from AVAILABLE to OFFERED in one atomic step. Then it sends the offer over the socket (or a push notification if the app is in the background) and waits up to 10 seconds.
The driver accepts. One transaction moves the ride from MATCHING to ASSIGNED and the driver from OFFERED to ON_TRIP. Each change applies only if the current state is still the expected one. If the offer timed out or the rider cancelled, the update changes zero rows and the driver gets 409 (Conflict). On a timeout or decline, matching sets the driver back to AVAILABLE and tries the next one.
During the trip, the driver's pings flow through the stream to the rider's socket. Each state change (ARRIVED, STARTED, COMPLETED) is a guarded transition, and each is recorded in ride_events.

Deep dives

The geo index: built for 10,000 writes a second

Weak: latitude and longitude columns in SQL, with a range query. A query like "WHERE lat BETWEEN ... AND lng BETWEEN ..." can use only one index range well.

Also, 10,000 updates a second to indexed columns keep rewriting the B-tree index pages, and every replica must repeat that work. Rows for drivers who went offline stay behind and look current.

Good: geohash cells in memory. Turn each position into a cell id, such as a geohash prefix (a short string that names a square on the map). An in-memory store with a sorted-set geo index also works.

Updating a driver means "remove from the old cell, add to the new cell". A nearby query reads the pickup cell and its 8 neighbours. Lookups take less than a millisecond.

Great: hexagon cells, sharded by city, with a search that widens step by step. Use hexagonal cells, like the open-source H3 grid system. Every neighbour of a hexagon is the same distance away. So "ring 1, then ring 2" widens the search evenly until you have enough drivers.

Shard by city, because Bengaluru never needs Delhi's drivers. Give each entry a TTL of about 30 seconds, so dead phones disappear on their own. Send raw pings to a stream for history and analytics, not to the index.

Trade-off: the index is soft state: data you can lose, because it rebuilds itself. If it is lost, the next round of pings refills it within 5 seconds. You accept that in exchange for memory-speed reads and writes.

Rank the drivers you find by road ETA, not straight-line distance. A river or a flyover changes everything.

Never assign one driver twice

Two riders near the same driver request a ride at the same moment. Two matching instances both pick that driver.

Weak: check, then set. Read "is the driver available?", then write the assignment. Both instances read "yes" and both assign. Locks in application memory do not help, because each instance has its own memory.

Good: a conditional update in the database. Make the change itself do the check: "UPDATE drivers SET status = OFFERED, ride = X WHERE id = D AND status = AVAILABLE".

Exactly one instance gets one row updated. The other gets zero rows and moves to the next driver. Accepting works the same way: one transaction updates both the ride and the driver, each guarded by its current state.

Great: offers as leases, changes as a state machine. An offer is a lease: a claim that expires on its own after 10 seconds. Every change is an allowed step in a state machine, for example AVAILABLE to OFFERED to ON_TRIP.

Each change carries a version number and is idempotent. A retried accept returns the same answer instead of failing or applying twice. An accept that arrives after the lease expired fails cleanly with 409 (Conflict).

You can also split matching for one city so each driver is handled by only one matcher. That reduces contention: fewer instances fighting over the same rows.

Trade-off: offering to one driver at a time is slower than sending the offer to five at once. But sending to five creates races and annoys drivers. A middle ground is offering to two drivers in turn, with short timeouts.

What breaks

A driver's phone goes silent. Their index entry expires after about 30 seconds, so they stop getting offers. An active trip is flagged if pings stop for more than a minute.
The geo index shard for a city fails. A replica takes over. In the worst case, fresh pings refill the index within one 5-second cycle.
Matching crashes in the middle of an offer. The offer lease expires. A sweeper (a background job that cleans up expired records) sets the driver back to AVAILABLE, and the ride goes back to MATCHING to try again.
The rides database primary fails. Requests return 503 (Service Unavailable) while a replica takes over. Idempotency keys make the app's retries safe.

What each level is expected to cover

Mid level: Keeps location ingest separate from matching. Uses a geohash or similar cell index in memory. Defines the ride states. Uses a conditional update to stop double assignment.

Senior: Sizes the write path. Designs a cell search that widens step by step, sharded by city, with TTLs. Specifies the offer protocol with leases and timeouts. Makes every state change idempotent and guarded. Handles crashes in the middle of an offer. Compares offering to one driver at a time against offering to several.

Common mistakes

Storing every ping in the main SQL database and querying it with latitude and longitude ranges.
Check-then-set assignment, which breaks when two requests run at the same time.
Ranking drivers by straight-line distance and ignoring road ETA.
No expiry on driver positions, so offline drivers keep getting offers.
No idempotency on ride creation, so a retry on a flaky network books two cabs.

Follow-up questions

How would you add surge pricing per area without slowing matching?
How would you support shared rides with two riders?
Drivers complain they get offers for pickups across a river. What do you change?
How do you detect and handle fake GPS locations?
How do you test the matching logic for race conditions before launch?