Design a nearby-places service (Yelp)

The problem

Given a location and a radius, return nearby businesses, ranked and filtered (cuisine, open now, rating). It is read-heavy: millions of searches a day but few changes to the places themselves.

Estimates: 200 million places at around 1 KB each is about 200 GB, which fits in memory across a few machines. Search traffic might be tens of thousands of queries per second at peak.

Why not a simple range query

WHERE lat BETWEEN a AND b AND lon BETWEEN c AND d works in a toy system, but an index serves one dimension well: it returns all rows in the latitude band (a strip around the world), then must filter by longitude. We need an index that understands two dimensions together.

Idea 1: geohash

A geohash converts a location into a short string by repeatedly halving the map: each extra character narrows the cell.

• Locations in the same cell share a prefix, so a string-prefix index can find them.
• A longer hash means a smaller cell (about 150 m on a side at 7 characters, roughly).
• Border problem: nearby points can fall in neighbouring cells with different prefixes, so query the cell and its 8 neighbours, then filter by exact distance.

100%

Figure SDA-RWS-04-1 · Nearby search with geohash cells · © forcsguy.com

100%

Figure SDA-RWS-04-2 · Longer codes mean smaller cells · © forcsguy.com

Idea 2: quadtree

A quadtree is a tree where each node is a square region. If a region holds more than N places (say 100), it splits into four child squares, repeatedly. Leaves hold the places.

• Dense areas (city centres) become deep and fine; sparse areas stay coarse.
• To search, find the leaf containing the user, then widen to neighbouring leaves until you have enough places.
• Built in memory, it is fast. Rebuild it periodically (for example nightly) or update incrementally as places change.

Production systems often use S2 or H3: hierarchical cell systems on a sphere with good neighbour handling.

100%

Figure SDA-RWS-04-3 · Building a quadtree: split only where it is crowded · © forcsguy.com

Architecture

100%

Figure SDA-RWS-04-4 · Nearby places architecture · © forcsguy.com

• The search service looks up candidate place ids by cell, fetches details from a cache or database, filters, ranks and returns a page.
• Writes (a business is added or moves) are rare. They go to the places database; an index builder refreshes the geo index, and it is fine if that is a few minutes behind.

Rolling out a quadtree service

A quadtree lives in each server's memory and is built at start-up. With hundreds of millions of places that can take minutes, during which the server cannot answer. Restarting every server at once would take the whole fleet down. Deploy to a small slice at a time so the rest keeps serving, and only move on when the slice is healthy.

Scale

• The index is small enough to replicate on every search node, which scales reads simply.
• If it grew past one machine, shard by region (cell prefix), taking care with queries that cross shard borders.
• Cache results for popular areas; most users search the same few hotspots.
• Filters such as "open now" or cuisine can be applied after the geo lookup, or stored as extra index fields.

Ranking and details

Distance is only one signal. Combine rating, popularity, relevance to the query, and personalisation. Keep ranking in a separate step so you can improve it without touching the index.

Real-world reading