Design a proximity service

Do the numbers before the boxes

An interviewer gives a scale, not a load. If we draw before we do the math, we cannot say why any box has its size.

We assume about 52 million daily users in our first country, at 5 searches per user a day: 260 million searches a day.

260,000,000 / 86,400 = about 3,000 searches a second on average. The lunch peak is twice that, our assumption: 6,000.

Later we grow 5 times across the region's countries: 15,000 searches a second on average, 30,000 at the peak.

There are 100 million businesses worldwide, about 1 KB a row: about 100 GB, or 120 GB with indexes.

Owners edit about 4 times a year: 100,000,000 x 4 / 31,500,000 seconds = about 13 edits a second worldwide.

So the service is read-heavy and write-light: thousands of searches against 13 writes a second.

Check in: Close the page and derive the first peak, and the edit rate.

Turn a point into a few keys

A database cannot ask "what is near this point" quickly without an index built for it. We need a way to turn a point into a few lookups.

A geohash splits the world into cells and names each with a string. Its length is the precision: each extra character is a smaller cell inside the last.

So a cell is a string prefix: one string serves as an index range in the database and as a cache key.

Cells are rectangles, not squares. At 45 degrees a precision-5 cell is about 3.46 km east-west by 4.89 km north-south.

Precision 6 is about 0.86 x 0.61 km, and precision 7 about 0.11 x 0.15 km.

Two points a metre apart can sit in different cells. So a search reads its cell and the 8 neighbours, and exact distance trims the corners.

Nine cells cover a radius up to the cell's shorter side: 3.46 km, 0.61 km and 0.11 km. Between precisions the over-fetch is large: 1 km at precision 5 reads about 50 times the circle.

Other indexes: a quadtree splits a cell until it holds about 100 businesses, so dense cities get small cells.

S2 covers a circle with a few cells of mixed size, so it reads little extra. H3 uses hexagons with 6 neighbours at equal distance.

PostGIS, a geographic extension, could do the radius inside the database. We use geohash because the same cell string becomes the cache key later.

Cells narrow towards the poles and wrap at the 180th meridian, so use a library for neighbours.

Step through the figure to see the cell, its neighbours, and how a search widens.

The trade-off:

Geohash is simple and cache-friendly. In exchange, a circle is covered by squares, so every search reads some ground it did not ask for.

A point, its cell, and its neighbours

1. A geohash names each cell with a string. A longer string is a smaller cell inside the shorter one.
2. Close points can sit in different cells, so a search reads its cell and the 8 around it. Exact distance trims the corners.
3. Cells are rectangles. At 45 degrees a precision-5 cell is about 3.46 by 4.89 km. Precision 6 is about 0.86 by 0.61 km, and precision 7 about 0.11 by 0.15 km.
4. The service uses the finer of two precisions: the finest whose 9 cells cover the radius, and the density precision at the user's point. Density precision is 5 if the precision-5 cell holds up to about 600 businesses, else 6 if the point's precision-6 cell does, else 7.
5. If fewer than 20 match, it reads the next ring, then the next, at most 3 rings. Then it answers with what it found and how far it looked.

Check in: Why read 9 cells and not just the one the user is in?

Every search queries the database

The simplest answer is one SQL statement a search. It reads the 9 cells by an index on the geohash, filters by distance, ranks, and returns 20 rows.

A stateless location service (LBS) builds the query. It takes about 2 ms of CPU a search, our estimate: 500 a second a task.

6,000 / (500 x 0.7) = 17.1, so 18 tasks at a 70% target, 66.7%.

The database is Aurora. A writer takes the rare edits, and readers, copies of it, serve the reads.

A search costs about 5 ms of reader CPU, our estimate: 1,600 a second per 8-vCPU reader. 6,000 / (1,600 x 0.7) = 5.4, so 6 readers, 62.5%.

Read the four tiles. Here the load buttons count searches a second. "First to saturate" reads "Nothing at this load"; its note names the Location service, at 67%.

A part saturates when it gets more work than it can serve. A card turns red at 90% of its limit; only past 100% does the result name it.

The latency tile shows 9ms: load balancer 1.5 + LBS 2 + database 5 = 8.5 ms. The cost tile shows $14k/mo.

Of that, $6,003.24 is data out to the internet, called egress: 6,000 answers a second of 5 KiB each.

AWS bills egress per GB, with the first 100 GB a month free. The price per GB falls as the volume grows.

The tile's 5 ms is reader CPU. A search that reads storage also waits for it, so the real p50, the median, is higher: perhaps 10 to 20 ms, our estimate.

Throughput is limited by CPU; latency is not.

Press 3,000, the average hour. Nothing saturates. Auto-scaling adds or removes tasks with the load, so the Location service stays near 67% at every button.

Press 10,000. The Business database saturates: 6 readers x 1,600 = 9,600 searches a second.

The tile shows "≥ 24ms". It draws a saturated database as a slower answer; really, queries past the readers' capacity time out, and those searches fail.

The trade-off:

Readers scale reads and the writer stays nearly idle. In exchange, every search costs a database statement.

Stage 1: Every search queries the database

• Load: 6,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $14k/mo

Check in: Why not shard the businesses table?

The same design, five times the users

The interviewer asks: We grow 5 times across the region's countries. What breaks?

Users in neighbouring countries are served from the same region, so Stage 2 runs Stage 1's design at 30,000 searches a second.

Aurora allows up to 15 readers in a cluster with a writer, the primary. 15 x 1,600 = 24,000 searches a second, against 30,000.

The Business database saturates. Its warning reads "Readers 125% used: 30,000 reads/s against 24,000 across 15 readers".

The tile shows "≥ 24ms". Really, with load shedding at best a fifth of searches get no answer; without it every query queues, and fewer than 24,000 are served.

The cost tile shows $45k/mo.

Bigger readers would carry it: 14 readers of 16 vCPUs, 3,200 searches a second each, 67.0% at 30,000.

That is $29,203.20 a month of Aurora, about 1.9 times the 15-reader bill. It is twice the vCPU at twice the price, on 15 instances instead of 16.

Stage 2 with bigger readers is then about $58,849 in all.

Press 6,000: Stage 1's load on 15 readers. Nothing saturates; the database reads 25%, and the cost tile shows $23k/mo.

The trade-off:

Readers scale reads linearly, and so does the bill. The ceiling is 15 a cluster.

Stage 2: The same design, five times the users

• Load: 30,000 req/sec
• First to saturate: Business database
• Estimated cost: $45k/mo

• Latency past saturation is a lower bound, not an estimate. Business database is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Business database: Readers 125% used: 30,000 reads/s against 24,000 across 15 readers (the writer takes no reads while readers exist).

Check in: Why not just buy bigger readers?

A cell store with complete lists

Most searches ask about the same busy places again and again. Their cells change only when a business opens, closes or moves.

A cell store in Redis holds, for every populated cell at precisions 5, 6 and 7, the complete list of its businesses.

It is a materialised index: built ahead of time from the database, not filled by reads.

It is bulk-loaded each night under a new generation, a fresh set of keys.

When the load is complete, one pointer key switches every read to the new generation at once.

An entry is 12 bytes: a 4-byte id, two 2-byte offsets inside the cell, and a 1-byte score. Then a 2-byte category mask and a 1-byte hours bucket.

The 2-byte category mask holds up to 16 top-level categories: restaurants, cafes, bars, shops and so on.

Finer categories and attributes, such as vegan or wheelchair access, are not in the entry. Those searches go to a search index, with text search, not drawn.

They are about 5% of searches, our estimate. The canvas counts every search on the location-service path, so it overstates that path by about that much.

Each LBS task holds a bitmap of populated cells, about 200 MB, so it never asks for an empty one.

The trade-off:

A nightly load means new and moved businesses wait a day. In exchange, the cell store never depends on reads to fill it.

Check in: Why does the cell store hold complete lists, not just the 200 best-rated businesses of each cell?

Finer cells where it is dense, rings where it is sparse

A downtown cell can hold thousands of businesses, a rural one none. One precision for every search reads too much in one place and too little in the other.

The service uses the finer of two precisions: the finest whose 9 cells cover the radius, and the density precision at the user's point.

Density precision is 5 if the precision-5 cell holds up to about 600 businesses, else 6 if the point's precision-6 cell does, else 7.

A small radius forces fine cells even where businesses are sparse. Dense areas force fine cells even for a large radius, and rings widen from there.

So a searched cell holds about 100 businesses on average, our estimate, often fewer. A precision-7 cell over about 1,000 is split into precision-8 cells.

If fewer than 20 qualify, the LBS reads the next ring at the same precision: 16 cells, then 24. It stops after 3 rings, 49 keys.

At the cap it returns what qualified, labelled with the distance covered, such as "3 cafes open now within 380 m".

With one ring on about 5% of searches, a whole-day estimate, a search reads 9 + 0.05 x 16 = 9.8 cell keys.

The 1-byte score is a nightly 0 to 255 quality value from rating and review count.

At query time the service ranks by score x (1 - 0.5 x distance / radius). So a business at the edge of the radius keeps half its score.

The trade-off:

In a dense centre the answer is the best 20 among the nearest that match. A strict "best-rated within 1 km" belongs to a search engine, named but not drawn.

Check in: A user downtown searches a 2 km radius. Which precision does the service use, and why?

From cells to 20 answers

The cell entries say who is near. The answer needs names, hours and photos, which change with every owner edit.

The LBS filters entries by exact distance, category and the hours bucket, ranks by score, and keeps 20. Filtering first keeps the business reads at 20.

If the full hours re-check drops some, it takes the next-ranked entries from cells already read, and fetches only their details. If none remain, it returns fewer than 20, labelled.

A business cache in Redis holds about 500 bytes of details per business, for the 30 GiB of most-viewed businesses: 95% hit, our estimate.

Redis Cluster spreads keys over hash slots, and each shard owns some. One command cannot span slots, so reads go as pipelined batches, one per shard.

Misses fall through to Aurora. Cells miss 2%, an allowance for load gaps such as a late nightly load, and businesses miss 5%.

A cell miss is one index range scan on a covering index, about 100 entries from one or two adjacent pages. It is priced as one lookup, 0.5 ms.

A lookup costs about a tenth of a search because it does about a tenth of the work.

It is one index probe instead of nine range scans, a thousand entries ranked and twenty rows joined.

Statement overhead is why it is not smaller still. Lookups per search: 9.8 x 0.02 + 20 x 0.05 = 0.196 + 1 = 1.196.

Step through the figure to follow one search through both caches.

The trade-off:

Two caches to load, invalidate and watch. In exchange, most searches never reach the database.

One search, through two caches

1. The service reads about 10 cell keys from the cell store. Each entry is 12 bytes, so a search moves about 11.76 KB.
2. It filters by exact distance, category and the hours bucket, ranks by score, and keeps 20, before fetching any details.
3. It fetches the 20 businesses' details. About 1 in 20 misses and is looked up in Aurora as one row.
4. Misses go to Aurora: about 1.2 lookups a search. A cell miss is one index range scan, priced like a row lookup.

Check in: How many database lookups does a search make, and why so few?

Size the caches by network and key rate

A cache node can run out of two things: network bytes, or key reads a second. Which comes first depends on the size of each entry.

A search moves 9.8 x 100 x 12 B = 11.76 KB of cells and 20 x 500 B = 10 KB of details.

One cache.r7g.xlarge node has a network baseline of 1.876 Gbps, 234.5 MB a second. Each cache has four nodes: 938 MB a second.

A node's key rate is how many key reads it serves a second: 348,000, measured by AWS on the previous node generation. The newer r7g node should serve at least as many, so 348,000 is a safe minimum.

Four nodes give each cache 4 x 348,000 = 1,392,000 key reads a second.

At 30,000 searches the cell store moves 30,000 x 11.76 KB = 352.8 MB a second, 37.6% of its network. Its 30,000 x 9.8 = 294,000 key reads are 21.1% of its key rate.

The business cache moves 30,000 x 10 KB = 300 MB a second, 32.0% of its network. Its 30,000 x 20 = 600,000 key reads are 43.1% of its key rate.

The limit a cache reaches first is the one that binds. Network binds on the cell store, whose lists are about 1.2 KB each. Key rate binds on the business cache, whose entries are only 500 B.

Three cell-store nodes give 703.5 MB a second, so network alone fits 3 shards at 30,000, at 50.1%. The fourth is for the heavy day: 50,000 x 11.76 KB = 588 MB a second, 83.6% of three.

With 4 extra cell keys a search, three would reach 110.9%, past the baseline. Four run at about 63%, and 83.2% with the extra keys.

A smaller blast radius follows: a lost cell-store shard is a quarter of the cells, not a third.

The business cache has its fourth shard for key rate. At 50,000 it takes 50,000 x 20 = 1,000,000 key reads a second.

Three shards would run at 1,000,000 / (3 x 348,000) = 95.8% of their key rate, a red card. Four run at 71.8%.

Memory fits with AWS's default 25% reserved. Each cache has 4 x 26.32 GiB x 0.75 = 79.0 GiB usable, against 13.4 GiB of cells and 30 GiB of details.

The trade-off:

Each cache buys nodes for the limit that binds, so it has room on the other. In exchange, a heavy day stalls on neither bytes nor key reads.

Check in: What do you size a cache by here?

Run the cached design

Stage 3 runs both caches at 30,000 searches a second, with smaller readers that only serve misses.

LBS: 30,000 / 350 = 85.7, so 86 tasks, 69.8%. The cell store takes 294,000 key reads a second and the business cache 600,000.

Aurora takes 5,880 + 30,000 = 35,880 lookups. Each 4-vCPU reader takes 8,000, so 35,880 / 5,600 = 6.4 gives 7 readers, 64.1%.

"First to saturate" notes the Location service, at 70%.

The latency tile shows 4ms. It reads the two caches in parallel, and adds the database at the business cache's 5% miss share.

That is 1.5 + 2 + 0.2 + 0.05 x 0.5 = 3.73 ms. In a real search, the business read follows the cell read.

By hand: 1 - 0.95^20 = 64% of searches wait for one business fetch. At p50 that is 1.5 + 2 + 0.2 + 0.2 + 0.5 = 4.4 ms.

The cost tile shows $36k/mo. The read path is $5,907.46: $2,013.70 of caches and $3,893.76 of Aurora, against $29,203.20 for readers big enough without caches.

Press 15,000, the average hour. Nothing saturates, and the cost tile shows $23k/mo.

Press 50,000, a heavy day. The Business database saturates. On the cards, the cell store's network runs at 62.6% and the business cache's key rate at 71.8%.

The database is the first wall, at 56,000 / 1.196 = 46,823 searches a second. The business cache's key rate would follow, at 1,392,000 / 20 = 69,600.

The trade-off:

The cache is the read capacity. Size each cache by whichever limit binds first: network or key rate.

Stage 3: A cell store and a business cache

• Load: 30,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $36k/mo

Check in: How much database work do the caches remove at 30,000 searches a second?

The whole design on one screen

Skip on a first read; come back before the interview. Every number on Stage 3 comes from the one before it, at the 30,000 peak.

Searches: 52 million users x 5 for growth x 5 searches a day / 86,400, then x 2 at the peak: about 30,000 a second.

Load balancer: $4,163.40. LBS: 30,000 / 350, so 86 tasks, $3,056.99.

Cell key reads: 30,000 x 9.8 = 294,000, 352.8 MB a second on 4 nodes, 37.6% of network: $1,006.85.

Cell misses: 294,000 x 0.02 = 5,880 lookups, one index range scan each.

Business key reads: 30,000 x 20 = 600,000 on 4 nodes at 348,000 each, 43.1% of key rate: $1,006.85.

Business misses: 600,000 x 0.05 = 30,000 lookups, one row each.

Aurora: 5,880 + 30,000 = 35,880 lookups, 1.196 per search, on 7 readers of 8,000: 64.1%, $3,893.76.

Answers to users: 30,000 x 5 KiB a second x 2,592,000 seconds = 370,789 GiB a month, which AWS bills as GB.

Egress, with the first 100 GB free: $0.09 a GB to 10,340 GB, $0.085 to 51,300, $0.07 to 153,700, $0.05 after. That is $22,425.63.

Total: $35,553.48 a month at the peak, the tile's $36k.

At the average, 15,000 searches a second, the month is $22,681.67, the tile's $23k.

Check in: Close the page and rebuild the chain from 30,000 searches to the reader count.

A cell-store node fails, no replicas

The interviewer asks: A cell-store node fails at the lunch peak. What happens?

One of the cell store's 4 shards fails, and its replacement starts empty. Stage 4 draws that as a hit rate, so it has no load buttons.

A quarter of the cell keys miss until the loader refills them: 98% of the other three quarters is 0.98 x 3/4 = 73.5% served.

Aurora gets 294,000 x 0.265 = 77,910 cell scans plus 30,000 business fetches: 107,910 lookups against 56,000.

That is about 2.6 cell scans a search instead of the usual 0.2. The warning reads "Readers 193% used".

The cell store's card stays quiet: its fixed 70% low-hit line does not fire at 73.5%.

A real alarm on the drop from 98%, or on the shard errors, would fire at once. The card shows the cost where it lands, at the database.

The tile shows "≥ 4ms": 1.5 + 2 + 0.2 + 0.265 x 2.0 = 4.23 ms, with the saturated readers at 2.0 ms.

Really, lookups fail at 48%, and a search makes about 3.6, so only about 9% of searches get every lookup.

Only with whole-search admission control are about 15,568 a second, 51.9%, served in full.

A cold cell is one index range scan of about 100 entries, priced as one lookup. If it costs more, Stage 4 is worse than drawn.

The cost tile shows $36k/mo, the same as Stage 3. Nothing was added; something was lost.

The trade-off:

A cache that carries the read capacity takes the database down with it when it fails.

Stage 4: A cell-store node fails, no replicas

• Load: 30,000 req/sec
• First to saturate: Business database
• Estimated cost: $36k/mo

• Latency past saturation is a lower bound, not an estimate. Business database is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Business database: Readers 193% used: 107,910 reads/s against 56,000 across 7 readers (the writer takes no reads while readers exist).

Check in: Why is one cache node a capacity problem?

A cache failure in three phases

The hit rate on the card is one number. A real failure goes through three phases, and each needs its own answer.

Phase 1: until a replacement exists, the lost shard's keys return errors, not misses. The other shards keep serving.

It lasts as long as ElastiCache's node replacement: minutes, not a documented bound, our estimate.

An LBS that treats an error as a miss sends those cells to the database. One that fails fast returns the cells that answered.

Phase 2: the replacement is up but empty. Refilling it from reads would hit readers already at 193%, so the bulk loader refills it instead.

The loader writes about a quarter of 6.7 GiB, 1.7 GiB. At 100 MB a second that is well under a minute, plus the time to detect and start it.

Phase 3, with a replica: ElastiCache promotes it with its data. Errors last a few seconds by AWS's account, plus the time for the client to refresh its map of which shard holds which keys.

A whole lost cluster is seeded from the backup in S3 before it takes traffic.

Step through the figure to follow the three phases.

The trade-off:

Each phase needs code that never runs on a good day. That code is the difference between a slow minute and an outage.

Losing one cache shard, in three phases

1. Until a replacement exists, the lost shard returns errors. Treating them as misses floods the database; failing fast answers from the other shards.
2. The replacement starts empty. Refilling it from reads would hit readers already at 193%, so the bulk loader refills it.
3. With a replica in the other zone, the replica is promoted with its data. Errors last a few seconds, plus the client's refresh.

Check in: Why must the bulk loader, not reads, refill an empty shard?

A replica per shard, and defence in depth

The caches now carry the read capacity, so they must be as available as the database.

Each shard of both caches gets one replica in the other zone. A failover keeps the data, so hit rates stay at 98% and 95%.

Defence in depth covers what a replica does not: a cache error is not a miss, and each cold key is fetched once.

A cap on LBS calls to Aurora, sized to the readers, sheds whole searches, not a share of every search.

Nothing saturates; the note names the Location service, at 70%. The latency tile shows 4ms.

The cost tile shows $38k/mo: $37,567.17, about $2,014 more than Stage 3.

The replicas take no reads here, so every percentage stays as in Stage 3. Reads from a replica in the same zone are the next lever on cross-zone traffic.

Press 15,000, the average hour. Nothing saturates, and the cost tile shows $25k/mo.

The trade-off:

Surviving a lost shard with readers would take 1.9 times them, and the whole cell store 5.8 times. A replica per shard costs $2,013.70 a month, as much as the caches themselves.

Stage 5: A replica per shard, and defence in depth

• Load: 30,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $38k/mo

Check in: Why not size Aurora to survive a cache failure?

Fresh edits, and more than one region

The interviewer asks: An owner changes their opening hours. And how do you go global?

A cached detail can be stale. Aurora replica lag is usually well under 100 ms, but it has no hard bound: it grows under heavy writes or behind a long query.

An edit deletes the business key on commit, and again about 1 second later, after the readers catch up. A 10-minute expiry bounds the worst case.

In other regions, the edit service publishes the id and version to a cross-region topic. Each region deletes once its own copy shows that version.

So edits show within about a second at home, a few seconds elsewhere, 10 minutes at worst. Locations change at the next nightly load.

A closed business is dropped when its details are read; a moved one shows at its old point until the rebuild.

Going global is a copy of this design per region, not a bigger cluster. Each region has its own LBS, caches and readers.

An Aurora Global Database adds up to 10 secondary regions, replicated typically within a second. A secondary cluster has no writer and allows up to 16 readers.

Owner edits go to the primary region.

The user's point is used for one request and never stored. Logs keep at most a precision-5 cell.

Step through the figure to follow one edit.

The trade-off:

Deleting twice and expiring keys costs a few extra misses. In exchange, a stale detail is bounded, never permanent.

One edit, and a stale copy that cannot last

1. An owner's edit commits on the writer, and the cached details are deleted at once.
2. A read in that gap can refill the cache from a reader that has not caught up. A second delete a second later clears it.
3. Other regions delete once their own copy shows the new version. A 10-minute expiry bounds any copy that slips through.

Check in: Why delete the cached detail twice?

The real monthly bill

Skip on a first read; come back before the interview. The cost tile holds the peak all month, so this bill is the average month throughout.

Stage 5 at 15,000 searches a second is $24,695.36 a month on the canvas, $13,155.91 of it internet egress.

15,000 x 2,592,000 = 38.9 billion searches: $0.64 per million.

The card bills the load balancer by new connections. Apps keep connections open, so billed by processed bytes it is $1,499.35 at the average.

With that, the average month is about $24,105, $0.62 per million.

Internet egress for the 5 KiB answers is on the tile: 185,394 GiB, $13,155.91 after the first 100 GB free.

Cache traffic across zones is not on the canvas: about $7,879.

With it, the average month is about $31,984, about $0.82 per million. The tile-based totals, $24,695.36 and about $32,575, carry the connection-based load balancer.

Zone-local cache reads remove most of the cross-zone line.

Aurora is I/O-Optimized on the merits: at 1 I/O a lookup, Standard would bill $9,300.10 at the average, against a flat $898.56 premium.

Storage is about 120 GB at about $0.225 a GB-month: about $27.

The trade-off:

Internet egress is over half the tile: $13,155.91 of $24,695.36, more than the caches and the database together.

Cross-zone cache traffic adds about a third more. A design review that skips data transfer misses the two largest lines.

Check in: What does a million searches really cost, and what drives the difference?

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a user see?

A design that works on a good day is half an answer. The interviewer asks what fails, who notices, and what it costs.

An LBS task dies: its in-flight searches fail and the app retries. It holds no state.

A cache primary fails with a replica: a few seconds of errors on its slots, then the replica serves.

Without a replica: errors until a replacement exists, then an empty shard refilled by the loader, as in Stage 4.

A whole cache cluster is lost: seed it from the backup and shed whole searches meanwhile.

An Aurora reader fails: its share moves to the other readers. The writer fails: edits wait for failover, and searches lose a reader to the promotion.

Pagination: the cursor carries the last rank and id, the cells read and the generation. The server holds no state.

The next page re-reads the same cells from the same generation, kept for an hour, re-ranks, and returns entries after that rank and id.

Say it out loud: "Geohash cells as cache keys, and complete lists. Two caches sized by network and key rate, a replica per shard, and readers for the misses."

Minutes 0 to 5: requirements. Read-heavy, write-light, freshness.

Minutes 5 to 10: the numbers. 6,000 then 30,000 searches a second; 100 million businesses, about 100 GB.

Minutes 10 to 18: geohash, quadtree, S2 and H3. Nine cells, and precision by radius and latitude.

Minutes 18 to 25: Stages 1 to 3. Readers, the 15-a-cluster ceiling, the cell store and the business cache.

Minutes 25 to 31: sizing caches by network and key rate, 12-byte entries, complete lists, finer cells where dense, widening by rings.

Minutes 31 to 38: a cache failure in three phases. Replicas, the loader refill, shedding whole searches.

Minutes 38 to 45: fresh edits, going global, data transfer and privacy.

The trade-off:

Each answer has a price. Two caches, a nightly loader and replicas are more to run than readers alone, and they cost less than readers big enough.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.