Design Search Autocomplete

• Return the top ten completions for a prefix — Ranked by popularity, not alphabetically. The ordering is the product; the prefix match is the easy part.
• Respond on every keystroke — Query volume is several times search volume, because a ten-character query produces up to ten requests.
• Reflect what is trending — A breaking news term must appear within minutes. A suggestion index rebuilt nightly is a day behind the thing people are actually typing.
• Personalise lightly — A user's own recent searches rank above global ones for the same prefix, without a per-user index.
• Tolerate typos and prefix gaps — "recieve" should still suggest "receive"; "new yor" should suggest "new york".
• Filter unsafe and abusive suggestions — Autocomplete puts words in the product's mouth. Blocklists, category suppression and a kill switch for a specific suggestion are requirements, not extras.
• Out of scope — The search results themselves, spelling correction of the submitted query, and multilingual transliteration beyond per-language indexes.

• Latency (p99 < 50 ms end to end) — A suggestion that arrives after the next keystroke is wasted work. This budget is the design constraint that decides everything else.
• Query rate (500 k/s peak) — Roughly five keystroke requests per search, against 100 k searches/s. Reads dominate by orders of magnitude.
• Freshness (trending terms within 10 minutes) — Slower than a news site, far faster than a nightly batch. The gap between those two is where the design lives.
• Availability (99.99 %) — Degrades gracefully: no suggestions is an acceptable search box, an error is not.
• Index size (fits in memory per shard) — Disk seeks do not fit a 50 ms budget with a keystroke rate this high. If it does not fit in RAM, prune it until it does.
• Cache hit rate (> 90 %) — Prefix popularity is extremely skewed, so short prefixes are served almost entirely from cache. Everything after that is a rounding error on capacity.
• Safety (blocked terms never served) — A false negative here is a public incident, so filtering is applied at build time and again at serve time.

• Requests per second: ~500 k/s — 100 k searches/s × ~5 keystroke requests each after debouncing a 10-character query = ~500 k/s. Without debouncing it would be twice that, which is why the client debounces.
• Distinct queries worth indexing: ~100 M — Billions of distinct queries are seen, but the tail is seen once and helps nobody. Keeping terms with at least ~50 occurrences in 30 days leaves ~100 M — two orders of magnitude smaller and almost all of the value.
• Index size in memory: ~30 GB — 100 M terms × ~30 B average, plus the top-10 list cached at each of ~50 M internal nodes at ~80 B = ~25–35 GB. Shards by prefix so each holds a few GB.
• Cache hit rate and size: > 90 % from ~1 GB — Prefix frequency follows a steep power law: the top 1 M prefixes cover the great majority of requests. 1 M entries × ~1 KB of serialised suggestions = ~1 GB and > 90 % hits.
• Log volume for ranking: ~10 B events/day — 100 k searches/s × 86 400 = ~9 B searches/day, plus selection events. At ~100 B each that is ~1 TB/day feeding the popularity counts.
• Index build time: ~20 min — Aggregate a 30-day window with a recency weighting, prune, build the trie, serialise, distribute: ~20 minutes end to end on a batch cluster. That sets the floor on full-rebuild freshness and is why a separate trending layer exists.
• Bandwidth per response: ~500 B — Ten suggestions × ~30 characters plus scores and JSON overhead ≈ 500 B compressed. At 500 k/s that is ~250 MB/s of egress — small, and worth keeping small because mobile users pay for it.

• Search box — Debounces keystrokes to about 100 ms, cancels in-flight requests when the user types again, and caches locally so backspacing costs nothing. Roughly half the total load is removed here before a request is ever sent.
• Edge / CDN — Caches responses for short, popular prefixes at the edge with a short TTL. Because those prefixes are an enormous share of traffic, this is the single largest latency and capacity win in the design.
• Suggest API — Normalises the prefix — lowercase, trim, collapse whitespace, strip accents — then checks the cache, queries the right shard, merges in trending and personal terms, filters, and returns. Stateless.
• Prefix cache (Redis · prefix → top 10) — The merged, filtered, ready-to-serve answer for a prefix, with a TTL of a minute or two. Short TTLs rather than invalidation: suggestions are a ranking, and a ranking that is ninety seconds old is indistinguishable from a fresh one.
• Suggestion shards (in-memory trie, by prefix range) — Each holds a slice of the trie with the top ten precomputed at every node, so a lookup is a walk down the prefix and a read — no traversal of the subtree at query time. Replicated for read throughput.
• Trending layer (stream counts, 10-minute windows) — Terms whose rate has risen sharply in the last few minutes, held separately from the main index and merged at query time with a boost. This is how the system is minutes fresh without rebuilding a 30 GB trie every few minutes.
• Personal history (key-value, user → recent queries) — A user's last few dozen searches, read in parallel with the shard query and merged above global results for the same prefix. Small, per-user, and never mixed into the shared index or the shared cache.
• Safety filter — Blocklists, category classifiers and manual suppressions, applied when the index is built and again on the way out. Applied twice on purpose: a build-time-only filter means a bad suggestion is live until the next build.
• Query log stream (Kafka) — Every search and every suggestion the user selected. Selections matter more than searches for ranking: they say which suggestion was the one people wanted.
• Count aggregator (stream + batch) — Maintains 30-day decayed counts per term and the short-window rates that feed trending. One pipeline, two outputs on different cadences.
• Index builder — Prunes the tail, applies safety filters, builds the trie with top-10 lists at every node, serialises it, and publishes a versioned artefact. Runs hourly.
• Index artefacts (object store, versioned) — Immutable built indexes. Shards download and swap atomically, and a bad build is rolled back by pointing at the previous version rather than by rebuilding under pressure.

1. A user types "new y" — The hot path, and it has to fit in 50 ms. Almost every request should end at the first or second box.
   1. The client debounces and cancels the previous in-flight request.
   2. The edge serves it from cache if this prefix is popular, which it usually is.
   3. On a miss, the API normalises the prefix and checks the prefix cache.
   4. The API asks the shard that owns this prefix range.
   5. Trending and personal results are fetched in parallel and merged.
   6. The safety filter runs, the result is cached, and the response goes back.
2. How a suggestion earns its place — The background loop that makes the top ten good. Selections, not searches, are the signal that matters.
   1. The client logs the search and, crucially, which suggestion was selected.
   2. The aggregator maintains decayed counts over a rolling 30-day window.
   3. The builder prunes the tail, filters, and builds the trie with top-10 lists at every node.
   4. The artefact is published, versioned and immutable.
   5. Shards download the new version and swap atomically.
3. A term starts trending at 14:03 — Hourly rebuilds cannot cover breaking news. A small, fast, separate layer does, merged at query time.
   1. Searches for a new term jump from near zero to thousands a minute.
   2. The aggregator computes short-window rates and flags terms rising sharply against their baseline.
   3. Flagged terms go into the trending layer, keyed by their prefixes.
   4. Queries merge trending candidates with a time-decaying boost.
   5. Trending terms pass the safety filter like everything else — in fact more strictly.
   6. The next hourly build absorbs the term and the boost is no longer needed.
4. The user types "new yorl" — A strict prefix match returns nothing and the box goes empty — the most common way autocomplete feels broken.
   1. The exact prefix lookup finds no node in the trie.
   2. The API retries with an edit-distance-tolerant lookup, bounded tightly.
   3. Fuzzy matches are scored down so an exact match always wins.
   4. If fuzzy also finds nothing, fall back to the longest prefix that did match.
   5. The selection, if any, is logged against the prefix that was actually typed.
5. A suggestion has to be removed now — The path that matters when something goes wrong in public. Minutes, not the next build.
   1. A harmful suggestion is reported for a particular prefix.
   2. An operator adds a suppression for the term or the (prefix, term) pair.
   3. The suppression list is pushed to every API instance within a minute.
   4. Affected cache entries are invalidated.
   5. The next build excludes it permanently and the suppression stays as a backstop.

Ask: Trie with precomputed top-k, a sorted array with binary search, or an inverted index?

Good answers name: Trie with the top-k precomputed at every node, Sorted array of terms with binary search for the prefix range, Inverted index / search engine with edge n-grams, Precomputed key-value: every prefix → its top 10.

Our pick: A compressed trie (radix tree) per language with the top ten precomputed and stored at every node, held entirely in memory, sharded by prefix range and replicated for read throughput. Built hourly as an immutable artefact and swapped in atomically. Fuzzy matching is a bounded extension over the same structure rather than a second index.

1. How much memory do the top-k lists actually add?
   Storing the ten terms as pointers or ids rather than strings — roughly 4 bytes each plus a score — is about 80 bytes a node. With tens of millions of internal nodes that is a few gigabytes on top of the terms themselves. Storing the strings inline would be several times worse, which is why the lists hold ids into a term dictionary.
2. Where do you shard, and what breaks at the boundary?
   By first two or three characters, with ranges balanced by traffic rather than by term count, because prefix popularity is wildly uneven. Nothing breaks at a boundary because a query only ever needs one shard: every term matching a prefix shares that prefix by definition. That is the property that makes this shard beautifully, unlike a general search index.
3. A single shard gets hot — everything starting with "a".
   Split that range further and add replicas. Because shards are read-only artefacts, adding replicas is just copying a file and updating routing; there is no rebalancing of live data. The edge cache absorbs most of the imbalance before it reaches a shard anyway.
4. Why one index per language rather than one big one?
   Ranking and normalisation are language-specific — accent folding, tokenisation, what counts as a prefix in a script without spaces — and mixing languages puts irrelevant terms in everyone's top ten. Separate indexes also mean a language can be rebuilt or rolled back on its own.

Ask: How do you get from a nightly batch rebuild to "trending within ten minutes"?

Good answers name: Hourly full rebuild plus a small real-time trending layer merged at query time, Continuous incremental updates to the live trie, Nightly rebuild only, Rebuild every ten minutes.

Our pick: Immutable hourly rebuilds of the main trie, plus a trending layer computed from ten-minute windows and replicated to every API instance, merged at query time with a decaying boost. Personalisation is merged the same way, from a per-user store. The merge is the only place ranking signals combine, which keeps calibration in one function rather than three.

1. How do you calibrate the trending boost against index scores?
   Put both on a comparable scale — log of the decayed count — and express the boost as a multiplier on the trending term's current rate relative to its baseline, capped. Then check it empirically: the fraction of sessions where a trending suggestion was shown and selected. Set by feel, it either does nothing or floods the box.
2. A term appears in both the index and the trending layer. What happens?
   Deduplicate on the normalised term and keep the higher score. Simple, but it must be done after normalisation, or "New York" and "new york" both appear — one of the most common visible bugs in this kind of system.
3. The trending layer is down. What does the user see?
   Slightly stale suggestions and nothing else. It is on a short deadline in the parallel fetch and is dropped from the merge if it misses. That is the point of keeping it separate: the fresh layer is the one allowed to fail.
4. How do you stop the index reinforcing itself?
   Rank on selections rather than impressions, and normalise by how often a suggestion was shown. A term shown a million times and selected twice should fall, even though a naive count says it is popular. Without that correction, whatever reaches the top ten stays there forever regardless of quality.

Ask: Where does the budget go, and what do you do when part of it is missed?

Good answers name: Client debounce, edge cache for short prefixes, in-memory shards, deadline-bounded parallel merges, Origin-only, no edge cache, Ship the index to the client, Persistent connection streaming suggestions as the user types.

Our pick: Debounce at about 100 ms in the client with cancellation of superseded requests and a local cache for backspacing; cache short non-personalised prefixes at the edge with a five-second TTL and stale-while-revalidate; serve everything else from in-memory shards with trending and personal lookups issued in parallel under a hard few-millisecond deadline, dropped from the merge if they miss. No component on the path touches disk.

1. Personalisation and edge caching conflict. How do you resolve it?
   Serve the global response from the edge and merge personal terms in the client from its own recent-search store. The user's own history is already on their device, so the merge needs no server round trip and no per-user cache key — the edge stays shared and the response is still personalised.
2. What happens if a shard is slow?
   The request has a deadline. If the shard misses it, return whatever the cache and trending gave, or an empty list. An empty suggestion box is a mildly worse search experience; a search box that hangs is a broken product. Fixed deadlines with partial results is the right default for anything on a typing path.
3. Does debouncing hurt the experience?
   Barely, and it must be tuned rather than guessed. Around 100 ms is below the threshold where typists notice, and it removes half the traffic. Too long — 300 ms — and the box visibly lags behind fast typists, who are exactly the users most likely to be irritated.
4. How do you measure the 50 ms if most requests are cached?
   Measure at the client, from keystroke to render, and report percentiles by cache outcome and by region. Server-side timing flatters you: it excludes the network, which for this feature is most of the budget. A p99 measured at the origin can look fine while the product feels slow everywhere outside its home region.

Ask: How do you stop the product putting harmful words in its own mouth?

Good answers name: Layered filtering: build-time exclusion, serve-time suppression, and per-pair rules, Build-time filtering only, Classifier at query time only, Suppress suggestions entirely for sensitive categories.

Our pick: Filtering at both ends: the builder excludes blocklisted terms and anything a classifier flags above a threshold, and the API applies a small, frequently refreshed suppression list at serve time, after the merge, with both term-level and (prefix, term)-level rules. Suppressing invalidates the affected cache entries immediately. Suggestions against what look like named individuals are restricted by category rather than left to per-term rules.

1. Why filter after the merge rather than before?
   Because trending and personal terms never went through the build-time filter. Filtering only the index leaves the two freshest, least reviewed sources unchecked — which are precisely the ones that will surface something about a breaking news event. The last thing before the response is the only place that sees everything.
2. A legitimate query is caught by a blocklist. How is that found?
   Log suppressions as events with the prefix and the rule that fired, and review the high-volume ones. A rule suppressing something people are typing thousands of times a day is either doing exactly its job or is badly wrong, and only a human can tell which. Silent filtering with no telemetry is how blocklists rot.
3. Does the cache undermine suppression?
   It would, so suppression writes bump a cache generation for the affected prefixes and the entries are dropped. Without that, a suppressed suggestion keeps serving for the TTL — which is fine in the abstract and unacceptable during an incident with a journalist watching.
4. How do you handle this across languages and regions?
   Blocklists are per language and per region, because harm is contextual and a word that is innocuous in one language is a slur in another. It also means a suppression in one market does not silently apply worldwide, which matters both legally and for trust.

Ask: How do you rank a user's own history above global results without building 500 million indexes?

Good answers name: Global index plus a small per-user recent list, merged at the edge of the request, Per-user index, Cohort indexes — by language, region or interest segment, Client-side merge only.

Our pick: A per-user list of recent searches and selections — a few dozen terms — prefix-matched and merged above global results for the same prefix, with a decay so a search from three months ago does not outrank what is relevant now. The merge happens in the client where possible, so the shared edge cache keeps working; the server-side store exists for cross-device continuity and is fetched in parallel under the same deadline as everything else.

1. How far should a personal term outrank a global one?
   Far enough to be visibly first when it genuinely matches, but not so far that a single mistyped search haunts the box for weeks. A large boost with a decay of days, plus a cap on how many personal suggestions can occupy the top ten — typically two or three — so the list does not become a history viewer.
2. What about privacy and deletion?
   It is the user's search history, which is about as sensitive as data gets. It lives in its own store, keyed by user, with a short retention, an in-product control to clear it, and exclusion from the global counts when the user is in a private mode. Deletion has to actually remove it from the store rather than only hiding it, and that has to be true of the client copy too.
3. Does personalisation break the edge cache?
   It would if the merge happened server-side for every request, which is why the client does it whenever it can: the edge serves the shared global response, and the client merges from local storage. Server-side personalisation is reserved for a signed-in user on a new device, where a cache miss is acceptable because it happens rarely.
4. A user searches for something embarrassing once. How long does it follow them?
   Until the decay makes it uncompetitive, or until they clear it — and the in-product control has to be genuinely easy to find, because this is the single most common complaint about personalised suggestions. It is also an argument for a shorter retention than the ranking would ideally want.