Design Yelp: A Proximity Service with Geohashes, Quadtrees and Ranked Results

Listen

Requirements. A user searches for businesses near a location, within a radius like five hundred metres or five kilometres, and filters by category, price and open now. Results can be sorted by distance or rating. They view details, and write reviews with a star rating. Business owners can edit their listing. Booking, ads and photo handling are out of scope.

Qualities. Search should come back in under a hundred milliseconds at p ninety-nine. It's very read heavy, and business data changes slowly: a new restaurant appearing a few minutes late is fine, so we can rebuild indexes in the background. A user should see their own review immediately. And for privacy, we don't keep a history of where users searched from.

Ask scale

Say two hundred million businesses worldwide and a hundred million daily users doing five searches each: five thousand queries a second, fifteen thousand at peak. Business details are about a kilobyte each, two hundred gigabytes in total. But the geo index needs only an ID and a location code per business, sixteen bytes, which is about three gigabytes. The whole index fits in the memory of a single server, so we can replicate it rather than shard it.

businesses            200M
DAU                   100M
searches/user/day     5
  500M / 100,000 s  = 5K qps
  peak x3           = 15K qps

business row ~1 KB
  200M x 1 KB       = 200 GB
geo entry: id 8 B + hash 8 B
  200M x 16 B       = 3.2 GB
-> geo index fits in RAM

Define API

The API. The nearby search takes a latitude and longitude, a radius in metres, optional filters and a sort, and returns a page of compact results: ID, name, distance, rating and price level. Full details are a separate call, because most results are never tapped. Reviews are a POST on the business, and owners update their listing with a PUT.

GET /v1/search/nearby
  ?lat=28.46&lng=77.03
  &radius=2000&cat=cafe
  &open_now=1&sort=best
  &cursor=..&limit=20
  -> [{ id, name, distanceM,
       rating, priceLevel }]
GET  /v1/businesses/{id}
POST /v1/businesses/{id}/reviews
PUT  /v1/businesses/{id}

Data model

Data model. Businesses and reviews are classic relational data with modest volume, so a SQL database with read replicas works well. The business row stores its coordinates, category, hours, and a denormalised average rating and review count. A user gets one review per business, enforced by a unique key. The geo index is derived: a map from a location cell to the business IDs in it, rebuilt from database changes.

business (id PK, name, lat, lng,
          category, price, hours,
          avgRating, reviewCount)
review   (id, businessId, userId,
          stars, text, ts)
  unique (businessId, userId)

geo index (derived):
  geohash6 -> [businessId..]
rebuilt from DB changes

High-level design

The high-level design. A stateless search service holds the geo index in memory or reads it from a nearby index replica. For a query, it finds the location cells covering the search circle, gets the business IDs in them, filters and ranks, then hydrates the top twenty from a cache backed by read replicas. Business edits go through a separate business service to the primary database.

Deep dive: why not SQL

First, why not just index latitude and longitude? A query with a range on latitude and a range on longitude can use an index for only one of them efficiently. An index on latitude returns a thin band that circles the whole planet, and then you filter longitude row by row. The fix is to turn two-dimensional positions into one-dimensional keys that keep nearby places close together. That's exactly what a geohash does.

SELECT id FROM business
 WHERE lat BETWEEN :a AND :b
   AND lng BETWEEN :c AND :d

index on lat: returns a thin
  band around the whole world
index on lng: same problem
composite (lat, lng): range on
  lat, then scan every lng

need: map 2D to 1D keys

Deep dive: geohash

A geohash repeatedly splits the world in half, alternating longitude and latitude, recording a bit for which half you're in. Every five bits become one base-thirty-two character. A longer hash means a smaller cell: five characters is about five kilometres, six is about a kilometre by six hundred metres, seven is about a hundred fifty metres. Places that share a prefix are in the same cell, so 'all businesses in this cell' becomes a simple prefix or key lookup.

To search a radius, choose the precision from the radius, then look up the user's cell and its eight neighbours. The neighbours matter: if you're near the edge of a cell, the closest café might be just across the border, in a cell with a completely different hash. Fetch the IDs from those nine cells, compute the exact great-circle distance, and drop anything outside the radius. If too few results come back, step up to a larger cell size.

split the world in half by
  longitude, then latitude,
  again and again: one bit each
every 5 bits -> 1 base32 char

length  cell size (approx)
  4     39 km x 20 km
  5     4.9 km x 4.9 km
  6     1.2 km x 0.6 km
  7     153 m x 153 m
shared prefix = same area

Deep dive: quadtree

The main alternative is a quadtree. Start with the whole map, and whenever a cell holds more than about a hundred places, split it into four. Manhattan ends up with tiny cells, the desert with huge ones, so every leaf holds a similar number of results. It lives in memory and is rebuilt at startup. Libraries like S2, which uses cells on a cube, or H3, which uses hexagons, give more uniform cells. In an interview, geohash is the easiest to explain and store; mention quadtrees for uneven density.

Deep dive: ranking

Location narrows things to a few hundred candidates. Now filter by category, price and open now, which needs the business's hours and timezone. Then score. Raw average stars would let one five-star review beat four point six from two thousand, so use a Bayesian average that pulls small samples toward the overall mean, add a bonus for volume and subtract a distance penalty. Elasticsearch can do geo, text and filters in one query, a fine alternative to building it yourself.

Deep dive: reviews

Reviews. Insert the review row, with the unique key preventing duplicates. Then an event goes to an aggregator that keeps a running sum and count per business, so the average is just sum divided by count, with no rescanning. An edit subtracts the old stars and adds the new. The average in search results can lag by a minute. The author, though, reads their own review from the primary, so it appears immediately. Spam filters run before a review counts.

Trade-offs

Scaling and failures. The index is only a few gigabytes, so replicate it to every search node rather than sharding, and scale reads by adding nodes. Keep it fresh from the database's change stream; minutes of lag is acceptable. Busy areas like a city centre are hot cells, so cache query results by cell and filters for a minute. If a search node dies, the load balancer routes around it. Monitor p ninety-nine latency and the share of searches that return nothing.

Trade-offs. Geohash is simple and works in any database, but cells have fixed sizes and you must handle borders. Quadtrees adapt to density but are in-memory structures you rebuild. Replicating the full index costs memory on every node but avoids scatter-gather queries. Async rating updates trade a minute of lag for cheap writes. At ten times the scale, or if you add many attributes to the index, shard it by region, since a search rarely crosses regions.

Say it like this

The summary. It's a read-heavy service, five to fifteen thousand queries a second, and the geo index is only a few gigabytes, so keep it in memory and replicate it. Encode locations as geohashes, pick the precision from the radius, and look up the user's cell plus its eight neighbours. Filter by exact distance, then rank with a Bayesian rating, review volume and a distance penalty. Hydrate from cache. Mention quadtrees for uneven density.