Design Proximity Search

You type "pizza" into an app. It shows twenty places within a couple of kilometres, best first, each with a star rating and a distance. You tap one, read some reviews, and later leave your own. A review site with a map, such as Yelp, is the kind of product this question means.

It looks like plain CRUD until you ask "near me". Then you need a spatial index, a query that mixes location with text, a read path built for hundreds of reads per write, and an average rating that stays right when two people review at once. The steps follow A Framework for Any Design. Try each "Your turn" box before reading on.

#Clarify the problem

• Functional: search businesses near a point by category and keywords, with filters (open now, price, minimum rating); view a business page with its reviews; add or edit one review per business, with 1 to 5 stars.
• Non-functional: search in under 200 ms at the 99th percentile; reads highly available; new reviews and businesses searchable within a minute; the average rating counts every review exactly once.
• Out of scope: photos (see Design Photo Sharing), ads, owner dashboards, fake-review detection.

#Estimate the scale

A day is 86,400 seconds. Assume the evening peak is 3 times the average.

• Searches: 100 million × 5 = 500 million a day ÷ 86,400 ≈ 5,800 a second, about 17,000 at peak.
• Business page views: say 2 per search, 1 billion a day ≈ 11,600 a second, about 35,000 at peak.
• Review writes: 2 million a day ÷ 86,400 ≈ 23 a second, about 70 at peak. Reads outnumber writes about (500 million + 1 billion) ÷ 2 million = 750 to 1.
• Storage: 50 million businesses × 2 KB = 100 GB. Say 1 billion existing reviews × 1 KB = 1 TB, growing 2 million × 1 KB × 365 ≈ 730 GB a year.

#Define the API

GET /search?lat=40.7128&lng=-74.0060&radius_m=2000
           &q=pizza&category=restaurants&open_now=true&min_rating=4&cursor=...
  200 { "results": [ { "id": "b_81", "name": "Luigi's", "rating": 4.6,
                       "review_count": 312, "distance_m": 450 }, ... ],
        "next_cursor": "..." }
  400 Bad Request   radius over 50 km, or no location
 
GET /businesses/{id}                   page data, cacheable for 60 s
GET /businesses/{id}/reviews?sort=recent&cursor=...
 
PUT /businesses/{id}/reviews/me        create or replace my review
  body: { "rating": 5, "text": "..." }
  200 { "rating": 5, "business_rating": 4.61, "review_count": 313 }
  400 Bad Request   rating not 1 to 5
  404 Not Found     no such business
DELETE /businesses/{id}/reviews/me

The decision worth arguing is PUT .../reviews/me instead of POST .../reviews. A POST creates a review each time, so a retry after a timeout tries to add a second one. A PUT names the one review this user may have, so a retry replaces it with the same content. "One review per user" becomes the shape of the URL, backed by a primary key.

#Model the data

businesses
  business_id   BIGINT PRIMARY KEY
  name          VARCHAR(200)
  categories    TEXT[]            -- ["restaurants", "pizza"]
  lat, lng      DOUBLE
  hours         JSON              -- weekly opening intervals
  price_level   SMALLINT
  rating_sum    BIGINT            -- total stars of all reviews
  rating_count  INT               -- number of reviews
  -- about 2 KB per row
 
reviews
  business_id   BIGINT
  user_id       BIGINT
  rating        SMALLINT          -- 1 to 5
  text          TEXT
  updated_at    TIMESTAMP
  PRIMARY KEY (business_id, user_id)   -- one review per user, enforced

Access patterns: find businesses near a point that match words and filters (17,000 a second at peak); read one business and a page of its reviews (35,000 a second); write one review and update one business's rating (70 a second).

The writes need a transaction across two rows, the review and the business, so the source of truth is a relational database, partitioned by business_id once it outgrows one machine. A business and its reviews share a partition, so that transaction never crosses machines. The search query is a different shape: geometry plus text plus ranking. That goes to a search index with geo support (see search systems), a copy built from the database. A geospatial extension of the database itself is a fine alternative at small scale; the deep dive compares them.

#High-level design

Split the services by path, because each has its own store and load. Search never touches the database, which takes only page misses and 70 writes a second.

#Deep dives

Interviewers push on the geospatial index, the 750-to-1 read load, the rating under concurrent writes, and queries that mix words with location.

#The geospatial index

An ordinary index on latitude finds a thin band around the whole planet, and the database then checks every business in it. You need an index that groups points by area. Design Ride Sharing introduces geohash cells and the neighbour-cell problem; here the points are businesses, which almost never move, and that changes the choice.

Know the hand-built versions anyway, because interviewers ask how they work. With geohash, pick the precision from the radius. A 3 × 3 block of cells covers any circle whose radius is no bigger than one cell's shorter side, so the cell must be at least as large as the radius. A precision-6 cell is about 1.2 km × 0.6 km, too small for 2 km. A precision-5 cell is about 4.9 km square at the equator, so 9 of them cover 2 km. The east-west width shrinks with latitude: at 50° north a precision-5 cell is only about 3.1 km wide. Still enough for 2 km, but compute from the real cell size.

A quadtree fits places well. With at most 100 places per leaf, 50 million places need at least 500,000 leaves, and the tree plus 1.2 GB of coordinates fits in one server's memory. Build it offline, ship it to every search server, and apply the day's new places as a small overlay until the next rebuild. The strong answer: "I'd use the engine's geo field, and here is how it works inside."

#Serving 750 reads for every write

The index is 25 GB, so every search machine holds a complete copy. Do not shard it for size; add replicas for throughput. If one replica handles about 1,000 of these queries a second (measure yours), the 17,000 peak needs 17, so run about 20 for headroom. A query then touches one machine, with no scatter-gather.

Business pages go through a cache. All 50 million pages are 100 GB; caching the most viewed 10% takes about 10 GB. The review service deletes a page's key after each commit, and a 60-second expiry bounds the damage if a delete is lost. Cache search results for 60 seconds, keyed by the user's precision-6 cell, the words and the filters, so everyone in one 1.2 km × 0.6 km cell asking for "pizza" shares an entry; recompute the 20 distances for the exact point.

#Keeping the average rating correct

Luigi's has 10 reviews totalling 40 stars, an average of 4.0. Ana gives 5 stars and Ben gives 1 at the same moment. The correct result is 46 stars over 12 reviews, about 3.83. If each request reads the row, computes the new values in the app and writes them back, both read (40, 10). Ana writes (45, 11); Ben writes (41, 11). The final row says 11 reviews averaging 3.73, and Ana's review is lost from the total. This is the lost-update race.

BEGIN;
-- 1. lock the business row: reviews of this business now take turns
SELECT 1 FROM businesses WHERE business_id = 81 FOR UPDATE;
-- 2. my old review, if any
SELECT rating FROM reviews WHERE business_id = 81 AND user_id = 7;  -- 3, or none
INSERT INTO reviews (business_id, user_id, rating, text, updated_at)
     VALUES (81, 7, 5, '...', now())
ON CONFLICT (business_id, user_id)
     DO UPDATE SET rating = 5, text = '...', updated_at = now();
-- 3. new review: +5 stars, +1 review.  edit from 3 to 5: +2 stars, +0.
UPDATE businesses SET rating_sum = rating_sum + 2, rating_count = rating_count + 0
 WHERE business_id = 81;
COMMIT;

Why it is safe: every review of business 81 first locks its row, so those transactions take turns, and the old-review read in step 2 sees what the previous one committed (at read committed, as in PostgreSQL, each statement reads fresh data). The primary key rules out a second review by one user even if two requests race. The lock lasts a few milliseconds, nothing at 70 writes a second. Store the sum and count, never the average: an average cannot be updated by a delta.

#Mixing words, filters and location

"Wood-fired pizza, open now, 4 stars or more, within 2 km" has three parts. Running them as separate steps fails either way: location first fetches thousands of downtown places to keep 20; text first finds every pizza place on the planet.

Put everything in one search index query: the geo filter and the structured filters cut the candidates inside the index, the words match against the inverted index, and the engine scores only what is left. A simple score multiplies text relevance by a distance decay and a rating factor, so a 4.8-star place at 1.5 km can beat a 4.1-star place at 300 m. "Open now" is a filter on opening intervals stored as minutes of the week in the business's local time; the search server converts "now" into the local time of the search area, so the filter compares one number.

#Bottlenecks and failures

At 10x, 170,000 searches a second at peak, you need about 200 index replicas at 1,000 queries each. Split them into regional clusters near their users, each holding only its region's index. Writes at 700 a second still fit a partitioned relational database. A dense city at dinner sends the same queries from the same cells, which the 60-second result cache absorbs.

#What a strong answer sounds like

#Follow-up questions

#Fewer than 20 results within 2 km. What then?

Widen the radius in steps, 2 km, then 5, then 10, until you have enough or hit a limit. A quadtree does this by walking to neighbouring leaves.

#The user pans the map. How do you search a rectangle?

Send the map's corners instead of a point and radius; geo fields filter by a box directly. Cap the box size, and show clusters when zoomed out.

#Should a place with one 5-star review rank above one with 300 reviews at 4.7?

No. Rank by an adjusted rating that pulls small samples toward the site-wide average, such as (sum + 10 × site average) ÷ (count + 10). Show the real average on the page.

#Search shows Luigi's at 4.60 but the page shows 4.61. Is that a bug?

No. Search reads a copy that lags by seconds; the page reads the database through a cache that is cleared on every review. The requirements allow search to lag, and the totals behind both numbers are exact.

#A review is removed as fake. What changes?

Hide it in the same kind of transaction: subtract its stars from the sum and 1 from the count. A nightly job recomputes sums from the reviews to catch drift from bugs.