01. Proximity Service — High-Level Design¶

~15 min read · Part 2 of 4 (Overview → HLD → LLD → Q&A)

This file turns the solutioning narrative into boxes and the flows between them. Read the architecture top to bottom, follow a place-update and a nearby-query through it, then look at what breaks when a downtown shard runs hot.

Architecture¶

                          ┌──────────────┐
         client ────────▶ │ API Gateway   │  (auth, rate-limit, snap coords)
                          └──────┬───────┘
                                 │
                          ┌──────▼───────┐
                          │  Load Balancer │
                          └──────┬───────┘
                                 │
                   ┌─────────────┼─────────────┐
                   ▼             ▼             ▼
             ┌──────────┐  ┌──────────┐  ┌──────────┐
             │  Search  │  │  Search  │  │  Search  │   stateless search tier
             │  service │  │  service │  │  service │   (fan-out, filter, rank)
             └────┬─────┘  └────┬─────┘  └────┬─────┘
                  │             │             │
        ┌─────────┼─────────────┼─────────────┼──────────┐
        ▼         ▼             ▼             ▼          ▼
  ┌──────────┐  ┌──────────────────────┐  ┌──────────────┐
  │  Result  │  │   Geo-Index cluster   │  │  Place Store  │
  │  cache   │  │  (in-mem, geohash-    │  │  (durable SoT,│
  │(cell→page)│  │   sharded quadtrees)  │  │  metadata)   │
  └──────────┘  └───────────▲──────────┘  └──────┬───────┘
                            │ rebuild / update           │ CDC
                            │                            ▼
                     ┌──────┴───────┐            ┌──────────────┐
                     │  Index Builder │◀──────────│  Update /     │
                     │  (batch+stream)│            │  Ingestion    │
                     └──────────────┘            │  pipeline     │
                                                  └──────────────┘
                            ▲
                            │ rating/review aggregates (async)
                     ┌──────┴───────┐
                     │  Aggregation  │
                     │  pipeline     │
                     └──────────────┘

Read it top to bottom. A client request enters through the gateway, which authenticates, rate-limits, and — importantly — snaps the raw coordinates to a cell so the result cache can hit. The load balancer spreads requests across a stateless search tier. Each search service first checks the result cache; on a miss it fans out to the geo-index cluster (the in-memory spatial structure that turns point-and-radius into candidate place ids), enriches and ranks against attributes it holds, and writes the page back to cache. The place store is the durable source of truth for full records, but it is off the hot query path — it feeds the index, not the query. Writes flow up the right side: the ingestion pipeline lands edits in the place store, change-data-capture drives the index builder to update the geo-index, and a separate aggregation pipeline rolls up ratings and review counts and pushes them into the index asynchronously.

Components¶

API Gateway. Terminates TLS, authenticates, enforces per-client rate limits, and performs the one piece of query rewriting that makes the cache work: snapping the raw (lat, lng) to its geohash cell and bucketing the radius and time window into the cache key. Doing this at the edge means every search service downstream sees an already-normalized query.

Search service. The stateless brain of the read path. It owns the sequence: check cache, compute covering cells, fan out to the geo-index shards, gather candidates, run exact-distance filtering, apply "open now" and other attribute filters, rank, paginate, and cache. It holds no durable state, so any instance handles any query and the tier scales by adding boxes.

Geo-Index cluster. The in-memory spatial index, sharded by geohash prefix. Each shard holds the quadtrees (or geohash buckets) for its slice of the world and answers "give me the candidate place ids in these cells." It is rebuildable from the place store, so a lost node is a capacity event, not a data-loss event. This is where the read-heavy load actually lands after the cache.

Place Store. The durable system of record: full place records keyed by place_id. A document or relational store sized for 100 GB, tuned for point reads by id and the occasional write. It is deliberately not queried by location — location queries go to the index — so it never carries the 50,000 QPS.

Result cache. An in-memory cell+filters → ranked page store fronting the whole read path. This is where the 50,000 QPS is largely absorbed. Entries carry a short TTL (tens of seconds to a couple of minutes) because "open now" and ranking drift, so a stale page self-heals quickly.

Update / Ingestion pipeline. Handles place create/edit/delete, validates and geocodes, writes the durable record, and emits a change event. Rare traffic, so it can be careful and synchronous without hurting anyone.

Index Builder. Consumes change events (and runs periodic full rebuilds) to keep the geo-index current. Location changes trigger a cell move; attribute changes update the in-index ranking fields. Batch rebuilds give a clean, defragmented index; the stream path keeps it fresh between rebuilds.

Aggregation pipeline. Rolls up raw reviews into a rating and review count per place and pushes those into the index on a schedule (say every few minutes). Ranking reads these lagged aggregates; nobody waits on a review write.

Primary write path (add or edit a place)¶

POST /api/v1/places (or PATCH) reaches the ingestion pipeline through the gateway.
The pipeline validates the payload, geocodes the address to (lat, lng) if needed, and writes the full record to the place store, which assigns or confirms the place_id. This write is durable and synchronous — the owner must know their place is saved.
The place store emits a change event (via CDC or an outbox) describing the create/edit.
The index builder consumes the event. For a new place or a moved place it computes the geohash cell and inserts/relocates the entry in the owning shard's structure; for an hours/category edit it updates the in-index attributes. Location changes are the only ones that touch cell membership.
The place becomes searchable once the index update lands — typically seconds behind the write, which the freshness budget allows. Ranking aggregates (rating, review count) arrive later still, on the aggregation pipeline's own cadence.

Primary read path (nearby query)¶

GET /api/v1/nearby?lat=…&lng=…&radius_m=1000&open_now=true reaches the gateway, which snaps the coordinates to a cell and builds the cache key.
The search service checks the result cache. On a hit — the common case in a busy area — it returns the ranked page directly. One in-memory lookup, done.
On a miss, the service computes the covering cells: the geohash cell containing the snapped point plus the neighbors needed to cover the radius (9 cells for a 1 km radius at precision 6).
It fans out to the geo-index shards owning those cells and gathers candidate place ids with their in-index attributes (~1,800 candidates in a dense cell).
It runs the exact-distance filter (haversine ≤ radius), dropping the corner false positives that square-ish cells include (~1,800 → ~1,200), then applies "open now" (computed from stored hours and the current clock) and any category/rating filters (down to a few hundred).
It ranks the survivors by the blended score and takes the top N (20).
It writes the page to the result cache with a short TTL and returns it. Any attribute it needs beyond the index it can fetch from the place store, but for the standard card it stays entirely in memory.

Storage choices¶

Spatial index: in-memory, geohash-sharded. The access pattern is "fetch the candidates in these cells" thousands of times a second; only RAM is fast enough, and 5 GB fits. It is a derived structure, rebuildable from the place store, so durability lives elsewhere and the index optimizes purely for read speed and clean sharding by geohash prefix. Redis GEO (geohash-scored sorted sets) is the off-the-shelf version; a custom in-process quadtree per shard is the version that adapts granularity to density.
Place store: durable document/relational store. Point reads by place_id, rare writes, 100 GB. DynamoDB, Postgres, or Cassandra all fit; the choice is driven by durability and operational familiarity, not by query shape, because location queries never hit it.
Result cache: Redis, in-memory, short TTL. Chosen for microsecond reads and TTL-driven self-healing. It is an accelerator, not a source of truth — a cold cache just means more index-tier work until it warms.
Rating/review aggregates: append-optimized, rolled up. Raw reviews are write-heavy and queried by aggregation; a columnar or time-series store behind the aggregation pipeline suits them, and keeping them out of the hot path is what lets ranking use lagged values without hurting latency.

Scaling¶

Read path. Two tiers absorb reads in order: the result cache, then the geo-index cluster. The cache handles the repetitive downtown-at-lunch load; the index handles the misses. To scale reads you grow the cache cluster, add geo-index replicas (especially for hot shards), and add stateless search boxes — all independent, horizontal moves. Snapping coordinates to cells is what makes the cache effective: it converts near-infinite distinct coordinates into a bounded set of cell keys.

Write path. Writes are ~tens/second at peak, so the index builder and place store are never stressed by volume. The work is keeping the index fresh, not keeping up with throughput; batch rebuilds plus a streaming update path do both.

Partitioning and hot shards. The geo-index shards on geohash prefix, which keeps geographically-close cells together — good for neighbor lookups, but it means a single dense, busy region (all of downtown shares a prefix) becomes a hot shard. Put the scenario on it: 50,000 QPS with a lunchtime concentration might send 40% of misses to the handful of shards covering major-city centers. The cache absorbs ~70% before that, and the hot shards get extra read replicas so the remaining load spreads across copies. A query that straddles a shard boundary (its 9 cells live on two shards) becomes a scatter-gather across both — cheap when rare, but a boundary that runs through a busy area raises the cross-shard rate, which is one of the first things to watch.

Operational signals¶

The healthy signal is result-cache hit ratio, sitting around 70% and rising when a crowd gathers — a lunch rush that concentrates thousands of users into a few cells should lift the hit ratio, because that is the cache working as designed. The first metric to degrade under trouble is candidate fan-in per query: when a cell grows pathologically dense (a convention packs a district, or the index hasn't rebuilt and a coarse cell is overfull), the candidate set climbs from ~1,800 toward tens of thousands and p99 latency follows it up. The misleading metric is average query latency — it stays flat because most queries are cache hits, hiding a cold-path fan-out that has quietly gone from 30 ms to 200 ms; watch p99, not the mean. The graph an experienced operator opens first during an incident is per-shard QPS and candidate-fan-in distribution: a single hot shard, or one cell whose candidate count has blown out, explains most latency incidents, and it is invisible in the aggregate.

Failure modes and resilience¶

Geo-index shard outage. Queries whose cells live on the dead shard fail or fall back. Mitigations: replicate each shard (serve from a replica on primary loss) and rebuild the lost shard from the place store — minutes of work because the index is derived and only 5 GB total. During the gap, cached pages for that region keep serving.
Hot shard under the scenario. At 50,000 QPS, downtown lunch can drive a few city-center shards far above the rest. If replicas are saturated, the symptom is rising p99 on cold-cache queries in those regions. Mitigations: add read replicas to the hot shards, lower the snap granularity slightly to raise the cache hit ratio (trading a little accuracy for a lot of relief), and shed load on the coldest attribute filters first.
Result cache outage. The 50,000 QPS falls through to the index tier, roughly tripling its load (15k → 50k QPS). Mitigations: cluster the cache with replicas so a single node loss is survivable, and size the index tier with enough headroom (and request coalescing on identical cell keys) that a cold cache degrades latency rather than collapsing.
Stale index after a location edit. A place that moved keeps showing at its old spot until the index update lands. Because location edits are rare and the streaming path is seconds-fast, the window is small; for correctness-critical moves, the builder can prioritize location changes over attribute changes.
"Open now" clock skew. If a search box's clock or a place's timezone data is wrong, open/closed flips incorrectly. Mitigation: compute open-now in the place's local timezone from a trusted clock, and treat timezone as validated data at ingestion, not at query time.
Aggregation lag. If the rating rollup stalls, ranking uses older scores — degraded relevance, never wrong results. Mitigation: alarm on aggregation lag, and cap how stale a ranking input may be before it is flagged.

Where this shows up in production¶

Yelp — serves nearby-business queries from a geospatial index tuned to metro density, exactly the granularity-vs-fan-in tradeoff, with ranking blending distance, rating, and review volume rather than pure distance.
Google Maps / S2 — Google's S2 library maps the sphere onto a Hilbert curve of cells at many levels, the production answer to "one cell size doesn't fit both a city and an ocean."
Uber / H3 — Uber's hexagonal grid indexes the world into cells for supply-demand and nearby-driver queries; hexagons give more uniform neighbor distances than square geohash cells.
Redis GEO — ships geohash-scored sorted sets with GEOSEARCH, the off-the-shelf in-memory spatial index behind many "nearby" features, and the direct model for our geo-index cluster.
PostGIS — the durable, indexed (R-tree/GiST) spatial store many teams start with before an in-memory tier exists; it is the "place store that can also do location queries" fallback.
Elasticsearch geo_point / geo distance — combines spatial filtering with attribute filtering and ranking in one query engine, the "index everything and filter" alternative to a dedicated geo tier.
Foursquare — built a places graph and proximity API where the hard part was keeping tens of millions of venues fresh, the update-lag-vs-accuracy tradeoff at the center of this study.
Tinder / dating apps — "people within N km" is the same primitive with a faster-moving index (users move, restaurants don't), which pushes them toward coarser cells and more frequent index updates.
DoorDash / delivery — "restaurants that can deliver to this address" layers a delivery-radius filter on the same nearby core, and caches heavily per delivery zone.