1. Matching, not storing

Requirements

The hard part is not storing driver locations; it is answering "which drivers are near this rider, right now" fast enough to matter, while locations change every few seconds.

Ask what the matching objective is — nearest driver, shortest pickup time, best for the network — because they need different data. Ask what happens when two riders are matched to the same driver, which is the correctness question hiding in the problem.

The correctness question is double-assignment, not storage.

2. Location updates dominate

Estimate

A million active drivers each sending a location every four seconds is 250,000 writes a second, continuously, forever. Ride requests are a tiny fraction of that — perhaps a few thousand a second — so this is a write-heavy system with a small read workload attached.

A location update is small: driver id, latitude, longitude, timestamp, heading. Call it 64 bytes. 250,000 a second is 16 MB a second, 1.4 TB a day if you keep all of it — and you probably do not need to, which is worth saying.

250k location writes/s. Ride requests are noise beside it.

3. Partition by geography

A first design

The natural partition key is location: divide the world into cells, and put each cell on a shard. A rider's query touches their cell and its neighbours, which is a handful of shards rather than all of them.

This is correct and it is what everyone does. It also has a problem that no amount of hashing fixes.

Friday night in a city centre. What does the shard holding that cell look like?

Several times busier — it is a hot shard — Geography is the most skewed key there is. A stadium at kick-off is a single cell containing a hundred times the drivers of the cell next to it, and hashing the cell id spreads cells, not the load within one.

4. The hot cell

Watch it break

Run it with a hot key and watch the imbalance number. One shard at several times the average, while the others idle. Adding shards divides the cold traffic and leaves the hot cell exactly where it was.

This is the same lesson as the load balancer with a hot key, and it is worth internalising as a general rule: you cannot split a single key by adding capacity. You have to change what the key is.

A hot cell stays hot however many shards you add.

5. Make the cells adaptive

Find the bottleneck

The fix is a hierarchical grid rather than a fixed one: cells subdivide when they get busy and merge when they do not. A geohash or an S2 cell id gives you that for free, because a shorter prefix is a bigger cell and the hierarchy is in the key.

A dense city centre becomes many small cells spread across shards; an empty motorway is one large cell. The load per shard evens out because the partitioning follows the density rather than the map.

The cost is that the cell boundaries move, so a query near a boundary has to be careful, and rebalancing is continuous rather than occasional.

Subdivide by density, not by area. The hierarchy goes in the key.

6. And the double-assignment problem

Change one thing

Two riders request at the same moment and both matchers pick the same nearest driver. Whatever you do about locality, this is a mutual exclusion problem, and it is the part an interviewer is actually testing.

A distributed lock on the driver id is the obvious answer and it is not sufficient on its own: the lock has to expire, and a matcher that pauses for a garbage collection can wake up believing it still holds one. Run the lock concept and watch that happen.

The answer is a fencing token, or — better here — a conditional update: assign the driver with a compare-and-set on their state, and let the loser retry with the next nearest. The database enforces the invariant, which is the only place it can be enforced.

Enforce single-assignment at the store with a conditional update, not at the lock.

7. What else they will ask

What gets asked next

"Do you need the location writes to be durable?" Almost certainly not. A driver's position four seconds ago is worthless, so the current-location store can be in memory with no replication, and the durable trip record is a separate, far smaller write path. Separating them is worth several hundred thousand writes a second.

"What if a matcher reads a stale location?" It will. Locations are seconds old by construction, and the match is a proposal that the driver accepts or declines. Building the accept step in makes staleness a non-problem rather than a bug.

"How do you handle a region-wide outage?" Dispatch is naturally partitionable by geography, so a region is an isolation boundary you already have. Saying that unprompted is a strong signal.