Designing a Proximity Service
High Level Design·intermediate·~25 min read
- system-design
- proximity-service
- quadtree
- geospatial
- hld
What you'll learn
Problem Statement
Design a service that lets users discover nearby places (restaurants, hotels, gas stations, etc.) based on their current location. Users provide their coordinates and a search radius, and the system returns relevant places sorted by dist…
Requirements
Functional Requirements
1. Given a user's location (latitude, longitude) and a radius, return nearby places 2. Business owners can add, update, or delete places 3. Users can view detailed information about a place 4. Filter results by category (restaurant, hote…
Non-Functional Requirements
1. Low latency — search results must return in >100:1) |
Memory (QuadTree Index)
| Component | Calculation | Value | |-----------|-------------|-------| | PlaceID | 8 bytes | | | Latitude | 8 bytes (double) | | | Longitude | 8 bytes (double) | | | Per-place total | 8 + 8 + 8 | 24 bytes | | Total index memory | 500M x…
Location Table Storage
| Field | Size | Notes | |-------|------|-------| | LocationID | 8 bytes | Primary key | | Name | 256 bytes | Business name | | Latitude | 8 bytes | Geographic coordinate | | Longitude | 8 bytes | Geographic coordinate | | Description |…
QuadTree Structure
| Metric | Value | |--------|-------| | Max places per leaf | 500 | | Total leaf nodes | 500M / 500 = ~1 Million | | Tree depth (dense area) | ~12-15 levels | | Tree depth (sparse area) | ~4-6 levels | ---
System APIs
---
Design Evolution & Trade-offs
How this system grew from an MVP to what a production version looks like — and the choices you'd defend in an interview.
Stage 1 — MVP: One box, one database
The simplest thing that could possibly work for a proximity service. - A single API server (monolith) exposing searchNearby(lat, long, radius). - A single relational database (Postgres) with two B-tree indexes — one on latitude, one on l…
Stage 2 — Scale-out: Multiple pods behind a load balancer
- Search API becomes stateless — no in-process spatial state, so N replicas sit behind an L7 load balancer. - User session and rate-limiting state moved to Redis. - Postgres stays single-node, still serving spatial queries the same way.…
Stage 3 — Bottleneck: Spatial query latency in dense regions
This is the defining problem of a proximity service. A query in Manhattan should not be 100× slower than a query in the Sahara, yet with any coordinate-index scheme built on independent lat/long B-trees, that is exactly what happens. The…
Stage 4 — Second bottleneck: Read QPS and hot geographic regions
Even with a QuadTree responding in ---
Stage 5 — Mature architecture
The full production shape after Stages 2 - 4. Reads flow through cache -> aggregator -> sharded QuadTree replicas; writes flow through the Place service into Postgres, then propagate asynchronously to the QuadTree shards via Kafka; stati…
Cost vs Complexity — When to Pick What
| Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Compute | Single VM running API + DB | K8s deployment, HPA on Search API | Multi-region K8s, per-region QuadTree f…
Migration Path (MVP → Enterprise)
Stepped list — the order matters, and several steps can be shipped independently without downtime. 1. Introduce PostGIS on the existing Postgres — swap two B-trees for a GiST index over a geometry column. Dual-index during rollout, cut q…
Database Design
Schema
Storage Decision
- Place DB: SQL or NoSQL with full place metadata (address, hours, photos, reviews) - QuadTree: In-memory data structure for spatial queries only (not a database) - Separation of concerns: QuadTree answers "which places are near X?" whil…
Geospatial Indexing Approaches
Before diving into QuadTree specifically, it's worth understanding the progression of spatial indexing approaches and why each falls short:
Approach 1: SQL with Separate Lat/Long Indexes
The naive database approach creates two separate B-tree indexes — one on latitude, one on longitude — then queries both: Why it fails at scale: Each index returns a massive list (potentially millions of rows in dense areas). The database…
Approach 2: Even Grid (Fixed-Size Cells)
Divide the world into fixed-size grid cells (e.g., 10-mile squares). Store a GridID with each location. To find nearby places, query the user's grid plus its 8 neighboring grids. Grid count derivation: Earth's total surface area is ~200…
Approach 3: Dynamic Size Grids (QuadTree)
Break any grid cell that exceeds 500 places into 4 sub-grids, recursively. Dense areas get progressively smaller cells; sparse areas keep large cells. This is the preferred approach and is detailed below. ---
Geospatial Index Taxonomy
Geospatial indexes fall into two families: | Family | Approaches | Key Characteristic | |--------|-----------|-------------------| | Hash-based | Even Grid, Geohash, Cartesian Tiers | Map coordinates to a discrete cell identifier | | Tre…
Geohash: A Hash-Based Alternative
Geohash encodes latitude and longitude into a single string by interleaving bits of each coordinate. Longer strings mean higher precision: | Geohash Length | Cell Size | Use Case | |----------------|-----------|----------| | 4 | 39.1 km…
Core Data Structure: QuadTree
How It Works
A QuadTree is a tree where each internal node has exactly 4 children, representing four quadrants of a 2D space (Northwest, Northeast, Southwest, Southeast).
Recursive Subdivision
Properties: - Dense areas (Manhattan) → deep tree, many tiny leaves - Sparse areas (Sahara) → shallow tree, few large leaves - Every leaf guaranteed to have > writes and writes can tolerate slight delay, this topology works well When to…
Option A: Shard by Geographic Region
Option B: Shard by PlaceID (Chosen)
Query flow with PlaceID sharding: Why this works despite scatter-gather: - Each shard's QuadTree is smaller (3 GB vs 12 GB) — faster traversal - All shards respond in parallel — latency = slowest shard, not sum - Load is perfectly balanc…
Fault Tolerance: Detailed Design
Replication Architecture
Failure Scenarios
| Scenario | Impact | Recovery | |----------|--------|----------| | Primary dies | Secondary promoted to primary | Automatic failover, ~seconds | | Secondary dies | Reduced read capacity | Spin up new secondary, replicate from primary |…
Rebuild Process
Since the QuadTree is a computed index (derived entirely from place coordinates in the DB): ---
Caching Strategy
What to Cache
Cache Invalidation
LRU Configuration
| Parameter | Value | Rationale | |-----------|-------|-----------| | Cache size | 2-4 GB per cache node | Hot cells for popular areas | | Eviction | LRU | Naturally keeps popular areas cached | | TTL | 5 minutes | Balance freshness vs.…
Complete System Architecture
Component Responsibilities
| Component | Role | Scale Consideration | |-----------|------|---------------------| | Search Service | Accepts (lat, long, radius), fans out to shards | Stateless, horizontally scalable | | QuadTree Servers | Hold in-memory spatial ind…
Scaling for 100K QPS
Read Replica Strategy
Horizontal Scaling Path
---
Key Design Trade-offs
| Trade-off | Decision | Reasoning | |-----------|----------|-----------| | In-memory vs. disk index | In-memory | 12 GB fits in RAM; microsecond vs. millisecond latency | | Threshold per leaf | 500 places | Lower = deeper tree (more tra…
Interview Discussion Points
Why Not PostGIS / Database Spatial Indexes?
| Approach | Latency at 100K QPS | Complexity | |----------|---------------------|------------| | PostGIS (R-tree on disk) | 5-50ms per query (disk I/O) | Low (use existing DB) | | In-memory QuadTree | 0.01-1ms per query | Medium (custom…
Why QuadTree Over R-Tree or KD-Tree?
| Structure | Best for | Weakness for this problem | |-----------|----------|---------------------------| | QuadTree | 2D spatial with variable density | Slightly more memory than KD-tree | | R-tree | Range queries on rectangles | Comple…
Summary: Why Each Decision Matters
| Decision | What it Solves | |----------|---------------| | In-memory QuadTree (12 GB) | O(log N) spatial lookup without any disk I/O | | 500-place threshold per leaf | Balances tree depth vs. per-leaf scan cost | | Doubly-linked neighb…