Proximity Service

What is a proximity service?

A proximity service answers "what's near me?": given a latitude/longitude point and a search radius, return a ranked list of businesses or users within that area. The engineering challenge is the index. Scanning 500M lat/lng rows for every query is a full table scan, and at 58K requests/second that saturates the database. This design uses spatial indexing, caching for a read-heavy workload, and separate data paths for static listings and dynamic locations.

The problem starts with a simple distance filter but quickly exposes an important constraint: a normal B-tree does not index two dimensions together. The design therefore begins with a spatial approximation and finishes with an exact distance check.

TL;DR

For static businesses, compute a geohash on write and index it in PostgreSQL. For a search, choose a precision for the requested radius, query the target cell plus its eight neighbors, apply a Haversine distance post-filter, and rank the remaining results. Redis and a CDN cache popular, quantized cell responses; geographic shards and replicas handle scale.

Dynamic locations are a different workload. Use a dedicated update service and Redis GEO with short TTLs for drivers or friends; do not put positions that change every few seconds in the business database. The correctness invariants are boundary coverage, true-distance filtering, bounded result sizes, and privacy-preserving access to precise locations.

Scope and Assumptions

This design assumes:

• The primary path searches mostly static business listings by location, radius, category, and minimum rating; owners can create, update, and delete listings.
• The illustrative workload is 500M businesses, 100M daily active users, and 5B searches per day (about 58K requests per second at peak), with a 100ms p99 search target.
• Geohash is an approximate candidate index, not the final distance calculation. Search queries cover adjacent cells and apply Haversine filtering to meet the 100-meter accuracy target.
• Cached business results may be briefly stale. Precise dynamic user/driver locations are an optional extension with short retention and a separate Redis-backed path.
• Reviews, photos, navigation, real-time analytics, and other content or routing systems are out of scope for the core proximity service.

Functional Requirements

Core Requirements

1. Given a user's location (lat/lng) and a search radius, return a list of nearby businesses sorted by distance.
2. Business owners can add, update, and delete listings.
3. Users can filter results by category (restaurants, gyms) and minimum rating.

Below the Line (out of scope)

• Real-time friend or driver location updates
• Reviews, photos, and ratings management
• Turn-by-turn navigation

The hardest part in scope: Indexing billions of lat/lng coordinates so that "find everything within 5km of this point" completes in under 100ms, not a full table scan.

Real-time location updates are below the line because they introduce a separate architecture: persistent WebSocket connections, Redis GEO writes, and a completely different data freshness model. To add them, build a dedicated location update service that accepts position pushes over WebSockets and writes to Redis GEOADD. The dynamic search path reads from Redis GEORADIUS rather than the business database.

Reviews and ratings live in a separate content service. They share a business_id with the business record but do not affect spatial indexing. To add them, attach a reviews table keyed on business_id and serve aggregated ratings via a separate content API.

Turn-by-turn navigation is a solved problem (Google Maps, Mapbox). Whether in scope or out, reference a third-party routing API rather than building from scratch.

Non-Functional Requirements

Core Requirements

• Scale: 500M businesses, 100M DAU, 5B location queries per day.
• Latency: Under 100ms p99 for nearby search queries.
• Availability: 99.99% uptime. Availability favored over consistency (slightly stale business results are better than a 500 error).
• Accuracy: Results within 100 meters of true position.

Below the Line

• Sub-10ms latency via edge caching for the coldest paths
• Real-time analytics on search patterns and query distribution

Read/write ratio: This is overwhelmingly read-heavy, 100:1 or more. Businesses add and update listings occasionally. Search queries happen constantly. This ratio drives aggressive caching and read replicas. Nearly every scaling decision traces back to it.

5B queries per day works out to approximately 58,000 requests per second at peak. A single database with a naive lat/lng scan cannot approach that throughput. The 99.99% availability target eliminates single-node architectures for both the read and write paths.

30-Second Answer

1. Store each business with lat, lng, and a server-computed geohash; index the geohash and shard by geographic prefix as the dataset grows.
2. For a nearby query, quantize the location for caching, choose a geohash precision from a radius lookup table, and read the target cell plus its eight neighbors.
3. Fetch candidates from the cell cache or read replicas, apply the exact Haversine distance filter, then sort and cursor-paginate the results.
4. Use CDN/Redis cell caches for repeated static searches and invalidate affected cells on listing writes. Keep stale reads bounded and safe.
5. If live drivers or friends are added, route their updates to Redis GEO with TTLs and query that store separately. The central correctness rule is: geohash finds candidates; Haversine decides membership.

5-Minute Explanation

The core data is static business metadata plus a Location record containing coordinates and a precomputed geohash. A naive bounding-box query is a useful baseline but cannot scale across hundreds of millions of rows. Geohash converts two dimensions into a prefix, allowing a B-tree or key-value lookup to narrow the candidate set.

A search chooses cell precision based on the requested radius, computes the target geohash and its neighboring cells, and queries all nine cells. Because cells are rectangles and the desired area is a circle, the service computes the true Haversine distance for every candidate, removes false positives, applies category/rating filters, sorts by distance, and returns a bounded page with a stable cursor. This boundary step is required for correctness.

The read path is heavily cached. Quantizing coordinates and standardizing radius/filter keys lets a CDN and Redis reuse popular cell responses. Listing writes update the authoritative PostgreSQL shard and invalidate the affected cell; replicas serve cache misses. Geographic sharding by geohash prefix limits most searches to a small set of shards, while large-radius queries need explicit scatter-gather limits.

Dynamic proximity is not just a feature flag on the static path. A driver or friend location changes every few seconds, so WebSockets plus Redis GEO and short TTLs are a better fit than durable relational rows. Security and operations must treat precise locations as sensitive, protect against scraping, monitor hot cells and shard skew, and distinguish stale static listings from stale live presence.

45-Minute Interview Approach

Use this agenda to answer the design question and prioritize spatial correctness, read scaling, and the static-versus-dynamic boundary:

• 0–5 minutes — Clarify the contract: Confirm static businesses versus live drivers/friends, radius limits, accuracy, ranking, filters, pagination, freshness, and privacy expectations.
• 5–10 minutes — Establish scale: Calculate 5B queries/day as roughly 58K requests/second, list size and density skew, listing-write frequency, the 100ms p99 target, and cacheability.
• 10–15 minutes — Define entities and APIs: Introduce Business, Location, SearchResult, optional UserLocation, GET /search/nearby, and listing CRUD. State that geohash is computed server-side.
• 15–22 minutes — Draw the baseline: Show a lat/lng bounding-box scan and explain why a single B-tree or database cannot serve 500M rows at the target rate.
• 22–30 minutes — Draw the static search path: Add geohash precision selection, the 9-cell lookup, Haversine post-filter, stable pagination, read replicas, and geographic sharding.
• 30–35 minutes — Add caching: Explain quantized cache keys, CDN/Redis cell caches, invalidation on listing writes, hot-cell protection, and bounded large-radius queries.
• 35–41 minutes — Cover dynamic and operational concerns: Only then add WebSocket + Redis GEO for live locations, TTLs, privacy, auth, stale data, shard health, and metrics.
• 41–45 minutes — Close with trade-offs: Compare geohash, quadtrees/R-trees, database versus Redis, CDN versus dynamic reads, and exact versus approximate search. Recap the candidate-index/post-filter invariant.

Core Entities

• Business: A listing with a name, category, rating, and a fixed geographic position. The primary read target for all search queries.
• Location: The geographic coordinate of a business, stored as lat, lng, and a precomputed geohash string for fast spatial queries. Updated whenever a business is created or its position changes.
• SearchResult: The response shape for a nearby search: a ranked list of businesses with name, category, rating, and computed distance. Ephemeral, never stored.
• UserLocation: For dynamic proximity use cases (nearby friends, drivers), a user's current lat/lng with a last_updated timestamp. Lives in a separate in-memory store, not the business database.

The full schema, indexes, and column types belong in a data model deep dive. What matters here: Business is static and persisted in a relational database; UserLocation is dynamic and requires an in-memory store with fast writes and short TTLs.

API Design

FR 1 - search nearby businesses:

GET /search/nearby
Params: lat, lng, radius_km, category?, min_rating?, limit=20, cursor?
Response: { businesses: [...], next_cursor: "..." }

GET with query params because these requests are read-only and inherently cacheable. A CDN or API gateway can cache GET /search/nearby?lat=37.7&lng=-122.4&radius_km=1&category=restaurants for 60 seconds with no application logic changes. Cursor-based pagination handles large result sets correctly when new businesses are inserted between pages.

Radius in kilometers rather than degrees because degrees are not constant distances (1 degree of longitude is 111km at the equator, 0km at the poles). Kilometers give a consistent, human-readable API contract.

FR 2 - CRUD for business listings:

POST   /businesses
PUT    /businesses/{id}
DELETE /businesses/{id}

These are write operations executed by business owners, not searchers. They hit the write path and trigger invalidation of the relevant geohash cell cache on update or delete. The geohash field is computed server-side; clients submit raw lat/lng only.

High-Level Design

Critical flows

The critical flows are listing writes with geohash computation, static nearby search with boundary-safe candidate retrieval and exact filtering, cache invalidation, and the optional dynamic-location path. The numbered designs below start with the naive query and add only the indexing and caching layers needed for scale.

1. Single server with naive lat/lng query

The simplest possible system: one application server, one PostgreSQL database, lat/lng float columns on the businesses table.

Components:

• Client: Web or mobile app sending GET /search/nearby with lat, lng, and radius.
• App Server: Converts the radius in km to degree deltas and runs a 2D bounding-box query.
• PostgreSQL: Stores all businesses with lat FLOAT and lng FLOAT columns. No spatial index.

Request walkthrough:

1. Client sends GET /search/nearby?lat=37.7749&lng=-122.4194&radius_km=5.
2. App server converts 5km to degree deltas (roughly 0.045 degrees latitude).
3. App server runs SELECT * FROM businesses WHERE lat BETWEEN (user_lat - delta) AND (user_lat + delta) AND lng BETWEEN (user_lng - delta) AND (user_lng + delta).
4. App server sorts results by Haversine distance and returns the top 20.

What breaks: WHERE lat BETWEEN ... AND lng BETWEEN ... scans every row. A B-tree index constrains one dimension efficiently but must scan every row in the matching lat band to apply the lng filter. At 500M businesses and 58K requests/second, every query is a full table scan. The database saturates immediately.

This naive version is useful as a short baseline: it works at 10,000 businesses, but the full-table scan explains why it breaks at 500 million. The point is to quantify the bottleneck before choosing an index.

2. Geohash index