Design a ride-sharing service

In 2 minutes

I would treat location and trips as two different problems. Drivers send their position every four seconds, which is about 250,000 updates a second for a million drivers. I keep only the latest position in an in-memory grid index, mapping each cell to the drivers inside it. Dropping drivers not heard from in 30 seconds keeps it clean, and sharding by city keeps each shard small, around 100 MB. A ride request creates a trip in a database, then matching reads the pickup cell and its eight neighbours, shortlists drivers by distance and ranks a few by real travel time. It offers the trip to one driver at a time with a 15-second timeout, after taking a lock on that driver with set-if-absent and an expiry, so no driver gets two offers. When the driver accepts, the trip service performs a conditional update, setting the driver only if the trip is still requested with no driver, so a late cancellation and an acceptance cannot both win. The trip is a state machine with allowed transitions enforced in the database, and each change is logged as an event for billing and disputes. Payment and ratings follow asynchronously.

The question

Clarifying questions

• How many drivers are online at the same time, and how often do they report their position? Location updates will be the largest write load by far, so their rate decides how the index must be built.
• How should we choose a driver: nearest, fastest to arrive, or best overall? Straight-line distance is cheap, but road travel time is what a rider feels, so the shortlist needs a better ranking.
• Do we offer a trip to one driver at a time, or to several at once? Offering to many speeds up matching but creates conflicts when two accept. It drives the locking design.
• Do we support shared rides or scheduled rides? Both add planning work. Start with single, immediate rides and extend later.
• How exact must the trip record be? The trip drives billing and disputes, so its state changes must be strict, even though location data can be loose.

Requirements

Functional

• Let drivers go online and report their location continuously.
• Let a rider request a ride and be matched with a nearby available driver.
• Offer the trip to the driver, and let them accept or decline.
• Track the trip from request to completion, and trigger payment at the end.

Non-functional

• A driver is matched within 10 seconds at p95 in a busy area.
• A driver is never given two trips at once, and a trip never has two drivers.
• Handles 250,000 location updates a second at peak.
• Location data may be seconds stale, but trip state is always correct.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real service.
• 1 million drivers are online at the busiest time, each sending a position every 4 seconds. A location record takes about 100 bytes.
• 20 million rides a day, with a peak 5 times the average. An offer to a driver times out after 15 seconds.
• The index uses grid cells of about 1.2 km by 0.6 km. A search looks at the pickup cell and its 8 neighbours.

The arithmetic:

• Location updates per second: 1M drivers ÷ 4 s → 250,000/s
• Location ingest bandwidth: 250,000 × 100 bytes → 25 MB/s
• Geo index memory: 1M drivers × 100 bytes, latest position only → 100 MB, tiny
• Ride requests per second: 20M a day ÷ 86,400 s ≈ 231 → ≈ 230/s on average, about 1,160/s at a 5x peak
• Area searched per request: 3 cells wide × 1.2 km, 3 cells tall × 0.6 km → ≈ 3.7 km by 1.8 km
• Worst-case wait if three drivers decline: 3 offers × 15 s → 45 s, so keep the offer short and limit the tries

High-level design

Driver app and Rider app both reach the backend through an API gateway, which holds the live connection to each phone. Drivers send their position every few seconds to the Location service, which writes the latest position into the Geo index, an in-memory map from grid cell to the drivers inside it.

A ride request goes to the Trip service, which records the trip in the Trip DB and asks the Matching service for a driver. Matching looks up the cells around the pickup point in the Geo index and ranks the drivers it finds. It then locks the best one in the Lock store and sends them an offer.

If the driver accepts, the Trip service moves the trip to matched, but only if it is still waiting for a driver. Every later step, such as arriving, starting and finishing, is another controlled change of state in the Trip DB.

How a request flows

Driver location updates

1. The driver app sends its position every 4 seconds over its live connection.
2. The gateway routes the update to the Location service.
3. The service moves the driver to the right grid cell, removing it from the old cell. The entry expires after 30 seconds without news.
4. The service acknowledges the update.
5. The app gets the acknowledgement and keeps going. A lost update is replaced 4 seconds later.

Request a ride and offer it

1. The rider confirms a pickup point and destination.
2. The gateway passes the request to the Trip service.
3. The service creates the trip in the requested state, with a unique ID.
4. It asks the Matching service to find a driver.
5. Matching reads the pickup cell and its 8 neighbours from the geo index, keeping only available drivers.
6. It gets a list of nearby drivers, then ranks the closest few by estimated arrival time.
7. It locks the best driver for this trip, using set-if-absent with a 15-second expiry.
8. Matching sends the offer to that driver's app through the gateway.

The driver accepts

1. The driver taps accept within the 15-second window.
2. The gateway passes the acceptance to the Trip service.
3. The service sets the driver on the trip only if it is still in the requested state with no driver.
4. The update changed one row, so the match is final. If the rider had cancelled, it would change none.
5. The Trip service confirms the match to the gateway.
6. The rider sees the driver's name, car and estimated arrival.

Deep dive: location updates and the geo index

Each driver app sends its position every few seconds, faster during a trip and slower when idle. That is 250,000 updates a second in our estimate. Writing each one to a database would be wasteful, because a position is out of date within seconds. So keep only the latest position in memory. Send a sampled copy to a stream for analytics and trip history, off the critical path.

A grid index makes nearby searches fast. Divide the map into cells, and for each cell keep the set of drivers inside it. Common cell schemes are geohash, where a longer string means a smaller cell, and hexagonal grids. We use cells of about 1.2 km by 0.6 km.

• Update: work out the driver's new cell. If it changed, remove the driver from the old cell's set and add them to the new one. Store the driver's exact position, status and last-seen time. Drop drivers not heard from in 30 seconds.
• Query: take the pickup cell and its eight neighbours. Include the neighbours always, because a pickup near a cell edge has closer drivers on the other side. Prefilter by straight-line distance, then ask a routing service for the real travel time of the few best.

A quadtree is another choice: it splits a crowded area into smaller squares, so a dense city centre gets fine cells and a quiet suburb gets large ones. It adapts well but must be rebalanced as drivers move, and that is costly with 250,000 moves a second. A fixed grid is simpler, and cell updates are cheap, so I would start there.

Shard the index by city or region. A driver and a rider in the same city always reach the same shard, and 100 MB of data per city is easy to hold. If a shard restarts, drivers refill it within seconds from their next update.

Deep dive: matching and the lock against double booking

Offering a trip to many drivers at once is fast, but several may accept, and the losers see their offer vanish. Offering to one driver at a time, with a short timeout, is fairer and simpler, though slower when drivers decline. A refinement is to collect requests for a couple of seconds and assign drivers to riders together, which lowers the total waiting time in busy areas.

The danger is two matching workers picking the same driver for two trips. Prevent it with a lock. Before sending an offer, the Matching service writes a key for the driver, with the trip ID as the value, using set-if-absent and an expiry of the offer window plus a small margin. If the write fails, someone else has the driver, so try the next candidate. The expiry means a crashed worker can never hold a driver forever.

When the driver accepts, the Trip service makes the final decision with a conditional update in the database: set the driver on the trip only if its state is still requested and it has no driver. The lock gives fast, short-lived exclusion, but the conditional update is the real guarantee, because it is checked against the durable record.

Consider the races:

• The rider cancels while the driver accepts. Both are conditional state changes on the same row, so exactly one wins, and the other receives a clear 'no longer available' reply.
• The driver declines or the 15 seconds pass. The lock expires or is released, and Matching moves to the next candidate. Limit it to five tries, then tell the rider no driver is nearby.
• The Matching service dies mid-offer. Locks expire on their own, and the Trip service retries any trip that stays in requested for too long.

Deep dive: the trip state machine

A trip is a state machine. Its states are requested, matched, driver arriving, in progress and completed, with cancelled and no driver found as exits. Only certain moves are allowed. A trip cannot go from requested to in progress, and a completed trip cannot be cancelled.

Enforce this in the database, not only in code. Every change is a conditional update that names the state it expects: change this trip to in progress, but only if it is now driver arriving. If zero rows change, the move was invalid or someone else got there first. Because the check and the change are one statement, two services cannot both apply conflicting moves.

Record each move as an event in an append-only log: the trip, the old and new state, the time, and who or what caused it. This gives an audit trail for disputes, and the data for billing. Give each event an ID, so a retried message does not apply twice.

Phones lose signal, so the apps must cope. Realtime updates over the live connection are a convenience, but the source of truth is the Trip DB. When an app reconnects, it fetches the current state and carries on. A driver's app can buffer positions while offline and upload them later, so the fare can still be computed from the route.

When the trip completes, publish an event. Payment, receipts, ratings and fare adjustments follow it asynchronously, and each step is idempotent. Pricing during busy times is a separate calculation, often based on the number of requests and available drivers per cell, and it should never sit on the trip's critical path.

Trade-offs

• Location storage: An in-memory index holding the latest position over Write every update to a database. It handles 250,000 writes a second in 100 MB of memory. The cost is that positions vanish on a restart until drivers report again, which takes seconds.
• Spatial index: A fixed grid of cells over A quadtree that adapts to density. Updates are cheap and the code is simple. The cost is cells that are too large downtown and too small in quiet areas.
• Offers: One driver at a time, with a lock over Offer to many drivers and take the first to accept. No conflicts and no vanished offers. The cost is slower matching when the first drivers decline.
• Trip record: A database with conditional state changes over State held in the matching service's memory. Crashes and races cannot corrupt the trip. The cost is a database write on each state change.

Common follow-up questions

How do you estimate the arrival time?
Use straight-line distance only to shortlist drivers. Then ask a routing service that knows the road network and current traffic for the real time of the best few. Cache common routes for a short time so the service is not asked the same question again and again.

What happens if a geo index node crashes?
Drivers send their position again within 4 seconds, so the shard rebuilds itself almost at once. Matching in that city is slightly less accurate for those seconds. For a faster recovery, keep a replica fed by the same updates.

How would you add surge pricing?
Count ride requests and available drivers per cell over the last minute or two. When demand exceeds supply, raise a price multiplier for that cell, and smooth it over time so it does not flicker. Compute it in a separate service and show the price before the rider confirms.

How do you scale to many cities?
Shard everything by region. A city has its own geo index, matching workers and trip partition, so a busy city cannot slow another. Only global things, like accounts and payments, are shared.