Design nearby places search (NALSD)

01The design, in the six-step framework

1. Requirements

Functional

• Given a location and a radius, return the nearest places, optionally filtered by category.
• Places are added and updated by a separate pipeline a few thousand times a minute.
• Out of scope: ranking by reviews, opening hours logic, routing to the place.

Non-functional (given by the interviewer, NALSD style)

• 300 million places; 10 billion queries a day.
• Serve a query in 8 ms at the server.
• Hardware: machines with 128 GB RAM, either 8 × 1 TB HDD or 8 × 250 GB SSD, and a 1 Gbps network link.
• Availability 99.99 percent; place updates visible within a minute.

2. Core entities

• Place: place_id, latitude, longitude, category, name, version.
• Cell: a geospatial cell id (geohash prefix or S2 cell) → list of place ids in it.
• Index snapshot: version, build time, serialized cells, loaded by every server.
• Update: place change event with version, applied to the live index.

3. API

• GET /nearby?lat=…&lon=…&radius_m=…&category=…&limit=20: places sorted by distance. Called by the app servers.
• POST /places and PUT /places/{id}: create or update; called by the ingestion pipeline.
• GET /health: index version and freshness, for the load balancer.

4. High-level design

One query:

1. The app server calls nearby with a point and a 2 km radius; the load balancer picks any search server, since every server holds the whole index.
2. The server computes the geospatial cells that cover the circle: at a cell size of about 1 km that is the centre cell and its 8 neighbours.
3. It reads the place lists for those 9 cells from the in-memory map, computes the exact distance for each candidate (a few hundred), filters by category and radius, sorts, and returns the top 20.
4. Meanwhile, place updates arrive on the update stream and are applied to every server's in-memory index within seconds; the hourly snapshot exists so a restarting server loads 30 GB from object storage instead of replaying history.

5. Deep dives

Why does every server hold the whole index instead of sharding it?

With 30 GB of data and 128 GB machines, full replication wins: no hot shard, no scatter, and adding a server adds capacity linearly. Sharding becomes necessary only if the data outgrows RAM, say at 3 billion places with richer records, and then the shard key is the cell prefix with hot cells split further.

Which cell size, and what about a query at a cell boundary?

Too large a cell means thousands of candidates to sort; too small means many cells to visit for a large radius. With 300 M places over roughly 150 M km² of land, an average cell of 1 km² holds 2 places, but cities hold thousands; store two levels (1 km and 100 m cells) and pick the level whose cells cover the radius with the fewest candidates. Boundary effects are handled by always including neighbouring cells; the exact distance check afterwards removes anything outside the radius. If the first ring returns fewer than the limit, expand to the next ring, which is what makes a search in the desert still return something.

How does the 8 ms budget break down, and what would break it?

Network in, about 0.5 ms; cell lookups, under 0.1 ms; distance computation for 500 candidates, about 0.1 ms; sort, under 0.1 ms; serialization and network out, about 1 ms. Total around 2 ms, leaving room for p99 jitter. What breaks it: a disk read (10 ms on HDD), a garbage-collection pause (use a language or layout without one on the hot path), a lock held during an index update (use copy-on-write per cell), or a query with a 50 km radius in a dense city (cap the candidate count and return the nearest cells first).

The follow-up: what if the index must be consistent across continents, and is Paxos involved?

Serving replicas do not need consensus: they apply an ordered update stream and may lag by seconds, which the one-minute freshness requirement allows. Consensus belongs in the source of truth, the places database, where two ingestion pipelines might update the same place; a replicated log with a single leader per shard gives one order. Running that log across continents costs a cross-ocean round trip (about 150 ms) per committed write, which is fine for a few thousand updates a minute but would be wrong on the query path, which is why the design keeps queries entirely local and asynchronous updates one-way.

How are updates applied without ever locking the query path?

An update changes one place's cell membership: remove the id from the old cell's list, add it to the new one. If the lists are mutated in place, a query reading the list during the change sees a torn view or waits on a lock. Each cell's list is instead replaced by a new immutable copy (copy on write) and the pointer is swapped atomically; queries that began before the swap keep the old copy, and nothing ever blocks. Updates are rare enough, a few thousand a minute, that copying a list of a few hundred ids is negligible. Every server applies the same stream in the same order, and the stream position is stored with the snapshot so a restart resumes exactly where its snapshot ends.

6. What a strong answer sounds like

• Do the capacity arithmetic first and say what it implies: data fits in RAM, network sets the fleet size, HDD is unusable on the query path.
• Explain cell-based lookup with neighbour expansion and the exact distance filter.
• Argue full replication over sharding from the numbers, and name when sharding would become necessary.
• Expect follow-ups on update propagation, on a hot city, and on where consensus belongs; the interviewer in the reported loop asked about Paxos latency across continents.
• A common mistake is to reach for a database with a geospatial extension; it cannot meet 8 ms at 350,000 QPS, and the point of the exercise is to show you know why.

02Where this question was reported

• interviewkickstart.com · Listed
• interviewkickstart.com · Listed
• PracHub · 'Personalized Weekly Deals Service', Senior+
• PracHub · PM: Google app alerting shoppers to nearby deals
• Blind · 300M places, 10B queries/day, return nearby places in 8 ms; given machine specs (128 GB RAM, 8x1 TB HDD or 8x250 GB SSD, 1 Gbps); follow-up on Paxos latency acr
• desiqna.in · Geospatial search feature, e.g. find nearby restaurants; candidate had not studied geo indexes
• LeetCode Discuss · Rejected; candidate had prepared many designs but missed problems involving geospatial searches (search snippet)
• 1point3acres · Design a local business search service; advised to confirm details with interviewer (search snippet, Chinese)
• interviewkickstart.com · Listed (twice).