Proximity Service

Intermediate

Overview

A proximity service returns businesses or points of interest near a user's location - "coffee shops within 2 km," ranked by distance and relevance. Unlike ride-sharing, the data is mostly read-heavy and slow-changing (a restaurant doesn't move), so the design centers on an efficient, cacheable geospatial index rather than on absorbing a firehose of location updates.

High-level architecture for Proximity Service

Functional Requirements

Return businesses within a given radius (or the K nearest) of a latitude/longitude.
Support filtering (category, rating, open-now) and ranking (distance, popularity).
Let owners add, update, and remove businesses.
Return results fast enough for an interactive map that pans and zooms.

Non-Functional Requirements

Low latency: nearby search returns in under 100–200 ms at p99.
High availability: search must stay up; slightly stale business data is acceptable.
Read-heavy: searches vastly outnumber business updates.
Scalable: hundreds of millions of businesses worldwide, high query concurrency.

Capacity Estimation

Assume 200M businesses, 100M DAU, each doing ~5 searches/day.

QPS:
- Searches: 100M x 5 = 500M/day -> 500M / 86,400 s ~ 5,800 reads/sec (peak ~3x ~ 17,000/sec).
- Business writes: negligible by comparison (thousands/day), so this is overwhelmingly a read system.
Storage: 200M businesses x ~1 KB (name, location, category, metadata) = ~200 GB - small enough to replicate widely and cache aggressively.
Index: the geospatial index over 200M points is a few GB and fits in memory on each read node.

The tiny, slow-changing dataset and huge read volume make caching and read replicas the dominant tools.

High-Level Architecture

The architecture separates the read path (Location Search) from the write path (Business Updates). Businesses are stored in a relational database, but the critical piece is a Geospatial Index (like a Quadtree or Geohash grid) that is held entirely in memory on the search nodes. Because data rarely changes, aggressive edge caching and Redis are used to serve repeated queries for popular locations.

Data Model

Entity	Fields / Schema	Storage Choice
business	business_id (PK), name, lat, lng, geohash, category, rating	Relational store with read replicas (PostgreSQL)
geo_index	geohash_cell -> list of business_ids	In-memory index (geohash buckets) or PostGIS/Elasticsearch
business_meta	business_id, hours, photos, reviews summary	Document store / cache

Detailed Design

Geospatial Indexing

Every business is encoded to a geohash. A radius search computes the query point's geohash prefix at the precision matching the requested radius, then loads that cell and its 8 neighbors (to catch results just across a boundary), gathers candidate businesses, and ranks them by exact distance.

Because the world data is uneven - dense downtowns vs empty countryside - a Quadtree (or Uber's H3) is a strong alternative: it subdivides only where businesses are dense, keeping each cell's candidate list bounded.

Choosing Precision by Radius

A large radius uses a shorter geohash prefix (bigger cells, fewer cells to scan); a small radius uses a longer prefix (smaller cells, tighter results). The service picks the prefix length so the number of candidate businesses stays manageable.

Read Path and Caching

Since businesses rarely change, results are highly cacheable. The service caches per-cell candidate lists in Redis with a long TTL; a search for a popular area is answered entirely from cache. A CDN or edge cache can even serve static "nearby" tiles for hot regions. The business DB runs behind read replicas since the write rate is trivial.

Write Path

When an owner updates a business, the Business Service writes to the DB and asynchronously updates the geo index (and invalidates affected cell caches). Because staleness of a minute is harmless, the index update need not be synchronous.

Bottlenecks & Solutions

The main bottleneck is "density hotspots." If a query requests a 10km radius in central Manhattan, it might return 50,000 businesses, overwhelming the ranking algorithm. The solution is pagination and dynamic radius adjustment (stop searching outward once we hit 200 results, regardless of the requested radius).

Interview Follow-up Questions

Q: How is this different from designing Uber's location system?

Uber tracks cars that move every 5 seconds. That requires an incredibly high-write system, usually built on Cassandra or a specialized in-memory grid, where updates overwrite old data instantly. A Yelp/Proximity service tracks buildings that never move, so it is a high-read, low-write system optimized via caching and static indexes.

Q: How do you handle pagination on a map?

Traditional offset/limit pagination doesn't work well on a map where the user is panning around. Instead, we use 'cursor-based' or 'bounding-box' pagination. As the user pans, the client sends the new bounding box (N/E/S/W coordinates) and the server returns only the points inside that box.