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.

What you are building, and what you cut#

Back of the envelope#

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.

The whole system on one whiteboard#

Walking Figure 1:

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.
2. 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.
3. A rider opens the app and asks who is nearby.
4. That search reads the same in memory index the writes go into, filtered to available drivers.
5. The price is quoted once, here, and frozen into a quote id, so it cannot drift between looking and accepting.
6. Requesting a ride hands the problem to the matching service, which returns immediately with a trip in the matching state.
7. 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.
8. The trip row is created before any driver is contacted. If everything crashes now, there is a durable record saying a rider is waiting.
9. 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 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.

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.

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#

Interview replay#

Checkpoint#