Case study: search autocomplete

Search autocomplete (typeahead) suggests completions while the user types. The bar is strict: the top suggestions should arrive in under about 100 ms at p99, network included. That rules out running a full search query for every keystroke. Instead, popular prefixes are computed ahead of time, stored in a structure built for prefix lookup, and served from memory close to the user.

The core idea is to move work offline. No amount of indexing saves you if you rank every query from raw logs on each keystroke.

Requirements

• Given a prefix, return the top 5 suggestions, ranked mainly by popularity.
• Show new viral phrases within minutes to hours.
• Prefer a fast answer over a perfect one. An empty box beats a timeout.
• Filter offensive and sensitive suggestions.

Estimates

Searchers:      100M daily active users
Searches/user:  about 5 per day
Requests/search: about 5 after debounce
Average QPS:    100M × 5 × 5 / 86,400 ≈ 30,000/s
Peak (×3):      ≈ 90,000/s

At that rate, the browser cache and the CDN matter as much as the data structure. Most of the 100 ms budget is network time.

Concepts in this topic

Serving and safety

• Shard by prefix. Use the first one or two characters, or explicit ranges. English is skewed: s is much hotter than q. Split a hot letter into ranges such as sa–sm and sn–sz so one shard does not take most of the traffic.
• Replicate each shard. Reads are independent, so replicas scale them easily.
• Cache at the edge. Popular prefixes such as "", a and how can carry a short TTL of 10 to 60 seconds.
• Filter at build time. Blocklists and PII scrubbing run during the build, so banned terms never enter the top-k lists.
• Build one trie per locale. English popularity should not drown out Spanish suggestions.
• Rate-limit the suggest API. Open suggest endpoints are a magnet for scrapers, and full top-k lists can reveal your query distribution.

Failure modes

Common mistakes

• Running full search per keystroke. The index is built for documents, not for prefixes.
• Building top-k from raw logs at request time. Precompute it in batches.
• Letting bot traffic into the logs. Bots poison the suggestions.
• Shipping a new trie without measuring it. Gate rollouts on click and abandonment metrics, not on "the binary loaded".

Key takeaways

• Autocomplete is a precomputation problem: top-k per prefix, kept in memory.
• Feed the structure from batch query logs and add a streaming overlay for trends.
• Shard and replicate the trie, and cache popular prefixes at the edge and on the client.
• Debouncing, cancelling old requests and local caches are part of the design.

Further learning

ByteByteGo covers typeahead designs alongside other classic interview questions.

ByteByteGo blog (Alex Xu)Explain complex systems with simple terms, from the authors of the best-selling system design book series. Join over 1,000,000 friendly readers. Click to read ByteByteGo Newsletter, a Substack publication.blog.bytebytego.com

The System Design PrimerLearn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards. - donnemartin/system-design-primerGitHub

A clear system-design walkthrough of query autocomplete, including trie top-k and analytics pipelines.