ch01-proximity-service

Chapter 1: Design a Proximity Service

volume2 proximity geospatial geohash quadtree

Status: 🟩 Interview ready
Difficulty: Medium-Hard
Time to complete: 50 min read + practice

---

Overview

A proximity service finds nearby points of interest (businesses, restaurants, venues) given a user’s current location and a search radius. Think Yelp, Google Places, or the “restaurants near me” feature inside any map app.

Why this matters:

• Very common interview question (Uber, Yelp, Google, Meta frequently ask this)
• Combines database design, geospatial indexing, caching, and API design
• Teaches real-world geospatial techniques used in production systems

Problem Statement

Design a proximity service that:

• Accepts a user’s latitude/longitude and a search radius
• Returns a ranked list of businesses within that radius
• Handles 100M daily active users and 200M businesses
• Keeps search latency low (read-heavy, write-light workload)

---

Step 1: Requirements & Scope (5 min)

Functional Requirements

Clarifying questions:

• What radii do we support? → Fixed options: 500m, 1km, 2km, 5km, 10km, 20km
• Is location data real-time? → Near real-time is fine; business moves rarely
• Do businesses update their own location? → Yes, but changes propagate with slight delay (acceptable)
• Return limit per query? → Default 20 results per page, support pagination
• What data is returned? → business_id, name, address, lat/lng, rating, thumbnail

Scope:

• Search businesses by location + radius
• CRUD for business owners to manage listings
• Read path and write path are separate concerns

Non-Functional Requirements

• Low latency: Search results in < 200ms
• High availability: Downtime loses searches → revenue impact
• High read throughput: Read-to-write ratio ~100:1
• Scalability: 100M DAU, 200M businesses

Capacity Estimation

Daily Active Users:     100M
Searches per user/day:  ~5
Total daily searches:   500M
QPS (read):             500M / 86,400 sec ≈ 5,800 QPS
Peak QPS (read):        ~3x average       ≈ 17,400 QPS

Business writes (updates, new listings):
  200M businesses / day (spread evenly)   ≈ very low write QPS (~200 writes/sec)

Read-to-write ratio:    ~30:1 (heavily read-skewed)

Storage estimate:

200M businesses × ~1 KB per record ≈ 200 GB (business metadata)
Geospatial index (geohash strings + IDs): additional ~50 GB
Total: ~250 GB — fits in a modest PostgreSQL cluster with replicas

---

Step 2: High-Level Design (10 min)

API Design

Search nearby businesses:

GET /v1/search?lat={lat}&lon={lon}&radius={radius}&business_type={type}&page={page}

Parameters:
  lat           float   required   User latitude  (e.g., 37.7749)
  lon           float   required   User longitude (e.g., -122.4194)
  radius        int     optional   Meters, default 2000. Options: 500|1000|2000|5000|10000|20000
  business_type string  optional   Filter: "restaurant"|"gas_station"|"hotel"
  page          int     optional   Pagination cursor, default 1

Response 200 OK:
{
  "total": 142,
  "businesses": [
    {
      "business_id": "biz_abc123",
      "name": "Tartine Bakery",
      "address": "600 Guerrero St, San Francisco, CA",
      "lat": 37.7616,
      "lon": -122.4241,
      "rating": 4.7,
      "distance_meters": 380,
      "thumbnail_url": "https://cdn.example.com/biz_abc123.jpg"
    },
    ...
  ],
  "next_page": 2
}

Business CRUD (for business owners):

POST   /v1/businesses                    Create a business listing
GET    /v1/businesses/{business_id}      Get business details
PUT    /v1/businesses/{business_id}      Update business (name, address, hours)
DELETE /v1/businesses/{business_id}      Remove listing

Component Overview

┌──────────────────────────────────────────────────────────────────────┐
│                            Clients                                   │
│                     (Mobile / Web / Partners)                        │
└────────────────────────────┬─────────────────────────────────────────┘
                             │
                    ┌────────▼────────┐
                    │  Load Balancer  │
                    └────────┬────────┘
               ┌─────────────┴────────────┐
               │                          │
    ┌──────────▼──────────┐   ┌──────────▼──────────┐
    │  Location-Based     │   │   Business Service  │
    │  Service (LBS)      │   │   (CRUD)            │
    │  (read-only,        │   │   (writes go here)  │
    │   stateless)        │   └──────────┬──────────┘
    └──────────┬──────────┘              │
               │                         │
    ┌──────────▼──────────┐   ┌──────────▼──────────┐
    │  Geospatial Index   │   │   Business DB        │
    │  (Redis / PostGIS)  │   │   (PostgreSQL)       │
    │  Read-heavy         │   │   Write + Read       │
    └─────────────────────┘   └──────────┬──────────┘
                                         │
                              ┌──────────▼──────────┐
                              │   Read Replicas      │
                              │   (scale reads)      │
                              └─────────────────────┘

Two-database approach:

Database	Purpose	Characteristics
Business DB (PostgreSQL)	Business metadata: name, address, hours, phone	Write-heavy; normalized; ACID
Geospatial Index (Redis/PostGIS)	Spatial lookup: geohash → list of business_ids	Read-heavy; can tolerate eventual consistency

Location-Based Service (LBS):

• Stateless → horizontally scalable
• No business logic, pure query layer
• Translates (lat, lng, radius) → geohash prefix → business_ids → fetch details

---

Step 3: Deep Dive (20 min)

Approach 1: Naive — Full Table Scan (Too Slow!)

SELECT business_id, name, lat, lng,
       distance(lat, lng, :user_lat, :user_lng) AS dist
FROM businesses
WHERE distance(lat, lng, :user_lat, :user_lng) <= :radius
ORDER BY dist
LIMIT 20;

Problem:

• Computes distance for every row — O(n)
• 200M rows → unusable even with parallelism
• No index on a computed column

---

Approach 2: Two-Dimensional Index (Better but Still Slow)

Add separate indexes on lat and lng:

CREATE INDEX idx_lat ON businesses(lat);
CREATE INDEX idx_lng ON businesses(lng);
 
-- Bounding box query (approximate)
SELECT * FROM businesses
WHERE lat BETWEEN :min_lat AND :max_lat
  AND lng BETWEEN :min_lng AND :max_lng;

Problem: Database can efficiently use ONE index at a time. Combining two range indexes (“index merge”) is expensive. Still scans too many rows for dense areas.

---

Approach 3: Evenly Divided Grid

Divide the world into a fixed N×N grid. Store each business with its grid cell ID. Query a cell + adjacent cells.

┌─────┬─────┬─────┬─────┐
│ 0,3 │ 1,3 │ 2,3 │ 3,3 │
├─────┼─────┼─────┼─────┤
│ 0,2 │ 1,2 │ 2,2 │ 3,2 │
├─────┼─────┼─────┼─────┤
│ 0,1 │ 1,1 │ 2,1 │ 3,1 │
├─────┼─────┼─────┼─────┤
│ 0,0 │ 1,0 │ 2,0 │ 3,0 │
└─────┴─────┴─────┴─────┘

Problem: Uneven distribution. Manhattan has millions of businesses; Sahara desert has zero. Fixed grid is wasteful and inefficient for dense areas.

---

Approach 4: Geohash (Recommended for Interviews!)

Core idea: Encode the entire globe into a hierarchy of grid cells using a Base32 string. Longer string = smaller, more precise cell.

How geohash works:

1. Interleave latitude bits and longitude bits alternately
2. Encode the resulting bit string in Base32
3. Result is a short alphanumeric string where common prefix = geographic proximity

Geohash precision table:

Level	Length	Cell Size (approx)	Use Case
1	1 char	5,000 km × 5,000 km	Country level
2	2 chars	1,250 km × 625 km	Region
3	3 chars	156 km × 156 km	City
4	4 chars	39 km × 20 km	District
5	5 chars	4.9 km × 4.9 km	~5km radius
6	6 chars	1.2 km × 0.6 km	~1km radius
7	7 chars	152 m × 152 m	Street level

Radius → geohash level mapping:

Radius  → Geohash level
500m    → level 6  (0.6km cell)
1km     → level 6
2km     → level 5  (4.9km cell)
5km     → level 5
10km    → level 4  (20km cell)
20km    → level 4

Geohash example:

San Francisco (37.7749, -122.4194):
  Level 6 geohash: "9q8yy"
  Level 5 geohash: "9q8yy" → prefix "9q8y"
  Level 4 geohash: prefix "9q8"

Nearby restaurant (37.7616, -122.4241):
  Level 6 geohash: "9q8yw"
  → Shares prefix "9q8y" at level 5 (same area!)

Query algorithm:

1. Convert user (lat, lng) to geohash at precision P
   e.g., "9q8yy" at precision 6

2. Get 8 neighboring geohashes:
   ["9q8yz", "9q8yu", "9q8yv", "9q8yg",
    "9q8ys", "9q8yt", "9q8yw", "9q8yx"]

3. Query Redis for all businesses in 9 cells (center + 8 neighbors):
   ZRANGEBYLEX geohash_index "[9q8yy" "[9q8yy\xff"
   (repeat for all 9 cells)

4. For each candidate business_id, fetch metadata from Business DB

5. Compute exact distance, filter to radius, sort by distance

6. Return top 20

Why 9 cells? Boundary problem: A user standing at the edge of geohash cell X might miss businesses in the adjacent cell Y even though they are very close. Querying all 8 neighbors guarantees complete coverage.

┌─────────┬─────────┬─────────┐
│ NW nbr  │  N nbr  │ NE nbr  │
│ 9q8yg   │ 9q8yu   │ 9q8yv   │
├─────────┼─────────┼─────────┤
│  W nbr  │  CENTER │  E nbr  │
│ 9q8ys   │ 9q8yy   │ 9q8yz   │  ← Always query all 9!
├─────────┼─────────┼─────────┤
│ SW nbr  │  S nbr  │ SE nbr  │
│ 9q8yt   │ 9q8yw   │ 9q8yx   │
└─────────┴─────────┴─────────┘

Redis data structure for geohash index:

Sorted Set: geohash_index
  Key:    geohash string (lexicographic)
  Score:  0 (all same score → sorted lexicographically by member)
  Member: "9q8yy:biz_abc123"   (geohash:business_id)

# Insert a business:
ZADD geohash_index 0 "9q8yy:biz_abc123"

# Query all businesses with prefix "9q8yy":
ZRANGEBYLEX geohash_index "[9q8yy" "[9q8yy\xff"
→ ["9q8yy:biz_abc123", "9q8yy:biz_def456", ...]

Alternative: Redis GEOADD/GEODIST/GEORADIUS (built-in geospatial):

GEOADD locations 37.7616 -122.4241 "biz_abc123"
GEORADIUS locations 37.7749 -122.4194 2 km ASC COUNT 20

• Redis internally uses geohash for storage
• GEORADIUS is convenient but has less fine-grained control

Geohash edge case — boundary split:

Problem: Two adjacent cells share a border. A business 10m across
the border from a user appears in a different geohash. Without
neighbor queries, it would be missed.

Solution: Always query 9 cells (center + 8 neighbors).
This adds a small overhead but ensures correctness.

---

Approach 5: QuadTree (Good for Custom Implementations)

Core idea: Recursively subdivide the world into quadrants. Split a cell when it contains more than a threshold number of businesses (e.g., 100).

World
├── NW Quadrant (sparse) — leaf at level 2
├── NE Quadrant
│   ├── NW sub-quadrant (medium density) — leaf
│   ├── NE sub-quadrant
│   │   ├── NW (dense, e.g., Manhattan) — leaf
│   │   ├── NE — leaf
│   │   ├── SW — leaf
│   │   └── SE — leaf
│   ├── SW — leaf
│   └── SE — leaf
├── SW Quadrant — leaf
└── SE Quadrant — ...

QuadTree properties:

Property	Value
Max businesses per leaf	100 (configurable threshold)
Build time	O(n log n) — each business inserted once per level
Space	O(n)
Query time	O(log n + k) where k = results returned
Update	Hard — must re-balance subtree

Build the tree:

function buildQuadTree(businesses, bounds):
    if len(businesses) <= MAX_LEAF_SIZE:
        return LeafNode(businesses, bounds)

    NW, NE, SW, SE = splitIntoBounds(bounds)
    return InternalNode(
        NW = buildQuadTree(filter(businesses, NW), NW),
        NE = buildQuadTree(filter(businesses, NE), NE),
        SW = buildQuadTree(filter(businesses, SW), SW),
        SE = buildQuadTree(filter(businesses, SE), SE)
    )

Query:

function search(node, point, radius):
    if not overlaps(node.bounds, circle(point, radius)):
        return []
    if isLeaf(node):
        return filter(node.businesses, distance <= radius)
    return (search(node.NW, ...) + search(node.NE, ...) +
            search(node.SW, ...) + search(node.SE, ...))

QuadTree pros and cons:

Pros	Cons
Adapts to data density (more cells in NYC, fewer in Montana)	Hard to update incrementally (business moves = tree rebuild)
Efficient for irregular distributions	Must be rebuilt when data changes significantly
Entire tree fits in memory (~1-2 GB for 200M businesses)	Complex to implement correctly in an interview
No precision loss — exact geometry	Not as cache-friendly as geohash

When to use QuadTree: When you control the full stack and have heavily non-uniform data distribution. Geohash is simpler for interviews.

---

Approach 6: Google S2 (Advanced, Know the Concept)

Core idea: Map the sphere (Earth) onto a cube, then use a Hilbert space-filling curve to assign a 1D integer to each 2D cell. The Hilbert curve has excellent locality — nearby cells have nearby integer IDs.

Sphere → Cube face projection → Divide face into grid → Hilbert curve ordering

Hilbert curve property:
  Points that are geographically close → integers that are numerically close
  This makes range queries on a 1D integer work for 2D geography!

S2 key properties:

• Cells at 30 levels of granularity (1 cm² to entire Earth)
• Better area distortion than geohash (more uniform cell sizes)
• Used by Google Maps, Foursquare, Pokémon GO
• More complex to implement from scratch — use as knowledge, not interview code

---

Algorithm Comparison

Approach	Complexity	Pros	Cons	Use
Full scan	O(n)	Simple	Way too slow	Never
2D index	O(n) effective	Easy	Index merge expensive	Never
Fixed grid	O(1) lookup	Simple	Uneven distribution	No
Geohash	O(log n)	Simple strings, Redis-native, easy prefix search	Boundary problem (solved by 9-cell query), cells not equal size	Yes — interview default
QuadTree	O(log n + k)	Adaptive density	Hard to update, complex to code	Yes — if custom infra
S2	O(log n)	Best coverage, uniform cells	Very complex	Know concept only

---

Business Data: Read/Write Separation

Write path (low frequency):
  Business owner → Business Service → Primary DB (PostgreSQL)
                                    → Invalidate / update geospatial index

Read path (high frequency):
  User search → LBS → Redis Geospatial Index → business_ids
              → Business Service → Read Replica → full business details

Database schema:

-- Business metadata table
CREATE TABLE businesses (
    business_id  VARCHAR(36) PRIMARY KEY,
    owner_id     VARCHAR(36) NOT NULL,
    name         VARCHAR(255) NOT NULL,
    address      TEXT,
    lat          DECIMAL(10, 8) NOT NULL,
    lng          DECIMAL(11, 8) NOT NULL,
    category     VARCHAR(50),
    rating       DECIMAL(3, 1),
    is_active    BOOLEAN DEFAULT true,
    created_at   TIMESTAMP DEFAULT NOW(),
    updated_at   TIMESTAMP DEFAULT NOW()
);
 
CREATE INDEX idx_businesses_category ON businesses(category);
CREATE INDEX idx_businesses_lat_lng ON businesses(lat, lng); -- for bounding box fallback

---

Caching Strategy

What to cache:

Cache Layer	Key	Value	TTL
Geospatial index	Redis Sorted Set (geohash_index)	geohash:business_id pairs	No TTL — updated on write
Business details	biz:{business_id}	Full business JSON	24 hours
Search results	search:{geohash6}:{category}	List of business_ids	10 minutes
User location	user:{user_id}:geohash	Current geohash of user	5 minutes

Cache invalidation:

When a business updates location:
  1. Update primary DB
  2. Remove old geohash entry from Redis: ZREM geohash_index "old_hash:biz_id"
  3. Add new geohash entry:             ZADD geohash_index 0 "new_hash:biz_id"
  4. Invalidate business detail cache:  DEL biz:{business_id}
  5. Invalidate affected search caches: DEL search:{old_geohash6}:*
                                        DEL search:{new_geohash6}:*

---

Handling Scale

LBS horizontal scaling:

LBS is stateless → add more instances behind load balancer

┌───────────────────────────────────────┐
│            Load Balancer              │
└────┬──────────┬──────────┬────────────┘
     │          │          │
  ┌──▼──┐   ┌──▼──┐   ┌──▼──┐
  │LBS 1│   │LBS 2│   │LBS 3│   ... (add more on demand)
  └──┬──┘   └──┬──┘   └──┬──┘
     └──────────┴──────────┘
              │
     ┌────────▼────────┐
     │   Redis Cluster │   (sharded by geohash prefix)
     └─────────────────┘

Redis sharding for geospatial index:

Shard by first character of geohash (16 possible first chars in Base32):
  Shard 0: geohash prefix "0" - "3"
  Shard 1: geohash prefix "4" - "7"
  Shard 2: geohash prefix "8" - "b"
  Shard 3: geohash prefix "c" - "z"

This distributes global queries evenly across shards.

Read replica strategy:

Primary DB (writes) → replicate → Read Replica 1
                                → Read Replica 2
                                → Read Replica 3

LBS always reads from replicas.
Business Service writes to primary only.
Replication lag < 1 second (acceptable for near-real-time updates).

---

Design Summary

Final Architecture

┌────────────────────────────────────────────────────────────────────┐
│                       Client (Mobile/Web)                          │
└────────────────────────────────┬───────────────────────────────────┘
                                 │  GET /v1/search?lat=&lon=&radius=
                        ┌────────▼────────┐
                        │  Load Balancer  │
                        └───────┬─────────┘
               ┌────────────────┴─────────────────┐
               │  Search Path                     │  Write Path
    ┌──────────▼──────────┐          ┌─────────────▼──────────────┐
    │  Location-Based     │          │    Business Service         │
    │  Service (LBS)      │          │    (CRUD, Owner API)        │
    │  [Stateless, N pods]│          └─────────────┬──────────────┘
    └──────────┬──────────┘                        │
               │                                   │ read/write
    ┌──────────▼──────────┐          ┌─────────────▼──────────────┐
    │  Redis Cluster      │          │  PostgreSQL Primary         │
    │  Geospatial Index   │◄─────────│  (business metadata)        │
    │  (geohash → biz_id) │  sync    └─────────────┬──────────────┘
    │                     │                        │ replicate
    │  Also: detail cache │          ┌─────────────▼──────────────┐
    └─────────────────────┘          │  Read Replicas (×3)         │
                                     │  (LBS reads details here)   │
                                     └────────────────────────────┘

Key Decisions Summary

Decision	Choice	Reasoning
Geospatial algorithm	Geohash	Simple strings, Redis ZRANGEBYLEX, easy neighbor lookup
Geospatial storage	Redis Sorted Set	Fast prefix scans, in-memory, horizontally scalable
Business metadata	PostgreSQL + Read Replicas	ACID for writes, scale reads horizontally
LBS design	Stateless microservice	Horizontal scaling for high read QPS (5,800 peak)
Cache	Redis (detail + search result cache)	Sub-millisecond reads, TTL auto-expiry
Update strategy	Write-through + cache invalidation	Eventual consistency acceptable (near real-time)
Neighbor search	9-cell query (center + 8 neighbors)	Solves geohash boundary problem

---

Interview Questions & Answers

Q: Why geohash over a simple (lat, lng) index in the database?
A: A composite (lat, lng) B-tree index only helps with one dimension at a time. For a range query spanning both dimensions, the DB must merge two range scans, which is expensive. Geohash encodes 2D space into a 1D string where proximity is preserved — nearby locations share a common prefix. This turns a 2D spatial query into a simple string prefix scan, which Redis handles very efficiently with ZRANGEBYLEX.

Q: What is the geohash boundary problem and how do you solve it?
A: A user standing at the edge of geohash cell “9q8yy” may be very close to a business in the adjacent cell “9q8yz”, but a naive query on only “9q8yy” would miss that business. The fix is to always query 9 cells: the user’s own cell plus all 8 immediate neighbors. After collecting all candidate business IDs, compute exact distance and filter to the requested radius. This adds a constant overhead (9× the work) but guarantees no nearby business is missed.

Q: Geohash vs QuadTree — when would you choose each?
A: Geohash is simpler to implement, maps naturally to Redis strings, and is the right choice for most interviews and most production systems. QuadTree adapts better to highly non-uniform data distribution (e.g., ultra-dense urban areas vs sparse rural regions) and can be more memory-efficient in those cases. However QuadTree is harder to update incrementally — moving a business requires a subtree rebuild. Use geohash unless you have a strong reason to need the density adaptivity of a QuadTree.

Q: How do you handle a business that moves (e.g., a food truck)?
A: The update pipeline must be atomic in practice: (1) Write new lat/lng to the primary DB. (2) Remove the old geohash entry from the Redis sorted set. (3) Add the new geohash entry. (4) Invalidate any search-result caches that covered the old and new geohash cells. Replication lag to read replicas is acceptable (< 1 second). Users might get stale results for a few seconds, which is fine for a proximity service.

Q: How would you scale this to 10× more users?
A: The LBS is already stateless — horizontally scale it by adding more pods. Redis can be clustered and sharded by geohash prefix. PostgreSQL read replicas handle the read volume. The only global bottleneck is the Redis geospatial index — if needed, partition it into regional clusters (US, EU, Asia) since users typically search nearby businesses and cross-region queries are rare.

---

Key Takeaways

1. Geohash encodes 2D location as a 1D string — geographic proximity maps to string prefix proximity. This is the key insight enabling fast prefix-range searches.
2. Always query 9 cells (center + 8 neighbors) to avoid missing businesses near cell boundaries.
3. Separate read and write paths: LBS (reads) → Redis + Read Replicas; Business Service (writes) → Primary DB → sync geospatial index.
4. LBS is stateless → trivially horizontally scalable to handle peak QPS (~17,400).
5. Redis ZRANGEBYLEX is the natural fit for geohash prefix queries in production; Redis GEORADIUS is the higher-level convenience API.
6. QuadTree is adaptive to density but harder to update; geohash is fixed-grid but simpler and battle-tested.
7. Cache aggressively: business details (24h TTL), search results per geohash cell (10 min TTL), invalidate on any business update.

---

Related Resources

• ch02-nearby-friends — Real-time location tracking (contrast: query-based vs push-based)
• ch05-consistent-hashing — Used for Redis cluster sharding
• key-patterns > Geospatial Indexing — Geohash and QuadTree pattern reference
• distributed-system-components — Redis, PostgreSQL, Load Balancers

---

Last Updated: 2026-04-13
Status: 🟩 Interview ready — Geohash is the go-to answer; know the boundary problem cold!