Medium · 11 steps · ~60 min

Design a proximity service (nearby search)

Turn latitude and longitude into fast 'near me' lookups for millions of people.

A local-search app shows the places near you: cafes, shops and services. Searches vastly outnumber changes to the places themselves, and the queries are geographic, which ordinary indexes handle poorly.

Same problem as YelpGoogle Maps nearbySnap Map

How it works

• Search: given a position and radius, return nearby places.
• Details: open one place.
• Update: owners add or move places; users may also share live positions.

What you'll build

1. The API and a geohash-based data model
2. Caching and a CDN keyed by map cell
3. A geo index and a write-behind cache for location updates
4. Sharding by region
5. A design that survives a cold cache and a lost index node

Steps

1. 1Design the API
2. 2Design the data model
3. 3Serve 2,000 requests per second
4. 4Cache hot areas at 20,000 requests per second
5. 5Add a geo index and a CDN at 60,000 requests per second
6. 6Absorb location updates at 50,000 requests per second
7. 7Geohash or quadtree?
8. 8Go worldwide at 300,000 requests per second
9. 9Choosing the shard key
10. 10Survive a cold cache at 16,000 requests per second
11. 11Lose a geo index node