Dev Skills
Location

Nearby places

Design a service that answers "what is near me?" (restaurants, shops, stations), ranked by distance and quality, filtered by category and whether they are open now.

coreGeospatial indexingCachingIndexes and what makes a query slowCDNsSearch indexing basicsPartitioning (sharding)Latency vs throughput

Where’s the slack?

Query: ~200 ms. Place data freshness: hours. Opening hours: minutes.

Two hundred milliseconds to answer, and the underlying data barely changes. That makes this one of the most cacheable problems on the site, and one of the easiest to over-engineer.

The query budget is a normal mobile-app budget: about 200 ms, because the user has tapped a button and is looking at a loading state. Comfortable compared to typeahead, tight compared to a batch job.

The freshness slack is where the design comes from. Restaurants do not move. A place's location, name and category change perhaps once a year. Ratings shift slowly. So almost all the data behind an answer is effectively static, and users could not tell an index rebuilt daily from one rebuilt continuously.

There is one fast-moving field mixed into an otherwise static dataset: whether somewhere is open right now. That changes on a schedule, plus irregular closures. It is tempting to let that one field force the whole system to be dynamic. Resisting that is the main design skill this problem teaches. Compute openness at read time from static opening hours, and keep the index static.

The other dynamic case is live availability: a table free tonight, a bike at a dock. If that is in scope it is a separate fast path, not a reason to make the place index live.

So: Static data plus a hard query budget means aggressively precomputed and cached geographic tiles. The one dynamic field is computed at read time from static data rather than being allowed to invalidate everything.

Work it through

Five stages, gated. You write your answer for each stage before its model answer unlocks. That is the core of the method.

Loading your progress…

Reference material for this problem. The diagrams below are here to check your own against once you have drawn it, not to read first.

The lifecycle

Submittedprovider or ownerValidatedsystemIndexedbatch buildServedsearcherUpdatedownerDuplicate from two providersfuzzy match on name and proximity, merge with an unmerge pathCoordinates put a shop in the seaplausibility check against the addressBuild fails silentlyatomic swap keeps the old index; alert on index ageNothing within the radiuswiden progressively, then say nothing is nearbyThousands of candidates downtownadaptive cell precision plus precomputed top-NPlace permanently closedfast overlay path; do not wait for the daily build
A place, from ingestion to being served. Deduplication and the permanently-closed branch are the two that users notice most.

The numbers

Place updates~10 / sec globally
Queries~50,000 / sec
Candidates — city centre, 2 km~5,000 places
Candidates — rural, 2 km~3 places

So the hard part is density, not volume. The same query costs a thousand times more downtown than in a village. That is why cell precision has to adapt, and why fixed-radius designs fail at one end or the other.

Ten writes a second, fifty thousand reads. And a candidate set that varies a thousandfold with density.

The architecture

atomic swapmissProvidersOwner editsBuild pipelinededupe, validate, cellGeo indexby cell, top-NCorrection overlayclosuresUserResult cacherounded locationSearch svcrank + open now
A daily batch build produces a static index. The one apparently-dynamic field, open now, is computed at read time so the index never has to change.

The mechanism

Writeshash(key)Shard Aa–hShard Bi–pShard Cq–z
the key decides the shard — same key, same box, every time
Places are assigned to cells by their coordinates. A query reads its own cell plus the eight neighbours, because a place 50 metres away can easily be over a boundary.

The decision this turns on

A
Geohash cells (fixed grid)
  • —Simple: a string prefix, so an ordinary B-tree index answers proximity.
  • —Nearby things usually share a prefix, so each cell lookup is a range scan.
  • —Boundaries are arbitrary, so you must always query the eight neighbours.
  • —One fixed cell size is wrong somewhere: too big downtown, too small in the countryside.
B
Quadtree (adaptive)
  • —Cells subdivide where density is high, so candidate counts stay even.
  • —Handles the city-versus-countryside problem natively.
  • —A tree to build and maintain, rather than a string you compute.
  • —More work when points move, which places rarely do.
Which one: For places, geohash with adaptive precision gets you most of the quadtree's benefit for much less machinery, and the near-zero write rate means rebuilding the grid is cheap. Choose the quadtree when density varies extremely and you need the structure to handle it for you. For moving objects, use neither: keep positions in memory keyed by cell and update them continuously.
How you make the geographic lookup indexable.

Follow-ups you should expect

Many interviews are decided in the follow-ups, not the first diagram.

One key gets 90% of the traffic. What breaks, and what do you do?The cache just died. What happens?Why this database and not Postgres?One user reports a slow request. How do you debug it?Now make it multi-region.10x traffic tomorrow. What fails first?What does this cost per month?Replica lag is 30 seconds and a user reads their own write. What do they see?

Same shape, other products

Two dimensions pretending to be one, plus a very high write rate from things that move.

Writes hugely outnumber reads, positions are stale the moment they land, and the index gives you candidates rather than an answer.

Others with this shape: Nearby places · Delivery zones · Live location ingestion

Before you leave
Try this problem again in a week without reading anything. Comparing what you write then with what you wrote today shows you what stuck.
Stuck, or new to this?Read the full worked solutionAll five stages end to end, with the diagrams and the costs, written out the way you would say it. Best read after you have had a go.Read it →

How it is really built

Write your own answer first. Then read how teams who run this at scale describe it. Their constraints were real, and the write-ups often say what their choices cost.