# System Design Interview: Designing a Proximity Service (Yelp / "Restaurants Near Me") Given a location and a radius, return nearby businesses quickly. The interesting part is the spatial index. ## Requirements - Search businesses within a radius (0.5 to 20 km) of a point, with filters. - 100M businesses; 5k searches per second; businesses change rarely. - Reads vastly outnumber writes. ## Why a plain index fails `WHERE lat BETWEEN ... AND lng BETWEEN ...` uses one B-tree index at a time and scans a huge strip of the globe. You need an index that keeps nearby points together. ## Options - **Geohash**: encode lat/lng into a base-32 string where a shared prefix means a shared cell. Look up the cell containing the point plus its 8 neighbors (to handle points near cell edges), then filter by exact distance. Easy to store in any key-value store or as an indexed string column. - **Quadtree**: recursively split a square into four until each leaf has at most K businesses (say 100). Dense cities get small cells, oceans stay large. Built in memory on each search server from the database at startup (100M points is a few GB). Good when density varies a lot. - **S2 / H3 cells**: hierarchical cells on a sphere used by Google and Uber; better at the poles and for covering a circle with cells. ## Architecture 1. **Location service** (stateless, read-only replicas): holds the spatial index, answers "IDs near (lat, lng, r)". 2. **Business service**: details, hours, photos; cached heavily. 3. Writes (new or edited businesses) go to the database and are picked up by an index rebuild every few minutes, which is fine because the data changes slowly. ## Ranking and edge cases Sort by distance, rating or relevance after fetching candidates. Expand the search to larger cells if the first ring returns too few results. Shard the index by region if it outgrows one machine. --- *Disclosure: I work at [Linkjob AI](https://www.linkjob.ai/), which builds an interview copilot app.*