Proximity / Nearby Service#
Problem statement (interviewer prompt)
Design a generic proximity / nearby service: given a point (lat, lng) and a radius (or k), return the nearest POIs in <200ms. Cover the spatial index choice (quadtree / geohash / S2 / H3 / R-tree), sharding, and how to handle hot cells (e.g. city centres).
flowchart LR
U([User])
Q[Nearby Query]
IDX[(Spatial Index<br/>quadtree / S2 / geohash)]
POI[(Places)]
U --> Q --> IDX --> POI --> U
classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
class U client;
class Q service;
class IDX,POI datastore;
flowchart TB
subgraph Clients
APP[App]
end
subgraph Edge
CDN
GW
end
subgraph Query[Query API]
NEAR[Nearby k-NN]
RAD[Radius search]
BBOX[Bounding box]
AUTO[Autocomplete with location bias]
end
subgraph Indexes[Spatial Indexes]
QT[Quadtree]
GH[Geohash prefix tree]
S2[S2 cells]
H3[H3 hexagons]
RTREE[R-tree for polygons]
end
subgraph Data
PSVC[Place Service]
PDB[(Places sharded by cell)]
CACHE[(Hot cell cache)]
end
subgraph Ingest
UP([POI ingest pipeline])
GEOC[Geocoder]
DEDUP[Dedup / merge]
end
subgraph Ranking
REL[Relevance + distance combine]
PER[Personalization]
end
Clients --> CDN --> GW --> Query
Query --> Indexes --> PDB
Query --> CACHE
PDB -. seed .-> Indexes
Ingest --> PSVC --> PDB
Ranking --- Query
classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
class APP,NEAR,RAD,BBOX,AUTO,QT,GH,S2,H3,RTREE,PSVC,GEOC,DEDUP,REL,PER service;
class PDB,CACHE datastore;
class UP compute;
Index choices#
| Index | Strengths | Weaknesses |
|---|---|---|
| Quadtree | adaptive density | unbalanced trees |
| Geohash | string-prefixable, easy sharding | corner cases at edges |
| S2 | sphere-aware, uniform cells | learning curve |
| H3 | hexes have nice neighbor properties | non-hierarchical |
| R-tree | shapes, not just points | harder to shard |
k-NN approach#
- Locate cell containing query point.
- Iteratively expand to neighbor cells until enough candidates.
- Sort by Haversine distance; return top-k.
Glossary & fundamentals#
Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.
| Tag | Concept | What it is | Page |
|---|---|---|---|
HLD |
CDN | edge caching for static assets | cdn |
HLD |
Sharding | horizontal partitioning across nodes | database-sharding |
HLD |
Geo indexing | Geohash, Quadtree, S2, H3, R-tree | geo-indexing |
Quick reference#
Functional#
- Nearby query: list places within radius / k-NN of point.
- Bounding box query.
- Optional autocomplete with location bias.
Non-functional#
- p99 < 200 ms.
- Read-heavy.
- 99.99% availability.
Capacity#
- 100M+ POIs globally.
- Millions of queries/s peak.
Schema#
places(id, name, lat, lng, cell_id_S2, category)cell_index(cell_id → place_id list)materialized for fast fetch.
Trade-offs#
- Static fence vs dynamic boundary: store cell IDs at multiple zoom levels for flexible queries.
- Precompute hot cells (city centers) into cache for instant response.
- Geohash vs S2 vs H3: pick one and stick; cross-system conversion is painful.
Refs#
- "S2 Geometry Library" docs.
- Uber H3 hex grid docs.
- ByteByteGo "Design proximity service".
- Alex Xu Vol 2.
FAQ#
Which spatial index should I pick for a proximity service?#
Geohash and S2 are simple to shard and good for radius queries. H3 has nicer neighbor properties for ride sharing. R-trees and quadtrees handle non uniform density better but are harder to distribute.
How does the service answer k nearest neighbors in under 200 ms?#
Query expands outward from the user's cell, fetching candidate POIs from neighboring cells until k results are found. A second pass computes exact haversine distance and ranks by score.
How do you handle hot cells like city centers?#
Hot cells are split into finer subcells until the per cell load is manageable. Read replicas and caches absorb popular queries, and unsplittable hot shards get dedicated capacity.
How does a proximity service stay consistent as POIs change?#
Writes go to a primary store, then async propagate to the spatial index and search engine. Stale results are tolerable because users rarely notice millisecond level lag in nearby place data.
Why is geohash sometimes a poor choice near the equator or poles?#
Geohash cells distort with latitude and break near the date line. S2 cells fix this with a Hilbert curve over a sphere and produce more uniform cell sizes worldwide.