Geospatial indexing

A normal database index sorts by one column, but "nearby" depends on latitude and longitude together. Geospatial indexes get around that by dividing the map into cells, so a location turns into something you can look up quickly.

To find what's nearby, work out the search point's cell, look in that cell and the ones around it, and then calculate real distances for whatever you found.

Uber built and open-sourced H3, and has written about using it for pricing and dispatch. Hexagons are handy because every neighbor is the same distance away, which makes analyzing a map simpler.

Cell size is the big decision. Small cells are precise, but you have to check more of them. Big cells are cheap to search, but you get more results to filter through.

Things that move are their own headache, since constant updates are expensive on an index stored on disk. Fast-changing positions usually live in memory, and that's fine because they go out of date so quickly.

• Explain why you have to check the neighboring cells.
• Pick a cell size based on how far you're searching.
• Keep fast-changing positions separate from permanent records like finished trips.
• Think about crowded areas, because one busy cell can get overloaded.

Finding drivers within 2 km

A rider in a city opens the app. You need the available drivers within 2 km, out of 20,000 drivers in that city, and each driver sends their location every 4 seconds.

1. Pick a cell size close to the search radius. Geohash precision 6 cells are about 1.2 km by 0.6 km, which is a reasonable fit for a 2 km search.
2. Every location update computes the driver's cell and stores them in an in-memory set for that cell, say in Redis. 20,000 drivers every 4 seconds is 5,000 writes a second, which one Redis node handles easily.
3. When the rider searches, compute their cell and the cells around it. A 2 km circle crosses a handful of cells, so you look up maybe 9 to 25 sets.
4. That gives you, say, 300 candidate drivers. Compute the real distance to each one and keep the ones within 2 km. Checking 300 distances is nothing.
5. Sort what's left by distance, or better, by estimated arrival time from a routing service, since a driver across a river can be close but slow to reach.
6. When a driver moves to a new cell, remove them from the old set and add them to the new one. Put an expiry on each entry so a driver whose phone died drops out after a short time.

Things interviewers tend to ask once you've brought this up.

What about a downtown area with thousands of drivers in one cell?

Use smaller cells there, or a quadtree that splits busy areas more. You can also stop early once you have enough good candidates.

What if there's nothing nearby?

Widen the search ring by ring until you find enough results or hit a maximum distance.

Why not just use a database's built-in geo index?

For things that don't move much, like restaurants, that's often the right call. PostGIS and MongoDB do this well. For thousands of updates a second that are stale in seconds, an in-memory index is cheaper.

How do you shard this across machines?

By region or by a coarse cell, so a search usually stays on one machine. Searches near a boundary may have to ask two.

• Only searching the one cell the point is in.
• Writing every GPS ping to a disk-based database.
• Treating straight-line distance as travel time.
• Picking a cell size without tying it to the search radius.
• Forgetting to remove drivers who went offline.

• Sharding and consistent hashingSplit data across machines and keep it balanced.
• Stream processing and windowingCount things in data that never stops coming in.
• Caching strategiesMake reads faster, and figure out what to do when data changes.