Design a Proximity Service: Nearby Restaurants at Scale

A proximity service, the part of an app that finds places near you, gets slow when it measures the distance to every place in the database on every search. That work grows with the number of places times the number of searches.

Picture a common setup. A food app lists restaurants and street-food stalls in Indore, and you pick a distance such as 1 km to see what is close, nearest first. The setup is made up, but the problem is real.

The first version stores 18,000 places in one database table, each with a latitude and a longitude. Those are the two numbers that pin any spot on Earth. Every search loads every row, measures each distance, sorts the list and keeps the top 20.

That is the naive version, and it is fine only for a demo. On our test machine, a plain Python scan of 18,000 places took about 37 milliseconds per search. A scan of 20 lakh places took about 4.5 seconds.

Now add the busy hours. Picture 400 searches a second around Sarafa Bazaar, Indore's night food street, between 9 pm and 11 pm (made up). Each search repeats the full scan, mostly measuring places nobody asked about.

The team also plans 40 more cities with about 20 lakh places, and wants most searches answered in under 200 milliseconds. This guide follows that redesign in the order you would use in a system design interview.

A proximity service is a backend service that takes a location and a distance and returns the places inside that distance, usually nearest first. Restaurant finders, hotel search and pharmacy finders all depend on one.

Interviewers often call this question design Yelp. The hard part is answering a map question quickly for millions of people at once.

Three words come up all the time. The radius is the search distance around the user, like 1 km; the food app offers 500 m, 1 km, 2 km and 5 km.

A spatial index is a lookup structure that groups places by where they are on the map. It lets you skip far-away places without ever reading them.

A system is read-heavy when it serves far more reads than writes. People search the food app all evening, but a stall owner edits a listing perhaps once a month.

A proximity service must return nearby places for a location and radius, show each place's details, and let owners add or edit listings. It must also stay fast and available at the busiest hour.

What the system must do

• Search: given a latitude, longitude and radius, return up to 20 places, nearest first.
• Filter: narrow the results by type, such as street food, cafe or pure veg.
• Details: show a place's name, address, photos, rating and opening hours.
• Owner edits: owners add, update or remove their places. Changes do not need to appear in search instantly.

How well the system must do it

These are non-functional requirements: rules about speed, uptime and safety rather than features. The team agrees on four.

• Low latency, meaning how long one request takes: under 200 milliseconds for most searches.
• High availability: search keeps working when one server or the main database fails.
• Freshness can lag: a new stall may appear in search a few minutes after the owner saves it.
• Privacy: the user's exact location is used for the search and not stored against their name.

Next comes a back-of-the-envelope estimate: quick, rough maths that shows which parts of the system are big. All the inputs are made up, but the arithmetic is real.

Two facts jump out. Searches outnumber edits by about a thousand to one: 5 crore against 50,000. And the index of where things are is small enough to sit in one server's memory.

The API for nearby search

The API needs one read endpoint for nearby search, one for place details and a few for owner edits. An endpoint is one path your server answers, together with an HTTP method such as GET for reading.

Keep the search response small. Return just enough for the list screen, and load full details only when someone taps a place. For more results, return a cursor: a marker that says where the next page starts.

Public place APIs have the same shape. As of October 2026, Google's Places Nearby Search (New) takes a circle with a radius of up to 50,000 metres and returns at most 20 places per request. It ranks by popularity unless you ask for distance.

A normal database index, a B-tree, keeps rows in one sorted order, but nearness depends on two values at once. So it finds a thin strip of the map, not a small circle.

Picture an index on latitude alone. A 1 km search around Sarafa Bazaar matches every place within about 1 km north or south of the user. That band is 2 km tall and runs right around the world.

A second index on longitude gives a north-south strip. PostgreSQL can combine the two with a bitmap scan: it scans each index, marks the matching rows, then keeps rows marked by both. It still reads every entry in both strips first.

What you need is an index where places that are close on the map are also close in the index. That is what a spatial index gives you.

A geohash turns a latitude and longitude into a short text code for a rectangle on the map, called a cell. Places in the same cell share the same code, so a nearby search becomes a lookup of a few codes.

It works by cutting the world map in half again and again, switching between longitude and latitude. Each cut adds one bit, a 0 or a 1. Every 5 bits become one character from a 32-character alphabet of digits and letters, skipping a, i, l and o.

A longer code means more cuts, so a smaller cell. Each place is filed under the cell it sits in. To search, you work out the user's cell and read only the places filed there and close by.

A printed city atlas works the same way. Its index says a street is on page 12, square C4, so you turn to one small square instead of reading every page. The first characters of a geohash are the page, and the later ones are the square.

Where the picture breaks: atlas squares are all the same size, but geohash cells get narrower as you move away from the equator. And two cells that touch can have codes that look nothing alike, as you will see shortly.

The Elasticsearch documentation lists the cell size for each code length at the equator. We computed the Indore column ourselves on the WGS84 ellipsoid, the standard model of the Earth's shape that GPS uses.

Notice the width column. Cells lose width, their east-west size, away from the equator, because lines of longitude come closer together. Their height barely changes.

Why you must also search the 8 neighbouring cells

It will not. The cart sits in the next cell to the north, so a search of one cell misses a place well inside 1 km. Anyone standing near a cell edge has this problem.

In our test of 400 random 1 km searches around Indore, searching only the user's own cell gave a wrong list 223 times. Searching all 9 cells matched a full scan every time.

So the rule is to read 9 cells: the user's cell and the 8 around it. If each cell is at least as wide and as tall as the radius, the circle cannot reach past those 9 cells. This holds away from the poles and the 180th meridian, which India never touches.

There is a second catch. Two stalls 1 metre apart on the 22.5 degree latitude line at longitude 75.94, about 25 km south of central Indore, get the codes tsn000 and teypbp. They share only the first character.

A shared prefix means the places are close, but close places do not always share a prefix. So you work out neighbours from the cell's position on the map, never by matching code prefixes.

Beginners can stop here: you now have the whole idea. The rest of the guide builds it in code, checks it against Redis and scales it to 41 cities.

Building geohash codes in Python

The three code blocks below need only Python's standard library, and they run together as one file. We ran them on Python 3.13.16.

The first block holds three helpers. geohash_encode makes the cuts and turns bits into characters. geohash_box replays the cuts to find a cell's edges. geohash_neighbours steps one cell width or height away from the cell's centre.

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

def geohash_encode(lat, lng, length):
    lat_lo, lat_hi, lng_lo, lng_hi = -90.0, 90.0, -180.0, 180.0
    code, value, bits, cut_lng = "", 0, 0, True
    while len(code) < length:
        if cut_lng:
            mid = (lng_lo + lng_hi) / 2
            bit = lng >= mid
            lng_lo, lng_hi = (mid, lng_hi) if bit else (lng_lo, mid)
        else:
            mid = (lat_lo + lat_hi) / 2
            bit = lat >= mid
            lat_lo, lat_hi = (mid, lat_hi) if bit else (lat_lo, mid)
        value, bits, cut_lng = value * 2 + bit, bits + 1, not cut_lng
        if bits == 5:
            code, value, bits = code + BASE32[value], 0, 0
    return code

def geohash_box(code):
    lat_lo, lat_hi, lng_lo, lng_hi = -90.0, 90.0, -180.0, 180.0
    cut_lng = True
    for ch in code:
        value = BASE32.index(ch)
        for shift in (4, 3, 2, 1, 0):
            bit = (value >> shift) & 1
            if cut_lng:
                mid = (lng_lo + lng_hi) / 2
                lng_lo, lng_hi = (mid, lng_hi) if bit else (lng_lo, mid)
            else:
                mid = (lat_lo + lat_hi) / 2
                lat_lo, lat_hi = (mid, lat_hi) if bit else (lat_lo, mid)
            cut_lng = not cut_lng
    return lat_lo, lat_hi, lng_lo, lng_hi

def geohash_neighbours(code):
    lat_lo, lat_hi, lng_lo, lng_hi = geohash_box(code)
    mid_lat, mid_lng = (lat_lo + lat_hi) / 2, (lng_lo + lng_hi) / 2
    h, w = lat_hi - lat_lo, lng_hi - lng_lo
    return [geohash_encode(mid_lat + dy * h, mid_lng + dx * w, len(code))
            for dy in (-1, 0, 1) for dx in (-1, 0, 1) if dy or dx]

Notice that geohash_neighbours never compares codes. It moves on the map and encodes the new spot, which is why the prefix trap cannot fool it. It does not handle the poles or the 180th meridian, which a service in India can safely ignore.

Picking the cell size in Python

Next, map each radius to a code length. Pick the longest code whose cell is at least as wide and as tall as the radius, measured at Indore.

# (code length, largest safe radius in km near Indore)
SAFE_RADIUS = [(6, 0.6), (5, 4.5), (4, 19.0)]

def pick_length(radius_km):
    for length, safe_km in SAFE_RADIUS:
        if radius_km <= safe_km:
            return length
    raise ValueError("Radius too large for nearby search")

The list runs from small cells to big ones, so the first match is the smallest cell that still works. A 500 m search gets length 6, a 1 km or 2 km search gets length 5, and a 5 km search gets length 4.

Each safe radius is just under the smaller of the cell's width and height at Indore, from the table above. The 0.6 comes from a height of about 608 m. Margins are thin: the 4.5 km pick holds only up to about 23 degrees north.

Cities further north have narrower cells, so the multi-city version stores these numbers per city. In our Delhi test, reusing Indore's 4.5 km limit gave a wrong 4.5 km list 18 times in 400. Delhi's length-5 cells are only 4.3 km wide.

The nearby search in Python

The third block builds a tiny index and runs the search. CELL_INDEX is a dictionary from a geohash code to the places filed in that cell. Each place is filed under its length-4, 5 and 6 codes, because a search may use any of them.

import math
from collections import defaultdict

CELL_INDEX = defaultdict(list)   # geohash code -> places filed in that cell

def add_place(place_id, lat, lng):
    for length in (4, 5, 6):     # one entry per code length a search may use
        CELL_INDEX[geohash_encode(lat, lng, length)].append((place_id, lat, lng))

def distance_km(lat1, lng1, lat2, lng2):
    p1, p2 = math.radians(lat1), math.radians(lat2)
    dp, dl = p2 - p1, math.radians(lng2 - lng1)
    a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
    return 2 * 6371 * math.asin(math.sqrt(a))

def nearby(lat, lng, radius_km, limit=20):
    cell = geohash_encode(lat, lng, pick_length(radius_km))
    found = []
    for c in [cell] + geohash_neighbours(cell):   # own cell plus 8 around it
        for place_id, p_lat, p_lng in CELL_INDEX.get(c, []):
            d = distance_km(lat, lng, p_lat, p_lng)
            if d <= radius_km:
                found.append((round(d, 3), place_id))
    found.sort()
    return found[:limit]

add_place("poha-stall", 22.7183, 75.8560)
add_place("kachori-cart", 22.7240, 75.8570)
add_place("bypass-dhaba", 22.7500, 75.9200)
print(geohash_encode(22.7179, 75.8555, 5), geohash_encode(22.7240, 75.8570, 5))
print(nearby(22.7179, 75.8555, 1.0))

Run the three blocks as one file. The first line printed should be tsjcn tsjcq: the user and the kachori cart are in different cells. The second should be [(0.068, 'poha-stall'), (0.696, 'kachori-cart')], with distances in kilometres.

What just happened? The search read 9 cells, found the cart in the northern neighbour and dropped the dhaba, which is about 7.5 km away. Sorting the pairs put the nearest first, because Python compares the distance before the ID.

The distance_km function is the haversine formula: the distance along the surface of a sphere with the Earth's average radius, 6,371 km. The real Earth is slightly flattened, so this is an approximation.

Redis's documentation says the haversine error may be up to 0.5% in the worst case. Around Indore, our check against the WGS84 ellipsoid found at most 0.41%. A true 1,000 m north reads as 1,004 m.

Use a geohash when you want simple, fixed cells stored in a key-value store or database. Use a quadtree when the number of places varies a lot from area to area.

A quadtree is a tree that splits a map square into four smaller squares, but only where it is crowded. Sarafa Bazaar, packed with stalls, gets tiny squares. Farmland outside the city stays one big square.

That fixes a weak spot of geohash. A length-5 cell over a busy market can hold hundreds of places, while one over a lake holds none. A quadtree keeps each leaf, an end square with no children, at a similar number of places.

The price is that a quadtree usually lives in server memory and must be rebuilt or carefully updated when places change.

PostGIS, a map extension for the PostgreSQL database, has a function called ST_DWithin. Its documentation says the call includes a bounding box comparison, a quick check against the smallest rectangle around each shape, that uses any spatial index on the columns. For geography columns, the distance is in metres.

Redis, an in-memory data store, has geo commands. GEOADD stores each place in a sorted set, a list kept in score order, with a 52-bit geohash as the score. GEOSEARCH, added in Redis 6.2, returns places within a radius or a box.

What Redis GEOSEARCH does inside

The Redis source code shows that GEOSEARCH uses the same 9-cell method as our Python. We read the 7.0.15 release, and the same lines are on its main development branch as of October 2026.

In geohash_helper.c, Redis picks a cell size from the radius, then builds the centre cell plus 8 neighbours. If a neighbour does not reach the edge of the search's bounding box, Redis uses cells one step coarser, one bit less each of latitude and longitude. Neighbours the box cannot touch are skipped.

Then geo.c measures each candidate's exact haversine distance and drops anything outside. Redis uses an Earth radius of 6,372,797.56 metres, about 0.03% more than the 6,371 km in our code. So distances near the edge of a radius can differ slightly.

Results come back unsorted unless you pass ASC (nearest first) or DESC (farthest first). One exception is in the 7.0.15 source: COUNT without ANY makes Redis sort nearest first anyway. As of 19 October 2026, the documentation says such a search sorts matches but not in which direction, so always pass ASC.

You can check the whole thing with redis-cli on Redis 6.2 or later. Note that geo commands take longitude first, then latitude.

redis-cli GEOADD places 75.8560 22.7183 poha-stall 75.8570 22.7240 kachori-cart 75.9200 22.7500 bypass-dhaba
redis-cli GEOSEARCH places FROMLONLAT 75.8555 22.7179 BYRADIUS 1 km ASC WITHDIST

On our Redis 7.0.15 server, the second command printed poha-stall 0.0679 and kachori-cart 0.6956, distances in kilometres. The dhaba is missing because it is outside 1 km.

Memory is bigger than the raw estimate. One geo set of 20 lakh places with 8-character IDs took about 203 MB in Redis 7.0.15, roughly 100 bytes a place. That still fits easily on one server.

Speed was not a worry either. A 1 km search over 50,000 Indore places, returning 20 of 163 matches, took about 0.13 milliseconds inside Redis on our test machine.

So the team picks Redis, with one geo set for all 41 cities. One set also avoids a trap: with one set per city, a user near a city's edge would never see places just across it.

It handles them by copying, not splitting. The geo index and place details are small enough to copy onto several replicas and caches, while stateless search servers sit behind a load balancer.

Stateless means a search server keeps nothing between requests, so any server can answer any search. When dinner traffic triples, you add servers. A load balancer is the front door that spreads requests across them.

The food app makes copies in three places.

• Geo index: one Redis geo set with a primary and two read replicas. A read replica is a copy that serves reads and applies the primary's changes a moment later.
• Place details: a cache keeps popular places' details in memory, so most taps never reach the database.
• Database: one primary takes every owner edit, and read replicas serve the detail lookups the cache misses.

Why not shard, which means splitting the data across machines by some key? At about 203 MB for the geo set and 20 GB for details, one machine holds everything. Sharding would add routing work for no gain yet.

Shard later, by region, if the data outgrows one machine. A search near a region's border then needs both shards. You can query both, or file places near a border in both shards.

Here is one search, step by step. Notice that the primary database never appears on the search path.

The detail cache uses a pattern called cache-aside. The service checks the cache first. On a miss, it reads a database replica and stores the result in the cache for next time.

Each cached entry expires after 10 minutes. So an owner's edit shows up soon, even if nothing clears the cache on purpose.

New and edited places go to the primary database first. A background job then copies the changes into the geo index, usually within a few minutes. Search sees them late, which is fine for restaurants.

This is eventual consistency: copies agree with the original after a short delay, not instantly. A stall owner at Chappan Dukan who adds a place sees it on the owner page at once. Other users find it in search a few minutes later.

The owner page reads from the primary database, so it always shows the latest save.

The index builder reads the database's change stream, an ordered feed of every insert, update and delete. This is often called change data capture. Once a night it also rebuilds the whole index from scratch, to fix any drift.

The diagram shows both paths. Follow the searches to the geo index and cache, then follow owner edits through the primary database to the index builder.

It should widen the search in steps until it finds enough places or reaches a maximum radius. Then it shows what it found, with honest distances.

On the edge of Indore, near the bypass road, a 1 km search may find only two dhabas. A list of two feels broken. The team wants at least 10 results whenever they exist within 16 km.

So the search service doubles the radius and tries again, never going past 16 km. A 1 km search tries 1, 2, 4, 8 and then 16 km. A 5 km search tries 5, 10 and then 16 km.

Follow the arrow from the doubling step back to the search. That loop is what gives a user on the edge of town a useful list.

Each widening is another trip to the geo index, so even a 500 m search stops after at most six rounds. The 16 km cap also stays under the 19 km safe radius in the pick_length code.

Lead with the read-heavy shape of the problem. Then build up from a simple scan to a spatial index, replicas and caches, giving a reason for each step.

1. 1

   Ask clarifying questions

   Ask about radius choices, the number of places and users, whether places move, and how fresh results must be.

2. 2

   Estimate the load

   Work out peak searches per second, the index size and the read to write ratio.

3. 3

   Define the API

   One nearby search endpoint returning IDs, names and distances, plus details and owner endpoints.

4. 4

   Explain the spatial index

   Draw geohash cells, the 8 neighbours and the exact distance filter. Mention quadtrees for uneven crowds.

5. 5

   Scale the read path

   Add stateless search servers, index replicas, a detail cache and database read replicas. Explain why you do not shard yet.

6. 6

   Cover writes and edge cases

   Owner edits flow through the primary database and an index builder. Then cover empty areas and crowded markets.