System Design: Design a Proximity Service

A proximity service powers “find nearby restaurants” or “show gas stations within 5 km.” Think Google Maps, Yelp, or Uber’s driver matching. The core challenge is indexing geographic locations so that radius queries are fast — you can’t scan every business on earth for each request.

Functional Requirements

• Search for businesses within a given radius of a location (latitude, longitude).
• Return results sorted by distance, filterable by category (restaurant, gas station, etc.).
• Business owners can add, update, or delete their listing.
• View detailed business information (name, address, hours, photos).

Non-Functional Requirements

• Read-heavy: 100x more searches than updates. Assume 500M daily searches, 10M businesses.
• Search latency: p99 under 200ms.
• Business updates can be eventually consistent (a few minutes delay is acceptable).
• High availability for search; updates can tolerate brief downtime.

High-Level Architecture

Mobile/Web Client
│
▼
Load Balancer
│
┌───┴───┐
▼       ▼
Search   Business
Service  Service
│         │
▼         ▼
Geospatial   Business
Index       DB
(read replicas)  (primary)
│
▼
Cache
(Redis)

Search Service handles location queries — it’s read-only and stateless. Business Service handles CRUD operations on business data. Separating them lets you scale reads independently.

Spatial Indexing Approaches

Geohash

Geohash encodes a latitude/longitude into a string by recursively bisecting the world into a grid. Nearby locations share a common prefix.

Latitude: 37.7749, Longitude: -122.4194
Geohash:  9q8yyk (precision 6 → ~1.2km × 0.6km cell)

How search works: compute the geohash of the user’s location at the desired precision. Query the database for all businesses whose geohash starts with the same prefix. Also query the 8 neighboring cells to handle edge cases at cell boundaries.

Pros: simple to implement with a standard database index on the geohash string column. Prefix queries are fast B-tree lookups.

Cons: cells at the same precision level vary in size near the poles. Edge cases at cell boundaries require querying neighbors.

Quadtree

A quadtree recursively divides a 2D space into four quadrants. Dense areas get subdivided more deeply, giving finer granularity where it matters.

How search works: traverse the tree from the root to find the leaf node containing the user’s location. Return all businesses in that leaf and adjacent leaves within the search radius.

Pros: adapts to density — downtown Manhattan gets more cells than rural Montana. No edge-case neighbor queries needed if you traverse up to the parent.

Cons: the tree must be built and stored in memory (~1.7 GB for 10M businesses). Updates require tree rebuilds or re-balancing.

Which to Choose?

For interviews, geohash is usually the right starting point — it’s simpler and most interviewers expect it.

Database Schema

businesses (
  business_id   BIGINT PRIMARY KEY,
  name          VARCHAR(255),
  category      VARCHAR(64),
  latitude      DECIMAL(10, 7),
  longitude     DECIMAL(10, 7),
  geohash       VARCHAR(12),   -- precomputed
  address       TEXT,
  city          VARCHAR(128),
  rating        DECIMAL(3, 2),
  created_at    TIMESTAMP,
  updated_at    TIMESTAMP
)

INDEX idx_geohash ON businesses(geohash);
INDEX idx_category_geohash ON businesses(category, geohash);

Search Flow

1. Client sends: GET /search?lat=37.77&lng=-122.42&radius=2km&category=restaurant
2. Search service computes the geohash at the appropriate precision for the radius.
3. Computes the 8 neighboring geohash cells.
4. Queries the database: WHERE geohash LIKE 'prefix%' AND category = 'restaurant' across all 9 cells.
5. Filters results by exact distance (some results may be outside the radius).
6. Sorts by distance and returns the top results.

Caching Strategy

Searches are highly cacheable because business locations don’t change often:

• Cache key: geohash:precision:category — e.g., 9q8yyk:6:restaurant
• TTL: 5-15 minutes. Business updates propagate on the next cache miss.
• Cache layer: Redis with read replicas in each region.

With geohash-based caching, many users in the same area hit the same cache entry — cache hit rates of 80%+ are typical.

Handling Business Updates

Business data changes (new listings, updated hours) flow through the Business Service to the primary database. The search index updates via two approaches:

1. Periodic rebuild: every few minutes, rebuild the geospatial index from the primary DB. Simple and consistent.
2. Change Data Capture (CDC): stream database changes to the search service via a message queue. Lower latency but more complex.

For the interview, option 1 is usually sufficient given the “eventually consistent” requirement.

Scaling

• Read replicas: the geospatial index is read-heavy. Deploy multiple read replicas across regions.
• Sharding by geohash prefix: partition businesses by the first 2-3 characters of the geohash, distributing load geographically.
• CDN for static data: business photos, menus, and reviews are served from a CDN.

Interview Tips

• Start with geohash — it’s the simplest approach that works. Mention quadtree as an alternative and compare.
• Explain why you can’t just use WHERE distance(lat, lng, ...) < radius on every row — it’s a full table scan.
• The 8-neighbor query for geohash boundary handling is a key detail interviewers look for.
• Separate the read path (search) from the write path (business updates) early in your design.
• Mention that the search results are approximate until you compute the actual Haversine distance — the geohash gives you candidates, not final results.