Design a proximity service

Open a food app and type "restaurants near me". In under a tenth of a second you get twenty places, closest and best first. A proximity service is the system behind that answer: give it a point on the map, and it returns the places around that point worth showing.

"Restaurants near me" looks like the same question as "drivers near me", and it is almost the opposite one. Drivers move all the time and are looked up now and then. Restaurants never move and are looked up all the time. Watch one search go through.

That one flip, rarely changes and is read constantly, decides almost everything. The ride hailing design (Design Uber) keeps everything in memory and throws it away freely. This one works things out ahead of time, keeps answers for minutes, and treats a restaurant changing address as a rare event that is allowed to be slow. Saying this out loud in the first two minutes is most of the interview.

A few words you will see all through the page:

• A cell is one square of a grid laid over the map, like the squares on a city map in an old street atlas. Every place belongs to exactly one cell.
• The index is the lookup table "cell to the places inside it". It is the heart of the design.
• Hydrate means fetching the full details (name, address, hours) for an id you already have. You do it only for the few results you actually show.

Step 1: Understand the problem#

Six questions turn "find places near me" into something you can design. The first one matters most.

What you are building, and what you cut#

Back of the envelope#

Three inputs. Watch the headline: it decides whether this is a sharding problem at all. (New to estimates like this? The back of the envelope chapter walks through the method.)

Step 2: Propose the high level design#

The API#

{ "name": "...", "lat": 12.9352, "lng": 77.6245, "categories": ["restaurant"], "hours": {...} }

Here is the rounding as a worked example. One person stands at 12.93524, 77.62451 and a friend at 12.93548, 77.62467, about thirty metres away. Rounded to three decimals, both become 12.935, 77.625. Same key, one cache entry, one computation for both of them.

The data model#

Two stores, split by how they are read. The index answers "which places", the store answers "what are they".

Two words in that table. S2 is a Google library that cuts the globe into cells at levels 0 to 30, each level splitting a cell into four smaller ones. A geohash turns a point into a short string like tdr1vx, and nearby points usually share the same first letters. Either gives you integer cell ids, which is all this design needs. A bitmap is a row of bits, one per place: 1 if the place is a restaurant, 0 if not. ANDing the "restaurant" row with the "open late" row keeps the places that are both, in a single pass.

(SQL vs NoSQL covers how to choose the place store. For this design, either works.)

The whole system on one whiteboard#

Figure 1 is the same path as the picture at the top, with the update pipeline added.

Walking Figure 1:

1. A search arrives with a point and a radius. Many never get further than the CDN, a network of servers near users that keeps copies of recent answers (the CDN section of push vs pull explains how they fill). The rest reach a search node, which rounds the coordinates first. That is what makes the next steps cacheable.
2. The node works out which cells cover the circle and reads them from its own memory. No network call, because every node holds the whole index.
3. Category filters are bitmap ANDs over the candidates, not a lookup per place.
4. A few hundred candidates go to ranking, which combines real distance, precomputed quality and whether the place is open right now.
5. Only the top twenty are hydrated from the place store. This is the only database read in the request. The answer is also kept in the result cache (the layers of caching are laid out in caching patterns).
6. Separately, place updates trickle in from owners and bulk imports.
7. Every few minutes a builder produces a new index version and ships it to every node, which swaps it in all at once. The autocomplete design uses the same build and swap trick.

The dashed closure feed exists because the batch cycle is too slow for one case. A permanently closed business must disappear now, not in three minutes, so closures go straight to the serving path instead of waiting for a rebuild. Being minutes behind is fine for everything else, which is a choice called eventual consistency (strong vs eventual consistency).

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. The real question is which way you round.

The rule is over cover, then filter. Take every cell the circle touches, gather all their places, then compute the true distance for each one and drop the ones outside the radius. Under covering means missing a place that really was nearby, and users notice that. Over covering means a little extra work, which they do not. True distance on a round planet uses the haversine formula, which takes two latitude and longitude pairs and returns the distance along the surface. You only run it on the candidates, never on the whole world.

Try it. Grey dots are places, orange ones came back from a cell you read, green ones are really inside the circle.

Two things to notice. Shrink the cells and the wasted orange dots drop, but the cell count climbs fast. Grow the radius and everything grows with its square. Now the harder part: one cell size for the whole world.

The cost of the last rung: the cell level is now data. It has to ship with the index, and the search node and the builder have to agree on it.

Filter is not ranking#

The most common mistake in this question is treating distance as the answer. It is a filter. The ranking that follows is where the product lives.

Figure 2 plays the third rung message by message.

That shape, cheap filter into expensive rank into a tiny hydration, is the same one behind a search engine's leaf shards and the ride hailing service's candidate list. Once you see it, most "find me the best few" questions become the same question.

Replicate, do not shard#

At a few gigabytes, the whole world fits on every search node. Replicating means every node keeps a full copy. Sharding means splitting the data so each node holds one slice (the sharding chapter covers it from the start). The reflex is to shard. Here it is the wrong reflex.

Adding identical machines is horizontal scaling, compared with buying a bigger machine in vertical vs horizontal scaling. The cost of the last rung is that every node needs memory for the whole index, and every rebuild ships to every node. Both are fine at this size. Say where the line is, though: once the index stops fitting comfortably on one machine, you shard by cell range, with busy regions split more finely than empty ones (hash, range, or a directory).

Break it#

Push each failure and watch which box goes red first.

The festival case shows that optimisations create their own failures. Rounding locations gave you a high hit ratio by pushing requests onto fewer keys, and pushing requests onto fewer keys is the definition of a hot key: one key so popular that the single machine holding it overloads. The URL shortener meets the same problem in the read path, and the one key that ruins it, and consistent hashing explains why spreading keys evenly does not help.

Trade-offs#

The level bar#

One moment from this round, answered three ways. Pick the one you think is staff level before the labels appear. (What changes at senior and staff explains the gap.)

Then run the question cold, with a 45 minute timer and no notes, and score the run on the five things this question is really testing.

Interview replay#

Checkpoint#