Design a proximity service
"Restaurants near me" looks like the same question as "drivers near me" and it is almost the opposite one. Drivers move constantly and are read occasionally. Restaurants move never and are read constantly.
That single inversion changes every decision. Where the ride hailing design keeps everything in memory and refuses to write to disk, this one precomputes aggressively, caches for hours, and treats a business moving address as a rare event that can afford to be slow. Getting this distinction out loud in the first two minutes is most of the interview.
Step 1: Understand the problem#
| You ask | They say | What it settles |
|---|---|---|
| How often does the underlying data change? | A business changes address a handful of times ever. New ones open daily. | Everything. This is a read heavy index over near static data, so it can be precomputed, replicated everywhere and cached for hours. If you have just designed a ride hailing service, say out loud that this is the mirror image of it. |
| How many places, and how many searches? | A couple of hundred million places, tens of thousands of searches a second. | The index fits on one machine, so every server can hold a full copy and there is no partitioning problem to solve. That is a rare luxury and it should shape the design. |
| What does "near" mean: a radius, or a count? | The twenty best within about five kilometres, whichever binds first. | A variable radius search, which is harder than a fixed one. In a dense market five kilometres returns thousands and you need the best twenty, while in a rural one it returns three and you should widen rather than return three. |
| What makes a result good, besides being close? | Rating, whether it is open now, and relevance to what was typed. | Two stages. Geography is a filter, not a ranking, and the actual ordering is a scoring problem over a small candidate set. |
| Does the result have to be exact at the boundary? | No. Nobody notices a place at 5.1km being included. | Permission to use approximate cells instead of true distance during the filter, which is what makes the filter a set lookup rather than a geometry computation. |
| Is it personalised? | Lightly. Mostly it is the same for everyone in the same place. | Results cache well if you quantise the query location. Two people fifty metres apart should get the same cache entry, and that one decision multiplies your hit ratio. |
What you are building, and what you cut#
- Find places near a point, optionally filtered. By category, open now, rating.
- Rank the candidates. Distance is one signal among several, not the answer.
- Add, update and remove places. Rare, and allowed to take minutes to propagate.
- Serve tens of thousands of searches a second. Mostly from cache, close to the user.
- 200 million places worldwide.
- Under 100ms at p99 for a nearby search.
- A new place is searchable within a few minutes.
- Results may be minutes stale, but must never include a permanently closed business.
- Turn by turn navigation and routing. A graph problem with its own literature.
- Reviews and photos. A content system that this one links to.
- Real time occupancy or wait times. A streaming problem bolted onto the side.
- Indoor positioning. Different sensors, different everything.
Back of the envelope#
That headline is the design. At 12.0GB the geographic index fits comfortably in memory on any server you would rent, so you replicate it everywhere instead of sharding it, and a search never crosses the network to find candidates. The 80GB of full records stays in a normal database and is only read for the twenty results you actually return.
Notice what a larger radius does to the cell count: it grows with the square. At 5km you scan about twenty cells, at 25km about five hundred. A naive implementation that lets a client pass any radius has a request that is a thousand times more expensive than another, on the same endpoint, with the same timeout. Either cap the radius or use coarser cells for wider searches, and say which before someone finds it in production.
Step 2: Propose the high level design#
The API#
{ "name": "...", "lat": 12.9352, "lng": 77.6245, "categories": ["restaurant"], "hours": {...} }The data model#
| cell_id | uint64 | PK | S2 or geohash cell at a fixed level, roughly 1km on a side. The key everything hangs off. |
| place_ids | sorted array | Places in this cell. Sorted by a static quality score so a truncated read still returns the good ones. | |
| category_bits | bitmap per place | A category filter is a bitmap AND rather than a lookup per candidate, which matters when a cell holds a few thousand places. | |
| quality | float | Precomputed from rating and popularity. Static ranking, so the expensive part of scoring is already done. |
| place_id | bigint | PK | |
| name, address, phone | text | The heavy fields. Only read for the twenty results you return, never during the filter. | |
| lat, lng | double | The authoritative position. The cell in the index is derived from this, not the other way round. | |
| hours | json | IDX | Open now is computed at read time in the user timezone. Precomputing it means rebuilding the index every hour for no reason. |
| status | enum | open, temporarily_closed, permanently_closed. Checked at serve time, because a stale index must never resurrect a closed business. |
The whole system on one whiteboard#
Walking Figure 1:
- A search arrives with a point and a radius. The coordinates are quantised before anything else happens, which is what makes the next step cacheable.
- The node computes the covering cells for that circle and reads them from its own memory. No network call, because every node holds the whole index.
- Category filters are bitmap operations over the candidate set rather than a lookup per place.
- A few hundred candidates go to ranking, which combines real distance, precomputed quality, and whether the place is open right now.
- Only the surviving twenty are hydrated from the place store. This is the only database read in the request.
- Separately, place updates trickle in from owners and bulk imports.
- Every few minutes a builder produces a new index version and ships it to every node, which swaps it in atomically.
The dashed closure feed exists because the batch cycle is too slow for one specific case. A permanently closed business must disappear now, not in three minutes, so closures are applied to the serve path directly rather than waiting for a rebuild.
Step 2 reads the cells covering a 5km circle. A user in Manhattan and a user in rural Rajasthan run the same query. Describe what goes wrong for each of them with a single fixed cell size.
Step 3: Design deep dive#
Covering a circle with cells#
Cells are squares and a search is a circle, so every cell scheme is an approximation and the interesting question is which way you round.
The rule is to over cover and then filter. Take every cell that intersects the circle, union their contents, then compute true distance on the candidates and drop the ones outside the radius. Under covering means missing a place that was genuinely nearby, which users notice. Over covering means doing slightly more work, which they do not.
The answer that survives contact with production is usually adaptive levels for the index plus expanding rings for the query, and it is worth saying you would combine them. The density map keeps candidate counts even, and the ring expansion handles the cases the density map got wrong.
Filter is not ranking#
The most common mistake in this question is treating distance as the answer. It is a filter, and the ranking that follows is where the product lives.
The shape of that sequence, cheap filter into expensive rank into tiny hydration, is the same one behind the search engine's leaf shards and the ride hailing service's candidate list. When you recognise it, most retrieval questions become the same question.
"How do you handle 'open now' if hours are in the index?" Do not put them in the index. Opening hours change the answer every hour, so baking them in means rebuilding constantly. Keep hours on the place record, evaluate them at serve time in the user's timezone, and over fetch candidates so that filtering out the closed ones still leaves twenty. Over fetching by a factor of two is far cheaper than an hourly index rebuild.
Replicate, do not shard#
At a few gigabytes, the whole world fits on every search node, and that is worth taking advantage of rather than reflexively partitioning.
Sharding geographically sounds natural and creates problems you then have to solve. Traffic is wildly uneven, so the shard holding Tokyo is a hundred times busier than the one holding the Sahara. Searches near a boundary have to fan out to several shards and merge. Rebalancing means moving cells while queries are running. All of that disappears if every node holds everything: a search is local, any node can serve any request, and scaling out is adding an identical machine.
The cost is that every node needs enough memory for the whole index and every rebuild ships to every node. Both are fine at this size. Say where the threshold is, though: once the index stops fitting comfortably in memory on one machine, you shard by cell range, with the hot regions split more finely than the empty ones.
The most valuable line of code in this system is the one that rounds the coordinates before building the cache key. Full precision means every request is unique and your cache does nothing. Rounding to about a hundred metres means everyone in the same block shares an entry, and a cache hit ratio that was three percent becomes seventy. It is a one line change with a bigger effect than any amount of index cleverness, which is worth saying out loud because it demonstrates you know where the wins are.
Break it#
Read every step as text
- 30k/s · Healthy. Design load with quantised cache keys. Most searches are answered from cache, misses are a memory scan of twenty cells, and the store sees twenty key reads per miss. Everything is comfortable.
- radius 50km · Degraded. Someone sets a wide radius. Cell count grows with the square of the radius, so this single request scans five hundred cells and produces tens of thousands of candidates. One user can now cost a thousand times what another does on the same endpoint.
- festival in one city · Down. Everybody searches from the same few blocks. The quantised cache keys collapse to a handful of entries, which is good, but those entries are on one cache node and it saturates. A hot key problem produced by the very thing that gave you a good hit ratio.
- index rebuild · Degraded. A new index version ships to every node. Memory doubles during the swap and the first queries after it run against cold CPU caches. Stagger it, and never let more than a fraction of the fleet swap at once.
- repaired · Healthy. Cap the radius and use coarser cells above a threshold, so a wide search is cheap and slightly less precise rather than expensive and exact. For the hot city, keep a small local cache in each search node in front of the shared one, which is the same one second trick from the URL shortener.
The festival case is a nice illustration that optimisations create their own failures. Quantising locations gave you a high hit ratio by concentrating requests onto fewer keys, and concentrating requests onto fewer keys is the definition of a hot key.
Trade-offs#
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Replicate the index everywhere | A search is a local memory read, any node serves any request, and scaling out is copying a machine. | Every node needs the whole index in memory, and every rebuild ships to all of them. | While the index fits comfortably on one machine. Past that, shard by cell range and split the hot regions finely. |
| Cells over true geometry | The filter becomes set operations on integers, with no spatial index to maintain. | Approximate at the boundary, and one fixed cell size is wrong somewhere in every country. | Always for the filter stage. Compute true distance afterwards on the few hundred candidates that survive. |
| Quantising the query location | Turns an unbounded key space into a bounded one and takes the cache hit ratio from single digits to most of your traffic. | Results are computed for a nearby point rather than an exact one, and popular blocks become hot keys. | Any location keyed cache. Pick the quantisation so the error is smaller than the user cares about, which is around a hundred metres. |
| Batch index builds with a closure fast path | A simple, testable pipeline for the common case, and immediate propagation for the case that matters. | Two paths into the serving layer, and the fast path needs its own correctness argument. | Whenever one class of update is far more urgent than the rest. Making the whole pipeline fast to serve one case is the expensive mistake. |
Interview replay#
Checkpoint#
1. Why is a fixed cell size wrong in both dense and sparse areas?
2. What does rounding the query coordinates before building the cache key actually achieve?
3. Same design, but the places are now food delivery couriers moving through the city. What changes first?
- 200 million places is a few gigabytes of index, so every node holds all of it and nothing is sharded.
- Cell count grows with the square of the radius: 5km is about 20 cells, 25km is about 500.
- Round the query location to about 100 metres. That one line is your cache hit ratio.
- Filter with cells, rank with ETA, hydrate twenty rows. Cheap, then expensive, then tiny.
A proximity service is the mirror image of a ride hailing index. The data barely changes and is read constantly, so everything is precomputed. Two hundred million places is only a few gigabytes of geographic index, which means every search node holds a full copy and a search never leaves the machine, removing fan out and hot shards entirely. A query rounds its coordinates to about a hundred metres first, which is the single most valuable decision on the page because it turns an unbounded cache key space into a bounded one. Then it reads the cells covering the radius, ANDs a category bitmap, computes true distance on what survives, ranks a few hundred candidates on distance, quality and whether they are open, and hydrates only the top twenty from the place store. Cell size adapts to density so candidate counts stay even, because one fixed size is wrong in Manhattan and wrong in rural Rajasthan for opposite reasons. Index builds run every few minutes, with one exception: a permanently closed business is removed immediately through a fast path, because additions can wait and removals cannot.