Proximity Service

Design a proximity service to discover nearby places (restaurants, hotels, etc.) on Yelp or Google Maps.

Figure 1: Nearby search on Yelp

Step 1 of 4: Understand the problem and establish design scope #

Goal: lock in requirements and scale.

Functional requirements #

Must have:

1. Return all businesses based on the user's location (lat/lng) and radius
2. Business owners can add/delete/update a business; updates effective next day (not real-time)
3. Customers can view detailed information about a business
4. Search radius options: 0.5km, 1km, 2km, 5km, 20km. Max radius: 20km
5. User's moving speed is slow; no constant page refresh needed

Non-functional:

1. Low latency for nearby business search
2. Data privacy: comply with GDPR, CCPA
3. High availability and scalability for peak hours in dense areas

Back-of-the-envelope estimation:

1. 100M DAU, 200M businesses
2. 5 search queries per user per day
3. Search QPS = 100M × 5 / 10⁵ = ~5,000

Step 2 of 4: Propose high-level design and get buy-in #

Goal: agree on APIs, data model, and the geospatial index choice.

API design #

GET /v1/search/nearby: returns businesses based on search criteria (paginated).

Business CRUD APIs:

Data model #

1. Read/write ratio: read-heavy (search + detail views), write volume low (infrequent business edits)
2. Business table: primary key = business_id

Table 3: Business table

3. Geo index table: for efficient spatial operations (discussed in the deep dive)

High-level design #

Figure 2: High-level design

1. Load balancer: distributes traffic across services; single DNS entry routes to appropriate services by URL path
2. LBS (Location-Based Service): read-heavy, stateless, horizontally scalable. No write requests. High QPS at peak
3. Business service: handles CRUD (low QPS writes) + detail views (high QPS reads)
4. Database cluster: primary-secondary setup. Primary handles writes; replicas for reads. Replication lag acceptable for non-real-time business data
5. Scalability: auto-scale for peak (mealtimes), scale down off-peak; multi-region deployment on cloud

Algorithms to fetch nearby businesses #

Options: even grid, geohash, cartesian tiers (hash-based); quadtree, Google S2, RTree (tree-based).

Figure 5: Geospatial index types

All divide the map into smaller areas and build indexes for fast search. Geohash, quadtree, and Google S2 are the most widely used.

Option 1: Two-dimensional search (naive) #

Draw a circle with the radius, find all businesses within it. Inefficient: requires a full table scan. Indexes on lat/lng columns help, but the intersect of two large 1D datasets is still slow.

Option 2: Evenly divided grid #

Divide the world into even grids. Problem: uneven business distribution (dense in NYC, empty in deserts). Need adaptive granularity.

Option 3: Geohash #

Reduces 2D lat/lng to a 1D string. Recursively subdivides the world into quadrants; each additional bit = finer precision. Uses base32 representation.

Examples: Google HQ → 9q9hvu, Facebook HQ → 9q9jhr.

Geohash precision table:

Useful lengths: 4–6 (longer → too small; shorter → too large).

Radius → geohash mapping:

Boundary issues:

1. Two close locations on opposite sides of the equator/meridian share no prefix (e.g. u000 and ezzz 30km apart in France)
2. A long shared prefix doesn't guarantee the same grid: must also query neighbor grids
3. Solution: fetch from the current grid + all 8 neighbors. Neighbor geohashes computable in constant time

Not enough businesses: remove the last geohash digit to expand the search radius gradually until enough results are returned.

Option 4: Quadtree #

In-memory data structure (NOT a database). Recursively subdivides 2D space into 4 quadrants until a grid has ≤ N businesses (e.g. ≤100).

Memory estimation (200M businesses):

1. Leaf nodes: ~200M / 100 = ~2M
2. Internal nodes: ~0.67M (≈ 1/3 of leaf nodes)
3. Leaf node size: 832 bytes (32B coords + 8B × 100 business IDs)
4. Internal node size: 64 bytes (32B coords + 32B child pointers)
5. Total: ~1.71 GB. Fits in one server's memory

Build time: O(n/100 log(n/100)): several minutes for 200M businesses.

Operational considerations:

1. Long server start-up → incremental rollout (subset of servers at a time) or blue/green deployment
2. Updates: nightly rebuild (acceptable per "next day effective" agreement). On-the-fly update requires locking → complex
3. Quadtree supports k-nearest queries (unlike geohash's fixed radius). Dynamically adjusts grid size by density

: Real-world quadtree near Denver : Remove a business from geohash index : Update quadtree (O(log n) but needs locking)

Option 5: Google S2 #

Maps the sphere to a 1D index via the Hilbert curve. Two close points on the curve are close in 1D. Advantages: geofencing with arbitrary areas at varying levels; flexible Region Cover algorithm (min/max level + max cells).

: Hilbert curve : Geofence

Industry adoption #

Geohash vs Quadtree comparison #

Geohash: easy to implement; fixed precision → fixed grid size; simple index updates (remove row); supports radius-based queries.

Quadtree: harder (tree build needed); supports k-nearest queries; dynamic grid sizing by density; updating is O(log n) but complex with locking.

Recommendation for the interview: choose geohash or quadtree (S2 too complex to explain).

Step 3 of 4: Design deep dive #

Goal: scale the DB, caching, regions, filtering.

Scale the database #

Business table: shard by business_id: even load distribution, easy to maintain.

Geospatial index table (geohash-based): two schema options:

1. Option 1: single row per geohash with a JSON array of business IDs: complex updates (scan array, lock row, handle duplicates)
2. Option 2: compound key (geohash, business_id) with one row per business: simple add/remove, no locking needed. Recommended

Scaling: the full geospatial index fits in the working set of a modern DB (~1.71GB). No need to shard: use read replicas instead. Sharding adds application-layer complexity unnecessarily.

Caching #

Heavily read-heavy, small dataset → DB queries are already fast. Caching requires careful benchmarking. If beneficial:

Cache key: geohash (not raw lat/lng, which varies slightly with each reading). Small location changes map to the same geohash.

Cache data types:

Memory for Redis geohash cache (3 precisions):

1. 8 bytes × 200M × 3 = ~5 GB
2. One modern Redis server sufficient; deploy a global Redis cluster for HA and low cross-continent latency
3. Radii mapping: 500m→geohash_6, 1km/2km→geohash_5, 5km→geohash_4

Business info cache: key = business_id, value = business object. Updated nightly via batch job.

Region and availability zones #

Deploy LBS to multiple regions:

1. Users physically closer to servers
2. Spread traffic across dense regions (Japan, Korea → separate regions or multi-AZ)
3. Comply with local privacy laws (country-specific deployments via DNS routing)

Filter results by time or business type #

Return business IDs first, hydrate business objects, then filter on opening time/type. The result set is small enough (per-grid) for this approach.

Final design diagram #

Figure 21: Design diagram

Flow for nearby search (500m radius example):

1. Client sends (lat=37.776720, lng=-122.416730, radius=500m) to load balancer
2. LBS receives request
3. LBS maps 500m → geohash length 6 (per Table 5)
4. LBS computes neighboring geohashes → list of 9 geohashes
5. LBS fetches business IDs from "Geohash" Redis (parallel calls per geohash)
6. LBS fetches hydrated business info from "Business info" Redis, computes distances, ranks, returns to client

Business CRUD flow: business service handles all. Checks the "Business info" cache first; falls back to DB. Cache updated nightly.

Step 4 of 4: Wrap up #

What we designed:

1. Geospatial indexing options covered: 2D search, even grid, geohash, quadtree, Google S2 (geohash chosen for simplicity)
2. Caching with Redis reduces latency
3. Database scaled via replication and sharding
4. Multi-region deployment for availability, latency, and privacy compliance