Why Uber chops the map into hexagons

transcript

One and a half million cars. All moving. Find the free ones near you. You get under 100 milliseconds. Uber's answer? Hexagons.

One and a half million drivers are online at once. Each one sends its location every 4 seconds. That's about 500,000 pings a second at peak. Check them all? Far too slow.

So bucket the map into cells. Squares look obvious. But a square has two kinds of neighbour. Corners sit farther away than edges. So square rings distort your radius. A hexagon has six neighbours. Every one the same distance away. So rings of hexagons approximate circles. Exactly what near me means.

Uber open-sourced this grid. It's called H3. For matching, resolution 9. Each cell is about 0 point 1 square kilometres. An edge of about 200 metres. Roughly a street block.

Your pickup becomes a cell ID. In Redis, that cell is a set of free drivers. Not enough? Read the six cells around it. Ring one. Still short? Ring two. Keep growing until you have enough. No distance maths over millions. Just a few set lookups.

Here's the clever bit. Every ping overwrites a driver's position. But a driver only changes sets when they cross into a new cell.

So near me stops being a search. It's a set lookup. Hexagons make near me a set lookup. Say that in your interview.

Full breakdown in the lecture.