Design a Proximity Service (Yelp / Nearby Places) Walkthrough

A proximity service answers one question at scale: which businesses are within a given radius of this point? The standard design splits a stateless, read-heavy location-based search service from a write-light business service, indexes every business by a geospatial cell (geohash, quadtree or S2), and answers each search by reading the user's cell plus its neighbors, filtering by exact distance and then ranking. Because businesses rarely move, the index is small, heavily replicated and cached, and an edit can take minutes to reach search.

This is the classic "design Yelp" or "find nearby places" question. Below is a 45-minute walkthrough, from requirements to pacing.

1. Clarify requirements and estimate scale

Spend the first five minutes pinning down scope. A typical agreed scope:

Functional requirements

• Given a latitude, longitude and radius (plus an optional category), return nearby businesses, paginated.
• Show a business's details: name, address, hours, photos and rating.
• Business owners can add, update or remove a listing.

Non-functional requirements

• Low search latency. Propose a concrete target, such as p99 under a few hundred milliseconds.
• High availability on the read path. A slightly stale result beats an error page.
• Eventual consistency for edits. Ask how quickly a new listing must be searchable. Minutes, or even the next day, is often acceptable, and the answer shapes the update path.
• Location privacy. Do not keep raw user coordinates in logs longer than you need them.

Park the review pipeline, map tiles and routing (see our Google Maps walkthrough) and personalization unless the interviewer pulls them in.

Back-of-the-envelope numbers. State assumptions out loud; reasoning matters more than matching a textbook.

The sentence to say out loud: data size is not the problem; read throughput and latency are. It justifies most of what follows.

2. API and data model

# Search (location-based service)
GET /v1/search/nearby?lat=37.7764&lng=-122.4172&radius=1000&category=coffee&page_token=...
  -> { results: [ { business_id, name, distance_m, rating, is_open } ],
       next_page_token }

# Business details and owner edits (business service)
GET    /v1/businesses/{id}
POST   /v1/businesses
PUT    /v1/businesses/{id}
DELETE /v1/businesses/{id}

Cap the radius on the server so one request cannot scan a whole region, and return an opaque page token instead of an offset, because each page is merged from several cells.

Store one geohash per business at your finest precision. A B-tree index then answers any coarser cell as a prefix range scan, such as WHERE geohash >= '9q8yy' AND geohash < '9q8yz' for one length-5 cell in San Francisco.

3. High-level architecture

                    Mobile / web client
                            |
                   +-----------------+
                   | Load balancer   |
                   +--------+--------+
         /search            |            /businesses
        +-------------------+-------------------+
        v                                       v
+--------------------+                +--------------------+
| Location-Based     |                | Business Service   |
| Service (LBS)      |                | owner CRUD, detail |
| stateless, reads   |                | pages              |
+----+----------+----+                +---------+----------+
     |          |                               | writes
     v          v                               v
+---------+ +-----------+               +----------------+
| Geo     | | Business  |               |  Primary DB    |
| cache   | | cache     |               +-------+--------+
| cell -> | | id ->     |                       | replication
| ids     | | summary   |                       v
+----+----+ +-----+-----+  on miss      +----------------+
     +------------+-------------------> | Read replicas  |
                                        +----------------+

The location-based service (LBS) handles every search, is read-only and keeps no state, so you scale it by adding servers. The business service writes owner edits to the primary database and serves detail pages. Read replicas absorb cache misses, and replication lag is acceptable because you agreed on eventual consistency. Separate services let thousands of searches a second scale independently of a trickle of edits.

4. The geospatial index: geohash vs quadtree vs S2

The naive query, WHERE lat BETWEEN ... AND lng BETWEEN ..., fails at scale: separate indexes on latitude and longitude each return a huge band around the globe, and the database must intersect them. Every serious answer maps 2D positions onto 1D keys or a tree.

Geohash: match the precision to the radius

The rule: pick the longest geohash whose shorter cell side is at least the search radius. The user sits somewhere inside the center cell, so the center plus its eight neighbors always covers at least one full cell width in every direction. Cells narrow east to west away from the equator, so at high latitudes use a geohash one character shorter or let a library compute the covering.

Quadtree

Start with the whole world as one node and split any node holding more than a threshold you choose, say 100 businesses, into four children. Dense districts get deep, small leaves; oceans stay as large ones. Memory is fine: the IDs alone are about 200M × 8 bytes = 1.6 GB plus node overhead. The catch is operational: every LBS server rebuilds the tree at startup, so roll out deployments gradually, and live inserts need locking or a periodic rebuild.

S2, and when to mention H3

Google's S2 library gives every cell a 64-bit ID across 31 levels (0 to 30). IDs follow a space-filling curve, so cells with close IDs are close on the map. Level 12 cells cover about 3 to 6.4 square kilometers, roughly 2 km on a side, and a region coverer approximates a circle or polygon with a handful of cells, which makes S2 the strongest option for geofences. Uber's open-source H3 uses hexagonal cells instead; name it if asked.

Off-the-shelf options to name

• Redis GEO. GEOADD stores points in a sorted set scored by a 52-bit geohash; GEOSEARCH (Redis 6.2+) answers radius or box queries by checking the center area plus eight neighbors. It assumes a spherical Earth, with worst-case distance error up to 0.5%, which is fine for restaurants.
• PostGIS. ST_DWithin on a geography column with a GiST index. Filter with it, not with ST_Distance, which cannot use the index.
• Elasticsearch. A geo_distance query on a geo_point field, handy when the search also includes free text and filters.

A strong line: "In production I would serve the hot path from Redis GEO, but here is how the index works underneath."

5. The search flow, step by step

1. Map the radius to a precision. Clamp it, then pick the cell size: a 1 km search uses geohash length 5.
2. Compute the user's cell and its eight neighbors with a library. Do not hand-roll this: the math must wrap around the 180th meridian, where adjacent cells share no prefix, and handle the poles.
3. Fetch business IDs for those nine cells from the geo cache, falling back to a read replica on a miss.
4. Widen if results are thin. Drop one geohash character (or use a coarser S2 level) and repeat.
5. Hydrate the candidates from the business cache in one batched multi-get.
6. Filter by exact distance. Nine cells form a square; the query is a circle. Compute the haversine distance and drop anything outside the radius.
7. Rank, cut to page size and return a page token that encodes where the next page resumes.

6. Scaling the read path and caching

• Replicate the index before you shard it. At around 5 GB it fits on every cache node. Sharding by geography creates hot shards in dense cities and awkward queries at shard edges. If the business store outgrows one database, shard it by business_id instead.
• Use two cache layers: cell to business IDs, and business ID to summary (name, rating, hours). Our distributed cache walkthrough covers eviction and invalidation.
• Deploy per region. People mostly search near where they are, so run the LBS and a copy of the index in each region.
• Handle dense hot spots. A nine-cell query downtown can return thousands of candidates. Use finer precision there, cap candidates (Redis COUNT with ANY returns as soon as it has enough matches, though not necessarily the closest), or precompute a top-N list per cell.

7. Business updates and ranking

Owner edits go to the business service and the primary database. Search catches up asynchronously:

• Index. A change-data-capture stream or queue updates the business's geo_index row and invalidates the affected cell keys. With geohash or Redis GEO that is a cheap delete and insert.
• Quadtree. Incremental updates need locking, so many designs rebuild on a schedule, such as nightly, if freshness allows.
• Caches. Invalidate the business key on every edit and keep TTLs as a safety net.
• Closures. Soft-delete with a flag so search hides a closed business before the index catches up.

Ranking. Pure distance sorting is weak, because the closest place may have one review. Score candidates on several signals:

• Distance, with a score that decays as distance grows.
• Rating quality, using a smoothed average such as (C × m + rating_sum) / (C + review_count), where m is the global mean and C a prior weight, so one 5-star review cannot outrank 2,000 reviews averaging 4.6.
• Popularity and context: review count, open now, category and text match.

Keep rating_sum and review_count on the business row and update them when a review lands, so search never averages on the fly.

8. Trade-offs and how to pace the interview

The classic pacing mistake is spending 20 minutes on CRUD endpoints and reaching the index with five minutes left. The index is the question. Expect these follow-ups:

• "What if the points move?" Then you are designing ride-hailing: constant location writes push you toward an in-memory index that is overwritten continuously. Compare our Uber walkthrough.
• "Can users search a neighborhood by name?" Store its polygon, cover it with S2 cells or geohashes, then query those cells.
• "What breaks first?" Cache hit rate in dense areas, then replica load. Say you would watch p99 latency per region.

The hardest part to improvise is explaining the geohash vs quadtree trade-off cleanly in two minutes, so rehearse it out loud, for example in a free AI mock interview in CoPilot Interview with the question mix set to system design.

FAQ

What is a proximity service in system design?

It is a backend that returns businesses or places within a given radius of a location, like a "restaurants near me" search. The interview question tests geospatial indexing, read-heavy scaling and caching.

Should I use geohash or a quadtree in the interview?

Geohash is usually the easiest to explain, store and update. Choose a quadtree if density varies wildly and you want cells that adapt to it, and mention S2 if you need near-uniform cells or arbitrary shapes.

How do you handle businesses near a geohash cell boundary?

Query the user's cell plus its eight neighbors, then compute the exact distance to every candidate and drop anything outside the radius. Use a library for the neighbor calculation so edge cases like the 180th meridian are handled.

Do you need to shard the geospatial index?

Usually not at first. Even 200 million businesses fit in a few gigabytes as cell and ID pairs, so replicating the whole index to every read node is simpler than sharding by geography and avoids hot shards.

How is a proximity service different from designing Uber?

A proximity service indexes businesses that rarely move, so the workload is read-heavy and index updates can lag. Ride-hailing indexes drivers whose positions change constantly, which makes it a write-heavy, in-memory problem.