# Design search autocomplete > Design typeahead suggestions that answer in under 50 ms: tries with precomputed top-k, an offline aggregation pipeline, caching, freshness and filtering. System Design roadmap · Case studies · 19 min read · https://levelcode.org/roadmaps/system-design/design-typeahead As you type into a search box, suggestions appear after every keystroke: "how to" becomes "how to tie a tie", "how to screenshot on mac". Autocomplete (typeahead) looks like a small feature, but it gets several requests for every search, and each answer must arrive faster than the user can type the next letter. This lesson designs it for a large search engine, and the same ideas apply to product search, address lookup and command palettes. ## Requirements **Functional:** - Return the top 10 suggestions for a prefix, ranked by popularity of past searches. - Suggestions update to reflect what people search for, within an hour for trending topics and a day for everything else. - Filter offensive, dangerous and legally removed suggestions. - Out of scope: spelling correction, personalised ranking (discussed at the end), and full search results. **Non-functional:** - **p99 latency under 50 ms** at the server, so the whole round trip feels instant. - Very high availability: if suggestions fail, search still works, but the experience degrades visibly. - Freshness matters less than speed: slightly stale suggestions are fine. ## Numbers ```text daily active users: 200 million, 10 searches each → 2 billion searches/day keystrokes per search: ~20 characters typed, but the client debounces → ~6 suggestion requests per search suggestion requests: 12 billion/day ≈ 140,000/s avg, ~400,000/s peak distinct queries: ~1 billion per day; after dropping rare ones (< 5 searches), ~50 million worth indexing ``` 400,000 requests per second with a 50 ms budget rules out querying a database per keystroke. Suggestions must come from memory, precomputed. And because the *ranking* comes from billions of searches a day, the system splits in two: an **offline pipeline** that computes what to suggest, and an **online serving path** that only looks things up. ## The client does half the work Before designing servers, reduce the load at the source: - **Debounce**: wait ~100 ms after the last keystroke before sending, so fast typists don't send a request per letter. - **Cancel stale requests**: when a new prefix is sent, abort the previous request (with `AbortController`), and ignore responses for prefixes that no longer match the box. - **Cache per session**: a user who types "pyth", deletes back to "py" and types again shouldn't refetch. A small in-memory map from prefix to results handles that. - **Short prefixes from the CDN**: the top suggestions for one- and two-letter prefixes are identical for everyone in a region. Serve them as cacheable `GET /suggest?q=py` responses with `Cache-Control: max-age=300`, and the edge absorbs a large share of all traffic. The API is deliberately boring and cacheable: ```http GET /suggest?q=how+to+t&lang=en®ion=US 200 OK Cache-Control: public, max-age=300 {"q": "how to t", "suggestions": ["how to tie a tie", "how to take a screenshot", "how to train your dragon", ...]} ``` ## The data structure: a trie with precomputed top-k A **trie** (prefix tree) stores strings character by character, so every prefix is a path from the root. Finding all completions of "tr" means walking `t → r` and collecting the subtree below. Collecting and sorting the whole subtree on each request is far too slow for a prefix like "a", which has millions of completions. The standard fix is to **store the top k completions at every node**, computed when the trie is built: ```text (root) └─ t top: [twitter, translate, target, ...] └─ r top: [translate, trump, train tickets, ...] └─ a top: [train tickets, trader joe's, trailer, ...] ``` A lookup becomes: walk one node per character of the prefix, return that node's list. That's O(length of prefix), independent of how many queries exist. The cost moves to memory and build time: with 50 million queries, average length 20, and 10 suggestions per node stored as IDs, a compressed trie needs tens of gigabytes. That fits in RAM on a large machine, and comfortably once split across several. Two simpler alternatives are worth knowing, because they're often good enough: | Approach | How | Fits when | |---|---|---| | Trie with top-k per node | Walk to the node, read its list | Huge query volume, strict latency | | Prefix → list in a key-value store | Precompute `top10("how to t")` for every prefix of every popular query; serve from Redis | Millions of queries, simpler ops | | Search engine prefix query | Edge n-gram or completion suggester in Elasticsearch/OpenSearch | Product catalogues; you already run one | The key-value approach is just the trie flattened: one entry per node. It uses more memory (no shared structure) but needs no custom server. ## The offline pipeline Ranking comes from search logs, and the pipeline turns raw logs into a new trie on a schedule: 1. **Collect**: every completed search is logged (query, timestamp, language, region) to an event stream such as Kafka. 2. **Aggregate**: a batch job counts queries per language and region. Weight recent searches more: a score such as `sum(count_day × 0.9^age_in_days)` lets new topics rise and old ones fade. 3. **Filter**: drop queries below a minimum count (they're mostly typos, and rare queries can expose private information, such as a person's name with their address). Remove anything on block lists. 4. **Build**: construct a trie per language and region, computing top-k bottom-up: each node's list is the best 10 of its own query and its children's lists. 5. **Publish**: serialise the trie to a file in object storage with a version number, and tell the serving fleet a new version exists. A full rebuild once a day is enough for the long tail. For trending topics, a **streaming path** counts queries over the last hour (an approximate counter such as a [count-min sketch](https://levelcode.org/concepts/count-min-sketch) keeps memory bounded) and produces a small "trending" trie or list that the serving layer merges in. ## Serving: replicas, shards and swapping versions Each **suggestion server** loads a trie into memory at startup and answers from it. Because the data is read-only between builds, scaling reads is easy: run many identical replicas behind a load balancer. If one language's trie is too large for one machine, **shard by prefix**: for example, prefixes starting `a–f` on shard 1, `g–m` on shard 2. Range sharding by first letters is skewed (far more queries start with "s" than "x"), so cut ranges using the actual distribution, or shard by hash of the first two characters. A router in front knows which shard owns which prefix; every request touches exactly one shard. Publishing a new version without downtime: - Each server downloads the new file in the background, builds the new trie in memory alongside the old one, then swaps a single pointer. Requests in flight finish on the old trie. - Roll the change through the fleet gradually and watch error rates and latency; if suggestions look wrong, roll back by pointing at the previous version. - Memory must allow two tries briefly, which is part of capacity planning. ```sequence title: A keystroke becomes suggestions participants: Browser, CDN, Router, Suggest shard Browser -> CDN: GET /suggest?q=how+to+t > Short, popular prefixes are usually CDN hits. CDN -> Router: Cache miss Router -> Suggest shard: Prefix "how to t" → shard 3 Suggest shard -> Suggest shard: Walk trie, read node's top 10, merge trending Suggest shard --> Router: 10 suggestions Router --> CDN: 200, max-age=300 CDN --> Browser: Suggestions ``` ## Safety and quality Autocomplete puts words in users' mouths, so it carries a reputational and legal risk that search results don't. - **Block lists** for slurs, sexual content and dangerous queries are applied in the pipeline *and* re-checked at serve time, so a newly blocked term disappears immediately instead of at the next rebuild. - **Removal requests** (defamation, privacy, legal orders) go into the same serve-time filter. - **Manipulation**: bots repeating a query to push it into suggestions. Count each user or IP at most once per query per day, and require a query to come from many distinct users before it's eligible. - **Personalisation**, if added, should be a separate small list (the user's own recent searches) merged in at the client or a thin layer, not baked into the shared trie, which must stay identical for everyone to keep caching effective. ## Practice The product team wants two additions: (1) **fuzzy matching**, so "pyhton tut" still suggests "python tutorial"; and (2) suggestions for an **online store** with 2 million products, where a product's stock and price change constantly and out-of-stock items must not be suggested. Explain how each changes the design. **Solution** **(1) Fuzzy matching.** - A trie walk is exact, so typos need another route. The common approach is to **try exact first, fall back to fuzzy**: if the exact prefix returns fewer than 10 suggestions (or none), search for prefixes within edit distance 1–2 of what was typed. - A trie supports bounded edit-distance search by walking several branches at once (allowing one insertion, deletion or substitution per step), but the work grows quickly with distance and prefix length, so cap it at distance 1 for short prefixes and 2 for longer ones. - Alternatively, keep a **spelling-correction map** built offline from the logs: people who type "pyhton" and then immediately search "python" teach you the correction. Correct the prefix, then do a normal exact lookup. This is cheap at serve time and catches the common typos. - Rank fuzzy results below exact matches, and keep the latency budget: fuzzy lookups run only on the fallback path. **(2) Product suggestions in a store.** - The corpus is small (2 million items) but **changes constantly**, which is the opposite of web search. A nightly trie rebuild can't keep stock status fresh. - Split the problem: suggestions are ranked by a slowly changing popularity score (sales, views), rebuilt hourly, while **availability is checked at serve time**. Fetch, say, the top 30 candidates for the prefix, filter out-of-stock IDs against an in-memory set or a fast cache fed by inventory events, and return the top 10 remaining. - With only 2 million items, a search engine's completion suggester (or Redis sorted sets per prefix) is often simpler than a custom trie, and it can update individual items in near real time as inventory events arrive. - Prices shouldn't live in the suggestion index at all; if the dropdown shows prices, fetch them from the pricing service or a cache when rendering, so a suggestion never shows a stale price. ## Key takeaways - Autocomplete splits into an offline pipeline that decides what to suggest and an online path that only looks it up. - Store the top-k completions at every trie node, so a lookup costs one step per character regardless of corpus size. - Debounce, cancel stale requests and cache short prefixes at the CDN: most load can be removed before it reaches your servers. - Rebuild daily from logs with recency-weighted counts, add a streaming path for trends, and swap trie versions atomically. - Filter at serve time as well as build time, and resist manipulation by counting distinct users, not raw searches. ## Quiz 1. Why store a precomputed top-10 list at every trie node? A. It makes the trie smaller B. A lookup then costs one step per prefix character instead of scanning and sorting a possibly huge subtree C. It enables fuzzy matching D. It's required for sharding **Answer: B.** A prefix like "a" has millions of completions. With the answer stored at the node, serving is a walk plus a read; the expensive ranking happens at build time. 2. Which part of the load is best absorbed by a CDN? A. Requests for one- and two-letter prefixes, which are identical for everyone in a region B. Personalised suggestions C. Search log ingestion D. Trie rebuilds **Answer: A.** Short prefixes are both the most frequent and the same for every user, so caching them at the edge with a short TTL removes a large share of traffic. 3. A newly reported offensive suggestion must disappear right away, but the trie is rebuilt nightly. What handles it? A. Trigger an immediate full rebuild B. Ask users to clear their cache C. A serve-time block-list filter applied to every response D. Lower the CDN TTL to zero permanently **Answer: C.** Filtering at serve time removes the term immediately; the next pipeline run then excludes it at build time too. 4. Why drop queries searched by only a handful of users from the suggestion index? A. Tries can't store rare strings B. Rare queries are slower to look up C. It's required by the CDN D. They're mostly typos, and rare queries can expose private information or be manipulated **Answer: D.** A minimum count of distinct users removes noise and protects privacy (someone's name plus address) while making it harder for a few accounts to push a query into suggestions.