Design Ride Sharing

You tap "Request" on a street corner. Within a few seconds the app shows a driver two minutes away, and a little car moves along the map toward you. Behind that screen, a million drivers are reporting their position every few seconds, and the system must find the right one near you and make sure no other rider gets the same car.

Interviewers like this question because it has three distinct hard parts that do not appear in request-and-response designs: a write rate far above the read rate, searching by location, and a race between riders for the same driver. The steps follow A Framework for Any Design.

#Clarify the problem

• Functional: drivers go online and report location; riders request a ride from a pickup point; the system offers the ride to a nearby driver, who accepts or declines; both see the trip's progress live; trips move through clear states and can be cancelled.
• Non-functional: no driver on two trips at once (strong consistency for assignment); match within about 5 seconds; locations at most about 5 seconds stale; trip records durable; the system keeps matching even if a location node dies.
• Out of scope: payments, pricing, shared rides, ratings, driver onboarding.

#Estimate the scale

• Location updates: 1 million drivers, one update every 4 seconds: 10⁶ ÷ 4 = 250,000 writes a second at peak. At about 100 bytes each that is 25 MB/s.
• Ride requests: 10 million ÷ 86,400 s ≈ 116 a second on average. Assume a rush-hour peak of 3x: about 350 a second. Writes outnumber matching requests about 700 to 1.
• Latest positions: 1 million drivers × 100 bytes = 100 MB. The whole live map fits in memory on one machine.
• Trip history: a 20-minute trip with a point every 4 seconds has 1,200 ÷ 4 = 300 points, 30 KB. 10 million trips × 30 KB = 300 GB a day, about 110 TB a year.
• Riders watching a car move: if each ride has about 5 minutes of waiting and 20 minutes of riding, 10 million × 25 ÷ 1,440 ≈ 174,000 riders are watching at once on average, each needing an update every 4 seconds: about 43,000 pushes a second.

#Define the API

Driver connection (WebSocket), app -> server:
  location { lat, lng, heading, speed, sent_at }      every 4 s, no reply
  status   { "available" | "offline" }
 
Driver connection, server -> app:
  offer { offer_id, trip_id, pickup, expires_in_s: 15 }
Driver connection, app -> server:
  accept { offer_id }
    -> accepted { trip }  |  refused: offer expired or already answered
 
POST /v1/trips   Idempotency-Key: 7f3a...
  body { pickup, dropoff, quote_id }
  202 { trip_id, state: "MATCHING" }
POST /v1/trips/{id}/cancel     200 | 409 trip already completed
Rider connection, server -> app: trip state changes, driver position

The decision worth arguing is how location updates travel. A fresh HTTP request every 4 seconds from a million phones is 250,000 requests a second, each with headers and often a new connection. A persistent connection carries small messages cheaply, and the server needs it anyway to push offers. Location messages get no reply and are never retried: if one is lost, the next one, 4 seconds later, is fresher than a retry would be. The realtime communication lesson covers the connection servers behind this.

#Model the data

-- in memory, sharded by region; rebuilt from updates within seconds
driver_pos:  driver_id -> { lat, lng, cell, updated_at }   expires after 30 s
cell_index:  cell -> set of available driver_ids
 
-- durable, strongly consistent per row
drivers:     driver_id PK, state,        -- offline | available | offered | on_trip
             offer_id NULL, trip_id NULL, version INT
trips:       trip_id PK, rider_id, driver_id NULL, state, pickup, dropoff,
             created_at, updated_at, version INT
 
-- append-only, partitioned by trip_id
trip_points: (trip_id, sent_at) PK, lat, lng

Three stores for three kinds of data. Positions go in an in-memory store (such as Redis): 100 MB, 250,000 overwrites a second, and nothing lost that the next update will not restore. Driver status and trips go in a relational database or any store with per-row conditional writes, because assignment correctness depends on "update only if the state is still X". Trip points are a high-volume append-only log read by trip ID, which suits a wide-column store (such as Cassandra).

#High-level design

#Deep dives

Interviewers push on four places: the location write rate, how you find nearby drivers, how you stop double assignment, and how a trip's states stay consistent.

#Location updates at 250,000 a second

Each update replaces the previous one. That changes everything: you do not need durability, history or replicas for the live positions, only a fast overwrite. If a geo index node dies, its drivers reappear within 4 seconds as their next updates land on the replacement. Say that out loud; it is the reason this part can be simple.

Shard the geo index by region: a city, or a block of cells within a big city. Requests and drivers are local, so a ride request touches one shard. Inside a shard, most updates do not move the driver to a new cell. At 50 km/h a car covers 50 ÷ 3.6 × 4 ≈ 56 metres between updates, and a cell is about 600 metres across, so a driver changes cell at most once every 10 or so updates. The rest are a single overwrite.

Only trip points need to be durable. While a driver is on a trip, the gateway also appends each point to a stream that feeds the trip-points store and the rider's screen. That is 300 points per trip and only for drivers on trips, a fraction of the 250,000 a second.

#Finding nearby drivers

"Drivers within 2 km" is slow if you compute the distance to a million drivers. Divide the map into cells, keep a set of available drivers per cell, and look only at the cells near the pickup.

A geohash interleaves the bits of latitude and longitude and writes them in base 32, so each extra character makes the cell 32 times smaller. Cell sizes shrink away from the equator in the east-west direction, which is a simplification the numbers above ignore.

The trap is the neighbour-cell problem. A rider standing near the edge of a cell may have the nearest driver 50 metres away, across the border, in a cell with a completely different string. Searching only the rider's cell misses that driver. Always search the cell plus its 8 neighbours: 9 × 1.2 × 0.6 ≈ 6.5 km². If that returns too few drivers, step out to the next ring or to a coarser precision. Straight-line distance is only a filter: a driver 300 metres away across a river may be 10 minutes out, so rank the top few by driving time from a routing service.

#Matching without double assignment

Two riders across the street from each other both see driver D7 as the closest. If both matchers read "available" and both write "assigned", D7 gets two trips. This is a classic read-then-write race, and it is the part interviewers care about most.

UPDATE drivers
SET    state = 'offered', offer_id = 'o-981', version = version + 1
WHERE  driver_id = 'D7' AND state = 'available';
-- 1 row updated: we own the offer.  0 rows: someone else got there first.

The precise guarantee to state: the conditional write must run against a single authority for that row, a leader or a consensus group. Quorum reads and writes on their own do not make "read, check, write" atomic; two clients can each read "available" from a quorum before either writes. The condition has to be checked and applied as one operation.

The offer itself is a lease with a 15-second expiry. Accepting checks the offer_id, so a retried accept is harmless and a late one is refused.

Accepting is two conditional writes in two stores, in a fixed order: the driver row (offered to on_trip, only if the offer is still live), then the trip (MATCHING to DRIVER_ASSIGNED, only if still matching). It is not one transaction. If the trip write fails because the rider cancelled, release the driver. If a crash falls between the two writes, the driver app retries the accept with the same offer_id, and a sweeper releases any driver whose trip_id points at a trip that is not theirs. Cancelling and completing release the driver the same way.

#The trip state machine

A trip passes through a fixed set of states, and many actors can try to change it at once: the rider cancels while the driver accepts, or a timeout fires as the driver taps "arrived". Write the allowed moves down and refuse everything else.

Each move is a conditional update on (trip_id, state, version). If the rider cancels and the driver accepts in the same instant, exactly one of those updates finds the expected state; the other gets a conflict and the app shows the true state. Every change is also published as an event, read from the database's change log so none is lost between write and publish. Events drive both apps and billing.

#Bottlenecks and failures

At 10x (10 million drivers, 2.5 million updates a second) the geo index needs more shards, split by smaller regions; a single dense city may need splitting by cell prefix. Each shard still holds little data, so the limit is update throughput, not memory. Matching grows to about 3,500 requests a second at peak, and driver-state writes grow with it; partition driver state by region so claims stay local.

#What a strong answer sounds like

#Follow-up questions

#How would you do surge pricing?

Count open requests and available drivers per cell every minute from the same index and events, and publish a multiplier per area. The pricing team owns the formula; the design only has to supply fresh counts.

#How do you estimate arrival time?

Use a routing service over the road graph with live traffic, a shortest-path search like Dijkstra's algorithm with heavy precomputation. Only call it for the handful of candidates that pass the straight-line filter.

#Could you match better by waiting?

Yes. In dense areas, collect requests for one or two seconds and assign them together to minimise total pickup time. It trades a little latency for better matches, and fits the one-matcher-per-region option.

#How do riders see the car move smoothly?

The server pushes the driver's position every 4 seconds over the rider's connection, and the app animates between points along the road.

#What if a driver's GPS jumps a kilometre?

Reject updates that imply an impossible speed, and snap positions to the road network before using them for matching or billing.