Design a Proximity Service
Open a maps app, tap "restaurants near me", and a list appears in a blink. Behind it is a proximity service: given a location and a radius, return the nearby businesses. The hard part is the index. Databases are great at "find rows where one number is in a range" but not at "find points inside a circle". In this chapter you'll see why, then learn the two classic answers, geohash and the quadtree, and put them in a design that serves thousands of searches a second.
This is the first chapter that follows System Design Interview, Volume 2.
- 17.1Requirements and scaleLet's agree on what we're building before drawing anything. Search: given the user's latitude, longitude and a radius (0.5, 1, 2, 5 or 20…
- 17.2Why a plain latitude/longitude query is slowThe obvious first try is a normal SQL query on a table of businesses: SELECT id, name FROM business WHERE latitude BETWEEN :lat - :dLat AND…
- 17.3Geohash: turning a location into a stringGeohash squeezes latitude and longitude into one short string by repeatedly cutting the world in half: Split the map down the middle by…
- 17.4Quadtree: split where the businesses areA fixed grid has a problem: a cell in downtown Tokyo may hold thousands of businesses, while a cell in the middle of the ocean holds none.…
- 17.5The architectureThe design splits naturally into a read path and a write path: Location-based service (LBS): handles searches. It's read-only and…
- 17.6Searching, step by stepPutting it together, a nearby search does this: The client sends latitude, longitude and radius. (Send the location only when searching,…