Design ride matching
A million drivers, each sending where it is every four seconds, and a rider who wants the nearest one within two. The round turns on one sentence: locations live in memory keyed by a one-kilometre cell, a search reads nine cells, and a driver goes to one ride at a time under a lease.
The round this design follows
Why keep driver locations in memory and not in a database?
Because they are written 250 thousand times a second and every one of them is stale four seconds later. A durable database would spend its whole write budget on data nobody reads again. In memory the whole map of a million drivers is about 100 MB. If a node dies, every driver sends a fresh point within four seconds, so the map rebuilds itself; a snapshot every thirty seconds only shortens the gap.
Why search the neighbouring cells and not only the rider's cell?
Because the nearest driver can sit a few metres across a cell edge, in the next cell, while every driver inside the rider's own cell is further away. Reading the rider's cell and its eight neighbours covers a kilometre in every direction around any point in the middle cell. Nine reads for every ride request at the peak is 1.5 thousand reads a second, which the index does not notice.
How do you stop two riders being matched to the same driver?
The match service claims the driver in a small lock store before it sends the offer, with a conditional write: set this driver to this ride only if no other ride holds it, and let the claim expire after ten seconds. The second claim for the same driver is refused, and that match moves to its next candidate. The expiry means a driver who ignores the offer is free again without anyone cleaning up.
How do you shard the location index?
By city, because a ride never crosses one: every search and every update for a place lands on the one shard that holds it. A node at half its limit holds about 100 thousand drivers, so ten nodes carry the prompt and even the largest city fits on one. When a city outgrows a node, it splits into ranges of cells drawn by driver count, not by area.
What happens when the index for a city dies?
Its follower is promoted after three missed heartbeats, and for those three seconds the gateway holds each driver's latest point while searches read the follower. When the follower takes over it catches up on the held points within a few seconds. If both copies die, a fresh node is complete within one update interval, four seconds, because every driver sends again.