Appearance
11.17 — Proximity Service
"Coffee near me." Two hundred million businesses in the world, and the system has 200 milliseconds to find the twenty that matter.
This looks identical to 11.10. Same geometry, same cells, same "find things near a point". It is architecturally the mirror image, and understanding why is the point of the study.
There, a million drivers each reported a new position every four seconds — 250,000 writes a second against 5,000 queries. Here, businesses barely change: perhaps a hundred edits a second against 25,000 searches. Same shape, inverted ratio, opposite design. Ride hailing keeps everything volatile in memory and never writes to disk on the hot path. This one precomputes the index offline, ships it as an immutable snapshot, and caches nearly everything.
Getting that inversion out loud in the first two minutes is what makes the rest of the design look inevitable rather than invented.
1. Requirements
Functional. Find businesses within a radius of a point. Filter by category, rating, price, and whether they are open now. Sort by distance or by relevance. Business detail pages. Reviews and ratings.
Non-functional, with numbers.
- Search p99 under 200 ms.
- 200 million businesses globally.
- Results may be minutes stale. A restaurant changing its opening hours does not need to propagate in real time, and this single admission is what unlocks precomputation.
- 99.99% availability.
Out of scope today: the ranking model beyond the basics (11.20), review moderation, and advertising.
The clarifying questions, and what each answer changes
"How often does the data change?" This is the whole design. A hundred edits a second means the index can be built offline and treated as immutable. A hundred thousand means you are building the ride-hailing system instead, and everything below is wrong.
"How stale may a result be?" Minutes buys you an offline rebuild and aggressive caching. Seconds does not, and it should be resisted, because nobody is harmed by a newly opened café appearing four minutes late.
"How many results does a search return, and does anyone page past the first screen?" Twenty results and almost nobody paging deeply means you can cap candidate work aggressively and stop early. If people genuinely scroll to result three hundred, the expansion logic gets much harder.
"Which filters are common?" Category and open-now dominate real traffic by a wide margin. Knowing that in advance is what justifies precomputing filter indexes for those two and not for the other fifteen.
"How concentrated are the queries?" Extremely — a small number of places generate most searches. That concentration is what makes result caching effective, and it is worth confirming rather than assuming.
2. Estimation
Business data. 200 million businesses × ~2 KB of detail = 400 GB. What that forces: the full records live in an ordinary store and are fetched only for the results actually shown. Nothing about the search path touches 400 GB.
The spatial index, which is the number that matters. An identifier plus a cell reference is about 30 bytes: 200 million × 30 B = 6 GB. What that forces: the entire index of every business on earth fits in memory on one large machine, and comfortably across a few. That is what makes a memory-resident, immutable, hot-swapped index affordable — and it is the single fact the architecture rests on.
Read volume. 500 million searches a day ÷ 86,400 ≈ 5,800 a second average, ~25,000 at peak.
Write volume. Business edits — new opening hours, a closure, a new listing — perhaps 100 a second. What that forces: a 250:1 read-to-write ratio, and therefore a design where reads never touch the write path at all. Compare the same two numbers in 11.10: 250,000 writes against 5,000 reads. Identical geometry, opposite ratio, opposite architecture.
Candidates per query. With cells sized to hold tens to hundreds of businesses, a nine-cell cover returns a few hundred candidates in an average area. What that forces: a few hundred distance calculations is microseconds of work. The problem is that this number is not stable — a dense city centre can return five thousand from the same nine cells, and section 6.3 is entirely about that skew.
Cache key space. Raw coordinates are effectively unbounded, so a result cache keyed on them has a hit rate of approximately zero. Snapping coordinates to a grid of, say, 100 metres turns a city into a few tens of thousands of distinct keys. What that forces: the single highest-value trick in this design, worth more than any algorithmic improvement — section 6.2.
3. API
http
GET /search?lat=51.5211&lng=-0.1339&radius=2000
&category=cafe&openNow=true&minRating=4
&sort=relevance&cursor=&limit=20http
200 OK
Cache-Control: public, max-age=120
{ "results": [
{ "id": "biz_8821", "name": "…", "distanceMeters": 210,
"rating": 4.6, "priceLevel": 2, "openNow": true } ],
"nextCursor": "eyJkIjoyMTB9",
"snappedTo": { "lat": 51.5210, "lng": -0.1340 },
"candidatesConsidered": 412,
"expandedRings": 1 }http
GET /businesses/biz_8821
POST /businesses/biz_8821/reviewssnappedTo is honest about what happened. The service rounded the caller's coordinates to a grid before answering, which is what makes the response cacheable. Saying so in the response means a client that genuinely needs metre-level precision knows it did not get it, rather than silently assuming it did.
candidatesConsidered and expandedRings are diagnostic fields that earn their place. Section 6.3's density problem is invisible in aggregate latency and immediately obvious when you plot latency against candidate count. Putting the number in the response is how it reaches the logs at all.
Cursor pagination on distance, not offset. The result set is stable for the life of a snapshot, so an offset would work — but distance is already the sort key, and a cursor encoding the last distance seen costs nothing and survives a snapshot swap mid-scroll.
Cache-Control: public, which is only possible because there is no user identifier in the request. Personalised results would make every response unique, and the edge cache — the thing absorbing the concentrated head of the query distribution — would stop working entirely.
4. Data model
businesses -- the full records, ~400 GB
business_id UUID PRIMARY KEY
name, address, phone, url
lat, lng DOUBLE PRECISION
category_ids INT[]
price_level SMALLINT
rating_avg REAL, rating_count INT
timezone TEXT -- IANA name, for open-now
hours JSONB -- regular weekly schedule
exceptions JSONB -- holidays, temporary closures
state SMALLINT -- active | closed | pending
-- the spatial index, built offline, held in memory:
cell_index cell_id → [ business_id, … ] -- ~6 GB total
biz_meta business_id → { lat, lng, cats, rating, price, openBits }
open_bits business_id → 168-bit mask -- one bit per hour of the week
reviews
review_id, business_id, user_id, rating, body, created_atAccess patterns:
| Query | Frequency | Returns |
|---|---|---|
| Read the business lists for a set of cells | 25,000/s peak | a few hundred ids |
| Read compact metadata for candidates | 25,000/s × hundreds | small records |
| Fetch full records for the returned page | 25,000/s × 20 | 20 rows |
| Write a business edit | ~100/s | one row |
| Rebuild the index | every few hours | the whole thing |
The index holds identifiers and compact metadata, never full records. This is the split that keeps 6 GB in memory instead of 400 GB: filtering and ranking need a category list, a rating and a coordinate, and nothing else. The name, address and photographs are fetched only for the twenty results actually returned — which is section 6.4's deferred hydration, and frequently the largest single latency win available in a badly built version of this system.
open_bits is a 168-bit mask, one bit per hour of the week. Evaluating "is this open now?" from a schedule means parsing hours, applying a timezone, checking day boundaries and handling a closing time after midnight — per candidate, hundreds of times per query. A bit test is one operation. Section 6.5 covers the exceptions this does not handle.
timezone is an IANA name, not an offset, for the same reason as in 11.6: an offset is wrong for half the year in most of the world, so open-now would silently shift by an hour twice a year.
5. Indexing space, and the four options
| Approach | How it works | Verdict |
|---|---|---|
| Separate indexes on latitude and longitude | intersect two range scans | poor — two huge candidate sets, tiny intersection, and a "box" is a wildly different area near the poles |
| Text prefix on an encoded position | nearby points share a prefix | workable, but adjacent cells can differ entirely in prefix, so neighbours must always be queried explicitly |
| Recursive subdivision by density | split a cell when it gets crowded | good for skewed data; built in memory, rebuilt offline |
| Sphere-aware hierarchical cells | cells defined on the sphere at many resolutions, with a neighbour operation | best — no pole distortion, near-uniform areas, adjacency as a primitive |
Choose the sphere-aware hierarchical scheme. The two widely used ones divide the globe into cells at many resolutions — one using hexagons, one using squares projected from a cube — and both give you the two operations that matter: "which cell contains this point at resolution r" and "which cells are adjacent to this one". That second operation is the thing you are actually shopping for, and its absence is why prefix matching alone is wrong.
Pick a resolution where a typical cell holds tens to hundreds of businesses.
Why the exact distance filter is not optional. A cell that overlaps the circle's edge contains points outside the radius. Returning cell members directly would return results that are simply not within the distance the user asked for — and the error is worst exactly where it is most visible, at the edge of a small radius in a dense area.
6. Architecture
The index is an immutable versioned snapshot, hot-swapped. Same discipline as 11.11: a node loads the new index alongside the old, verifies it, flips a pointer, and rollback is flipping back. No locks on the read path and no rebuild pause.
A delta overlay carries recent edits, merged at query time. A newly opened business appears within minutes rather than waiting for the next full rebuild. This is the slow-base-plus-fast-delta shape that appears in 11.11 and 11.12 for the same reason.
Sharding is geographic. One index shard per region, with the router choosing shards from the query's cell cover. A query near a shard boundary reads two shards and merges, which is rare and cheap. The alternative — hashing business identifiers across shards — would make every query fan out to every shard, which is exactly the cost that geographic locality exists to avoid.
7. Deep dives
7.1 Why the ratio, not the geometry, chose this design
The comparison with 11.10 is worth making explicit, because the two systems share a data structure and share almost nothing else.
Ride hailing: 250,000 writes a second, 5,000 reads. State changes constantly, so it lives in a volatile in-memory structure updated in place, is never written to disk on the hot path, and is designed to be lost — it rebuilds in one ping interval, and durability would cost more than it is worth. Caching is impossible, because a cached driver position is wrong before it is stored.
Proximity search: 100 writes a second, 25,000 reads. The data is effectively static, which unlocks a completely different set of moves — precompute offline, ship an immutable snapshot, swap it without locking, and cache results aggressively because they are stable.
What a stale answer costs differs too. A stale driver position produces a bad match, which is a real failure. A stale business record shows yesterday's opening hours, which is a minor annoyance — and that is precisely why "minutes stale" is in the requirements and why that one line authorises half of this design.
And the queries differ in shape. Ride hailing asks for the nearest few available drivers right now, on volatile data. Proximity search asks for everything within a radius matching several filters, ranked and paginated — bigger result sets, complex filtering, which pushes effort into filter indexes and result caching rather than into write throughput.
7.2 Snapping coordinates, the single highest-value trick
A phone reports a position with more precision than anyone can use. Two searches from opposite ends of the same café produce different coordinates, so a result cache keyed on raw coordinates never gets a hit.
Round the coordinates to a grid before doing anything else. A hundred-metre grid turns a city into tens of thousands of distinct keys instead of billions, and takes the cache hit rate from approximately zero to around ninety per cent.
The cost is tens of metres of precision, which nobody perceives when the results are ranked by distance anyway and the nearest café is 200 metres away. The benefit is that the concentrated head of the query distribution — and human location queries are extraordinarily concentrated, with a small number of places generating most searches — is answered from cache without touching your servers at all.
Snap consistently and snap early, at the edge, so that the cache key and the query both derive from the same rounded value. Snapping inside the service after the cache lookup gets you the precision loss without the cache benefit.
7.3 Density skew, which is the real difficulty
A cell resolution tuned for average density fails at both ends. In a city centre a single cell holds thousands of businesses, so a nine-cell cover returns tens of thousands of candidates and every downstream step — distance, filters, ranking — scales linearly with that number. In a rural area the same cells hold nothing, so the search expands ring after ring, issuing many lookups to find five results.
Two complementary fixes, and they attack different halves.
Hierarchical resolution. Index at several resolutions, and choose per query based on the cell's known population. Dense areas query fine cells and get small candidate sets; sparse areas query coarse cells and get few lookups. This is the structural fix, and it targets the cause directly.
Candidate caps with early termination. For a "nearest twenty" query, walk cells outward from the centre and stop as soon as twenty results survive filtering. In a dense area this terminates almost immediately, which converts the worst case into the best case — the density that made the query expensive is the same density that lets it finish early.
The general lesson, and it applies well beyond maps: an algorithm tuned for average data density has a worst case proportional to the skew, and geographic, social and commercial data are all severely skewed. The design must adapt its resolution to local density, and the monitoring must carry the skew as a dimension — otherwise the system works fine on average and badly exactly where the users are.
7.4 Filters have to apply during expansion, not after
"Cafés open now with four stars or better" may match nothing in the initial cell cover, even in a busy area.
If filters are applied after expansion finishes, the sequence is: expand, materialise five thousand candidates, filter down to zero, expand again, materialise fifteen thousand, filter to two. The expensive part is repeated with a larger set each time.
Applying filters during expansion means each ring contributes only its surviving candidates, and the termination condition — enough results — is evaluated against filtered counts. The work is proportional to what you keep rather than to what you looked at.
Precomputing the common filter combinations takes this further. Category and open-now dominate real traffic, so maintaining a separate list per category per cell, and an hourly open-now bitmap, turns filtering from a per-candidate predicate into a set intersection. It costs memory, and it is worth it for the two or three filters that carry most of the traffic and for nothing else.
7.5 Open-now is harder than it looks
It depends on the business's timezone, not the user's. It depends on the day of the week. It depends on closing times after midnight, which belong to the previous day's schedule. It depends on public holidays, which differ by country and region. And it depends on temporary closures, which are the most common edit of all.
Precompute a 168-bit mask per business — one bit per hour of the week, in the business's own timezone — so the check during a query is a single bit test rather than a schedule evaluation repeated for hundreds of candidates.
Handle exceptions as a small override layer rather than by baking them into the mask: holidays and temporary closures are sparse, they change often, and they belong in the delta overlay where they can take effect in minutes.
And accept a known limit: the bitmap has hour granularity, so a place closing at 17:30 is shown as open until 18:00. That is a deliberate trade, it should be recorded, and the fix — half-hour granularity at 336 bits — is available if anyone complains.
7.6 Deferred hydration
The index holds identifiers and thirty bytes of metadata. Everything else — name, address, photographs, description, review snippets — lives in the business store and is fetched only for the twenty results being returned.
This sounds obvious and is one of the most common performance defects in a real implementation of this system. Hydrating every candidate before ranking means fetching two kilobytes for each of five hundred businesses, then discarding 96% of it. In a dense area that is megabytes of I/O per query for data nobody sees, and it will dominate the latency profile completely.
Rank on the compact metadata; hydrate the page. That ordering is the whole optimisation.
8. Decision Ledger
| Decision | Alternatives | Why this | What it costs |
|---|---|---|---|
| Sphere-aware hierarchical cells | separate lat/lng indexes; text prefixes; density subdivision | no pole distortion, near-uniform areas, and adjacency as a primitive operation | a scheme and a resolution policy to understand |
| Cell cover, then exact distance | trust the cell boundary | a cover over-approximates by construction, so the radius must be enforced afterwards | one extra pass, on a few hundred items |
| Immutable snapshots plus a delta overlay | a live-updating index | lock-free reads, rollback by pointer flip, cheap rebuilds | minutes of staleness, which the requirements authorised |
| Geographic sharding | hash business ids across shards | a query touches one or two shards instead of all of them | dense regions need finer sharding; boundary queries merge |
| Snap coordinates for cache keys | use exact coordinates | takes the hit rate from ~0% to ~90% | tens of metres of precision nobody perceives |
| Index holds ids and 30 bytes | index holds full records | 6 GB in memory instead of 400 GB | a second fetch for the returned page |
| Hourly open-now bitmaps | evaluate the schedule per candidate | one bit test instead of timezone and date arithmetic, hundreds of times per query | hour granularity; exceptions need an override layer |
| Filters applied during expansion | filter after expanding | work is proportional to what you keep, not what you looked at | expansion logic is more complex |
9. Scale and failure
At 10×, shard dense regions more finely — the skew is geographic, so the sharding should be too — add read replicas per region, and push snapped-coordinate results to the edge. And the observation worth making explicitly in an interview: because the write rate is negligible, there is no write-scaling problem here at all. That is the structural difference from 11.10, and saying it demonstrates you are reasoning from the ratio rather than from the map.
| What breaks | Blast radius | How you find out | What keeps it running | Recovery |
|---|---|---|---|---|
| One index shard down | that region's searches | shard error rate | serve from a replica, or degrade to a coarser index with a wider radius | restore; the snapshot is immutable so nothing is lost |
| Rebuild pipeline broken | results freeze, silently | snapshot age alarm | stale results are wrong-ish, never broken | fix the pipeline; the next build catches up |
| Delta overlay stalled | new listings and closures stop appearing | delta lag, measured separately from snapshot age | the base snapshot still answers everything | restart; the overlay refills in minutes |
| Bad snapshot promoted | everyone, immediately | canary queries over a fixed panel of locations | the canary blocks promotion; versions are immutable | flip the pointer back — seconds |
| A dense-area query explodes | the users in the busiest places | latency plotted against candidatesConsidered | candidate caps and early termination | hierarchical resolution; finer shards there |
| Edge cache cold after a snapshot swap | a brief origin spike | origin request rate | version the cache key so the swap invalidates cleanly | it refills within minutes |
| Hydration fetching all candidates | every query in dense areas | bytes fetched per query | rank on metadata, hydrate the page only | a code fix, and usually a large win |
Two of these produce no errors at all. A broken rebuild pipeline and a stalled delta overlay both leave a system that answers every query successfully with increasingly old data. The only signals are snapshot age and delta lag, measured separately, because they fail independently and the second is the one users notice first (10.10).
What the interviewer will push on
"This looks exactly like the ride-hailing design. Why is it different?" Because the ratio is inverted and the ratio decides the architecture. There: 250,000 writes against 5,000 reads, so state is volatile, in memory, never on disk, designed to be lost, and uncacheable. Here: 100 writes against 25,000 reads, so the index is precomputed offline, immutable, hot-swapped, and cached aggressively. Then add the two secondary differences — what a stale answer costs, and the query shape — and close with the general point: the map is a red herring, always derive from the ratio, the staleness tolerance and the query shape.
"Why not index latitude and longitude separately?" Two reasons, and the second one is the tell. It is inefficient — two enormous range scans with a tiny intersection, and most engines will only use one of the indexes effectively anyway. And it is geometrically wrong: a degree of longitude is about 111 km at the equator and near zero at the poles, so a fixed coordinate box is a wildly different physical area depending on where you are, and it breaks entirely where longitude wraps.
"Your cell cover returns the results. Why filter again?" Because a cover is an over-approximation by construction — a cell overlapping the circle's edge contains points outside the radius. Skipping the exact distance filter returns results that are simply not within the distance requested, and the error is most visible exactly where users notice, at the edge of a small radius.
"Searches in city centres are ten times slower and adding servers has not helped. Why?" The "adding servers has not helped" is the diagnostic: the bottleneck is per-request work, not capacity, so scaling out multiplies the same slow request. The cause is density skew, confirmed by plotting latency against candidate count. The fixes in order: hierarchical resolution, candidate caps with early termination, filters during expansion, and — check this first, because it is often most of the latency — whether the code is hydrating every candidate before ranking instead of only the returned page.
"How would you cache this?" The trap is to say "cache the results" without addressing the key. Raw coordinates are effectively unbounded, so the hit rate is zero. Snapping to a grid before the cache lookup turns a city into tens of thousands of keys and takes the hit rate to around ninety per cent, at the cost of precision nobody perceives. And the reason it works at all is that human location queries are extraordinarily concentrated.
"Is this business open right now?" Harder than it sounds: the business's timezone rather than the user's, closing times after midnight belonging to the previous day, holidays that differ by region, and temporary closures. The design answer is a 168-bit hourly mask so the query-time check is a bit test, with exceptions in the delta overlay where they can take effect in minutes — plus the honest admission that hour granularity means a 17:30 closure shows as open until 18:00.
Volunteer this, because nobody asks: put candidatesConsidered in the response and in the logs. Density skew is completely invisible in an aggregate latency percentile — the median query is fast, and the users in the busiest, most valuable locations are the ones having a bad time. The moment you can plot latency against candidate count, the whole class of problem becomes obvious in one chart, and it stops being something you learn about from a complaint.
Next: 11.18 — from a question about where things are to a question about when things run: a million timers that must fire once, on time, and exactly once, even when the machine holding them dies.
Recall
- Same geometry as 11.10, inverted ratio — 250:1 reads here against write-dominated there — and therefore the opposite design: precomputed immutable indexes, aggressive caching, offline rebuilds, and no volatile write path at all.
- The number that permits it: the spatial index is identifiers plus ~30 bytes each = 6 GB for 200 million businesses, so it fits in memory. Full records (400 GB) are fetched only for the page returned.
- Sphere-aware hierarchical cells, because the operation you actually need is adjacency. Query = cover the circle → read those cells → exact distance filter (the cover over-approximates on purpose) → attribute filters → rank → hydrate twenty.
- Snap coordinates to a grid before caching. Unbounded coordinate pairs become tens of thousands of keys: hit rate goes from ~0% to ~90% for precision nobody perceives. Snap at the edge, before the lookup.
- Density skew is the real difficulty: hierarchical resolutions chosen by cell population, plus candidate caps with early termination so a dense area's worst case becomes its best case.
- Filters apply during expansion, not after, or you expand, materialise thousands, filter to zero, and expand again with a larger set.
- Open-now is a 168-bit hourly mask in the business's own IANA timezone, with holidays and closures as an override layer. Hour granularity is a stated trade.
- Immutable snapshots plus a delta overlay, geographic sharding (one or two shards per query rather than a full fan-out), and separate alarms on snapshot age and delta lag — both failures are silent.
Self-test: Why does the read/write ratio flip the design compared with ride hailing? Why must exact distance be recomputed after the cell cover? What single change makes results cacheable, and why does it work? Name the two fixes for density skew. Why must filters run during expansion?
Quiz Bank
FoundationalWhy not just index latitude and longitude separately?
Because a two-dimensional range query decomposed into two one-dimensional scans is both inefficient and geometrically wrong.
Inefficient. The engine scans everything in a latitude band — a strip circling the globe — and everything in a longitude band — a strip running pole to pole — and then intersects two enormous candidate sets whose intersection is tiny. Nearly all of the work is discarded. In practice most engines can only use one of the two indexes effectively anyway, so it degenerates into a scan plus a filter.
Geometrically wrong. A degree of longitude is about 111 km at the equator and approaches zero at the poles. A fixed coordinate box is therefore a wildly different physical area depending on where you are, so a "10 km box" computed naively returns far too much near the poles — and it breaks entirely near the antimeridian, where longitude wraps and a range query on the raw value covers the wrong half of the world.
The alternative is a structure that maps two dimensions onto one while preserving locality. Encoding a position as text so that nearby points share a prefix is simple and workable, but it has a boundary problem: two points ten metres apart on opposite sides of a cell edge can have completely different prefixes, so neighbouring cells must always be queried explicitly. Recursive subdivision adapts well to skewed data. And sphere-aware hierarchical cells are the practical best — defined on the sphere rather than on a projected plane so there is no pole distortion, cells of near-uniform area, and hierarchy and adjacency available as built-in operations.
The query then becomes: cover the circle with cells, read those cells' candidate lists, filter by exact distance. That last step is essential rather than optional, because any cell cover over-approximates the circle — cells that overlap the boundary contain points outside the radius. Returning cell members directly would return results that are not within the distance the user asked for, and the error concentrates exactly where it is most noticeable.
InterviewThis looks exactly like the ride-hailing design. Why is the architecture different?
Because the read-to-write ratio is inverted, and the ratio — not the geometry — determines the architecture.
Ride hailing takes 250,000 location writes a second against roughly 5,000 queries. The state changes constantly, so it must live in a volatile in-memory structure updated in place, must never be written to disk on the hot path, and is deliberately designed to be lost — it rebuilds within one ping interval, so durability would cost more than it is worth. Nothing about it is cacheable, because a cached driver position is stale before it is stored.
Proximity search takes about 100 business edits a second against 25,000 queries. The data is effectively static, which unlocks a completely different set of moves: precompute the index offline, ship it as an immutable versioned snapshot, hot-swap it with no locking on the read path, cache results aggressively — which is only possible because they are stable — and add a small delta overlay for recent edits rather than accepting mutation into the main structure.
The second structural difference is what a stale answer costs. A stale driver position produces a bad match, which is a genuine failure. A stale business record shows yesterday's opening hours, which is a mild annoyance. That is exactly why "results may be minutes stale" is in the requirements here and would be unacceptable there, and that single line authorises half of this design.
The third is query shape. Ride hailing asks for the nearest few available drivers right now — a small-result query over volatile data. Proximity search asks for everything within a radius matching several filters, ranked and paginated — larger result sets, complex filtering, and pagination. That pushes effort into filter indexes and result caching rather than into write throughput, which is a completely different set of engineering problems even though both start by covering a circle with cells.
The answer that shows judgement: the map is a red herring. Derive the architecture from the read-to-write ratio, the staleness tolerance and the query shape. Two systems can share a data structure and share almost nothing else.
StaffSearches in dense urban areas are ten times slower than elsewhere, and adding servers has not helped. Diagnose and fix.
"Adding servers has not helped" is the most useful clue in the question. It means the bottleneck is per-request work, not throughput capacity, so scaling out simply multiplies the same slow request rather than relieving it. That single observation eliminates half the possible causes before you look at anything.
The cause is density skew. At a fixed cell resolution tuned for average density, a city-centre cell holds thousands of businesses rather than tens. The query returns a huge candidate set, and everything downstream scales linearly with it: distance calculation for every candidate, attribute filtering, ranking, and — often the worst offender — fetching full records. A hundred-fold density difference produces something close to a hundred-fold latency difference, and no amount of horizontal scaling touches it.
Confirm it in one chart. Instrument candidate count per query and plot latency against it. The correlation is immediate, and it shows the same code path behaving completely differently by geography. The fact that this needed a user complaint rather than a dashboard is itself a finding: an aggregate latency percentile hides a geographically segmented problem completely, because the median query is in a normal-density area (10.10).
The fixes, in order of impact.
Check hydration first, because it is often most of the latency and it is a small change. If the code fetches full business records for every candidate before ranking, a dense-area query is pulling megabytes to discard 96% of it. Rank on the compact metadata and hydrate only the page being returned.
Hierarchical resolution. Index at several resolutions and choose per query based on each cell's known population. Dense areas use fine cells and get small candidate sets; sparse areas use coarse cells and need fewer lookups. This is the structural fix and it addresses the cause directly.
Candidate caps with early termination. For a "nearest twenty" query, walk cells outward and stop as soon as twenty results survive filtering. In a dense area that terminates almost immediately, which converts the worst case into the best case — the density that made the query expensive is the same density that lets it finish early.
Apply filters during expansion rather than after, so a filtered query in a dense area never materialises thousands of candidates only to discard them.
Precompute the dominant filter combinations — category and open-now carry most real traffic — so filtering becomes a set intersection instead of a per-candidate predicate.
Cache hardest where it hurts most. Dense areas are also the most repeated queries, so snapped-coordinate result caching has its highest hit rate exactly where queries are most expensive. That is the cheapest immediate mitigation while the structural fixes land.
The generalisation worth stating: any algorithm tuned for average data density has a worst case proportional to the skew, and geographic, social and commercial data are all severely skewed. The design must adapt its resolution to local density, and the monitoring must carry the skew as a dimension — otherwise the system works fine on average and badly exactly where the users are.
Flashcards
FlashThe ratio flips the design
Ride hailing: 250,000 writes a second, volatile memory, nothing cacheable. Proximity: 250:1 reads, immutable precomputed snapshots, cache almost everything. Same geometry; the ratio decides.
FlashThe query pipeline
Cover the circle with cells (an over-approximation) → read candidate ids → exact distance filter → attribute filters → rank → fetch full records for the twenty returned only.
FlashWhat makes it cacheable
Snap coordinates to a grid at the edge, before the lookup. Unbounded coordinate pairs become tens of thousands of keys, taking the hit rate from ~0% to ~90% for precision nobody perceives.
FlashDensity skew
A fixed resolution gives thousands of candidates downtown or many empty rings rurally. Fix with hierarchical resolutions chosen by cell population, plus candidate caps with early termination.
FlashOpen now
A 168-bit hourly mask per business in its own IANA timezone, so the check is a bit test rather than timezone arithmetic per candidate. Holidays and closures go in the delta overlay. Hour granularity is a stated trade.
FlashThe two silent failures
A broken rebuild pipeline and a stalled delta overlay both answer every query successfully with old data. Alarm on snapshot age and delta lag separately, because they fail independently.
Scenario Drill
DrillAdd search along a route: find fuel and coffee within a five-minute detour of a 400 km drive. What breaks, and what is the right structure?
What breaks is that the query is no longer a circle. Every structure in section 5 answers "within radius R of a point". A route is a polyline hundreds of kilometres long whose relevant region is a narrow corridor. Approximating it with one enormous circle returns a country's worth of candidates; approximating it with a circle at every route point issues thousands of queries and returns massive duplication.
The right structure is to cover the route rather than the points. Compute the cell cover of a buffered polyline — the hierarchical cell schemes support covering an arbitrary region directly — so a corridor of a given width around the route becomes a deduplicated set of cells, at a resolution chosen from the corridor width rather than from a search radius. That is one covering operation and one batched candidate fetch, regardless of how long the route is.
And then the correction that matters most: "five-minute detour" is not "within two kilometres". Distance to the route line is a poor proxy. A fuel station 200 metres away across a motorway, with the next exit eight kilometres ahead, is a fifteen-minute detour. One three kilometres further along, directly on the route, is a two-minute one.
Correct evaluation is detour time = (route to candidate) + (candidate back to route) − (the route segment bypassed), which requires the routing engine rather than geometry.
So the pipeline becomes cheap-wide-generation followed by expensive-narrow-scoring: geometric candidate generation deliberately over-produces, the candidate count is capped, and only then does routing-based detour scoring run. That is the same shape as retrieval-then-ranking in 11.20, and it is the standard answer whenever the true scoring function is too expensive to apply broadly.
Two requirements the naive design misses.
Position along the route matters as much as proximity. A coffee shop 380 km into the drive is useless to someone deciding now, so results rank on a combination of detour cost and estimated arrival time at that point, and the query is usually anchored to a window ahead of the current position rather than to the whole route.
Direction matters. On a divided highway, a station on the opposite carriageway may be effectively unreachable. Geometry cannot see that and routing can, which is another reason the expensive stage is not optional.
Caching changes shape too, and this is the interesting part. Exact routes are nearly unique, so caching at the route level is useless. But the cell-level candidate lists are highly cacheable and shared across every route passing through that area, so the cache moves one layer down. That is the general fix whenever the query is unique but its components are not, and it is worth recognising as a pattern rather than as a trick.
The sentence for the design document: route search is corridor covering plus routing-aware scoring — geometry generates candidates and the routing engine ranks them — and any design that answers a time-based question with a distance-based index will be confidently wrong in exactly the cases drivers care about.