Design nearby place search and friend discovery

01Problem and scope

A proximity service finds eligible records near a query coordinate using a stated distance model. Spatial indexes reduce the candidate set; exact distance and a valid stopping rule establish radius or nearest-k correctness, where k is the requested number of closest results. For example, in local projected meters a query at x=990 asks for cafés within 50 meters. Place P12 at x=1010 with the same y coordinate is only 20 meters away, although a grid boundary at x=1000 puts it in another cell. Searching only the query’s cell is therefore incomplete.

This example explains a proximity service: find records near coordinates. Yelp-like places are relatively stable; nearby friends are moving private records. Both require spatial lookup, but their freshness and permission rules differ.

The primary product returns the nearest twenty eligible cafés within a requested radius, with category and text filters. It also supports distance or rating ordering under an explicit API contract. Nearby friends are a separate extension with moving, private records and current sharing checks. Routing, advertising and reservations are excluded; a map display is not the spatial correctness mechanism.

Query q31 uses a 50-meter radius to demonstrate boundary coverage and exact filtering. The local coordinates support a simple proof; production globe queries require a suitable geographic-distance implementation. Spatial coverage, freshness and ranking must each meet the declared contract.

02Functional requirements

1. Manage places: Authorized owners/editors can add, move, close or delete a place.
2. Search nearby: Apply bounded radius and text/category filters; sort by distance or rating and use opaque pagination. Decide whether the caller needs all matches or only the best k.
3. Show reviews and details: Accept review text, ratings and photo references under abuse controls. Return current place details and a clearly defined review-aggregate freshness.
4. Return correct nearest-k results: Return the closest eligible records under the stated distance model, not merely the first k in the caller's cell.
5. Share friend locations explicitly: The user chooses an audience and may revoke sharing. Store sequence, observation/receipt time and expiry; return location age.
6. Protect private positions: Require current sharing relationships. Never use a public-place cache as permission to expose a private location.

Bounded search behavior

Set maximum radius and a low-latency read target. If the requested radius contains fewer than k matches, return those matches without silently expanding it. An expansion feature must label the new radius and belong to the API contract. Routing, ads and reservations are outside scope.

Freshness and privacy distinctions

A stale review count is different from a café being in the wrong city. Likewise, returning an old friend position as “here now” is a correctness error, not merely a harmless stale display.

Do not tell arbitrary callers whether a non-sharing person is nearby. Empty results must not become a side channel for probing restricted locations through repeated filters.

03Non-functional requirements

1. Workload: 100,000 searches/s.
2. Latency: p95 below 150 ms and p99 below 500 ms for bounded normal-radius queries.
3. Availability: 99.95% read availability.
4. Place freshness: Updates enter search within five seconds p99. Names/review aggregates may have a separately defined longer cache horizon.
5. Friend-location freshness: Assume updates every five seconds while sharing; mark positions older than 15 seconds stale and expire them at 30 seconds. Negotiate these product assumptions rather than treating them as universal safe values.
6. Durability: Authoritative place writes survive one storage-node failure under the chosen replicated commit policy. The spatial index is derived and rebuildable.
7. Bounded query cost: Cap radius, result count, filters and query time. A global-radius rating query over 500M places cannot inherit the same latency promise as a 50-meter café search.

Coverage, freshness and privacy invariants

If strict read-your-write search is required, route to an index that has applied the write or supplement its candidates with the known recent change, called an update overlay. Do not silently strengthen the ordinary five-second indexing contract.

04Capacity estimates

Workload assumptions and arithmetic

Use these workload assumptions: 500M places, 100K searches/second, and 20% annual growth. QPS below means queries per second.

Worked estimates

The compact tuple is just the ID and coordinates needed to locate a candidate, without its full place details. The leaf estimate considers a quadtree: an index that repeatedly divides a region into four subregions and stores points in terminal nodes called leaves. Actual space also depends on how full those leaves are.

Capacity implications and limits

Ten-mile square cells cover 100 square miles each, not ten: do not divide area by a linear radius. Quadtree internal pointers and node bounds add space; partial occupancy increases leaf count. Coincident points require a maximum depth/overflow policy.

Suppose a square cell is 100 meters wide. A 50-meter circle near a corner can intersect four cells, including the cell containing its center; covering the query's bounding square and then testing exact distance avoids missing the twenty-meter café. The number of cells increases with radius/resolution and location; do not assume a fixed nine-cell rule for every hierarchical globe index.

If a dense urban query retrieves 5,000 candidates and exact distance/filter evaluation costs an illustrative two microseconds each, that is ten milliseconds CPU/query before loading full place details from the candidate IDs, called hydration. At 100K QPS, such a workload would require about 1,000 CPU-seconds/s just for that stage. Measure density distribution and filter selectivity; average global place density hides city hotspots.

At twenty returned records of 1 KB each, responses are about 2 GB/s before thumbnails. Serving photos through object delivery avoids multiplying application bandwidth. Three copies of the 12 GB raw spatial tuples are only 36 GB, but tree nodes, IDs, indexes, version metadata and replicas can substantially exceed that. Reviews and media dominate separate storage; do not pretend the 793-byte place record includes an unlimited review history.

05APIs and contracts

Request and response example

GET /places?lat=40.7&lon=-74.0&radiusMeters=50
    &category=cafe&sort=distance&limit=20&cursor=opaque
→ {places:[{id:P12,distanceMeters:20,version:4,...}],
   asOf:indexWatermark,nextCursor:...,partial:false}

PUT /places/P12 {expectedVersion:4,point:...,name:...}
→ {version:5,status:"stored",searchStatus:"pending"}

Validate latitude/longitude range, coordinate system, radius units and maximum count. Use exact units in field names so “50” cannot mean degrees on one path and meters on another. A cursor binds the location, radius, filter set, sort and snapshot context. An altered query cannot reuse an old boundary. For distance ties, add stable place ID ordering.

For private presence, PUT /me/location {streamEpoch:3,sequence:18,point,observedAt} derives identity from authentication and returns accepted sequence/expiry. The server decides whether the observation is fresh enough and enforces share policy. Older sequences do not overwrite newer positions. Restrict queries by current sharing relationships and bound location history retention.

Place writes use optimistic versions to reject conflicting edits; idempotency identities recover a lost creation response. Review creation has its own identity and author permissions. A map result can be partial only when the response says so; silently omitting an unavailable neighboring shard is incorrect for a claimed exhaustive nearest query.

Location sequence numbers are scoped to a server-issued stream epoch. Starting a replacement publishing session obtains a new epoch and fences the older session, so a device restart at sequence one is not rejected forever and two devices cannot silently interleave one sequence space. The authoritative tuple is (streamEpoch,sequence). Receipt age is server-measured; client observedAt is an asserted observation time with bounded acceptance rules, not proof that the GPS reading is fresh or truthful.

06Data model and access patterns

The public-place path separates durable place/review records from derived search and rating data. The private-friend path adds a current position and a separate rule deciding who may see it. These are different authorities even though both search paths use coordinates.

Index place details by ID, reviews by (placeId,createdAt,reviewId) and spatial candidates by geometry/cell. Store media bytes outside these rows. A place change commits an outbox/change event so spatial indexers can recover. Each index record keeps the source version; late version 4 cannot overwrite a version-5 move or tombstone.

An outbox stores the intention to publish a place change in the same database transaction as the changed place. An index worker can then receive that change through a retryable relay; a crash between the database commit and event delivery does not silently leave the spatial index unchanged.

For a hand-built quadtree, nodes store bounding rectangles and either four child references or leaf records. Parent pointers assist traversal, but a linked list of leaves is an iteration convenience, not proof of geometric adjacency. Coincident points require maximum depth and overflow handling or a split could continue forever. A durable shard manifest or reverse mapping records which places belong to an index owner for rebuild.

Friend presence has much shorter retention and higher update rate. Keep the current authoritative point separate from the structural spatial index so small movements need not rebuild a tree.

For private friend locations, the authoritative read binds sharing policy revision and viewer to an exact presence sequence and point. Policy and current presence are read from one consistent authority snapshot, or the service verifies a version predicate before returning the point. The spatial index only supplies candidate identities; it cannot authorize a newer point under an older decision.

07Basic working design

Coordinate units and spatial predicates

Store each place with latitude/longitude. A naive latitude range plus longitude range can return many candidates and requires careful units. Degrees are not meters, and a rectangle is not a circle. A real spatial index organizes geometry to prune regions; a distance predicate then applies the requested radius.

Meter-based PostGIS example

For example, ST_DWithin(place.geography, query.geography, 50) uses a meter distance for geography in PostGIS and can use index bounding-box checks. PostGIS distance predicate. Handle antimeridian crossings, poles, and the chosen coordinate system. The local twenty-meter example teaches geometry; production globe calculations use geographic distance, not raw degree subtraction.

Indexes and authoritative visibility

Create a spatial index on the geography column and an ordinary index for appropriate filters. The caller's request reaches one service, which validates units, runs a radius predicate, filters category/open status, computes exact distances and sorts with a stable ID tie-breaker. It hydrates place details and returns at most twenty. A place update and its source record commit in the same database before acknowledgment.

Boundary correctness before partitioning

This baseline already handles the boundary café because the spatial predicate covers the query region, not one guessed cell. Use the database's explain plan and measured candidate counts to demonstrate index use. A geospatial library or database avoids inventing raw latitude/longitude math during the interview.

Batched reviews and bounded pagination

Reviews and media are separate reads, batched after candidate selection. A full scan of every review to compute an average per result would undermine an otherwise efficient spatial query, so maintain an aggregate under a stated freshness policy. For a small regional product, this baseline plus read replicas may be a strong final choice; custom distributed trees require evidence that they improve the actual workload.

08Find the baseline flaws

The spatial-database baseline already covers cell boundaries and applies the requested distance predicate. The first two counterexamples test tempting custom-index shortcuts; the third identifies the capacity pressure that could justify distributing the correct baseline.

09Improve the design, step by step

Distributing the spatial index requires choosing what each server owns. Region ownership keeps nearby candidates together, so a local query can contact a few owners; place-ID ownership spreads records independently of location, so a local query may need every index partition. Replicas add read capacity without making that partitioning decision.

Hash-by-ID partitions may build different valid quadtrees. Each can return its top k eligible places under a comparable score; merge globally, then hydrate. Ratings/quality can be updated in batches if the product permits hour-scale lag. Location changes need their own tighter promise. Rebuild lost trees from snapshots plus versioned changes; preserve the authoritative store’s reverse mapping of index shard to places or an equivalent durable manifest.

1. Change 1 — cache place details and replicate spatial reads. Trigger: repeated popular-area queries saturate reads. Replicas and bounded detail caches distribute work without changing ownership. Benefits depend on cache hit rate and query CPU; costs are memory, replicated updates and stale versions. Freshness-aware routing and final detail checks contain stale output. A single spatial database remains preferable at modest scale.

2. Change 2 — partition by region/cell with a routing manifest. Trigger: one index exceeds measured storage/rebuild limits. A query covers every intersecting region and merges candidates. Local queries touch fewer owners; cross-boundary fanout and hot cities are the new costs. Dense cells can split or gain replicas, but split/merge uses a published generation so no area disappears during migration. Hash-by-ID index partitions are an alternative when write balance matters more than read fanout.

3. Change 3 — versioned asynchronous indexing. Trigger: independent place authority and search storage need recoverable updates. Commit source changes, apply monotonically by version, and rebuild from snapshots plus replay. The benefit is decoupled write durability and search capacity. The cost is bounded search delay; hydration can remove stale candidates but cannot invent a new-cell candidate absent from the index. Strict read-your-write queries therefore need a caught-up owner or explicit update overlay.

4. Change 4 — separate moving presence. Trigger: friends update far more often than places and have different privacy. Keep fresh points by identity, update spatial membership on crossings, and expire old presence. The index changes less often, but each result still needs a fresh position and a current permission check. Do not merge this private store into a public place cache merely because both contain coordinates.

10Detailed architecture

Place authority and derived spatial indexes

The write path begins at an authenticated place API and durable place store with a change log. Index workers update regional spatial primaries and replicas, preserving versions and routing generations. Reviews update their own authority and aggregate pipeline. Object media is delivered separately from the spatial response.

Coverage, exact filtering and pagination

The query API validates the location and radius, then uses the region/cell manifest to find every region the search must cover. It queries healthy replicas of those regions and combines their candidates. Exact geographic distance and filters reduce that set. Hydration fetches current place details, rating aggregates and, for friend results, current sharing policy and fresh presence. The final result order uses comparable distances or a clearly defined rating/distance combination.

Separate private friend-location path

The friend branch is intentionally separate in the diagram. A cell lookup may identify a person, but only the sharing/presence authority can authorize returning their fresh location. If that authority cannot confirm eligibility, omit the private result or fail the private query. Public place browsing need not fail because the presence service is down.

Index replicas and recovery

Replicas improve read capacity; snapshots and source events restore a lost index generation. The manifest is the authority for routing, not a substitute for replicating the underlying data. During a region split, the coordinator must use one coherent generation or query overlapping old/new coverage and deduplicate until cutover is complete.

Versioned friend-cell membership

For the friend extension, the presence service must send versioned cell-membership changes to a separate index of private locations, or the query can first read the viewer’s bounded sharing set and fetch those current points directly. The latter is a useful simpler baseline when users share with few contacts and avoids a high-churn global private index. The diagram’s presence store represents current authority; it cannot by itself discover candidate IDs absent from a public place index. Keep its private projection and current authorization separate even if they use the same spatial library.

11Write path and acknowledgement

Place writes and spatial index updates have separate durability and freshness boundaries. The example moves place P12 from source version 4 to 5 and follows event E55 across old and new cells.

1. An authorized editor sends P12 version 4 → 5 with its new coordinates. The place service validates the change and commits version 5 plus event E55 before returning stored.
2. The index worker resolves the old and new spatial ownership under a routing generation. It writes the new-cell version-5 entry and records progress; the old-cell entry is removed or tombstoned with version 5. If the two owners differ, this is a recoverable multi-step update, not an assumed cross-shard transaction.
3. During overlap, both entries may exist. Query merging deduplicates P12 and detects the version mismatch during hydration. It must not substitute version-5 coordinates into a nearest-k traversal whose region bounds describe version 4; restart against a compatible generation, include a complete recent-move overlay, or mark the bounded response incomplete.
4. During a missing-new-entry interval, a query of only the new cell may omit P12. The five-second search-freshness target bounds this delay; a strict update-following query waits for an index watermark or includes a versioned recent-update overlay. Filtering alone cannot discover eligible places that the index failed to return.
5. The worker checkpoints only after required index effects are recoverable. A crash replays E55; version guards prevent an old E54 from moving P12 back.
6. Detail-cache invalidation carries the source version. A delayed version-4 refill must not overwrite a version-5 cache record. Review aggregates update independently and retain their own as-of watermark.

For presence u9 sequence 18, reject sequence 17, update the fresh point, and publish membership changes. Expiry removes the user from query eligibility even if spatial cleanup lags.

12Read and delivery path

A radius query must cover all intersecting regions before exact distance and eligibility determine its result. Query q31 below requests cafés within 50 meters with a bounded result count.

1. The caller’s q31 validates coordinates, radius, filters, and requested count.
2. The spatial router identifies every cell/node whose bounds intersect the search region, including P12’s neighboring cell.
3. Candidate lookup returns P12/P13; exact distance rejects any point outside fifty meters.
4. Ranking sorts eligible cafés; batch hydration supplies names, review aggregates, and thumbnails.
5. The response includes a stable cursor/order context.

Place writes commit to the authoritative store, then versioned changes update the index; deletion and movement cannot rely solely on stale query caches.

The coordinator does not assume neighboring tree nodes are adjacent in memory or linked-list order. It uses geometric bounds or a validated hierarchical-cell covering algorithm. Every candidate carries source version and coordinates; hydration verifies detail and geometry versions before final distance. If geometry changed, use the compatible-generation/complete-overlay rule from the nearest-k proof; do not apply fresh coordinates under obsolete region bounds. For rating order, gather enough eligible candidates to apply the agreed global score; a nearest-only prefilter can miss a farther but higher-rated result inside the permitted radius.

Each shard receives a deadline and bounded candidate budget. If a shard covering part of the 50-meter circle fails, return an explicit incomplete response or fail an exhaustive query. “We found twenty elsewhere” is not proof those are nearest. Pagination retains the query point, radius and stable order context; moving the query device creates a new query rather than secretly reusing the old cursor.

Friend results include age and are checked against expiry at serve time. Authorization after candidate selection protects privacy, but heavy filtering may require additional bounded candidate retrieval to fill k. Avoid revealing denied candidate IDs or exact counts in the response.

For each friend candidate, obtain the authorized presence sequence, coordinates, expiry and policy revision together. Use that exact point for distance and output. If hydration returns another sequence or policy revision, reauthorize that version or omit it within the deadline. A decision about an older shared point cannot expose a newly private location. New authorization reads after acknowledged revocation must deny access; an already authorized response follows the explicitly agreed in-flight boundary. This prevents disclosure from stale candidates without claiming that a lagging spatial index finds every newly moved friend.

13Correctness deep dive

Cells and adaptive quadtrees

Fixed cells group points by a predictable grid ID. An index cell → places narrows lookup, but dense downtown cells contain far more points than ocean cells. A quadtree recursively splits a dense rectangle into four children; leaves hold the points. Search descends through intersecting bounds, not only the leaf containing the caller.

Finding k is not a stopping proof

Finding k points in the query leaf does not prove they are the nearest k. Continue until bounds show no unvisited region can beat the current kth distance. A linked list of leaves is traversal order, not geometric adjacency; parent pointers help explore siblings/ancestors. Hierarchical cell systems such as H3 provide another indexing family, but still require correctly chosen query coverage. H3 introduction.

Visit the nearest possible region first

Use a priority queue ordered by each unvisited node's minimum possible distance to the caller. Maintain the best k eligible points found so far, with worst equal to the current kth distance. Bounds must be valid lower bounds under the same coordinate/distance model as exact checks.

The traversal uses two priority structures with opposite jobs. The node queue exposes the region with the smallest possible distance next. The bounded max-heap keeps the best k eligible points found so far and exposes the farthest of them, making the current cutoff cheap to update when a closer point is found.

queue = [root nodes covering allowed radius]
best = empty bounded max-heap of k eligible points
while queue not empty:
  node = pop smallest lowerBoundDistance
  if best has k and node.lowerBound > best.worstDistance: break
  if node.lowerBound > requestedRadius: break
  if internal: enqueue children with valid bounds
  else: for each point:
      verify eligibility; compute exact distance
      if within radius: update best with stable ID tie-breaker

Worked k=2 traversal

Why the stopping bound is sound

The proof is simple: after stopping, every unseen point is at least its node's lower bound, which is worse than the current kth result. Without that bound, finding k points proves only a count, not nearestness. Current eligibility must be considered before a point occupies the best-k heap. A private or closed café cannot block exploration of a valid farther one. On a globe, use an established geometry implementation for conservative bounds; the local Euclidean formulas in this worked example are not a universal spherical algorithm.

Fresh coordinates must match the geometry

14Failure and recovery

15Operations, security, and cost

Coverage, density and freshness signals

Monitor candidate-to-result ratio, cells/shards touched, exact-distance CPU, p99 by city/radius, index-update lag, current-version rejection rate and rebuild duration. A query that scans 50,000 candidates to return five is a different capacity problem from one returning twenty from forty. Track missing-boundary regressions with synthetic places placed deliberately on cell edges, corners and antimeridian cases.

Location privacy and abuse controls

Security checks include location-sharing ownership, review abuse, bounded query rates and protection against enumerating private presence. Store only required location history and avoid raw coordinates in broad analytics logs. A public place may be cached broadly; private location responses require audience-aware handling and short-lived authorization semantics.

CPU cost per query

At 100K searches/s, saving one millisecond CPU/query saves 100 CPU-seconds/s. That may justify a better index resolution or candidate filter more than adding another detail cache. Smaller cells reduce candidate density but increase cell coverage lookups and routing metadata; benchmark the actual distribution. Review/photo storage and bandwidth should have independent quotas so a media burst cannot evict the spatial index.

Exact-result shadow comparison and rollout

Roll out a new index generation in shadow mode, compare exact radius/nearest-k results against a trusted spatial database on sampled queries, and inspect every mismatch. Then canary routing with a rollback path. Test point movement during a split, delayed tombstones, coincident points, stale friend expiry and a failed neighboring shard.

16Decision ledger and limitations

The friends extension changes more than write frequency. It adds explicit consent, presence expiry, age display and per-viewer authorization. The same geometric index family can help both, but the data and access contracts should remain separate. A good interview answer makes these distinctions before adding caches and servers.

17Interview closing

“I begin with a spatial database and a radius predicate in meters. An eligible nearby place can lie across a cell boundary, so the query covers every intersecting region and then checks exact distance. When scaling, I replicate reads and partition with a routing generation; place changes flow from durable source records into a versioned index. For nearest-k I stop only when every unvisited region's lower bound is worse than the current kth eligible result. Finding twenty candidates in one cell is not enough.

“The tradeoffs are spatial locality versus hot-city skew, smaller cells versus more lookups, and asynchronous indexing versus move freshness. Current-record checks can reject stale candidates but cannot recover a missing new-cell candidate, so strict update-following reads need a caught-up index or overlay. Nearby friends add expiring fresh points and current sharing checks. I would next measure candidates examined per returned place and compare boundary-query results against a trusted spatial implementation under dense-city load.”

If the interviewer asks for travel-time proximity rather than straight-line distance, use spatial distance only for coarse candidate retrieval, then route/ETA ranking under a separate budget. If they ask for every result across the globe, the bounded interactive contract must change to pagination/export and a different capacity plan.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.