Design a Proximity Service

Geohash, quadtrees and read replicas

Searching "restaurants within 2 km" by computing distances to every place does not scale. Geohash encodes latitude and longitude into a string where a shared prefix means a nearby area, so a search becomes a lookup of the user's cell plus its eight neighbours (to handle edges). Quadtrees and libraries such as S2 or H3 are alternatives. Place data is read-heavy and changes rarely, so it suits caching and read replicas; filter and rank candidates by exact distance afterwards.

Real-time and location

Location search, persistent connections and fan-out to devices add new constraints.

Geohash cells for places in Delhi and Mumbai, run

I ran this with Python 3.12.3 using only the standard library; inputs are fixed or seeded, so the output is reproducible. India Gate and Connaught Place share the 5-character cell of a user near them; Qutub Minar is further away in another cell, and Mumbai starts with a different prefix.

# Proximity search: geohash cells group nearby places under a shared prefix
BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"

def geohash(lat, lon, precision=7):
    lat_r, lon_r, bits, even = [-90.0, 90.0], [-180.0, 180.0], [], True
    while len(bits) < precision * 5:
        rng, val = (lon_r, lon) if even else (lat_r, lat)
        mid = (rng[0] + rng[1]) / 2
        if val >= mid:
            bits.append(1); rng[0] = mid
        else:
            bits.append(0); rng[1] = mid
        even = not even
    return "".join(BASE32[int("".join(map(str, bits[i:i + 5])), 2)]
                   for i in range(0, len(bits), 5))

places = {
    "India Gate":     (28.6129, 77.2295),
    "Connaught Pl.":  (28.6315, 77.2167),
    "Qutub Minar":    (28.5245, 77.1855),
    "Gateway Mumbai": (18.9220, 72.8347),
}
for name, (lat, lon) in places.items():
    print(f"{name:15} {geohash(lat, lon)}")
user = geohash(28.6200, 77.2250, 5)
print("user cell (5 chars):", user)
print("same cell:", [n for n, p in places.items() if geohash(*p, 5) == user])

Output:

India Gate      ttnfv2u
Connaught Pl.   ttnfvh5
Qutub Minar     ttnfk2s
Gateway Mumbai  te7g9ks
user cell (5 chars): ttnfv
same cell: ['India Gate', 'Connaught Pl.']

Always search neighbouring cells

Two places metres apart can sit on either side of a cell border with different prefixes.

Quick check: Why query neighbouring geohash cells too?

• Geohash is inaccurate
• Nearby points just across a cell boundary have different prefixes
• To make results random
• Because cells overlap