Design a nearby points-of-interest service

Source: https://www.hack2hire.com/question-bank/questions/system-design/69f9729772a3d3fe39f8d21b
Company: OpenAI
Difficulty: Hard

Problem statement

Given a user's location, return the closest restaurants, shops and other places of interest within a radius, fast, for a read-heavy global audience.

Requirements

We are building a read-heavy geo search service: given a latitude, longitude and radius, return the nearest places (restaurants, shops, landmarks) ranked by distance, optionally filtered by category or keyword, for users worldwide. Business owners and ops tools add and edit places; that write path is small and may lag by minutes.

Clarifying questions worth asking first: Is the radius bounded (say 0.5–50 km)? Do results rank by distance only, or by a blend of distance, rating and open-now? How fresh must an edit be in search (seconds or minutes)? Is it a moving-user feed (like ride-hailing drivers) or static places? Here places are static; that one answer rules out a write-heavy in-memory location index.

Functional requirements

• Search nearby: (lat, lng, radius, category?, keyword?, limit) → up to N places sorted by distance, paginated.
• Get place details by id (name, address, hours, photos, rating).
• Create, update and soft-delete a place (owner or ops); changes appear in search within ~1 minute.
• Category filtering (e.g. restaurant, cafe, pharmacy) and simple keyword match on name.

Non-functional requirements

• Search p99 under 100 ms server side, including in dense cities.
• 99.99% availability for reads; writes can degrade to queued without hurting reads.
• Eventual consistency for search (≤ 60 s); details reads after an owner's own write are read-your-writes.
• Global: serve from the nearest region; the data set is small enough to replicate everywhere.
• Correct at cell edges, poles and the antimeridian (no missing places just across a boundary).

Back-of-the-envelope estimation

• 200M places worldwide. Record ≈ 1 KB of details → 200 GB in the primary store.
• Index entry: id (8 B) + lat/lng (16 B) + cell id (8 B) + category bitmask (8 B) ≈ 40 B → 200M × 40 B ≈ 8 GB. The whole geo index fits in RAM on one machine; we shard and replicate for throughput and availability, not size.
• 100M DAU × 5 searches/day = 500M/day ≈ 6K QPS average, ~30K QPS peak. Details reads ~2× searches, mostly cacheable.
• Writes: ~1M edits/day ≈ 12/s. Read:write ≈ 1000:1.
• Density: Manhattan has ~5K places per km²; a 1 km radius there is ~15K candidates, so filtering and top-K must not scan rows one by one from disk.

API design

GET /v1/places/nearby?lat=37.7749&lng=-122.4194&radius_m=1500&category=restaurant&q=ramen&limit=20&cursor=...
200 {
  "places": [{"id": "p_81f2", "name": "Ramen Nagi", "lat": 37.7751, "lng": -122.4189,
              "distance_m": 52, "category": "restaurant", "rating": 4.6}],
  "next_cursor": "eyJkIjo1MiwiaWQiOiJwXzgxZjIifQ"   // last (distance, id) seen
}

GET /v1/places/{id}
200 { "id": "p_81f2", "name": "...", "address": "...", "hours": {...}, "photos": [...], "version": 17 }

POST /v1/places            { "name", "lat", "lng", "category", "address", "hours" }  → 201 { "id", "version": 1 }
PATCH /v1/places/{id}      If-Match: 17   { "hours": {...} }                      → 200 { "version": 18 } | 412
DELETE /v1/places/{id}     → 204 (soft delete; tombstone propagates to the index)

Supporting surface: GET /v1/categories (static taxonomy, CDN-cached), an internal POST /internal/reindex?cell_prefix=... for ops, and rate limits per API key. Radius is clamped to 50 km; larger requests should use a different product (map tiles or city search).

Data model

Places (source of truth): a relational store (Postgres or MySQL, sharded by place_id) because edits need transactions, optimistic versioning and an outbox.

Outbox: place_events(event_id, place_id, version, op, payload, created_at) written in the same transaction as the place row. A relay publishes to Kafka topic place-changes, partitioned by place_id so events for one place stay ordered.

Geo index (derived, rebuildable): in-memory per shard. Key = S2 cell id at level 12 (~2–3 km²) → sorted array of {place_id, lat, lng, cat_mask, rating}. Dense cells are split into level-14/16 children (see deep dives). Each entry also carries version so late or duplicate events are dropped.

Details cache: Redis / CDN keyed by place:{id}:v{version} with a short TTL on the unversioned alias.

Invariants: the relational row is authoritative; the index holds only what search needs to filter and rank; every index entry can be rebuilt from the table; a place appears in exactly one leaf cell at a time.

High-level design

flowchart LR
  U[Client] --> GW[Edge and API gateway]
  GW --> SS[Search service]
  GW --> PS[Place service]
  SS --> GI[Geo index shards]
  SS --> DC[(Details cache)]
  PS --> DB[(Places DB)]
  PS --> DC
  DB --> OB[Outbox relay]
  OB --> K[Kafka place changes]
  K --> IX[Indexer]
  IX --> GI
  IX --> DC
  DB -. snapshot .-> BK[Bulk rebuild job]
  BK -. "snapshot files" .-> GI

1. Nearby search. The gateway routes to the nearest region. The search service computes the S2 cells covering the query circle (RegionCoverer, max ~8–16 cells), maps cells to index shards, fans out in parallel, and each shard returns its top-K by exact haversine distance after category and keyword filters. The service merges the per-shard lists into a global top-K, fetches display fields from the details cache in one multi-get, and returns them.
2. Create or update. The place service writes the row and an outbox event in one transaction and returns the new version. The relay publishes the event; indexers consume place-changes, recompute the leaf cell, remove the entry from its old cell if it moved, insert it in the new one, and bump the details cache version. End-to-end typically 2–10 s, bounded at 60 s.
3. Details. Read-through from cache to the DB. After an owner's own write the client sends the returned version, and a cache miss on that version goes to the primary.

Why this split works: the hot path never touches the relational DB, the index is cheap to rebuild because it is derived, and the 12 writes/s can be slow and safe without hurting 30K reads/s.

Deep dives

Choosing the spatial index.

Pick S2 with density-adaptive leaves: store at level 12 by default and split a cell into children when it holds more than ~2,000 entries. This gets the quadtree's adaptivity with S2's integer ids, which shard and range-scan cleanly. Geohash is an acceptable answer if the candidate explains the neighbor problem below.

Boundaries and neighbor lookups. A place 10 m away can sit in the next cell, so searching only the user's cell is wrong. With S2, ask the coverer for the set of cells that fully cover the circle (a mix of levels, capped at ~16 cells); with geohash, search the center cell plus its 8 neighbors at a precision whose cell is at least as wide as the radius (precision 6 ≈ 1.2 × 0.6 km for a 1 km search). Then filter candidates by exact haversine distance, since cells are squares and the query is a circle. For "nearest K with no radius", expand in rings: start with a 500 m circle, double until K results are found or 50 km is reached. Longitude wraps at ±180° and cells shrink near the poles; S2 handles both natively, while geohash needs explicit antimeridian splitting.

Sharding, hot cells and recovery. Shard the index by S2 cell range (the Hilbert order keeps neighbors on the same shard, so most queries hit 1–2 shards), with ~64 range shards per region, each replicated 3×. Shards are balanced by request load, not area: Tokyo and New York get small ranges, the Pacific gets one huge one. Hot cells (Times Square at noon) are handled three ways: more replicas for that shard, splitting the cell into finer leaves so each query scans fewer entries, and caching results for popular query tiles (round lat/lng to ~100 m and radius to a bucket, TTL 30 s); this absorbs 60–80% of downtown traffic. Recovery: each shard periodically writes a snapshot of its cells plus the Kafka offset it reflects to object storage. A new or crashed replica loads the snapshot (8 GB total loads in under a minute) and replays Kafka from that offset, then joins the load balancer only after lag is under 5 s.

Propagation, consistency and bulk reindex. Events carry (place_id, version); the indexer applies an event only if its version is higher than the stored one, which makes replays and out-of-order delivery safe. A move is delete-from-old-cell plus insert-into-new, done in one in-memory step per shard; if old and new cells live on different shards, the index briefly shows the place in both or neither for a second, which is acceptable. Deletes are tombstones kept until compaction so a late "update" can't bring a deleted place back. Full rebuilds (new ranking field, new cell levels, corruption) run as a batch job: scan the DB snapshot ordered by s2_cell_l16, write new shard snapshot files, load them into a parallel "blue" index fleet, replay Kafka from the snapshot time, compare result sets on shadow traffic, then flip routing. Backfills of millions of imported places go through the same batch path, not through Kafka, so they don't add minutes of lag to owner edits.

Category and keyword filtering on top of geo. Geo retrieval runs first and returns candidates; filters run in the same shard pass. Categories are a 64-bit mask on each entry, so a filter is one AND per candidate. Name keywords use a small per-cell inverted index (token → posting list of entry offsets) built only for cells above ~500 entries; smaller cells just scan. If a filter is very selective (e.g. "24-hour pharmacy"), the radius ring expansion continues until K matches are found. Full-text relevance with typos and synonyms belongs in a separate search engine (Elasticsearch with geo_distance filters), which is a reasonable alternative if the product shifts from "nearby" to "search".

Trade-offs

• An in-memory custom index is fast and cheap at 8 GB but means owning snapshotting, recovery and rebalancing; Elasticsearch or PostGIS gives that for free at higher latency and cost per query.
• Eventual consistency (seconds to a minute) keeps writes off the read path; a new restaurant can't be found right after creation except through its own details page.
• Result caching on rounded tiles cuts hot-cell load sharply but returns places up to ~30 s stale and slightly off-center results; exact distances are recomputed from the user's real point to hide this.
• Sharding by cell range keeps queries local but needs load-based rebalancing; sharding by place_id balances perfectly but makes every search fan out to every shard.
• Full replication per region spends storage (cheap at this size) to avoid cross-region reads on the hot path.
• Ranking by distance only is simple and cacheable; blending in rating or popularity improves results but makes top-K pruning by cell harder.

Interviewer expectations

Mid-level (L4)

• Gets the read/write ratio and the "index fits in memory" estimate right.
• Uses geohash or a quadtree, explains why a plain lat/lng B-tree index is not enough.
• Remembers to search neighbor cells and filter by exact distance.

Senior (L5)

• Compares geohash, quadtree and S2 with concrete weaknesses (edges, poles, density).
• Separates the authoritative store from a derived index fed by an outbox and a log, with versioned idempotent updates.
• Handles dense areas: adaptive cell sizes, hot-cell caching, ring expansion for selective filters.

Staff (L6+)

• Plans shard placement by load, snapshot plus log replay recovery, and blue/green full reindex with shadow comparison.
• States the consistency window and its product impact, and where read-your-writes is still required.
• Knows when to switch to an off-the-shelf engine, and what the custom index is buying at this scale.