How to design search autocomplete

Autocomplete is a cache-fill problem: suggest(prefix, locale) -> top 10 completions ranked by popularity, precomputed offline, kept in memory in region, with most requests deleted before they reach a server.

The contract

• Prefix (chars typed, e.g. car) + locale (language-region, e.g. en-US) -> ordered list of 10 completions, most popular first.
• Same answer for everyone in a locale: no server-side personalization, no document query. This is what makes it cacheable.
• Ranking = popularity from query logs (not a learned model). Out of scope: personalization, spelling correction, transliteration.
• Personalization happens on the client, by blending a local history list into the result.

The two numbers that force it

• Latency: feels-instant is under 100 ms keypress-to-paint. Retrieval gets ~24 ms after the rest is spent. Forbids DB query, cross-region hop, or anything not already in memory near the user.
• Write amplification: ~5,000:1. Precomputing top-k (k=10) at every trie node makes reads cheap and writes ruinous; only ~0.02% of ancestor touches actually reorder a list. So the index is a build artifact, not a live structure.

Latency budget (adds to 100 ms)

• 24 ms buys ~240,000 memory refs (~100 ns), ~240 SSD reads (~100 µs), or ~2.4 disk seeks (~10 ms).
• Cross-continent RTT ~150 ms = 6x the whole budget -> replicate into every region.

Sizing (numbers to defend)

• 500 M DAU × 8 searches × 8 keystrokes = ~32 B/day = ~320k QPS mean, ~960k peak (3x). Autocomplete is ~8x the search rate behind it.
• Collapse one-child trie chains into a radix tree: 1.5 B nodes -> ~200 M (7.6x).
• Index tiers: tree structure ~4.8 GB, cached top-10 ~16 GB (dominant), strings ~2.4 GB = ~23 GB per locale. Fits one 128 GB box -> replicate, not shard.
• All 50 locales ~361 GB -> shard by locale (natural placement key).

Serving artifact

• Flat, mmap-able byte array: nodes as fixed-width records, children as offsets (valid on any machine), not pointers (process-local). Separate string table addressed by 4-byte id (8 B per top-k entry vs ~30 B inline).
• OS page cache = one 23 GB copy per box shared by all processes. Swap is atomic: open new file, flip one reference; validate with a smoke query before the swap, roll back by flipping back.
• Bloom filter blocklist checked at render time: says definitely not or probably yes, never misses a real member (safe direction). Keep the check after the cache.

Build vs live update

• Live update: 4 B events × 20 ancestors = 80 B node updates/day (~800k/s); root alone ~40k writes/s under a global lock while serving ~960k reads/s; 14.4 M replication msgs/s for a structure needing no consistency. Rejected.
• Batch: ~160 GB/day log scanned in ~160 s, build ~1,600 machine-seconds. Cheap.
• Distribution sets the freshness floor, not computation. One origin pushing 23 GB to 18 replicas = ~55 min. Tree fan-out (each holder seeds one more, population doubles) = ceil(log2 18) = 5 hops, ~15.3 min. Hourly cadence -> ~30 min mean staleness.
• Trending overlay for terms that can’t wait: 5,000 prefixes × 10 × 8 B = 400 KB pushed every 30 s. Count-min sketch detects (over-, never under-estimates); trigger on 5-min rate vs 24-hr baseline with a distinct-user floor; merged at read time. Big slow artifact + tiny fast overlay = the recurring shape.

Why top-k is cached

• Read-time traversal of s (~3.85 M descendants) at ~100 ns each = ~385 ms = 16x budget, worse with poor locality. Cached top-10 turns it into a ~2 µs array read (~192,500x faster) for the 16 GB tier.
• Selective caching: cache only nodes with >10,000 descendants (~200k of 200 M, ~100x saving); traverse small subtrees. Full caching when memory allows, to kill slow-tail surprises. Subtree count stored per node makes the threshold checkable.

Sharding: skew and the client head blob

• By first char fails: s is 8.1% vs 3.85% uniform; hottest shard 2.1x mean, ~40x the coldest.
• Hashing 3 chars (17,576 buckets) cuts variance (CV ~0.7 -> ~0.039) but not a hot key: hottest 3-char bucket ~1.1% still leaves its shard ~2.1x mean. Sanity check with containment (no sea bucket can beat s’s 8.1%).
• Shard by locale, replicate each whole: lookups stay local (no scatter-gather), load is stable and placed near users, hot prefix dissolves into replication.
• Head blob: top 1,000 of 17,576 prefixes cover ~71% (ln m / ln K), ~100 KB gzipped, fetched once per session. Takes peak from 960k to ~281,280 QPS. Largest single lever.
• Fleet by footprint, not QPS: 361 GB / 128 GB = 3 boxes × 3 copies × 6 regions = 54 machines, 18 replicas per locale, ~10% peak utilization. Divide by regions OR multiply, never both.

The client (deletes ~2/3 of the work)

• Debounce 50 ms: at 300 ms mean keystroke gap, exp(-d/300) fires; 50 ms removes ~15%. Solve for it from the budget (only 50 ms left), don’t pick from a table. Debounce trailing; skip it on paste/history-pick.
• Ordering bug (most-shipped defect): stale ca response drawn while box reads car, ~0.6%/keystroke, ~1,603 wrong renders/s, never reproducible locally. Fix by rendering only if response prefix == current input (fails safe). Add AbortController for bandwidth, keep seq as telemetry.
• Warm connection: open on focus, not first keystroke. Cold TCP+TLS ~40 ms (TLS 1.3) = 40% of budget. HTTP/2 multiplexes; cheapest 20-40 ms, invisible server-side.

Load collapse

960,000/s  --head blob 71%-->  281,280/s  --6 regions-->  46,880/s per region
                                                          54 machines, 10% used

Gotchas

• Empty list, never 404: a prefix with no completions is normal.
• Cache-Control: public only because responses aren’t personalized.
• Alert on image age, not job exit code (a stale index still looks plausible).
• Count distinct authenticated users, not events, to resist poisoning.
• TTL every overlay entry; overlay fails open to the baked list.
• Blocklist enforced only at build time can’t beat your slowest cache.