Design a Ride-Sharing Service

A ride-sharing system matches riders who want a trip with nearby drivers, in real time, on a map. The problem combines three things that interviewers love: a very high rate of small location writes, a geospatial query ("who is near this point"), and a matching step where consistency matters because one driver must not be promised to two riders.

The chapter follows the usual shape: understand the problem, set up the interface, build the high-level design, then go deep on the places interviewers push, each with a weak, a solid and an excellent answer.

1. Understanding the problem

Riders request a trip from a pickup point to a destination. The system finds a nearby available driver, offers them the trip, and, once accepted, tracks the trip until it ends and the rider is charged.

Functional requirements

Core:

1. A rider can request a ride and see an estimated fare and arrival time.
2. The system matches the rider with a nearby available driver, who can accept or decline.
3. Rider and driver can see each other's live location during the trip.

Confirm in or out: ride pooling and shared rides, scheduled rides, ratings, payments inside the system, and driver onboarding. A sensible opening: "I will design request, matching and live tracking, with fares calculated at a high level, and leave payments and pooling out."

Non-functional requirements

• Low latency matching. The rider should see a driver assigned within seconds.
• High availability. An outage strands riders and drivers in the real world.
• Consistency in matching. A driver must not be assigned to two trips, and a trip must not be assigned twice.
• Eventual consistency is fine for the map. A driver's position may be a few seconds old.
• Scale. Assume 1 million drivers online at peak, 20 million rides a day.

Estimation

What the numbers say. The volume of location updates is large, but the data is tiny: the whole live driver table fits on one machine's memory. The challenge is the write rate and answering "who is near here" quickly, not storage. Ride requests are comparatively rare, so the matching path can afford stronger consistency than the location path.

2. The set up

Core entities

• Rider and driver, with driver status (offline, available, on a trip).
• Location: driver identifier, latitude, longitude, heading, time.
• Trip: rider, driver, pickup, destination, state, fare.

API

POST /v1/rides/estimate  { pickup, destination }          -> { fare_estimate, eta }
POST /v1/rides           { pickup, destination, ... }     -> { trip_id, state: "matching" }
POST /v1/drivers/location { lat, lng, heading }           (every few seconds, over a persistent connection)
POST /v1/trips/{id}/accept  (driver)  /decline  /start  /end
GET  /v1/trips/{id}                                       -> state, driver location, ETA

Real-time updates to the rider, such as "your driver is 2 minutes away" and the moving car on the map, are pushed over a persistent connection, the same pattern as chat.

3. High-level design

Separate the components by their consistency needs:

• A location service receives driver positions and updates an in-memory geo index. This path is high-volume and loss-tolerant.
• A matching (dispatch) service finds candidates and runs the offer protocol. This is the correctness-critical part.
• A trip service owns the trip state machine and stores it in a transactional database.
• A pricing service estimates fares and applies surge.
• A gateway terminates connections, and push notifications reach apps in the background.

Location updates also flow to a stream, which feeds historical storage and analytics, but the live index is what matching reads.

4. Potential deep dives

Deep dive 1: How do you ingest 250,000 location updates per second?

The challenge. Every driver reports a position every few seconds. Most of those updates are immediately overwritten by the next one.

Weak: write every update to the relational trips database. 250,000 durable writes per second to a transactional database is wasteful and unnecessary: the old position has no value once a new one arrives. It will saturate the database and slow down the trip operations that share it.

Solid: keep only the latest position in a fast in-memory store. Treat the current location as ephemeral state. A key-value store in memory keyed by driver, holding the latest position, can take hundreds of thousands of writes per second and shard by driver. A driver who stops reporting is aged out by a time-to-live. Persist only what needs durability: the trip's route points, written less often.

Excellent: ephemeral live state, a stream for history, and adaptive update rates. Keep the live geo index in memory, partitioned by region so that each node handles a fraction of drivers. Publish the same updates to a durable stream so that history, analytics and fraud detection consume them without touching the live path. Reduce load further by making the update rate adaptive: a stationary driver reports less often, a driver on a trip reports more often, and the client sends a new position only if it moved more than a threshold. If the live node dies, drivers repopulate it within seconds simply by sending their next update, so there is no recovery procedure for ephemeral state.

Deep dive 2: How do you find nearby drivers fast?

The challenge. For each request, find the available drivers within a few kilometres of the rider, out of a million, in milliseconds.

Weak: scan all drivers and compute distance. A million distance calculations per request is far too slow at hundreds of requests a second, and gets worse with scale.

Solid: a spatial index over a grid of cells. Divide the map into cells, and key each driver by their cell. Finding nearby drivers becomes "read the rider's cell and the neighbouring cells". Common cell systems are a geohash, which encodes a location as a string whose shared prefix means proximity, or hierarchical grids such as S2 or H3. Choose a cell size from the density: smaller in cities, larger in rural areas.

Excellent: adaptive cells, ring expansion and region sharding. Use a cell resolution fine enough to hold a manageable number of drivers per cell, and expand the search ring until you have enough candidates or reach a maximum radius. Remember that straight-line distance is a poor proxy for arrival time because of roads, rivers and one-way streets, so use cells to find candidates quickly, then rank by estimated travel time from a routing service. Shard the geo index by cell id, so that all the drivers in an area live on one node and a nearby query rarely crosses nodes. Handle the shard boundary by also querying the neighbouring cell's owner. A quadtree is an alternative that adapts its subdivision to density, but the fixed-grid approach is usually easier to shard and update.

Deep dive 3: How do you match without double-assigning a driver?

The challenge. Several riders may want the same nearby driver at the same moment, and a driver may be accepting a different offer.

Weak: pick the nearest driver and tell them. Two requests can pick the same driver concurrently, and both riders are told the driver is coming. The race leads to a stranded rider.

Solid: lock the driver while making an offer. Before offering a trip, atomically move the driver from "available" to "offered", with an expiry of about fifteen seconds. Only one request can make that transition. If the driver accepts, the trip is created and the driver becomes "on trip". If they decline or the offer times out, release the driver and move to the next candidate.

Excellent: a dispatch protocol with sequential offers, timeouts and fairness. Offer to one driver at a time, ranked by estimated arrival time, with a short timeout, and release locks automatically on expiry so a crashed dispatcher cannot hold a driver forever. Make the lock an atomic conditional update, and make the trip creation idempotent with the request identifier, so a retry does not create two trips. Consider fairness and efficiency beyond nearest-first: batching requests over a short window and solving a global assignment (minimise total wait across several riders and drivers) can beat greedy one-at-a-time matching in busy areas. Mention it as an optimisation and keep the simple protocol as the baseline.

Deep dive 4: How does the rider see the driver move?

The challenge. During a trip, the rider's map shows the driver's position and an arrival estimate, updated every few seconds.

Weak: the rider's app polls for the driver's location. Many apps polling every second multiplies load and adds delay.

Solid: push over a persistent connection. The rider's app holds a WebSocket. The server pushes the driver's position when it changes. Subscribe the rider to the single driver and trip they care about, so the fan-out is one to one.

Excellent: push with smoothing and degradation. Push position updates at a modest rate and let the client interpolate movement between updates so the car moves smoothly. If the connection drops, fall back to polling or a push notification for key events (driver arriving, trip started). Keep ETA updates cheap by recomputing at intervals or on significant deviation, not on every position update.

Deep dive 5: Surge pricing and supply-demand balance

The challenge. When demand exceeds supply in an area, prices rise to attract drivers and temper requests.

Weak: a fixed price everywhere. No signal to rebalance supply, so riders wait too long in busy areas.

Solid: compute demand and supply per cell and set a multiplier. Count recent ride requests and available drivers for each cell over a rolling window, and derive a multiplier from the ratio, within bounds.

Excellent: smoothed, bounded and transparent. Smooth the multiplier over time and between neighbouring cells so prices do not jump block to block, cap it, and show it to riders before they confirm. Lock the quoted price for a short time so a rider is not surprised. Note that dynamic pricing is also a policy and fairness question, and some regions regulate it, so build the cap as configuration.

Deep dive 6: Trip lifecycle and failure

The trip as a state machine. Requested, matching, driver assigned, driver arrived, in progress, completed, or cancelled, with each transition recorded in the transactional database and validated against the current state. A transition that arrives out of order, such as "end" before "start", is rejected.

Failure cases to cover. A driver's phone loses connection mid-trip: keep the trip alive, show the last known position and reconnect when possible. The dispatcher crashes while offering: offers expire and release their locks. The matching region goes down: fail over to a replica, and meanwhile new requests in that region queue briefly or are routed to a neighbouring region. A rider cancels after assignment: free the driver, apply the cancellation policy and record it.

5. What is expected at each level

Mid-level. You separate location updates from trips, propose a spatial index such as a grid or geohash, and recognise that a driver must not be assigned twice. You describe the trip flow end to end.

Senior. You explain why live location is ephemeral state in memory, size the write rate and the data, design the offer-lock protocol with timeouts, and use cells for candidates then ETA for ranking. You handle push updates and the main failure cases.

Staff. You reason about city-scale behaviour: hot regions, shard boundaries, surge dynamics, global assignment versus greedy matching, graceful degradation when a region is impaired, and the data pipeline for fraud and analytics. You also discuss privacy of location data and retention.

6. Interview questions and model answers

Q: Where do you store driver locations? In an in-memory store keyed by driver, partitioned by region, since only the latest position matters. History goes to a stream and durable storage written less often. If a node dies, drivers repopulate it with their next update.

Q: How do you find nearby drivers? Divide the map into cells, such as geohash, S2 or H3 cells. Look up the rider's cell and its neighbours, widen the ring if needed, then rank candidates by estimated travel time.

Q: How do you avoid assigning one driver to two riders? An atomic transition from available to offered with an expiry. Only one request wins it. Acceptance moves the driver to on-trip, and a decline or timeout releases the driver.

Q: Why is the database not the live location store? 250,000 writes per second of data that is stale in seconds is wasteful for a transactional database and would compete with trip operations. Live location is ephemeral and belongs in memory.

Q: What if two nearby cells are owned by different shards? Query the neighbouring shard as well, merge the candidates, and rank. Boundary queries cost an extra call, which is acceptable.

Q: How would you improve on nearest-driver matching? Batch requests in a short window and solve an assignment problem over riders and drivers to minimise total wait time, with the simple offer protocol as the fallback.

7. Common mistakes

• Writing every location update to a transactional database.
• Scanning all drivers to find the nearest.
• Using straight-line distance as the final ranking.
• Offering a trip to a driver without locking them.
• No expiry on offers or locks, so a crash strands a driver.
• Polling instead of pushing live positions.
• Forgetting the shard boundary in a spatial query.