Design a ride hailing service
Two hundred thousand drivers are moving around a city, each one reporting where they are every four seconds. A rider opens the app and wants the five nearest cars, then thirty seconds later wants exactly one of them assigned to nobody else.
Those are two completely different systems sharing a screen. One is a write heavy geospatial index taking fifty thousand location updates a second. The other is a matching problem where the same car must never be promised twice. Most candidates design the first one and hand wave the second, and the second is where the interview is.
Step 1: Understand the problem
Ask about the matching before you ask about the map. The map is a solved problem with a known answer, and the matching is where the real decisions are.
| You ask | They say | What it settles |
|---|---|---|
| How many drivers are online, and how often do they report position? | A couple of hundred thousand in a large city, every four seconds. | Fifty thousand writes a second into whatever holds locations. That number alone rules out a relational table with a spatial index and pushes you to an in memory grid. |
| How fresh does a driver location have to be for matching? | Within a few seconds. | Location is soft state. It can live in memory, be lost on restart and rebuild itself in four seconds, which removes durability from the hottest write path in the system. |
| Can two riders be matched to the same driver? | Never. | A serialisation point per driver, and an offer that locks the driver while they decide. This is the hard requirement, and it is not solved by the geospatial index. |
| What happens if a driver ignores the request? | Move to the next one, within seconds. | Offers with a short timeout and automatic reassignment, so the matching state machine has a timer in it. It also means a rider is waiting while you try three drivers in sequence. |
| Does the price change while the rider is looking? | It is quoted up front and honoured. | A pricing service that reads supply and demand per area on a slow loop, and a quote that is frozen into the trip. Recomputing at accept time is how you get a support ticket. |
| Is a trip record allowed to be lost? | Absolutely not. It is money and it is a legal record. | Two different storage systems with two different guarantees. Locations are disposable, trips are durable and transactional, and confusing the two is the most common mistake in this design. |
What you are building, and what you cut
- Drivers report location continuously. Fifty thousand writes a second, and none of them individually matter.
- Riders see nearby drivers and request a ride. A read of the same index the writes go into.
- Match one rider to exactly one driver. With offers, timeouts and reassignment. This is the actual system.
- Track the trip to completion and record it. Durable, transactional, and the source of truth for payment.
- 200,000 concurrent drivers per city, 50,000 location updates a second.
- Nearby drivers returned in under 200ms.
- A driver is never offered to two riders at once.
- A trip record survives any single component failing.
- Routing and ETA computation. It is a graph problem with its own literature, and here it is a call to a maps service.
- Payments. The trip ends with a call to a payment rail, which has its own design page.
- Pool and shared rides. A different matching problem entirely, and adding it doubles the page.
- Fraud, incentives and driver supply positioning. Real, enormous, and not what is being asked.
Back of the envelope
Those two numbers together are the design. 24MB of live state means the whole city fits in memory, and 50,000 writes a second means you must never touch a disk to record one. The moment somebody suggests persisting every location update, ask what reads it.
Candidates size storage for location history and end up designing a time series database. Nothing in the matching path ever reads a location older than a few seconds. Keep the live position in memory, and if the business wants trip traces for analytics, publish them to a log the matching system never queries. Two systems, two lifetimes.
Step 2: Propose the high level design
The API
{
"driverId": 88213,
"lat": 12.9352,
"lng": 77.6245,
"heading": 138,
"at": "2026-09-10T09:14:22Z"
}{
"riderId": 4471,
"quoteId": "q_71a2",
"pickup": {...},
"dropoff": {...}
}The data model
Two stores, and the split between them is the design.
| cell | geohash(6) | PK | About 1.2km on a side. A search reads this cell plus its eight neighbours, never a range scan. |
| driver_id | bigint | PK | Member of the cell set. Moving cells is a remove and an add. |
| lat, lng, heading | float | Overwritten every four seconds. There is no history and nothing reads the previous value. | |
| state | enum | IDX | available, offered, on_trip. Only available drivers are returned, and this field is why a search is cheap. |
| updated_at | timestamp | A driver whose entry is older than 30 seconds is treated as offline. Expiry, not a delete path. |
| trip_id | uuid | PK | Generated at request time, before any driver exists. |
| rider_id | bigint | IDX | |
| driver_id | bigint | IDX | Null until an offer is accepted. The unique constraint on active trips per driver is the last line of defence against double assignment. |
| state | enum | matching, assigned, arriving, in_progress, completed, cancelled. Transitions are guarded, not free. | |
| quote_id | varchar(32) | The price the rider was shown. Copied into the trip so it cannot drift. | |
| version | int | Optimistic lock. Every state change is a compare and set, which is how two concurrent accepts resolve. |
The whole system on one whiteboard
Walking Figure 1:
- Driver apps hold a persistent connection and stream position. Opening a fresh HTTPS request every four seconds for 200,000 drivers is a self inflicted denial of service.
- The gateway overwrites the driver’s entry in the geo index. No append, no history, no disk. If the driver moved into a new cell, that is a remove and an add.
- A rider opens the app and asks who is nearby.
- That search reads the same in memory index the writes go into, filtered to available drivers.
- The price is quoted once, here, and frozen into a quote id, so it cannot drift between looking and accepting.
- Requesting a ride hands the problem to the matching service, which returns immediately with a trip in the matching state.
- Matching reads candidate drivers from the index, ranked by ETA rather than by straight line distance, because a river or a one way street makes those very different numbers.
- The trip row is created before any driver is contacted. If everything crashes now, there is a durable record saying a rider is waiting.
- An offer goes to one driver with a short expiry, and a timer owns what happens if they do not answer. That timer is the part people forget, and it is the difference between a system and a demo.
Step 9 offers the ride to one driver at a time with a 15 second timer. The alternative is broadcasting to the nearest five and letting them race. Which would you pick, and what does the other one cost?
Step 3: Design deep dive
Finding nearby drivers without a spatial database
The obvious answer is a relational table with a spatial index and a bounding box query. It works, and it falls over at fifty thousand writes a second, because every one of those writes updates an R-tree and R-trees do not enjoy that.
The answer that scales is to give up on exact geometry and bucket the world.
Start with geohash cells and say why: it is a hash map of sets, a write is two operations, and it needs no rebalancing under load. Then name its weakness before the interviewer does, which is that a fixed cell size is wrong somewhere in every city, and say that S2 is what you move to when that starts costing you matches.
Sorting candidates by straight line distance is the beginner version and it produces visibly stupid matches: the closest car is across a river with a ten minute detour to the bridge. Rank by ETA from the maps service, on the handful of candidates the cells gave you. Nine cells might return two hundred drivers, you take the twenty closest, and you ask for real ETAs only for those twenty. That is the shape of nearly every geospatial ranking problem: cheap filter, expensive rank, small candidate set.
One driver, one rider, no exceptions
This is the part that separates the answers. Two riders, two matching workers, one driver sitting between them, and nothing in the geo index stops both from picking him.
Two details worth saying out loud. The lease has to expire on its own, so a matcher that crashes between the compare and set and the offer does not strand a driver as permanently offered. And the accept has to be idempotent, because a driver on a patchy connection will tap it twice and both taps will arrive.
“Why not broadcast to the five nearest drivers and let the fastest one win?” It matches faster and riders like it. It also means four drivers get a notification for a ride they cannot have, which is the single most complained about behaviour in every driver app that has tried it, and it turns acceptance into a race decided by phone hardware and network latency. The usual compromise is sequential offers with a short timeout, and broadcast only when sequential has already failed twice.
Sharding a city, and what happens at the edges
One matching service cannot own a whole country, and the obvious shard key is geography. Assign each region to one matcher, and that matcher is the single serialisation point for drivers inside it, which is what makes the compare and set cheap and local.
The problem is the boundary. A rider standing on the line between two regions has candidates owned by two different matchers, and now the thing that made assignment simple is gone.
The workable answer is that the matcher for the rider’s region owns the trip, and it may read candidates from neighbouring regions but must acquire the driver through the matcher that owns that driver. Cross region matches are a small percentage of traffic and they are allowed to be slower. What you must not do is let both matchers assign, which is the double booking you spent the last section preventing.
Sharding by city rather than by grid is usually the honest answer, because cities are natural boundaries. Almost nobody takes a ride from one city into another. Where they do, that trip is a business event worth handling specially, not a hot path.
Break it
The stadium case is the one to talk about unprompted. Every geospatial system has it, the map makes it look like a new problem, and it is the same hot partition you would get from a celebrity account or a viral link.
Trade-offs
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Locations in memory, trips in a database | The 50,000 writes a second never touch a disk, and the records that matter get real transactions. | Two systems to operate, and a rule everyone has to remember about which data goes where. | Always. The single store version either cannot take the write rate or is not durable enough for the money. |
| Geohash cells over a spatial index | A write is two set operations and a read is nine memory lookups, with nothing to rebalance. | Fixed cell size is wrong in both dense and empty areas, and cells distort away from the equator. | From the start. Move to S2 when you can measure the distortion costing you matches. |
| Sequential offers with a timeout | One driver is asked at a time, so nobody gets a notification for a ride they cannot have. | Slower matching when drivers are slow to answer, since three offers in sequence can take 45 seconds. | Default. Fall back to a broadcast round only after sequential offers have already failed. |
| One matcher per region | Assignment is a local compare and set with no distributed coordination. | Boundaries need special handling, and a hot region bottlenecks on one process. | Any system where the natural unit of contention is geographic, which is all of them. |
Interview replay
Checkpoint
1. Why keep driver locations in memory rather than in a replicated database?
2. Two matchers pick the same driver from the index at the same instant. What prevents a double assignment?
3. Same system, but now it delivers food instead of people. What changes first?
- 200,000 drivers reporting every 4 seconds is 50,000 writes a second.
- The entire live location state is a few hundred megabytes. It fits in memory and it is disposable.
- Nine cells cover a search: your own, plus the eight neighbours.
- One driver, one rider, settled by a compare and set with an expiring lease. The loser just takes the next candidate.
A ride hailing service is two systems that share a screen. Driver locations are 50,000 writes a second into an in memory index bucketed by geohash cell, with no durability at all, because nothing reads a position older than a few seconds and the whole state rebuilds itself in one reporting interval. Trips are the opposite: a real database with transactions, because that is money and a legal record. A nearby search reads nine cells, filters to available drivers, and ranks the top twenty by real ETA rather than straight line distance. Matching is the hard half. Two matchers will see the same driver, so I resolve it with a compare and set on the driver state from available to offered with an expiring lease, and the loser moves to its next candidate. Offers go to one driver at a time with a short timeout and automatic reassignment. The failure mode I would call out is a concert letting out, which is a hot partition in a handful of cells owned by one matcher, and the fix is splitting that region dynamically plus an honest queue for riders rather than a retry loop.
