Skip to content

02. Proximity Service — Low-Level Design

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

The HLD named the boxes. This file opens the ones that carry the design's weight — the geospatial index (geohash and quadtree), the radius query, the ranking step, and the index update path — and pins down the data, the algorithms, and the concurrency corners where a proximity service actually breaks.

Data models

The durable place record is keyed by place_id and holds everything a card needs. Location and hours are stored here as the source of truth; the index copies only what it needs.

CREATE TABLE place (
    place_id     BIGINT       PRIMARY KEY,
    name         TEXT         NOT NULL,
    lat          DOUBLE       NOT NULL,      -- WGS84
    lng          DOUBLE       NOT NULL,
    geohash6     CHAR(6)      NOT NULL,      -- precomputed cell at index precision
    category     SMALLINT     NOT NULL,      -- enum: restaurant, cafe, ...
    hours        JSONB        NOT NULL,      -- weekly open/close in local tz
    timezone     TEXT         NOT NULL,      -- IANA tz, validated at ingest
    rating       REAL         NOT NULL DEFAULT 0,   -- lagged aggregate
    review_count INT          NOT NULL DEFAULT 0,   -- lagged aggregate
    status       SMALLINT     NOT NULL DEFAULT 1,   -- 1=active, 0=hidden
    updated_at   TIMESTAMP    NOT NULL
);

CREATE INDEX idx_geohash6 ON place (geohash6);   -- for batch index rebuilds

Three deliberate choices. geohash6 is precomputed and stored, not derived per query, so an index rebuild is an indexed range scan by cell rather than a recompute over 50M rows. hours and timezone live on the record, never in the spatial index, because "open now" is derived at query time — storing a per-minute-changing boolean in the index would mean rewriting it continuously. And rating/review_count are lagged aggregates, refreshed by the aggregation pipeline; the query path reads whatever value is current and never blocks on a review write.

The in-memory index entry is a stripped-down projection — only the fields the fan-out and ranking need before the exact-distance step:

IndexEntry {
    place_id:  u64
    lat, lng:  f64        # for exact haversine
    category:  u8         # for the category filter without a store hit
    rating:    f16        # for ranking without a store hit
    review_ct: u32        # for ranking
    open_key:  u32        # packed weekly-hours bitmap for fast open-now
}                         # ~40 bytes packed → 50M × 40B ≈ 2 GB

open_key is a compact encoding of the weekly hours (e.g. 15-minute slots as a bitset) so the search service can evaluate "open now" without a place-store read — the hours themselves are static, only the current time changes. The result cache stores ranked pages:

key:   sha1( snapped_cell | radius_bucket | category | open_now | min_rating | time_bucket )
value: [ {place_id, name, distance_m, rating, open_now, score}, ... ]   # top-N page
ttl:   45s        # short: open-now and ranking drift, so pages self-heal

Component internals

Component 1 — The geospatial index (geohash + quadtree)

Responsibility: map a point-and-radius to the small set of candidate places that could be inside it, in memory, in microseconds.

Two structures solve this; the design uses geohash for sharding and a quadtree within each shard for density-adaptivity.

Geohash interleaves the bits of latitude and longitude and base32-encodes the result, so a shared prefix means spatial proximity. Each added character refines the cell ~8×:

precision 5  ≈ 4.9 km × 4.9 km     (too coarse for 1 km: cells hold ~5,000 places downtown)
precision 6  ≈ 1.2 km × 0.6 km     (chosen: matches 1 km radius, ~200 places/cell downtown)
precision 7  ≈ 153 m × 153 m       (too fine: 1 km needs ~49 cells to cover)

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"   # geohash alphabet (no a,i,l,o)

def geohash_encode(lat: float, lng: float, precision: int) -> str:
    lat_rng, lng_rng = [-90.0, 90.0], [-180.0, 180.0]
    bits, out, ch, even = 0, [], 0, True
    while len(out) < precision:
        if even:                                # bisect longitude
            mid = (lng_rng[0] + lng_rng[1]) / 2
            ch = (ch << 1) | (lng >= mid)
            lng_rng[lng >= mid] = mid           # keep the half we're in
        else:                                   # bisect latitude
            mid = (lat_rng[0] + lat_rng[1]) / 2
            ch = (ch << 1) | (lat >= mid)
            lat_rng[lat >= mid] = mid
        even = not even
        bits += 1
        if bits == 5:                           # 5 bits per base32 char
            out.append(BASE32[ch]); bits, ch = 0, 0
    return "".join(out)

The weakness of a fixed geohash grid is uniform cell size: a precision-6 cell is right for a 1 km query downtown but holds thousands of places in a packed district and two places in a rural county. A quadtree fixes that by adapting to density. Start with one cell for the world; whenever a leaf exceeds a capacity cap (say 100 places), split it into four quadrants and redistribute. Dense regions grow deep; empty regions stay shallow.

class QuadNode:
    bbox: BBox                 # the region this node covers
    points: list[IndexEntry]   # non-null only for leaves
    children: list[QuadNode]   # 4 quadrants, non-null only for internal nodes

    def insert(self, e: IndexEntry, cap: int = 100):
        if self.children:                      # internal: descend
            self._child_for(e.lat, e.lng).insert(e, cap)
        else:
            self.points.append(e)
            if len(self.points) > cap:         # leaf overflow → split
                self._subdivide()
                for p in self.points:
                    self._child_for(p.lat, p.lng).insert(p, cap)
                self.points = None

    def query_range(self, circle) -> list[IndexEntry]:
        if not self.bbox.intersects(circle.bbox): return []
        if self.children:
            return [e for c in self.children for e in c.query_range(circle)]
        return [p for p in self.points if circle.bbox.contains(p.lat, p.lng)]

The shard owns one quadtree per geohash prefix it is responsible for, giving both the clean prefix-based sharding of geohash and the density-adaptivity of the quadtree. The candidate cap is the guardrail that keeps the fan-in bounded no matter how dense a district gets — the property the fixed grid could not promise.

Component 2 — The radius query executor

Responsibility: run the full read pipeline — cover, fetch, distance-filter, attribute-filter, rank, page.

def nearby(q: Query) -> Page:
    key = cache_key(q.snapped_cell, q.radius_bucket, q.filters, q.time_bucket)
    if (page := result_cache.get(key)) is not None:
        return page                                     # ~70% land here

    cells = covering_cells(q.lat, q.lng, q.radius_m)    # ~9 cells for 1 km
    candidates = geo_index.fetch(cells)                 # scatter-gather across shards
    within = [c for c in candidates
              if haversine(q.lat, q.lng, c.lat, c.lng) <= q.radius_m]   # exact
    filtered = [c for c in within
                if passes(c, q.filters) and open_now(c.open_key, now())]
    ranked = sorted(filtered, key=lambda c: -score(c, q))[: q.limit]
    page = to_page(ranked)
    result_cache.set(key, page, ttl=45)
    return page

Component 3 — The ranking function

Responsibility: order survivors by usefulness, not distance alone — the difference between "the nearest place" and "the place you want."

Ranking is a weighted blend, computed over the few hundred post-filter candidates (cheap: a few hundred multiply-adds per query). Distance is normalized against the query radius so a 200 m place beats a 900 m one, rating and review count are combined so a 4.6★/2,000-review place beats a 4.8★/3-review one, and an open-now match gets a small boost:

def score(c: IndexEntry, q: Query) -> float:
    prox   = 1.0 - (haversine(q.lat, q.lng, c.lat, c.lng) / q.radius_m)   # 0..1
    quality = c.rating / 5.0
    confidence = min(1.0, log1p(c.review_ct) / log1p(1000))               # dampen low counts
    boost = 0.05 if open_now(c.open_key, now()) else 0.0
    return 0.45 * prox + 0.35 * quality * confidence + 0.15 * quality + boost

The weights are tunable and would in production come from a learned model (de-scoped here), but the shape is the point: distance is one input among several, not the sort key. Ranking reads only in-index fields, so it never touches the place store on the hot path.

Core algorithm — the radius query, stepped through the scenario

Take the threaded query: "restaurants within 1 km, open now, ranked" at 50,000 QPS, one request from a user at (37.7749, -122.4194) in a dense downtown, arriving as a cache miss.

  1. Cover. The snapped point sits in geohash cell 9q8yyk. A 1 km radius against a ~1.2 km × 0.6 km cell cannot be contained by one cell, so the executor takes the cell plus its 8 neighbors — 9 cells — computed by decoding the cell's bounding box and stepping one cell north/south/east/west (and the diagonals). This is the "not a full scan" moment: 9 cells, never 50M places.

  2. Fetch. The 9 cells resolve to 1–2 geo-index shards (neighbors share a prefix); the executor scatter-gathers the candidate lists. In this dense cell that is 9 × ~200 ≈ 1,800 candidates, each an IndexEntry with lat/lng, category, rating, and hours bitmap — no place-store reads yet.

  3. Exact-distance filter. Geohash cells are rectangular, so the 9-cell union is a jagged square, not a circle; its corners hold places farther than 1 km. A haversine check drops them: ~1,800 → ~1,200 genuinely within 1 km.

  4. Attribute filter. Apply category == restaurant and open_now. Open-now reads each candidate's open_key bitmap against the current local time — no store hit — and roughly half of restaurants are open at any given lunch hour, leaving ~1,200 → ~400.

  5. Rank. Score the ~400 survivors with the blended function and take the top 20. Four hundred score computations is sub-millisecond; the whole cold-path query lands in tens of milliseconds.

  6. Cache and return. Write the 20-place page under the cell-keyed cache key with a 45 s TTL. Every other user standing in 9q8yyk for the next 45 s issuing the same query gets this page in one lookup — which is exactly how a 50,000 QPS lunch rush collapses to ~15,000 QPS at the index tier.

The load story falls out of the steps: 50,000 raw QPS, ~70% served from the result cache, ~15,000 reaching the index, each touching 9 cells → ~135,000 in-memory cell fetches/second across the shards, each cell fetch a few hundred entries. No step scans the catalog; the largest working set any single query touches is ~1,800 entries.

Sequence diagram — a cold nearby query with scatter-gather

Client      API GW       Search svc     Result cache   Geo-index (2 shards)   
  │ GET /nearby │             │               │                │        
  ├────────────▶│ snap coords │               │                │        
  │             ├────────────▶│ get(cell_key) │                │        
  │             │             ├──────────────▶│  (miss)        │        
  │             │             │  cover→9 cells │                │        
  │             │             ├─ fetch(cellsA)─┼───────────────▶│ shard A
  │             │             ├─ fetch(cellsB)─┼───────────────▶│ shard B
  │             │             │◀───────────────┼── candidates ──┤ (gather)
  │             │             │ haversine filter │              │        
  │             │             │ open_now + rank  │              │        
  │             │             ├─ set(cell_key) ─▶│  (fill 45s)   │        
  │◀────────────┼─── page ────┤               │                │        
  │             │             │  next user in same cell → cache hit       │

One cold query does the full fan-out, distance-filter, and rank; it fills the cache so the crowd behind it in the same cell is served from memory.

Concurrency and edge cases

  • Quadtree leaf split under concurrent inserts. When a leaf overflows and splits, a concurrent query or insert could observe a half-built subtree. The index builder applies splits under a per-node write lock (or builds the new subtree off to the side and swaps a pointer atomically), so readers see either the old leaf or the fully-split node, never an intermediate. Because writes are ~tens/second, the lock is rarely contended.
  • A place moves across a cell (or shard) boundary. A location edit changes the geohash, so the entry must be removed from the old cell and inserted into the new one — possibly on a different shard. Do it as remove-then-insert with the insert first (so the place is briefly in both cells, findable, rather than briefly in neither); a duplicate in results is de-duplicated by place_id, a gap is not recoverable. Location edits are rare, so the transient double-entry is cheap.
  • Idempotent place creation. A retried POST after a network timeout could create two records for one business. Ingestion collapses retries with a client-supplied idempotency key (or a natural key like normalized name+address+phone), so a retry returns the original place_id rather than minting a second.
  • Stale ranking aggregates. Because rating/review_count are lagged, two search services may briefly rank the same candidate differently right as an aggregate lands. This is acceptable — ranking is best-effort ordering, not a correctness contract — and the short cache TTL bounds how long any one stale ordering is served.
  • Open-now boundary races. A place closing at 15:00 flips from open to closed at that minute; a query at 14:59:59 that returns from a 45 s cache may show it open until 15:00:44. The short TTL bounds the error to under a minute, which the freshness budget permits; if a use case cannot tolerate it, open-now is recomputed post-cache on the returned set rather than baked into the cached page.
  • Scatter-gather partial failure. If one of the two shards a query straddles is briefly unreachable, the executor can return the candidates from the reachable shard flagged as partial rather than failing the whole query — a slightly-incomplete nearby list beats an error on an interactive map — and retries or serves from a replica on the next request.
  • Cache stampede on a hot cell. When a hot cell's 45 s entry expires mid-lunch, thousands of identical queries arrive cold at once. Single-flight coalescing on the cache key ensures exactly one does the fan-out-and-rank while the rest await its fill, so the index tier sees one cold query per cell per TTL window, not thousands.