Design a Proximity Service (Yelp / Nearby)

1Requirements

2Back-of-envelope estimation

3API design

4High-level design

Split the system into two services: a stateless Location-Based Search (LBS) service that answers nearby queries, and a Business service that owns CRUD on business data. They scale independently because the workloads are wildly different: LBS is read-hot and latency sensitive, the business service is a boring CRUD API in front of a relational database with replicas.

The heart of the LBS is a geospatial index. The three mainstream options are geohash, quadtree, and Uber's H3. Geohash encodes lat/lng into an interleaved base32 string where a shared prefix implies spatial proximity, so a radius query becomes a prefix match over the target cell plus its 8 neighbors. A quadtree recursively splits the map until each leaf holds under ~100 businesses, adapting naturally to density but living in memory and needing rebuilds. H3 uses hexagons, which have the nice property that all neighbors are equidistant, making ring-based expansion cleaner. For an interview, geohash on top of a plain database index is the simplest defensible answer.

Query flow: the client sends lat/lng and radius. The LBS picks a geohash precision matching the radius (precision 5 is about 4.9 x 4.9 km, precision 6 about 1.2 x 0.6 km), computes the center cell and its 8 neighbors, fetches candidate business ids from the index for those 9 prefixes, computes exact haversine distance to filter false positives from cell corners, then ranks and hydrates the top N from the business service or a cache.

Writes take the slow path. Business updates land in the business DB immediately, and the geo index is updated asynchronously: either incrementally (insert/delete the geohash row) or via a periodic rebuild for the in-memory quadtree variant. Because the index rows are tiny, the whole index replicates cheaply across many read replicas, and a fresh replica can rebuild from the DB in minutes.

5Data model

6Deep dives

7Rapid implementation: build the MVP

Theory is table stakes. Here is how you would stand up a working version fast, on a budget, with the core algorithm in real code.

1. 01Create a Neon Postgres database and run CREATE EXTENSION cube; CREATE EXTENSION earthdistance;
2. 02Create the businesses table with latitude, longitude, and a geohash char(6) column
3. 03Seed 100k rows from the free OpenStreetMap POI extract for one city (osmnx or a CSV dump)
4. 04Add a B-tree index on geohash and a GIST index on ll_to_earth(latitude, longitude) so you can benchmark both strategies
5. 05Install ngeohash and write a /api/nearby route: encode the query point at precision 6, compute the 8 neighbors, query WHERE geohash IN the 9 cells
6. 06Filter candidates by exact haversine distance in TypeScript and sort by a score of distance decay plus rating
7. 07Add a Redis (Upstash free tier) cache keyed by center-cell geohash plus radius with a 60 second TTL
8. 08Deploy to Vercel and load-test the endpoint with autocannon to confirm sub-100 ms p99 on the cached path

import geohash from "ngeohash";
import { sql } from "./db";

const PRECISION_FOR_RADIUS = [
  { maxMeters: 1000, precision: 6 },
  { maxMeters: 5000, precision: 5 },
  { maxMeters: 20000, precision: 4 },
];

export async function nearby(lat: number, lng: number, radiusM: number) {
  const { precision } = PRECISION_FOR_RADIUS.find(
    (t) => radiusM <= t.maxMeters
  ) ?? { precision: 4 };

  const center = geohash.encode(lat, lng, precision);
  const cells = [center, ...geohash.neighbors(center)];

  // geohash column is stored at precision 6; prefix match covers coarser cells
  const rows = await sql(
    "SELECT id, name, rating, latitude, longitude FROM businesses " +
      "WHERE " + cells.map((_, i) => "geohash LIKE $" + (i + 1)).join(" OR "),
    cells.map((c) => c + "%")
  );

  return rows
    .map((r) => ({ ...r, distanceM: haversine(lat, lng, r.latitude, r.longitude) }))
    .filter((r) => r.distanceM <= radiusM)
    .sort((a, b) => a.distanceM - b.distanceM)
    .slice(0, 20);
}

export function haversine(lat1: number, lng1: number, lat2: number, lng2: number): number {
  const R = 6371000; // earth radius in meters
  const toRad = (d: number) => (d * Math.PI) / 180;
  const dLat = toRad(lat2 - lat1);
  const dLng = toRad(lng2 - lng1);
  const a =
    Math.sin(dLat / 2) ** 2 +
    Math.cos(toRad(lat1)) * Math.cos(toRad(lat2)) * Math.sin(dLng / 2) ** 2;
  return 2 * R * Math.asin(Math.sqrt(a));
}

CREATE TABLE businesses (
  id         BIGSERIAL PRIMARY KEY,
  name       TEXT NOT NULL,
  category   TEXT,
  rating     REAL DEFAULT 0,
  latitude   DOUBLE PRECISION NOT NULL,
  longitude  DOUBLE PRECISION NOT NULL,
  geohash    CHAR(6) NOT NULL
);

CREATE INDEX idx_businesses_geohash ON businesses (geohash);
CREATE INDEX idx_businesses_earth
  ON businesses USING GIST (ll_to_earth(latitude, longitude));

-- Alternative radius query without geohash, using earthdistance directly:
SELECT id, name,
       earth_distance(ll_to_earth(latitude, longitude), ll_to_earth(40.7484, -73.9857)) AS meters
FROM businesses
WHERE earth_box(ll_to_earth(40.7484, -73.9857), 1000) @> ll_to_earth(latitude, longitude)
ORDER BY meters
LIMIT 20;