Proximity service (Yelp)

01 · CONTEXT AND REQUIREMENTS

What a proximity service needs to do

A proximity service answers the question "what is near me?": restaurants, stores, or services around a position. The classic example is a local business review site, and it serves as a pretext for a bigger topic, location search. In an interview, the first step is to requirements gathering.

In the example's functional requirements, the user searches for businesses by name, location, and category, views a business with its reviews, and leaves a review with a rating and optional text.

The non-functional requirements drive the design: low-latency search, high availability, and scale to a hundred million users per day and ten million businesses, which pushes search toward a dedicated index and toward cache.

02 · THE PROBLEM

Why a regular index does not solve it

Finding who is between two ages is fast because the B-tree keeps keys sorted side by side on disk, and the range becomes a nearly sequential read.

With location the reasoning breaks down: the B-tree sorts by one of the two numbers at a time, and flattening the map onto one axis can separate points that are neighbors on the ground. An index on latitude returns a horizontal band of the entire Earth, and the database ends up examining too many rows.

1. The user opens the app and the request reaches the search service with the position, the radius, and the filter.

2. The service queries the businesses table asking for everything inside the radius, with a condition on latitude and on longitude.

3. Without a structure that preserves proximity, the database can only use the order of one of the two numbers and examines a huge range of rows.

The way forward is to build a structure that produces a small set of candidates near the point. The index almost never delivers the final answer: the exact distance is computed only over those candidates.

03 · INDEX FAMILIES

Spatial trees and encoded cells

The first family builds a tree designed for spatial data. In the quadtree, the whole map is the root, divided into four quadrants, and a quadrant with too many points is divided again. The tree adapts to density: the center of a metropolis gets deep, while a lake remains a coarse cell.

The cost shows up at scale: in dense regions the tree gets deep and the busiest regions get slower. Also, the quadtree is a pointer-based structure, poor for disk, although it remains common in memory. For shapes such as polygons, the on-disk variant is the R-tree, used by geospatial databases.

The second family turns each position into a key that a regular index already knows how to sort. In geohash, the world is divided into a grid of 32 cells, each with one character, and the division repeats inside each cell. Keys with the same prefix tend to be close, so the search becomes a prefix scan.

The edge is the trap: two points one meter apart can fall into completely different prefixes. The standard fix is to query the point's cell and the eight neighbors and filter by exact distance. Variations such as S2 and H3 follow the same idea, with more regular cells on the sphere or in hexagons.

04 · DESIGN

The service with a cell index

The design separates two paths. Search computes the point's cells, gathers the candidates, and filters by distance. Business registration writes to the primary database, and replication keeps the cell index up to date. Since search dominates, the index lives on read replicas and the cache absorbs the most requested cells.

1. The app sends the position, the radius, and the filter; the load balancer forwards it to the search service.

2. The search service computes the point's cell and the eight neighbors, so as not to miss anyone on the other side of an edge.

3. If the same region was queried recently, the cache returns the candidates without going through the index.

4. If the cache does not have the answer, the service reads the businesses in the cells from the replica with the cell index.

5. The service computes the exact distance of the candidates, discards those outside the radius, and sorts the rest.

6. When a business changes, the business service writes to the primary database and replication updates the cell index.

05 · SCALE AND TRADE-OFFS

Partitioning without creating hot spots

When the index does not fit on one machine, it is partitioned, for example by region, and each partition gets read replicas. The trap is density: busy regions concentrate more points and more queries, the same problem as the deep quadtree in the center of a metropolis.

1. The request reaches the search service, which finds out which regions the query radius belongs to.

2. The query goes only to the partitions of those regions, instead of scanning the entire index.

3. A dense region receives many more points and queries than its neighbors and becomes a hot spot.

4. Read replicas absorb the excess queries from the hot partition.

In short: spatial tree for shapes, encoded cells for moving points, and always a final filter by exact distance. This reasoning is worth more than memorizing the name of a library. See also the choice of database and the particionamento.