Design a Proximity Service

A proximity service returns places (restaurants, shops, gas stations) within a given radius of a location. It is the core of "near me" features in review and mapping apps. The central problem is running a two-dimensional range query quickly. Ordinary database indexes handle one dimension well, and combining latitude and longitude conditions is inefficient at scale.

Requirements

Functional

• Given a location (latitude, longitude) and a radius, return nearby businesses.
• Business owners add, update, and delete businesses. Changes need not appear instantly (next day is acceptable).
• Users view detailed information about a business.

Non-functional

• Low latency search (well under a second).
• High availability. The service is read-heavy, so it can scale by replication.
• Scalable to hundreds of millions of businesses and high query rates.
• Eventual consistency for business updates is acceptable.

Out of scope: ranking by reviews, personalization, and moving objects (see Design Uber for moving drivers).

Estimation

Assumptions: 100 million DAU, each performing 5 searches per day, and 200 million businesses.

• Search QPS: 100M x 5 = 500M/day. 500 x 10^6 / 86,400 is about 5,800 QPS average. Peak at 5x is about 30,000 QPS.
• Business writes: assume 1% change per day = 2 million updates/day, about 25/s. Negligible compared with reads.
• Business record size: about 1 KB of profile data, so 200M x 1 KB = 200 GB, which fits on a few database servers and easily in a sharded store.
• Geospatial index size: per business, an id (8 bytes) plus a location cell key (for example 8 bytes) is around 16 to 20 bytes with overhead. 200M x 20 bytes is about 4 GB, which fits in memory on a single server. Replicas exist for throughput and availability, not for capacity.

The read-to-write ratio is very high, so the design centers on replicated read paths and caches.

What the numbers imply

• 30,000 peak QPS with 9 cell lookups each is about 270,000 cell reads/s. From an in-memory index on a stateless service, one server can plausibly serve about 5,000 to 10,000 QPS, so peak needs roughly 6 to 10 replicas. Run at least 3 across availability zones regardless, and keep N+1 headroom so that losing one replica at peak is survivable.
• A response of 20 results at about 200 B is about 4 KB, so peak egress is about 120 MB/s (roughly 1 Gbit/s). Compress responses and return summaries, not full records.
• 25 writes/s and a 4 GB index mean there is no sharding pressure. The index is rebuilt or patched offline and pushed to replicas.
• Of the 200 GB of business data, only a small hot subset (popular city centers) receives most reads. Caching the top 10 to 20% (20 to 40 GB) captures most of the traffic, which fits in a cache tier.

API design

GET /v1/search/nearby?lat=37.77&lng=-122.41&radius=1000&category=cafe&pageToken=...
    -> { businesses: [ { id, name, lat, lng, distance, rating } ], nextPageToken }

GET    /v1/businesses/{id}          -> full business details
POST   /v1/businesses               -> create
PUT    /v1/businesses/{id}          -> update
DELETE /v1/businesses/{id}          -> delete

Radius is bounded (for example 500 m up to 20 km) to limit search cost. Results are paginated, and the search returns summaries so the client fetches full details on demand.

Data model

The business table is a straightforward key lookup workload and suits a relational database with read replicas, or a key-value store (see key-value and document stores). The geospatial index is a separate structure derived from business, rebuilt or updated as businesses change.

High-level design

graph TD
    C["Client"] --> LB["Load balancer"]
    LB --> LBS["Location-based service (read only, stateless)"]
    LB --> BS["Business service"]
    LBS --> GI["Geo index (in-memory or replicated DB)"]
    LBS --> BC["Business cache"]
    BC --> RDB[("Business DB: primary + replicas")]
    BS --> RDB
    BS -->|"change events"| IDX["Index updater (nightly or streaming)"]
    IDX --> GI

• Location-based service (LBS). Stateless and read-only. Converts the query location and radius into candidate cells, fetches businesses from those cells, filters by exact distance, sorts, and returns.
• Business service. Handles create, update, and delete, and detail reads. Write rate is low.
• Geo index. Read-optimized spatial index, replicated across many servers.
• Index updater. Applies business changes to the geo index.

Search flow:

sequenceDiagram
    participant C as Client
    participant L as Location-based service
    participant G as Geo index
    participant B as Business cache
    C->>L: nearby(lat, lng, radius)
    L->>L: compute covering cells for the radius
    L->>G: get business ids for each cell
    G-->>L: candidate ids
    L->>B: get business records
    B-->>L: records
    L->>L: filter by exact distance, rank, paginate
    L-->>C: results

Deep dive

1. Why a plain SQL query is slow

SELECT * FROM business
WHERE lat BETWEEN :lat - d AND :lat + d
  AND lng BETWEEN :lng - d AND :lng + d;

A B-tree index on lat returns every business in a horizontal band around the world at that latitude, and an index on lng returns a vertical band. The database must intersect two large sets, or scan one of them and filter. A single composite index on (lat, lng) only narrows the first column. The query needs an index that maps two-dimensional locations to positions that are near each other in one dimension.

2. Geohash

A geohash encodes a latitude and longitude into a string by repeatedly bisecting the ranges, alternating longitude and latitude bits, and encoding the bits in base 32. Longer strings identify smaller rectangles. Businesses sharing a prefix lie in the same rectangle, so the index is a table geohash -> businesses, and a prefix search finds a cell.

Rough cell sizes: a 4-character geohash is about 39 km x 20 km, 5 characters about 5 km x 5 km, and 6 characters about 1.2 km x 0.6 km.

Search procedure:

1. Choose the precision whose cell size is close to the search radius (see the precision rule in section 7; for example 5 characters for 1 km).
2. Compute the geohash of the query point and of its 8 neighboring cells. Neighbors are needed because a point close to a cell edge may have nearby businesses in the adjacent cell that has a different prefix.
3. Fetch businesses in those 9 cells.
4. Compute exact distance to each candidate, discard those beyond the radius, and sort.

Weaknesses: cells are rectangles, whose sizes change with latitude. Points near each other across some boundaries (for example the prime meridian or the equator) can have completely different prefixes, so the neighbor computation is required. Too few results in a cell requires widening the search by dropping a character from the prefix.

Storage: a table with a column geohash of the chosen precision (or several precisions), indexed. A query becomes WHERE geohash IN (...9 cells...). The table is small and the index is easy to cache. Updates are simple: delete and insert on the business's cell.

3. Quadtree

A quadtree is an in-memory tree that recursively divides space into four quadrants. A node splits into four children when it contains more than a threshold number of businesses (for example 100). Dense cities end up with deep, small cells, and rural areas have large cells. Leaves hold business ids.

Search: descend from the root to the leaf containing the query point, then collect businesses from that leaf and adjacent leaves (leaves are usually linked to neighbors), expanding until enough candidates cover the radius.

Memory estimate: 200M businesses with about 20 bytes each is about 4 GB for leaf data, plus internal nodes. With a leaf capacity of 100, there are about 2 million leaves, and internal nodes add roughly one third more, which is small. A server can hold the whole tree.

Operational characteristics: the tree is built at server start, which takes minutes for hundreds of millions of points. Updates apply in memory, and a business change may split or merge nodes. Servers often adopt changes on a schedule (nightly rebuild or incremental) and run as replicas, so a rolling restart avoids losing capacity.

4. Geohash versus quadtree

Other options are Google S2 and Uber H3 cell hierarchies, which address geohash edge effects and distortion. See geospatial indexing for detail.

5. Scaling the geo index

Since the geo index is about 4 GB, sharding for capacity is not required. Replicate it across servers for read throughput and availability, and route each request to any replica. If data grows, or to reduce per-server memory, shard by region or by geohash prefix (see sharding and partitioning). Sharding by prefix can cause hot spots because dense cities receive most queries, so use finer shards for dense areas, or shard by business_id hash and query all shards (scatter-gather) at the cost of more requests per search.

6. Caching

Cache search results keyed by the geohash of the query cell plus radius and category. Many users near each other share the same cell, so hit rates are good. Cache business detail records by id. Business data changes rarely, so long TTLs are acceptable. Because updates are allowed to appear the next day, cache invalidation can be simple TTL expiry (see caching fundamentals and strategies).

7. Thresholds and consistency choices

• Precision rule. The 3x3 block must cover the radius in every direction, so the smaller side of the cell must be at least the radius. A 1 km radius therefore needs the 5-character geohash (about 4.9 km x 4.9 km), because a 6-character cell is only 0.6 km high. In dense areas a 5-character cell holds thousands of businesses, so cap candidates (for example 500 per query) and prefer a quadtree or S2/H3 with finer cells there.
• Cache design. Cache candidate ids per (cell, category) instead of final results. Then compute exact distance per user, so two users in the same cell get correct, different orderings. Use a TTL of 1 hour for cell lists and 24 hours for business details, with jitter of about 10% to avoid synchronized expiry. 1 million hot cells x 100 ids x 8 B is about 800 MB, so this is small.
• Consistency. Eventual: a new business appears within a day with a nightly rebuild, or within minutes with a change stream. Closures matter more, so read the open/closed flag from the business record (short TTL of minutes) at ranking time rather than trusting the index.

Bottlenecks and scaling

• Read throughput. Replicate LBS instances, geo index, and the business cache. Read replicas serve the business DB (see database replication).
• Dense cities. Adaptive structures (quadtree) or finer geohash precision limit candidate set size. Cap results before computing distances.
• Cross-region users. Deploy replicas in several regions so a query is served near the user, with the geo index built from a central source of truth.
• Business DB primary. Low write rate makes the primary sufficient. Failover promotes a replica.
• Index updates. A nightly batch or a change stream keeps the geo index current. During an update the LBS keeps serving the old index until the new one is ready.

Failure modes

• Replica loss. The load balancer removes it on health check failure, and the remaining replicas absorb load thanks to N+1 headroom. Without headroom the service sheds load instead of collapsing: limit concurrency per replica and return 429 or reduced result counts.
• Bad index build. Validate before publishing (business count within 5% of the previous build, sample queries return expected results), swap atomically, and keep the old index for rollback.
• Cache flush or cold start. Misses hit the business DB and can overload it. Use request coalescing for identical keys, TTL jitter, and warm the cache from the previous hot key list.
• At 10x scale. 300,000 QPS needs about 60 to 100 replicas and 10 Gbit/s egress, so put a CDN or edge cache in front for common cells. With 2 billion businesses the index reaches about 40 GB, still possible per server but heavier to rebuild and replicate, so shard by region with replicas per shard and finer shards for dense cities. Scatter-gather across shards should be limited to border queries.

Trade-offs and follow-up questions

• Precision versus candidate count: finer cells reduce candidates but need more cell lookups.
• Freshness of business changes versus the complexity of live index updates.
• How to search by category plus distance? Index by (geohash, category) or filter after the spatial step.
• How to rank results, for example by rating and distance? Retrieve a candidate set spatially, then score it, possibly in a search engine (inverted index and full-text search) that supports geo filters.
• How would moving objects such as drivers differ? Locations update constantly, so an in-memory grid with frequent updates and short TTL replaces a mostly static index (see Design Uber).
• How to handle a search near the international date line or the poles? Cell neighbor calculation must wrap longitude, and the distance calculation should use great-circle distance (haversine).
• Results are too few in a sparse area? Expand to the next ring or drop a geohash character until enough results or the maximum radius is reached.
• "Open now" or category filters? Filter after the spatial step, or index by (cell, category); hours are evaluated at query time in the business's time zone.