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 interesting engineering challenge is not the concept but the index. Scanning 500M lat/lng rows for every query is a full table scan, and at 58K requests/second that means instant saturation. This question tests spatial indexing (geohashing, quadtrees), caching strategies for a 100:1 read-heavy workload, and the architectural fork between static data (Yelp businesses) and dynamic data (Uber drivers, nearby friends).

I love this question in interviews because it starts deceptively simple (just filter by distance!) and then forces you to invent a spatial index from first principles. The moment you realize a B-tree cannot index two dimensions simultaneously, the real design begins.

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, I would build a dedicated location update service that accepts position pushes over WebSockets and writes to Redis GEOADD. The 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.

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

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.

I'd draw this naive version first on the whiteboard and explicitly say: "this works at 10,000 businesses, here's why it breaks at 500 million." Interviewers want to see you reason about when a design stops working, not just jump to the optimal answer.

2. Geohash index

The key insight: encode each business's location as a string where shared prefix means geographic proximity. A database WHERE geohash LIKE 'dr5ru%' is an efficient B-tree prefix scan, not a full table scan.

Geohashing divides the Earth into rectangular cells using alternating longitude/latitude bit splits. Each additional character narrows the cell by roughly 8x. A 6-character geohash covers approximately 1.2km x 0.6km. Businesses in the same cell share the same 6-character prefix.

Components (added):

• Geohash column: A VARCHAR(12) geohash column on the businesses table with a B-tree index, precomputed on insert and updated on position change.

Request walkthrough:

1. Client sends GET /search/nearby?lat=37.7749&lng=-122.4194&radius_km=5.
2. App server encodes the user's position to a 6-character geohash: dr5ru.
3. App server computes the 8 neighboring cell hashes: [dr5rr, dr5rx, dr5ry, dr5rm, dr5rj, dr5rn, dr5rp, dr5rt].
4. App server runs SELECT * FROM businesses WHERE geohash IN ('dr5ru', 'dr5rr', 'dr5rx', ...) (9 cells total).
5. App server filters by exact Haversine distance and returns sorted results.

What break remains: geohash cells are rectangles, not circles. The 9-cell query returns some businesses outside the true circular radius. The Haversine post-filter in step 5 removes these false positives. This is cheap (runs in memory) and mandatory for the accuracy NFR.

I always call out that the Haversine filter is not optional. I've seen candidates skip it and then get tripped up when the interviewer asks: "what about a business at the corner of the 9-cell grid that's actually 8km away?" The post-filter is your safety net.

3. Redis geospatial cache layer

5B queries/day at 58K requests/second requires caching. The geohash-to-businesses mapping for popular areas changes rarely (restaurants do not move). Redis provides GEOADD and GEORADIUS commands with throughput exceeding 100K operations/second.

Components (added):