Design a proximity service

Design a proximity service like Yelp's "near me". Start with a latitude and longitude query, let the numbers lead to a geohash index searched over nine cells and held in memory on every server, then stress it with fresh changes, cell edges, other spatial indexes and density, with code.

Mid-level27 min core · 46 min full depth

Read first: Estimation Indexes
Scaling patterns: Hot keys and hot partitions Multi-region and active-active
Building blocks: Indexes Caching Replication Queues and streams Partitioning
Related: Ride hailing (Uber)

“Design a service that finds restaurants and shops near the user, like Yelp’s ‘near me’.”

It sounds like one SQL query with a WHERE on latitude and longitude. That query is the trap. A database index sorts things along one line, and “near” is a question about a flat map. Most of this problem is turning two dimensions into one. Then you notice the resulting index is small and almost never changes, and that decides where it lives.

So this page starts with that SQL query, and lets the numbers break it. Step by step, we turn two dimensions into one and decide where the index lives. Then we test the design at the edges of cells, against other spatial indexes, and in very dense and very empty places.

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains each part.

Give every business a geohash. A short string where nearby places share a prefix. “Near” becomes “starts with the same letters”, which a normal index can find.
Search the user’s cell and its eight neighbors. A coffee shop 50 m away can sit in the next cell with a totally different prefix. Nine small lookups never miss it.
Keep the whole index in memory on every search server. It’s only 6.4 GB. So a search is a couple of binary searches, about a millisecond, with no database on the path.
Stream changes on top of a nightly snapshot. Edits are captured from the database log. So a new or closed business shows in search within seconds.
Pick the radius from the density. Manhattan gets a small one, Wyoming a large one, and results are ranked by distance and rating together.

Scope it

A few questions decide whether the index lives in a database or in memory.

Interviewerminute 0

Design a proximity service, like Yelp’s “businesses near me”.

What they are testing

Whether you ask how many businesses, how many searches, and how fresh results must be.

These four questions matter most:

How many businesses? 200 million worldwide.
How many searches? 100 million daily users, 5 searches each.
How soon must an owner’s edit show? In search within a minute.
Do the points move? Rarely: a business, not a car. Drivers moving every 4 seconds are the ride-hailing problem.

From these answers we make five promises:

Always up. Search works 99.99% of the time. Owner edits 99.9%, because they can be retried.
Fast. Search under 100 ms of server time, a business page under 50 ms.
Fresh. A change shows in search within a minute, and never more than a day late, even if the change pipeline breaks.
Complete. A business inside the radius is never missed because of a cell boundary.
Safe edits. Two managers editing the same business can’t overwrite each other.

We leave out reviews and photos (separate services hand us a rating and links), free-text search, ads and map tiles.

Go deeperMore questions, and what each changes1 min

Question	We assume	If the answer were different
Radius, or “the 20 nearest”?	A radius up to 20 km, widened if too few	Pure nearest-k grows rings outward from the user’s cell
How are results ordered?	Distance and rating, with filters	Free-text relevance puts a search engine in the middle
2 billion businesses?	No	The index becomes 64 GB and must be split by region
Do we store where users search?	Only roughly, in logs	Precise location history is personal data with legal rules

The numbers that decide it

Now we work out the numbers. The most important one is the size of the index.

Assumptions

Daily active users: 100 million
Searches per user a day: 5
Peak over average: 3.5 to 1
Searches that open a detail page: 50%
Businesses: 200 million
Bytes per business in the geo index: 32 bytes
Bytes per business record: 2 KB
Business changes a day: 1 million

Searches6,000/s20,000/s at peak

100 million users × 5 searches ÷ 86,400 s. Lunch and dinner overlap in the busiest region, so plan for 3.5 times that.

So we every search can't be a geo query on one database; a good one runs about 2,000 a second.

Writes12/s1M changes a day

New businesses, edits, closures and rating updates.

So we storing them is easy; the question is how they reach search.

Geo index6.4 GB

Search only needs what it filters and ranks on: an ID, a geohash, the position, a rating and a category. About 32 bytes a business.

So we the whole world's index fits in memory on every search server, even twice during a reload.

Business data400 GB

Name, address, hours and photo links: about 2 KB a business.

So we keep it in one Postgres primary with replicas.

Business reads30,000/sat peak

Each search fills in 20 results, and half of searches open a business page.

So we names and ratings need a cache.

Writes are 500 times rarer than reads, and the index is small. Try the calculator. At ten times the businesses, the index passes 30 GB, and must be split by region. At ten times the searches, the index plan doesn’t change. We just add servers.

Change an assumption

Daily active users100 millionSearches per user a day5Peak over average3.5 to 1Searches that open a detail page50%Businesses200 millionBytes per business in the geo index32 bytesBytes per business record2 KBBusiness changes a day1 million

Searches, average: 5,800/s
Searches, peak: 20,000/s; Past the ~2,000 searches/s one database runs even with a geohash index: hold the index in memory on stateless search servers.
Location servers at peak: 5; At about 5,000 searches/s each, before headroom and spares. Each holds the whole index.
Business reads, peak: 30,000/s; Past what one database serves: cache business data in front of read replicas.
Geo index in memory: 6.4 GB; Small enough for every location server to hold all of it, twice during a snapshot swap.
Business data: 400 GB; One Postgres primary with replicas. Photos live in blob storage, not here.
Business cache (summaries for every business): 100 GB; Summaries are about 500 bytes. The hot 20% fits one cache node.
Business changes, average: 12/s; Noise for one primary, and few enough for every location server to apply all of them.
Search response bandwidth, peak: 200 MB/s; Twenty summaries of about 500 bytes, before compression. Not a design driver.

Build the design

We start with the simplest design that works. Then we let the numbers break it, one at a time. Each step fixes only what broke, adds only the boxes that fix needs, and says what the fix costs.

Step 1. One table, latitude and longitude

The simple version keeps every business in one Postgres table. It turns the radius into a box and runs WHERE lat BETWEEN ... AND lng BETWEEN ....

Proximity service · architecture

Stage 1: One server, one table

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Searches per second: 20,000

Stage 1 of 6

One server, one table

Why this stage

Nothing yet.

This is the smallest design that answers "what is near me".

What we add

An app server and a Postgres table of businesses with an index on latitude and another on longitude.

What it costs

Each search intersects two stripes that circle the globe: hundreds of thousands of index entries to find twenty businesses.

At 20k searches per second, Postgres primary is 6667% busy. Stage 2 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

How to read these numbers

These are rough planning figures for a large node of about 32 cores, not benchmarks.
Each could be off by 2 to 3 times without changing which box turns red.

What one machine can do

A location server handles about 5,000 searches a second, about 1 ms of CPU each for the index.
One Postgres node manages only a few hundred searches a second with two lat/lng indexes, because each search walks tens of thousands of index entries.
With a geohash index (nine short range scans) the same node manages about 2,000 searches a second.
It also does about 10,000 batched 20-id reads a second and 5,000 writes.
One Redis node handles about 100,000 requests a second.

Reads per search

Each search does one batched summary read. Half of searches also open a detail page, so there are 1.5 business reads per search.
Redis answers about 95% of them.
From stage 6, the largest region carries 40% of the traffic.

It is slow.

An index on latitude finds a stripe 2 km tall that circles the whole planet, through Spain, Sicily, Turkey and Korea. An index on longitude finds a stripe from pole to pole. Each holds tens of thousands of businesses. The database reads far more than it keeps, and manages a few hundred searches a second.

A combined index on (lat, lng) doesn’t fix it either. It’s sorted by latitude first, so longitude is only a filter inside the stripe. We need an order where nearby places get nearby keys.

Step 2. Index the location with a geohash

A geohash halves the world over and over, alternating between longitude and latitude: east or west half, then north or south, and so on. Every five halvings become one letter. Union Square is 9q8yyx1e4.

The key property: each letter only narrows the box before it. So every prefix is a cell, and a longer prefix is a smaller cell inside it. 9q8yy is a 4.9 km by 3.9 km cell around Union Square. 9q8yyx is a cell about a kilometer wide inside that. “Everything in this cell” is “every geohash starting with these letters”: a range lookup any sorted index can do.

Proximity service · architecture

Stage 2: Index the location

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Searches per second: 20,000

Stage 2 of 6

Index the location

Why this stage

One Postgres node runs a few hundred two-stripe searches a second, against 6,000 on average and 20,000 at peak.

One app server takes about 5,000.

What we add

A geohash column with a B-tree index, so a search reads nine small key ranges, plus a load balancer and stateless app servers.

What it costs

The database still runs every search: about 2,000 a second per node, ten times short of the peak.

At 20k searches per second, Postgres primary is 1000% busy. Stage 3 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

How to read these numbers

These are rough planning figures for a large node of about 32 cores, not benchmarks.
Each could be off by 2 to 3 times without changing which box turns red.

What one machine can do

A location server handles about 5,000 searches a second, about 1 ms of CPU each for the index.
One Postgres node manages only a few hundred searches a second with two lat/lng indexes, because each search walks tens of thousands of index entries.
With a geohash index (nine short range scans) the same node manages about 2,000 searches a second.
It also does about 10,000 batched 20-id reads a second and 5,000 writes.
One Redis node handles about 100,000 requests a second.

Reads per search

Each search does one batched summary read. Half of searches also open a detail page, so there are 1.5 business reads per search.
Redis answers about 95% of them.
From stage 6, the largest region carries 40% of the traffic.

Precision	Cell at the equator	Width in San Francisco	Good for a radius up to
4	39 km × 19.5 km	30.9 km	About 20 km
5	4.9 km × 4.9 km	3.9 km	About 4 km
6	1.2 km × 610 m	970 m	About 600 m
7	153 m × 153 m	121 m	About 120 m

Geohash.javaexample.pyGeohash.csbox.gobox.ts

// Geohash turns a point into a short string by interleaving longitude and latitude bits, five
// bits per character. Every prefix names a rectangle, so "same prefix" means "same cell", and a
// plain B-tree index finds a cell with one range scan instead of two stripe scans.
final class Geohash {
    // In ASCII order, so string order is bit order: each cell is one contiguous key range.
    static final String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

    record Box(double minLat, double maxLat, double minLng, double maxLng) {}

    static String encode(double lat, double lng, int precision) {
        double minLat = -90, maxLat = 90, minLng = -180, maxLng = 180;
        StringBuilder sb = new StringBuilder(precision);
        int bits = 0, ch = 0;
        boolean lngBit = true; // bits alternate, longitude first: that is what makes cells nest
        while (sb.length() < precision) {
            // Each bit halves one side of the box: 1 keeps the upper half, 0 the lower.
            if (lngBit) {
                double mid = (minLng + maxLng) / 2;
                if (lng >= mid) { ch = ch * 2 + 1; minLng = mid; } else { ch *= 2; maxLng = mid; }
            } else {
                double mid = (minLat + maxLat) / 2;
                if (lat >= mid) { ch = ch * 2 + 1; minLat = mid; } else { ch *= 2; maxLat = mid; }
            }
            lngBit = !lngBit;
            if (++bits == 5) { sb.append(BASE32.charAt(ch)); bits = 0; ch = 0; }
        }
        return sb.toString();
    }

    // The rectangle a hash stands for. Search needs it to step into the neighboring cells,
    // because two points 70 m apart can share no prefix at all (deep dive 2).
    static Box bounds(String hash) {
        double minLat = -90, maxLat = 90, minLng = -180, maxLng = 180;
        boolean lngBit = true;
        for (char c : hash.toCharArray()) {
            int v = BASE32.indexOf(c);
            if (v < 0) throw new IllegalArgumentException("not a geohash character: " + c);
            for (int b = 4; b >= 0; b--) { // replay the five halvings this character encodes
                boolean upper = ((v >> b) & 1) == 1;
                if (lngBit) {
                    double mid = (minLng + maxLng) / 2;
                    if (upper) minLng = mid; else maxLng = mid;
                } else {
                    double mid = (minLat + maxLat) / 2;
                    if (upper) minLat = mid; else maxLat = mid;
                }
                lngBit = !lngBit;
            }
        }
        return new Box(minLat, maxLat, minLng, maxLng);
    }
}

Go deeperA geohash as a number, not a string1 min

The letters are only for people. Inside the index, a geohash is stored as a 64-bit number: the longitude and latitude halvings, one bit each, woven together. This weaving is called a Z-order or Morton code.

A prefix of letters is a prefix of bits. So “every business in cell 9q8yy” becomes “every number between this one and that one”, which is two integer comparisons instead of string comparisons. Numbers are also smaller to store and faster to sort, which matters when the builder sorts 200 million of them every night.

Step 3. Nine cells, not one

A shared prefix means two places are close. But close doesn’t mean a shared prefix. A user standing at the edge of their cell has neighbors just across the line, in a cell with different letters. So a search never reads one cell. It reads the user’s cell and its eight neighbors, a 3 × 3 block. Then it checks the exact distance of each candidate and drops the corners outside the circle.

The precision is chosen so the block always covers the circle. It’s the finest precision whose cell is at least as wide as the radius, at the user’s latitude. A stress test shows the details.

Step 4. The whole index, in memory, everywhere

Now the key observation. A 6.4 GB index that changes 12 times a second isn’t something to query. It’s something to copy. So every location server holds the whole world’s index in memory: one array of entries, sorted by geohash. Because a cell is a prefix, every cell is one contiguous slice of the array, found with two binary searches. A 500 m search and a 20 km search use the same structure.

Proximity service · architecture

Stage 3: Search in memory

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Searches per second: 20,000

Stage 3 of 6

Search in memory

Why this stage

At 20,000 searches a second Postgres is 1,000% busy.

The geo index is only about 6 GB, small enough for every search server to hold all of it.

What we add

A location service that holds the whole index in memory, a nightly index builder that writes a sorted snapshot file, and a business service that owns business data.

What it costs

A new or moved business reaches search only with the next snapshot, up to a day later, and the business service still reads Postgres for every result list.

At 20k searches per second, Postgres primary is 300% busy. Stage 4 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

How to read these numbers

These are rough planning figures for a large node of about 32 cores, not benchmarks.
Each could be off by 2 to 3 times without changing which box turns red.

What one machine can do

A location server handles about 5,000 searches a second, about 1 ms of CPU each for the index.
One Postgres node manages only a few hundred searches a second with two lat/lng indexes, because each search walks tens of thousands of index entries.
With a geohash index (nine short range scans) the same node manages about 2,000 searches a second.
It also does about 10,000 batched 20-id reads a second and 5,000 writes.
One Redis node handles about 100,000 requests a second.

Reads per search

Each search does one batched summary read. Half of searches also open a detail page, so there are 1.5 business reads per search.
Redis answers about 95% of them.
From stage 6, the largest region carries 40% of the traffic.

CellIndex.javacell_index.pyCellIndex.cscell_index.gocell-index.ts

// One business as the search index sees it: only what search filters and ranks on. Names,
// photos and hours stay in the business service, which is why the whole world fits in memory.
record Place(long id, String geohash, double lat, double lng, float rating) {}

// What search needs from any index: every business inside one geohash cell.
interface Cells {
    List<Place> inCell(String prefix);
}

// Every business in the world, sorted by a 9-character geohash, in one array. A cell at any
// precision is a contiguous slice of it, so one structure serves 500 m and 20 km searches.
// Built offline from the business database and never modified, so reads need no locks; a new
// snapshot replaces the whole object. Production packs this into primitive arrays (a 64-bit
// geohash, two floats, an id): about 32 bytes a business instead of 100+ for objects.
final class CellIndex implements Cells {
    private final Place[] sorted;

    CellIndex(Collection<Place> places) {
        // String.compareTo compares UTF-16 units, which matches Base32's ASCII order,
        // so every prefix is one contiguous range.
        sorted = places.stream().sorted(Comparator.comparing(Place::geohash)).toArray(Place[]::new);
    }

    public List<Place> inCell(String prefix) {
        int lo = lowerBound(prefix);
        int hi = lowerBound(prefix + "{"); // '{' sorts right after 'z': past every hash with this prefix
        return Collections.unmodifiableList(Arrays.asList(sorted).subList(lo, hi)); // a view, nothing copied
    }

    // Two binary searches and no scan: dense-area search uses it to pick a finer cell first.
    int countInCell(String prefix) {
        return lowerBound(prefix + "{") - lowerBound(prefix);
    }

    private int lowerBound(String key) { // the first position whose hash is >= key
        int lo = 0, hi = sorted.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (sorted[mid].geohash().compareTo(key) < 0) lo = mid + 1; else hi = mid;
        }
        return lo;
    }
}

There’s no hot spot for Times Square, because every server holds Times Square. More traffic means more servers, nothing else.

Servers don’t build the index from the database. A nightly index builder reads a consistent copy from a replica, sorts it, and writes one file to object storage. A server downloads it in under a minute, loads it beside the live copy, and swaps one reference. A hundred servers restarting at once download a file, instead of scanning Postgres a hundred times.

Go deeperSizing the index and the fleet1 min

Each index entry is 32 bytes. 8 are for the geohash as a number, 8 for the business ID, and 8 for the exact latitude and longitude. The last 8 are for what search filters on, packed as small numbers: category, price level, rating and opening hours. 200 million entries × 32 bytes is 6.4 GB. That fits easily in a server with 32 GB of memory, with room for the next snapshot to load beside it.

A search does nine pairs of binary searches, then checks a few hundred candidates. That is about 0.2 ms of one CPU core, so one core serves about 5,000 searches a second. At the 20,000 a second peak, a handful of 8-core servers would be enough. We run about ten per region anyway, so losing one or two during a deploy or a failure changes nothing for users.

Step 5. Business details, separately

The index holds only what search filters and ranks on. Names, addresses and photos live in a separate business service, with Postgres as the source of truth and a Redis cache in front. A search gets its 20 IDs from the location server, then fetches 20 summaries with one batched cache read. A write deletes the business’s cache keys after it commits.

The two services scale differently. One needs CPU and memory, the other database reads. So each deploys and fails on its own. If the business service is down, the location server reads summaries straight from Redis, so a search still shows the 95% that are cached.

Proximity service · architecture

Stage 4: Cache business details

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Searches per second: 20,000

Stage 4 of 6

Cache business details

Why this stage

Every search hydrates 20 results and half of searches open a detail page: about 30,000 Postgres reads a second at peak, three times one node.

What we add

Redis in front of business summaries and details, and read replicas for the misses.

Writes stay on the primary.

What it costs

An edit can show stale details for a moment on other servers, until the cache entry is deleted.

At 20k searches per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

How to read these numbers

These are rough planning figures for a large node of about 32 cores, not benchmarks.
Each could be off by 2 to 3 times without changing which box turns red.

What one machine can do

A location server handles about 5,000 searches a second, about 1 ms of CPU each for the index.
One Postgres node manages only a few hundred searches a second with two lat/lng indexes, because each search walks tens of thousands of index entries.
With a geohash index (nine short range scans) the same node manages about 2,000 searches a second.
It also does about 10,000 batched 20-id reads a second and 5,000 writes.
One Redis node handles about 100,000 requests a second.

Reads per search

Each search does one batched summary read. Half of searches also open a detail page, so there are 1.5 business reads per search.
Redis answers about 95% of them.
From stage 6, the largest region carries 40% of the traffic.

Follow one search, and the details filled in behind it:

Proximity service · architecture

Trace a request: Search, cache miss

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasionalHop in motionHops doneResponse

Search, cache miss: step 1 of 6

Users to Load balancer

GET /v1/search/nearby?lat=37.788&lng=-122.4075&radius=500 from Union Square. The load balancer terminates TLS and routes /search to any location server.

2 ms of a 100 ms budget

Users → Load balancer2 ms
Load balancer → Location service3 ms
Location service → Business service1 ms
Business service → Redis cluster1 ms
Business service → Read replicas5 ms
Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

This is enough for a mid-level answer. A geohash, nine cells, the index in memory on every server, and cached business details. The stress tests are what make it a senior answer.

Go deeperThe business cache, in detail1 min

Thirty thousand reads a second is three times what one Postgres node handles. Business data is read far more than written, and can be a few seconds stale. So it gets a cache-aside Redis. The app reads the cache first. On a miss, it reads a replica, and fills the cache itself. It’s keyed by business ID, with summaries and full pages as separate keys. A search reads its 20 summaries in one batched read. Misses fill the cache with a one hour expiry. A write deletes the business’s keys after it commits, so the expiry is only a backstop.

One small race remains. A read that misses just before a write commits can put the old value back, for up to an hour. A second delete a few seconds after the write closes most of that window.

The index entry stays lean on purpose. Putting every field into it would turn 32 bytes into 2 KB a business, and 6 GB into 400 GB. That no longer fits on every server.

Go deeperThe API and the business table2 min

GET /v1/search/nearby?lat=37.7880&lng=-122.4075&radius=500&category=coffee&limit=20

200 OK
{ "radius": 500,
  "businesses": [
    { "id": "8812734", "name": "Blue Door Coffee", "distanceM": 68, "rating": 4.6,
      "reviewCount": 812, "openNow": true } ],
  "nextCursor": "eyJzIjowLjgxLCJpZCI6ODgxMjczNH0" }

radius in the response is the radius actually used, which can be larger than asked in a sparse area. The cursor holds the score and ID of the last result, so page two continues after it even if a business was added in between. Owners edit with PATCH /v1/businesses/{id} and If-Match: "v17": if someone saved first, they get 412 instead of overwriting.

CREATE TABLE businesses (
  id        BIGINT PRIMARY KEY,
  name      TEXT NOT NULL,
  category  SMALLINT NOT NULL,
  lat       DOUBLE PRECISION NOT NULL,
  lng       DOUBLE PRECISION NOT NULL,
  geohash   TEXT COLLATE "C" NOT NULL,   -- byte order makes a cell one range
  rating    NUMERIC(2,1),
  status    TEXT NOT NULL DEFAULT 'open',
  version   BIGINT NOT NULL DEFAULT 1    -- bumped on every change; orders changes downstream
);

Nothing is ever hard deleted, so old links still show “permanently closed”.

Go deeperOther places the index could live1 min

Option	Wins	Loses
Postgres with PostGIS and 10+ replicas	No new code; exact, handles polygons	Ten big databases doing an array lookup’s work
Redis, one key per cell	Shared by all servers; easy updates	A hop per search; dense cells become hot keys
Index split across servers by region	Scales to any size	Routing, border searches, hot spots in big cities
The whole index on every server	No hop, no hot spot; add servers to scale	Every server loads and refreshes 6 GB

Why Postgres for the source of truth? The write path needs transactions, version checks and a durable log, for only 12 writes a second. Postgres gives all three. Because search runs outside it, the search index becomes a disposable copy that can be rebuilt at any time. The cost is two copies of every business, and a pipeline between them whose delay is a number to watch. DynamoDB with a geohash prefix as its key would also work on AWS, but you write the cell logic yourself. Elasticsearch fits when search is text plus location.

Why not Redis GEOSEARCH? It’s this same algorithm. It stores a 52-bit geohash as a sorted set score, and scans neighboring ranges. It’s a great choice for tens of millions of points, or points that move. But for 200 million static businesses, one sorted set sits on one single-threaded node, at far more than 32 bytes each. And every search pays a hop.

Stress it

The design is complete. Now we test it where location search is hard. Changes that must show in seconds. A user at the edge of a cell. Other spatial indexes. And places that are very dense or very empty. Only the first adds new boxes.

Changes in seconds, not a day

Owners complain that a new business takes a day to show up. How do we fix it?

With a nightly snapshot, a closed business keeps sending hungry people to a locked door for up to a day. Rebuilding more often sorts 200 million rows to absorb a few thousand changes. So we stream the changes instead.

Change data capture reads the database’s own log of commits, with a connector like Debezium. It publishes each change to Kafka, keyed by business ID, so changes to one business stay in order. Each event carries the business’s whole new state, not a diff. So applying it twice is harmless. Every location server reads the topic, and keeps the changes since its snapshot beside it. A search reads both, and the newer one wins. A day of changes is under 100 MB, and the next snapshot absorbs them.

Proximity service · architecture

Stage 5: Changes in minutes

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Searches per second: 20,000

Stage 5 of 6

Changes in minutes

Why this stage

A requirement, not load: owners expect a new or closed business to show in search within minutes, and a nightly rebuild takes up to a day.

What we add

Change data capture from the Postgres log into Kafka.

Every location server applies the changes on top of its snapshot.

What it costs

Kafka to run, and a merge of snapshot and changes on every cell read.

At 20k searches per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

How to read these numbers

These are rough planning figures for a large node of about 32 cores, not benchmarks.
Each could be off by 2 to 3 times without changing which box turns red.

What one machine can do

A location server handles about 5,000 searches a second, about 1 ms of CPU each for the index.
One Postgres node manages only a few hundred searches a second with two lat/lng indexes, because each search walks tens of thousands of index entries.
With a geohash index (nine short range scans) the same node manages about 2,000 searches a second.
It also does about 10,000 batched 20-id reads a second and 5,000 writes.
One Redis node handles about 100,000 requests a second.

Reads per search

Each search does one batched summary read. Half of searches also open a detail page, so there are 1.5 business reads per search.
Redis answers about 95% of them.
From stage 6, the largest region carries 40% of the traffic.

LiveIndex.javalive_index.pyLiveIndex.cslive_index.golive-index.ts

// A change to one business as the change stream delivers it: the business's whole new state,
// not a diff. Applying the same event twice gives the same index, so redelivery is harmless.
record Change(long id, long version, double lat, double lng, float rating, boolean removed) {}

// The nightly snapshot plus every change since it was cut. Search reads both, and the change
// wins wherever both know a business. The next snapshot absorbs the changes and this resets.
final class LiveIndex implements Cells {
    static final int STORED_PRECISION = 9; // the same 5 m hashes the snapshot is sorted by

    private record Key(String hash, long id) {}

    private final CellIndex snapshot;
    // One writer (the stream consumer, about 12 changes a second) and thousands of readers.
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Map<Long, Change> latest = new HashMap<>(); // business id -> newest change seen
    // Present businesses from the changes, sorted by (geohash, id) so a cell is a range here too.
    private final TreeSet<Key> byCell =
            new TreeSet<>(Comparator.comparing(Key::hash).thenComparingLong(Key::id));

    LiveIndex(CellIndex snapshot) { this.snapshot = snapshot; }

    void apply(Change c) {
        lock.writeLock().lock();
        try {
            // A redelivered or reordered event carries an older version: ignoring it keeps a
            // stale position from overwriting a newer one.
            Change old = latest.get(c.id());
            if (old != null) {
                if (old.version() >= c.version()) return;
                byCell.remove(new Key(Geohash.encode(old.lat(), old.lng(), STORED_PRECISION), old.id())); // a move leaves its old cell
            }
            latest.put(c.id(), c);
            if (!c.removed()) byCell.add(new Key(Geohash.encode(c.lat(), c.lng(), STORED_PRECISION), c.id()));
        } finally {
            lock.writeLock().unlock();
        }
    }

    public List<Place> inCell(String prefix) {
        List<Place> result = new ArrayList<>();
        lock.readLock().lock();
        try {
            // A snapshot row the stream has changed since is stale: moved, closed or re-rated.
            // Its current state, if it still exists, comes from the changes below.
            for (Place p : snapshot.inCell(prefix)) {
                if (!latest.containsKey(p.id())) result.add(p);
            }
            // '{' sorts after every geohash character, so this view is exactly the cell.
            for (Key k : byCell.subSet(new Key(prefix, Long.MIN_VALUE), new Key(prefix + "{", Long.MIN_VALUE))) {
                Change c = latest.get(k.id());
                result.add(new Place(c.id(), k.hash(), c.lat(), c.lng(), c.rating()));
            }
        } finally {
            lock.readLock().unlock();
        }
        return result;
    }
}

The subtle step is the handoff between snapshot and stream. The builder records the Kafka position that matches its database snapshot, and a server replays from there. Starting slightly early is safe: a repeated change is harmless, because versions decide which state wins. Starting slightly late would skip a change until the next snapshot.

Loading a snapshot without losing or duplicating a change

Scroll or pinch to zoom, drag to pan

Color key
Service
Queue or stream
Database

Follow an owner adding a business, through to search:

Proximity service · architecture

Trace a request: Owner adds a business

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasionalHop in motionHops doneResponse

Owner adds a business: step 1 of 6

Users to Load balancer

POST /v1/businesses with the owner’s token, an Idempotency-Key, the address and the map pin the owner confirmed.

2 ms of a 200 ms budget

Users → Load balancer2 ms
Load balancer → Business service2 ms
Business service → Postgres primary6 ms
Postgres primary → Kafkaasync
Kafka → Location serviceasync
Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Go deeperOther ways to get changes to search1 min

Approach	Wins	Loses
Hourly rebuilds	No new parts	Still an hour; sorts everything for a few changes
Send to Kafka after commit	Simple	A crash between the two loses the change for good
Poll `updated_at`	No new systems	Misses rows committed out of timestamp order
Read the database log	Every commit, in order, nothing lost	A connector and Kafka to run

A business moves across the street into a different cell. The change carries the new position and a higher version. The server drops the old position, adds the new one, and hides the snapshot entry. Without versions, an older event delivered late could move it back.

The edge of the cell

Interviewerminute 26

The user stands at the edge of their cell. The best coffee shop is 50 m away, in the next cell. Do you find it?

What they are testing

Whether you know that a shared prefix means near, but near does not mean a shared prefix.

The extreme case shows why. Two points 70 m apart on either side of the Greenwich meridian are gcpuzgr8 and u10hb522. They share no letter at all, because the very first halving, east or west of 0°, differs. Smaller versions of this happen at every cell edge. So the search reads the 3 × 3 block:

	West	Center	East
North	`9q8zn2`	`9q8zn8`	`9q8znb`
Center	`9q8yyr`	`9q8yyx`	`9q8yyz`
South	`9q8yyq`	`9q8yyw`	`9q8yyy`

That’s Union Square at precision 6. The northern row starts with 9q8zn, the rest with 9q8yy. Neighbors are found by stepping one cell width and encoding again, with no lookup table.

Choosing the precision. The block reaches at least one full cell past the user in every direction. So we pick the finest precision whose cell, at the user’s latitude, is at least as wide as the radius. Then the block contains the whole circle. One level coarser would read 32 times the area. Far north, where cells are narrow, the search reads a 5 × 5 block instead.

Expanding. If the block holds too few results, double the radius and search again, up to 20 km. Then tell the client the radius actually used.

NearbySearch.javanearby_search.pyNearbySearch.csnearby_search.gonearby-search.ts

// Nearby search over any index of cells. Three rules: size the cell from the radius, always read
// the 3 x 3 block around the user's cell, and widen the radius when a sparse area returns too few.
final class NearbySearch {
    record Hit(Place place, double meters) {}

    static final double EARTH_RADIUS_M = 6_371_000;
    static final double METERS_PER_DEGREE = 111_320; // one degree of latitude; longitude shrinks with cos(lat)
    static final int FINEST = 7;   // 153 m cells: finer only multiplies cells to read
    static final int COARSEST = 4; // about 20 km tall: coarser cells would scan whole regions

    private final Cells cells;

    NearbySearch(Cells cells) { this.cells = cells; }

    List<Hit> search(double lat, double lng, double radiusM, int limit, double maxRadiusM) {
        while (true) {
            int precision = precisionFor(lat, radiusM);
            int rings = (int) Math.ceil(radiusM / smallerSideM(lat, precision)); // 1 unless far north
            List<Hit> found = new ArrayList<>();
            for (String cell : block(Geohash.encode(lat, lng, precision), rings)) {
                for (Place p : cells.inCell(cell)) {
                    // The block is a rectangle bigger than the circle: the exact distance
                    // check drops its corners, so a cell is only ever a candidate filter.
                    double d = haversine(lat, lng, p.lat(), p.lng());
                    if (d <= radiusM) found.add(new Hit(p, d));
                }
            }
            // Sparse area: double the radius rather than return an empty page, up to a cap
            // the product sets. The response reports the radius actually used.
            if (found.size() >= limit || radiusM >= maxRadiusM) {
                found.sort(Comparator.comparingDouble(Hit::meters)); // deep dive 3 ranks by more than distance
                return found.subList(0, Math.min(limit, found.size()));
            }
            radiusM = Math.min(radiusM * 2, maxRadiusM);
        }
    }

    // The finest precision whose cell is at least the radius in both directions at this latitude.
    // Then one ring of neighbors (the 3 x 3 block) reaches a full radius past the user, wherever
    // in the cell they stand. Only a big radius far north needs more rings of coarsest cells.
    static int precisionFor(double lat, double radiusM) {
        for (int p = FINEST; p > COARSEST; p--) {
            if (smallerSideM(lat, p) >= radiusM) return p;
        }
        return COARSEST;
    }

    // Cells narrow with the cosine of latitude, so a table of sizes at the equator is not enough.
    static double smallerSideM(double lat, int precision) {
        int lngBits = (5 * precision + 1) / 2, latBits = 5 * precision / 2; // longitude gets the odd bit
        double heightM = 180.0 / (1L << latBits) * METERS_PER_DEGREE;
        double widthM = 360.0 / (1L << lngBits) * METERS_PER_DEGREE * Math.cos(Math.toRadians(lat));
        return Math.min(heightM, widthM);
    }

    // The user's cell and the rings of neighbors around it, found by stepping whole cells from the
    // center and encoding again. Prefixes cannot find neighbors: across an edge they may share nothing.
    static Set<String> block(String center, int rings) {
        Geohash.Box b = Geohash.bounds(center);
        double h = b.maxLat() - b.minLat(), w = b.maxLng() - b.minLng();
        double cLat = (b.minLat() + b.maxLat()) / 2, cLng = (b.minLng() + b.maxLng()) / 2;
        Set<String> cells = new LinkedHashSet<>(); // a set: near a pole two steps can land in one cell
        for (int dy = -rings; dy <= rings; dy++) {
            for (int dx = -rings; dx <= rings; dx++) {
                double y = cLat + dy * h;
                if (y > 90 || y < -90) continue;                        // nothing lies beyond a pole
                double x = cLng + dx * w;
                if (x > 180) x -= 360; else if (x < -180) x += 360;   // wrap across the antimeridian
                cells.add(Geohash.encode(y, x, center.length()));
            }
        }
        return cells;
    }

    // Great-circle distance. Flat-earth math is off by kilometers away from the equator.
    static double haversine(double lat1, double lng1, double lat2, double lng2) {
        double dLat = Math.toRadians(lat2 - lat1), dLng = Math.toRadians(lng2 - lng1);
        double a = Math.pow(Math.sin(dLat / 2), 2)
                + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * Math.pow(Math.sin(dLng / 2), 2);
        return 2 * EARTH_RADIUS_M * Math.asin(Math.sqrt(a));
    }
}

Proximity service · architecture

Trace a request: Search in a sparse area

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasionalHop in motionHops doneResponse

Search in a sparse area: step 1 of 6

Users to Load balancer

A 2 km search in rural Nebraska.

2 ms of a 100 ms budget

Users → Load balancer2 ms
Load balancer → Location service4 ms
Location service → Business service1 ms
Business service → Redis cluster1 ms
Business service → Read replicas5 ms
Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Geohash, quadtree, S2 or H3

Why a geohash? What about a quadtree, or what Google and Uber use?

Structure	How it works	Strengths	Weaknesses
Geohash	Alternating halvings, as letters	A sortable key for any index or cache	Fixed sizes; jumps at edges
Quadtree	Split a square in four until each part holds ≤ 100	Adapts to density; natural “nearest 20”	A pointer tree in one process; not a key
S2 (Google)	The sphere mapped onto a cube, 64-bit cell IDs	Little distortion; better neighbors	A library to adopt; hard to eyeball
H3 (Uber)	Hexagons covering the globe	Every neighbor equally far; great for areas	Small cells don’t nest exactly in big ones

For 200 million static points, any of them works. The geohash wins here because it’s a sortable key: the database column, the in-memory array and log lines all share it. Reach for S2 if the product adds shapes, like delivery zones, or needs accuracy near the poles. Reach for H3 when the job is counting points per area, like demand per hexagon.

The sorted array also blurs the line with quadtrees. Geohash order is a quadtree laid flat: every two bits split a cell into four, like one quadtree level. And counting the points in any cell is two binary searches. So the array gets a quadtree’s density awareness, without pointers or rebalancing.

Dense and empty areas, and ranking

Midtown Manhattan has thousands of restaurants within a few blocks. Rural Wyoming has three within 30 km. Does the same code serve both?

Wyoming has too few results, which expansion solves. Manhattan has too many. A 2 km search there can cover 50,000 candidates, and the 20 nearest are just whatever is on the user’s block.

So we count first. When the user doesn’t set a radius, start at 2 km. Halve it while the block holds more than about 5,000 businesses. Counting is just two binary searches per cell. Midtown lands near 250 m, a suburb stays at 2 km, and in Wyoming expansion takes over. When the user does set a radius, scan it all, but keep only the top 20 in a small heap. 50,000 candidates take about 2 ms.

Ranking blends three things:

Quality. A Bayesian average, which pulls a rating toward the global average until there are enough reviews. So one five-star review doesn’t beat 800 reviews averaging 4.6.
Distance. A score that fades with distance, so 200 m against 300 m matters little, and 200 m against 2 km matters a lot.
Fit. Category match, open now, and later personal signals.

Rating and review count live in the index entry, so ranking never waits for business details.

Go deeperCan you cache search results?1 min

Keyed by the exact location, almost never: nearly every search URL is unique. Keyed by cell, it would hit in dense cells. But the in-memory index already made the search about a millisecond. And business details are already cached per business, which is a better key, because one business appears in many cells’ results.

The textbook alternative, Redis keys holding each cell’s IDs, fits when the index is too big for one process. Here it would add 180,000 Redis reads a second (9 cells per search) for nothing.

A cache of ranked IDs per cell only earns its place if ranking becomes an expensive model call. Then snap the location to a cell about 150 m wide, cache the ranked IDs for a minute, and recompute distances for each user.

When things break

Interviewerminute 40

A search server restarts during the evening peak. What do users see?

What they are testing

Whether a restart is invisible: the others take the traffic, and the new one catches up before it serves.

A search server restarts. It holds nothing that isn’t on every other server. So the load balancer simply stops sending it searches, and the rest of the region absorbs them. On start, it downloads the latest snapshot, about 6.4 GB, and loads it into memory. Then it reads the change stream from the position recorded with that snapshot. So businesses added or closed since then are there too. Only then does it report ready and take searches. Users see nothing.

A bad snapshot. The index is derived data, so it can be wrong, not just down. A bad snapshot would make results vanish everywhere at once. So every snapshot is checked against yesterday’s (counts within 1%), loaded on one canary server first, and the last three are kept for rollback. A sudden jump in searches with zero results is the alarm.

If Kafka or the capture connector fails, search keeps working, but stops seeing new and closed businesses. Changes wait in the database’s log until it recovers, so watch that disk. And the next nightly snapshot corrects everything anyway, which is the “never more than a day late” promise.

Click any box to break it and see what users would notice:

Proximity service · architecture

Break it: what fails, who notices, what users see

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Break

Failure: click any box to break it

Kafka goes down

What breaks

Business changes stop reaching the location servers.

How we notice

Consumer lag, and the age of the newest applied change on each location server.

What users see

New, moved and closed businesses stop updating in search.

Everything else works.

What we do

Changes wait in the Postgres log until capture resumes, then flow in order.

If Kafka is down for days, the nightly snapshot still catches search up.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Every region. At ten times the traffic, half of it comes from Asia and Europe. A far region is 150 ms away, more than the whole budget. So each of three regions runs the full read path: location servers with the whole index, a Redis cluster, and Postgres replicas. The change topic is copied to every region, about a second behind. Owner edits, 12 a second, go to one home region. Nobody notices 150 ms on a form save. A region outage is a DNS change for search.

Proximity service · architecture

Stage 6: Every region

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Searches per second: 20,000

Stage 6 of 6

Every region

Why this stage

At 10 times the traffic one Redis node is 300% busy, a user in Sydney pays 150 ms to reach a US region, and one region is one failure domain against 99.99%.

What we add

The whole read path in each of three regions, Redis as a cluster, and geo DNS.

Writes stay in one home region.

What it costs

Changes take another second to reach far regions, and owner edits pause if the home region fails.

At 20k searches per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

How to read these numbers

These are rough planning figures for a large node of about 32 cores, not benchmarks.
Each could be off by 2 to 3 times without changing which box turns red.

What one machine can do

A location server handles about 5,000 searches a second, about 1 ms of CPU each for the index.
One Postgres node manages only a few hundred searches a second with two lat/lng indexes, because each search walks tens of thousands of index entries.
With a geohash index (nine short range scans) the same node manages about 2,000 searches a second.
It also does about 10,000 batched 20-id reads a second and 5,000 writes.
One Redis node handles about 100,000 requests a second.

Reads per search

Each search does one batched summary read. Half of searches also open a detail page, so there are 1.5 business reads per search.
Redis answers about 95% of them.
From stage 6, the largest region carries 40% of the traffic.

Go deeperEvery failure, and what users see1 min

Part	Failure	What users see	What we do
Location server	Crash	Nothing; the load balancer moves on	No state that isn’t on every other server
Business cache	Node down	Slower searches for seconds	Replica takes over; reads go to replicas
Postgres primary	Down	Owner edits fail for about 30 s	Failover; edits retry safely
Kafka or capture	Down	New and closed businesses don’t update	Changes wait in the log; nightly snapshot
Index builder	Fails	Nothing visible	Yesterday’s snapshot plus more changes
Bad snapshot	Wrong data	Missing results everywhere	Count checks, one canary, keep three
Whole region	Outage	DNS moves users in 1 to 2 minutes	Every region has the full index

Under stress, shed expansion rounds and the “open now” filter first, because search still answers without them.

What users can see. An owner sees their own edit at once. Others see business pages updated within a second, and search within seconds. When a result and its page disagree for a moment, the page wins.

Go deeperHow fresh each answer is1 min

Each path gets the weakest guarantee it can live with, and a number for how weak.

Operation	Guarantee	What users can see
Owner edit	Strong: commit on the primary, with a version	Two editors never overwrite each other; one gets `412`
Owner viewing own business	Reads from the primary for a minute	Their edit, at once
Business page for others	Usually under a second behind	Old opening hours, briefly
Search: new, moved, closed	Seconds; a minute at worst on a bad day; a day if the stream breaks	A closed business in results for a few seconds
Ratings used in ranking	Minutes behind	Ranking lags a burst of reviews
Pagination	Cursor on score and ID	No duplicates; a business added mid-way may be skipped

“Eventually consistent” without a bound promises nothing: a pipeline stuck for a week is still eventually consistent. So we state the bound and measure it. Each location server reports the commit time of the newest change it applied, and the gap to now is the freshness alert in “Running it”.

Go deeperRunning it: alerts, abuse and privacy1 min

Wake someone up when:

search success drops below 99.95% in a region
server p99 passes 100 ms
any location server’s newest applied change is more than 5 minutes old while the database is taking writes
the zero-result rate jumps

Abuse. A grid of nearby searches can download the whole directory. Limit requests per key and address, cap pages at a few hundred results, and flag keys whose searches tile a city.

Privacy. Search coordinates are location data. Log them snapped to a cell about a kilometer wide, not the exact point.

Deploys and cost. Location servers deploy to 1% of traffic for 15 minutes first, comparing p99 and the zero-result rate. The snapshot carries a format version, and servers read the old and new format for one release, so code and snapshot roll out separately. A new field in the index entry needs no database migration: the next snapshot carries it. Cost is mostly location server memory (64 GB machines, at least three per region, so one can fail during a deploy) and the Redis cluster.

Wrap up

The whole design

Here is everything we built, in the order we built it. Use the buttons to step through it.

Proximity service · architecture

The full design, stage by stage

Color keyServiceDatabaseCacheQueue or streamBackground workerNew in this stageAsync or occasional

Stage

Searches per second: 20,000

Stage 6 of 6

Every region

Why this stage

At 10 times the traffic one Redis node is 300% busy, a user in Sydney pays 150 ms to reach a US region, and one region is one failure domain against 99.99%.

What we add

The whole read path in each of three regions, Redis as a cluster, and geo DNS.

Writes stay in one home region.

What it costs

Changes take another second to reach far regions, and owner edits pause if the home region fails.

At 20k searches per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.The whole design. Step through it: one table, a geohash, the index in memory, cached details, a change stream, then every region.

The numbers behind the busy bars

How to read these numbers

These are rough planning figures for a large node of about 32 cores, not benchmarks.
Each could be off by 2 to 3 times without changing which box turns red.

What one machine can do

A location server handles about 5,000 searches a second, about 1 ms of CPU each for the index.
One Postgres node manages only a few hundred searches a second with two lat/lng indexes, because each search walks tens of thousands of index entries.
With a geohash index (nine short range scans) the same node manages about 2,000 searches a second.
It also does about 10,000 batched 20-id reads a second and 5,000 writes.
One Redis node handles about 100,000 requests a second.

Reads per search

Each search does one batched summary read. Half of searches also open a detail page, so there are 1.5 business reads per search.
Redis answers about 95% of them.
From stage 6, the largest region carries 40% of the traffic.

The decisions, and what each one costs

Decision	We chose	We gave up	We’d choose differently if
Spatial key	Geohash	Accuracy near the poles; shapes	We needed polygons (S2) or areas (H3)
Where it lives	The whole index in memory on every server	13 GB of memory per server	The index passed about 30 GB (split by region)
Freshness	Nightly snapshot plus a change stream	Kafka and a connector to run	“By tomorrow” were fine (snapshot only)
Details	A separate business service with a cache	One more service	Results were IDs only
Density	Count first, then choose the radius	The app must show the radius used	Density were even
Ranking	Distance and Bayesian rating, in the index	Fully personal ranking in v1	Text relevance mattered most
Regions	Reads everywhere, writes in one home region	Edits pause if the home region fails	Edits needed 99.99%

How to spend 45 minutes

0 to 4. Businesses, searches, freshness.
4 to 9. 20,000 searches a second, 12 writes, a 6.4 GB index: copy, don’t split.
9 to 20. Build it: why the plain query fails, the geohash, nine cells, the index in memory, cached details. A mid-level answer can stop here.
20 to 31. The stress tests: fresh changes, then the cell edge.
31 to 40. Other spatial indexes, then density and ranking.
40 to 45. A bad snapshot, regions, then your own questions.

Never skip the eight neighbors, the index size, or how changes reach search.

Follow-up questions

Interviewer asksWhat if the index grows to 2 billion entries?

At 64 GB it no longer fits twice on a server, so split it by geography. Each piece owns a set of geohash prefixes, sized by business count, not area: Manhattan is one piece, and Montana shares one. A router sends each search to the piece that owns the user’s cell, or to two at a border. Ten times the data means splitting. Ten times the traffic only means more servers.

Interviewer asksThe map view searches a rectangle, not a circle. What changes?

Nothing structural. Cover the rectangle with cells at a precision that fits its size, scan each cell’s slice, and filter by the rectangle instead of a distance. Very wide views show only the top-rated places, chosen from a coarser precision.

Go deeperMore follow-up questions1 min

Add a text query: ‘vegan ramen near me’. Matching words well is a search engine’s job. Use Elasticsearch or OpenSearch, with a location field and a distance filter, fed by the same change stream. For a fixed list of categories, our location service can filter by keyword IDs itself, and faster.

How does the ‘open now’ filter work across time zones? Hours are stored with the business’s own time zone, and “now” is worked out in that zone. The location service fetches extra candidates, say 60. It filters after the details arrive. If that isn’t enough in dense areas, add a small bit mask of the 168 hours in a week (21 bytes) to each index entry.

Now the points are drivers that report every 4 seconds. Does this design still work? No. A million drivers every 4 seconds is 250,000 writes a second. And a nightly snapshot of positions that change every few seconds means nothing. Keep sets per cell, updated in place and split by city. Drop drivers that stop reporting, and accept positions a few seconds old. The geohash and neighbor logic carry over. The storage and freshness plan do not. See ride-hailing.

What happens at the date line and at the poles? A user in Fiji at longitude 179.99 has neighbors at −179.99. The neighbor step wraps longitude across ±180, and the distance math is correct across the line. Near a pole, steps past 90° are skipped, and steps that land in the same cell are counted once.

How much memory would a quadtree take instead? Say there are at most 100 businesses per leaf. Then 200 million need about 2 million leaves, plus about 670,000 inner nodes. IDs take 1.6 GB, and the nodes under 100 MB. Building it takes minutes per server, so a quadtree design wants a prebuilt snapshot too.

Ratings change after every review. Does that churn the index? Ratings arrive through the same change stream, as a new state for the business. The review service updates a business’s rating at most once a minute, so a burst of reviews is one change, not hundreds.

Design a proximity service

The answer in one minute

Scope it

The numbers that decide it

Build the design

Step 1. One table, latitude and longitude

Stage 1: One server, one table

Why this stage

What we add

What it costs

Step 2. Index the location with a geohash

Stage 2: Index the location

Why this stage

What we add

What it costs

Step 3. Nine cells, not one

Step 4. The whole index, in memory, everywhere

Stage 3: Search in memory

Why this stage

What we add

What it costs

Step 5. Business details, separately

Stage 4: Cache business details

Why this stage

What we add

What it costs

Trace a request: Search, cache miss

Stress it

Changes in seconds, not a day

Stage 5: Changes in minutes

Why this stage

What we add

What it costs

Trace a request: Owner adds a business

The edge of the cell

Trace a request: Search in a sparse area

Geohash, quadtree, S2 or H3

Dense and empty areas, and ranking

When things break

Break it: what fails, who notices, what users see

What breaks

How we notice

What users see

What we do

Stage 6: Every region

Why this stage

What we add

What it costs

Wrap up

The whole design

The full design, stage by stage

Why this stage

What we add

What it costs

The decisions, and what each one costs

How to spend 45 minutes

Follow-up questions

Further reading

Keep reading

The designbeyondcode digest, every Saturday