Design nearby places and friends (Yelp)

01Functional requirements

Nearby search answers a geometric question: which places are inside a circle around the requested centre? Public cafés change slowly; a friend’s reported position can change every few seconds and is private. We start with public places, then add the friend extension.

1. FR1: Radius search. Find public places within a validated, bounded radius of the query centre. A spatial index supplies possible matches, called candidates. Membership in a candidate cell is only a shortcut; exact geographic distance decides whether the place qualifies.

2. FR2: Category filtering. Filter qualifying places by a supported category, such as cafés, rather than treating every nearby object as a match.

3. FR3: Distance-ordered pages. Return qualifying places in distance order with a stable ID tie-break and a cursor bound to the centre, radius, filters, and traversal context.

4. FR4: Place details. Return the current display details for a selected public place.

5. FR5: Owner-managed places. Let authenticated place owners create or update their records, with abuse controls and version checks for concurrent edits.

6. FR6: Friend location reports. In the consenting-friend extension, accept a user’s latest location report with a verified session, a sequence number that increases within that session, and the time the position was observed. Reject reports that arrive out of order or are too old.

7. FR7: Private friend discovery. Show nearby friends only to viewers permitted by the current sharing rule. A user can disable or change sharing; every friend query uses private candidate discovery and current consent checks rather than a shared public-place response.

Out of scope

• Ratings and general free-text relevance ranking.
• Proof of a person’s physical presence. A recent coordinate report is evidence of what a client reported, not proof that the person is there.
• Recalling information already displayed on another device after sharing is revoked.

Example. Mina requests cafés within 1,000 metres. A is 600 metres away across a cell border, B is 1,200 metres away in a candidate cell, and C is 800 metres away. The distance-ordered result is A, then C; B must be excluded.

02Nonfunctional requirements

These are independently chosen exercise assumptions to validate, not measured production guarantees.

1. NFR1: Place-query latency. At least 95% of measured place queries must finish within 200 ms at the assumed peak of about 2,310 searches/second. Measure receipt to completed response, including finding candidates, reading current records and applying exact distance.

2. NFR2: Place-index freshness. An ordinary accepted place edit must become searchable within one minute. Measure from saving the edit in the main place database to the search index including that version.

3. NFR3: Friend-report freshness. Return no friend report older than 30 seconds under the documented policy for observation time, server acceptance time and tolerated clock error. Enforce age on every read, even if cleanup has not run. Uploading an old observation now must not make it fresh.

4. NFR4: Exact place geometry. For a fixed searchable place-index version, exact mode must cover every intersecting region and exclude points beyond the radius. An arbitrary candidate cap that can miss a nearer qualifying place requires an explicitly approximate response contract.

5. NFR5: Moving-index completeness boundary. Cell-list updates run after the latest position is saved. A query can temporarily miss a moved friend before the new cell lists that user. Measure and disclose that delay. Checking current positions removes old candidates but cannot discover an ID missing from the searched list.

6. NFR6: Current sharing correctness. Return zero friends whose current sharing rule denies the viewer. Missing permission evidence suppresses the friend, and precise private locations must not be placed in a reusable public-place cache.

7. NFR7: Location-data protection. Restrict access to raw reports, retain them only for a declared short-lived product purpose, reduce displayed precision when permitted, and rate-limit repeated location queries. Define the actual retention duration before launch; the 30-second display cutoff is not itself a deletion policy.

03Back-of-the-envelope Estimates

Public places and moving friends have very different update rates. Estimate them separately before giving both the same storage path.

1. Place searches. With 20 million searches/day, average rate is 20,000,000 ÷86,400 ≈231/second. An assumed tenfold peak is 2,310/second. Checking every one of ten million places per request would repeat ten million distance calculations, so use a spatial index to eliminate distant regions first.
2. Search responses. Twenty places at 500 bytes each make 10 KB/search. 20 million ×10 KB =200 GB/day before images and protocol overhead. Serve place photos through object storage/CDN rather than returning image bytes from the query database.
3. Place records. Ten million places at 1 KB each require 10 GB raw, before indexes and copies. A frequently used 100,000-record subset is 100 MB raw. A spatial database can be a sensible starting point; the record count alone does not justify a custom global grid.
4. Friend reports. One million active users reporting every ten seconds send 1,000,000 ÷10 =100,000 updates/second. At 100 bytes each, ingress is 10 MB/second. This path needs much more update capacity than occasional place edits.
5. Retention choice. Keeping every report produces 10 MB/second ×86,400 =864 GB/day. Keeping one latest 100-byte record per million users is about 100 MB raw, plus expiry and index state. Retain history only for a defined product purpose rather than treating it as free.
6. Busy regions. A single cell containing 100,000 places can still make queries expensive. Measure how many candidates the handler examines for each returned place, by region and radius, before choosing cell sizes or an approximation policy.

04API Design and Retry Contracts

Mina’s browser asks the place-query handler for cafés inside a circle. The example response names A and C, the same places used in the metre sketch; B is excluded because it lies outside the radius.

GET /places?lat=40.70&lon=-74.00&radiusM=1000&category=cafe&limit=20

{"radiusM":1000,"places":[{"placeId":"A","distanceM":600},{"placeId":"C","distanceM":800}],"nextCursor":null}

1. Validate a place search. GET /places takes a centre, radius, category, limit and optional cursor. Check coordinate ranges, cap radius and result count, and return 400 for invalid input. The response includes IDs, display fields, calculated distances and the next cursor.
2. Continue the same query. Bind the cursor to the centre, radius, category and ordering context. A distance from one centre is not the same sort key for a different centre, so a caller cannot reuse a cursor after changing those inputs.
3. Read or edit a place. GET /places/{id} returns current details. POST /places creates an owner-managed record; PATCH /places/{id} requires that owner and the expected record version. Reject a stale version rather than overwrite another edit.
4. Report a friend’s position. Authenticated POST /locations takes the active session ID, increasing report sequence, observation time and coordinates. Return server acceptance time. Session and sequence checks stop an old upload from replacing the user’s newer position.
5. Find friends or change sharing. GET /friends/nearby uses the logged-in viewer, not a viewer ID supplied by the caller. PATCH /sharing changes the user’s enabled state or audience with an expected version. Every friend response checks those current rules; a stale cell entry does not grant access.

05Data Model and Access Paths

The place database stores public records. For friends, keep the latest report and sharing decision separate from the search index: one record says where the user last reported being, and another says who may see it.

• Place-query code reads spatial-index candidates, then obtains the records needed for category, distance and display checks.
• Location-ingest code compares an arriving report with the current session and sequence in the user’s latest-location record. A sequence is an increasing number within that session. If 12 is already stored, delayed 11 cannot replace it.
• Membership work records the old and new cells with the accepted report version. A background program updates those cell-to-user lists; they are search shortcuts, not the main position record.
• Friend-query code checks current sharing, report age and latest coordinates before returning a candidate. It uses server acceptance and validated observation time under the documented clock-tolerance policy. Uploading an old observation now must not make it fresh.
• Cleanup code removes obsolete reports and memberships according to retention. The response still enforces the 30-second display cutoff if cleanup is late.

06Baseline: Cover the circle, then filter exactly

Start with public cafés in one database that supports indexed geographic distance queries. A spatial index groups points into regions so the database can skip most distant records.

1. Mina’s browser sends the centre, category café and radius 1,000 metres to the place-query handler.
2. The handler validates them and asks the database for points within that geographic distance. The index first finds regions intersecting the circle. Those regions supply possible matches, called candidates.
3. The database or query handler calculates exact geographic distance for those candidates and applies the category filter. A is 600 metres away across a cell border, so it must be considered. B belongs to a searched region but is 1,200 metres away, so it is rejected.
4. The handler sorts qualifying records by (distance,placeId) and returns A at 600 metres, then C at 800 metres. The stable ID breaks equal-distance ties.
5. The next-page cursor keeps the same centre, filters and traversal view. The handler cannot silently switch query geometry midway through the result.

The broad index check and exact distance check solve different problems. Reading only the centre cell can miss A; returning every member of a searched cell can wrongly include B. Use geographic types and tested distance operators. A degree of longitude changes its metre width with latitude, so flat degree arithmetic is unsafe.

A geohash is a string encoding nested cells; longer prefixes describe smaller areas. Nearby points can sit on opposite prefix borders. The string is useful for indexing, but the handler still needs complete region covering and exact distance.

07Evolution: Handle skew and moving objects

First measure the spatial database and consider a larger machine that can keep more indexes in memory. Add explicit cell routing only when measured query or moving-update work requires it.

Divide public-place retrieval across machines

1. Assign geographic cell ranges to storage machines. For Mina’s circle, the query handler computes every intersecting cell and sends lookup requests to the responsible machines.
2. Each machine returns candidate IDs. The handler combines IDs, removes duplicates and loads the records needed for exact distance and category checks.
3. Keep A and C, reject B and sort by distance/ID as before. For an exact result over a chosen searchable index version, no intersecting region may be silently omitted. Ordinary place edits still follow the agreed one-minute indexing target.
4. Cache reusable public candidate IDs or immutable place versions. A cache hit does not replace exact filtering. Replicate busy public regions when measured load justifies the extra copies.

Small cells remove more irrelevant points but require more cell requests for a large circle. Large cells need fewer lookups but can contain many irrelevant city points. Adaptive subdivisions can help dense cells. If a work cap can miss a nearer place, label the response approximate instead of promising the exact nearest twenty.

Add the moving-friend path

1. Location-ingest code accepts Jo’s new report only if its session is current and its sequence is newer than the saved one. It saves the latest position and required old-cell/new-cell work.
2. A background program removes Jo from the old cell and adds Jo to the new cell. It can retry those versioned operations after a crash. Until they finish, Jo can appear twice or be absent from the new cell.
3. The friend-query handler bypasses the public-place cache. It covers every intersecting private-index region and removes repeated user IDs.
4. For each candidate, it reads the latest report and current sharing rule, checks age and exact distance, then returns only permitted friends. An old membership can be rejected safely; a missing new-cell ID cannot be discovered by checking only the IDs already found.

This friend index therefore has an explicit temporary-omission limit. A stronger complete live view would require a different coordinated update/query contract, not merely another read-time check.

08Failure and Recovery Scenarios

Use Jo’s move from cell W to E to distinguish the checks:

1. A report arrives out of order. The main latest-location record already has sequence 12. Ingest code compares the session and sequence and rejects 11; arrival time does not make 11 newer.
2. Old membership remains. W still lists Jo after sequence 12 moved Jo to E. A W query reads the latest coordinates and rejects Jo if the exact distance is now outside its circle.
3. New membership is delayed. E does not yet list Jo. Its query can miss Jo entirely. Checking current records removes stale candidates but cannot find an absent ID; measure this indexing delay.
4. Sharing changes. Jo disables sharing while both memberships remain. Before return, the handler reads the current sharing record and omits Jo. If that check is unavailable, omit the friend rather than reuse old permission.
5. The report becomes old. The handler checks the 30-second age rule on every response. A slow cleanup worker cannot make an expired report eligible, and a late upload cannot refresh an old observation’s age.
6. The circle crosses unusual geography. Test cell borders, the date line and poles. Longitudes near +180 and −180 can be close on Earth; tested covering and distance tools must handle that wrap.

Restrict access to precise reports, keep them only for the declared purpose and reduce displayed precision where allowed. Rate-limit repeated location queries that could reconstruct movement. Revoking sharing governs later responses; it cannot erase information already shown on another device.

09Trade-offs and Validation

Choose an index by the work the handler actually performs.

• Stay with a spatial database when indexed distance and category queries meet the measured budget. It keeps public updates and queries in a simpler system.
• Add a cell service when measured region load or moving-report volume justifies routing, versioned memberships and repair. A global audience alone is not the trigger.
• State exactness separately: exact public results need complete region coverage and a consistent traversal; approximate suggestions may cap work only under a stated approximation contract.
• State private freshness separately: a smooth map animation does not prove the reported coordinates are recent, permitted or fully indexed.

Measure candidates examined per result, index delay, report age, rejected old reports, permission-check failures and query latency by radius and region. Close with the three cafés: include A across the border, exclude B by exact distance and return A/C in order. Then explain which current record excludes Jo after a move, expiry or sharing change.