Design a Ride-Sharing Service: Near, Now, Claimed Once (2026)

You tap “Request ride”. A few seconds later a driver three minutes away accepts, and a small car icon starts moving toward you on the map. It feels like one tap and one answer.

Behind it, an assumed half a million cars are moving. Each one reports its position every few seconds. In that moment the system must find the drivers near you, work out which one can really reach you soonest by road, ask that driver, and make sure nobody else is promised the same car.

Three words sum up the problem: near, now, claimed once. This lesson builds the system around one rule: index by place, rank by road, claim once.

Before You Start#

Step 1: Pin Down the Problem#

Ask before drawing. Each answer you assume becomes a number:

• One city or many? (Assume many, but a ride never leaves its city, so cities can be independent shards.)
• One vehicle type, or several? Pooled or scheduled rides? (Assume one type, none of the others.)
• Does the system pick the driver, or does the rider browse cars? (Assume the system picks.)
• How fresh must a driver position be? (Assume a few seconds.)
• Are pricing, payments and fraud in scope? (Assume not here. The follow-ups lesson covers them.)

Functional requirements:

1. Drivers go online and share their location.
2. A rider requests a ride from a pickup point to a destination.
3. The system finds a nearby driver, offers the ride, and on acceptance links the two.
4. Both see the ride progress live, until it is completed or cancelled.

Out of scope (say these out loud): pricing and surge, payments, fraud, driver onboarding and ratings, pooled and scheduled rides.

Non-functional requirements, each with a number. These are assumptions you announce:

• Fast: a rider sees a driver matched within a few seconds when drivers are nearby (assume the median under 10 s).
• Correct: a driver is never matched to two riders at once, and a rider is never charged for two rides from one tap.
• Available: a location service hiccup must not stop rides already in progress.
• Scale: assume 500,000 drivers online at peak across all cities. Step 4 turns that into numbers.

Step 2: Entities, API and Data Model#

POST /v1/rides
  {pickup, dropoff, request_id}
  201 new ride
  200 repeat of a request_id
  409 same id, different body
  422 pickup outside area
  429 too many requests
 
GET  /v1/rides/{id}
POST /v1/rides/{id}/cancel
GET  /v1/rides?cursor=...
     (history, paged)
 
Driver connection (held):
  location {lat, lng, heading,
            speed, ts, seq}
POST /v1/offers/{id}/accept
POST /v1/offers/{id}/decline
  200 matched
  409 OFFER_EXPIRED or taken

All calls carry a bearer token. A rider may read only their own rides, and a driver sees the pickup only once an offer is made.

Two fields matter most. request_id is made by the rider’s app, so a retry of the same tap never creates a second ride; a repeat with a different body is a bug, so it fails with 409 (payment APIs such as Stripe’s compare repeat requests with the original for the same reason). expires_at on an offer means a driver who does not answer stops blocking the ride.

Data model#

Access patterns drive the choices: ride by ride_id, ride by (rider, request_id), the active ride of a driver. Any store with single-row conditional writes works, such as a relational database or DynamoDB with condition expressions, where a write goes ahead only if the condition holds.

Step 3: A Design That Works#

Start with the obvious design. Drivers report their positions into a table. When a rider asks for a ride, the server computes the distance from the rider to every driver, sorts, and takes the nearest few.

It is correct, and for a small town it is fine. It is where many candidates stop.

All 20,000 (an assumed city size) are checked, and the answer is almost certainly among the few dozen nearest. Most of the work is wasted on drivers on the other side of the city. A toy test shows the gap: a grid index examined ≈ 338 drivers per request instead of 20,000, and returned the same five drivers every time. The rest of the design is about making “near” cheap.

Step 4: Estimate What Matters#

Assume 500,000 drivers online
Update every 4 s:
  500,000 / 4 = 125,000/s
Per update ~100 B on the wire:
  125,000 x 100 B = 12.5 MB/s
  = 100 Mbit/s inbound
Latest position: 100 B each
  500,000 x 100 B = 50 MB
 
Rides: 5M a day / 86,400
  ≈ 58/s, peak ≈ 290/s
Rides in progress (20 min each):
  5M x 1,200 s / 86,400
  ≈ 69,000 on average

Then the neighbourhood:

Dense area: 40 drivers/km2
2 km radius: π x 2 x 2
  ≈ 12.6 km2
  ≈ 500 candidates
Driver at 50 km/h
  ≈ 56 m moved per 4 s
Keep every point for a day:
  12.5 MB/s x 86,400
  ≈ 1.1 TB/day

What each number decides#

• ≈ 125,000 updates a second is the real load, almost all writes. The 100 Mbit/s inbound spreads over many gateways.
• The live set is only ≈ 50 MB. It fits in memory on one machine, so the problem is write rate and latency, not size.
• ≈ 290 ride requests a second at peak is small next to the updates. Even 290 × 500 candidates is 145,000 distance checks a second, trivial for memory. Ingest is the bottleneck, not matching.
• ≈ 1.1 TB a day if every point were kept. That is why the trail keeps only points from trips in progress and expires them, not the whole idle fleet.
• A driver moves ≈ 56 m between updates. Phone GPS is typically good to about 4.9 m under open sky and worse near buildings, so 56 m of staleness dominates. That is fine for finding candidates, but the final ETA must account for it.
• All of these are assumptions for the arithmetic. Measure your own.

Step 5: Deep Dives#

Four questions decide this design. Take them in this order unless the interviewer pulls you elsewhere.

How Do You Find Nearby Drivers Fast?#

Scan everything#

Grid cells#

Hierarchical cells#

Which index?#

All three common choices turn a point into a number.

Recommendation (judgement): for an in-memory index with a rider radius search, H3 or Redis GEO both work; choose H3 if you also want per-cell supply and demand counts, and S2 if the index lives in a sorted key-value store that serves range scans.

What cell size?#

The H3 table lists resolution 8 at an average 0.737 km² and 0.53 km edge, and resolution 9 at 0.105 km² and 0.20 km. A gridDisk of k returns every cell within k hops, which is 3k(k+1)+1 cells.

Target: 2 km radius = 12.6 km2
Neighbour spacing = 1.73 x edge
 
Res 8: spacing ≈ 0.92 km
  k = 3 -> 37 cells x 0.737
  = 27.3 km2  -> 1,090 drivers
Res 9: spacing ≈ 0.35 km
  k = 6 -> 127 cells x 0.105
  = 13.4 km2  ->   535 drivers
(at 40 drivers/km2)

Using the H3 areas, resolution 8 does 37 lookups and examines about 1,090 drivers, and resolution 9 does 127 lookups and about 535. Measure which is cheaper (judgement). Downtown, at an assumed 400 drivers/km², a resolution 8 cell holds ≈ 295 drivers, so dense areas want a finer one. The ring counts are rough: a precise distance check makes the result exact, and the search widens if fewer than five pass.

How Do You Ingest 125,000 Updates a Second?#

Write every update#

In memory#

By region#

How Do You Match Without Double-Booking?#

Nearest wins#

Rank, then claim#

Sequence and batches#

Why batching wins#

Assume two riders and two drivers with pickup ETAs in minutes (made-up numbers):

        D1   D2
R1       2    3
R2       3    9
 
Greedy, R1 first:
  R1-D1 (2) then R2-D2 (9) = 11
Batch, best pairing:
  R1-D2 (3) + R2-D1 (3)   =  6

The batch gives an average wait of 3 minutes against 5.5. If a batch window is 2 s and requests arrive at the peak of 290/s, a batch holds about 580 riders, a real assignment problem. Because a wide batch costs rider wait, shrink the window when supply is plentiful and widen it when it is scarce (judgement).

What Do You Pick Under a Partition?#

The claim must not double-book, even when a node fails, so state a stance per component rather than a slogan. CAP and PACELCCAP and PACELC: CAP says that during a network partition a system must choose between consistency and availability. PACELC adds that when there is no partition it still trades latency against consistency give the words.

The claim is a fast filter, not the final word#

Redis uses asynchronous replication, so acknowledged writes can be lost during a failoverfailover: moving work from a failed machine to a standby one, and WAIT does not turn it into a strongly consistent system. After a failover a claim can vanish and a second rider could claim the same driver.

So the accept is a conditional write on the durable ride record, such as “set driver = D and state = matched only if state is offered and the offer id is X”. Only one write passes, and the loser gets a 409. A stale holder is also why locks use fencing tokens: each offer carries an increasing number, and the store rejects anything older.

In PACELC terms this is PC/EC for claims and ride state and PA/EL for locations (judgement). Idempotent accept and decline follow from the same write: a double tap finds the ride already matched to that driver and returns 200 again; an accept after the offer expired fails with 409 and the app shows “no longer available”. When the 15 s timer and the accept race, both are conditional writes on the same version, so exactly one wins.

How Do You Keep Ride State Correct?#

Polling#

Stored events#

Idempotent transitions#

The Final Design in One Picture#

Follow one ride:

1. Drivers send their position every few seconds. The regional location service updates its in-memory grid.
2. A rider taps request. The app sends a request_id with the pickup and destination.
3. The matching service reads the cells around the pickup and takes the closest candidates.
4. It asks the routing service for travel times from those candidates to the pickup, and ranks them, in a batch when drivers are scarce.
5. It claims the best driver with an expiring key and sends an offer. If the driver declines or the claim expires, it releases the claim and offers to the next one.
6. On acceptance a conditional write stores the ride as matched, and both apps are notified. Later transitions are stored first, then announced.

What Each Level Should Show#

Red Flags and Green Flags#

Try It: Choose the Cell Size#

Downtown 400/km2:
  res 8: 400 x 0.737 ≈ 295
  res 9: 400 x 0.105 ≈  42
Suburb 10/km2:
  res 8: 10 x 0.737 ≈ 7
  res 9: 10 x 0.105 ≈ 1

Check Yourself#

In One Picture#

Requirements
  locate, request, match, track
Scale
  125,000 updates/s · 50 MB live
Near
  cells sized to density
Soonest
  road ETA, batch when scarce
Claim
  fast key + conditional write
State
  versioned events, one owner
Rule
  index by place, rank by
  road, claim once

Conclusion#

A ride-sharing service is a live map plus a careful handshake. Keep the latest position of every driver in a spatial index in memory, rank a few candidates by real travel time, and claim the winner with an expiring key backed by a conditional write so only one rider gets them. Store every ride transition before announcing it, and shard by city.

The same ideas, cheap lookups for “near”, leases for work that can go quiet, and stored events for state, run through most of the problems in this module.

Which would you defend first in an interview: the grid, the ETA ranking or the claim? Tell us in the comments.