Design Search Autocomplete

Design Google's search suggestion box. Every keystroke is a query. The system must return ranked suggestions in under 100ms — using a Trie or precomputed prefix tables backed by a fast cache.

What you will learn

• Explain how a Trie data structure enables prefix-based suggestions
• Identify why an in-memory Trie doesn't scale and design a distributed alternative
• Build a data pipeline that computes suggestion rankings from search logs
• Optimise the serving path to p99 < 100ms globally

When you type into Google's search box, suggestions appear before you finish the word. Each keystroke fires a request. The system must respond in under 100ms — globally, for billions of users, across the entire search query space.

This is the autocomplete system. Its core data structure is the Trie. The core engineering problem is that a Trie doesn't scale naively.

Functional requirements:

• Return the top 5 search suggestions for a given prefix
• Suggestions are ranked by search frequency (global popularity)
• Results update as the user types each character
• Support for typo tolerance is optional (out of scope for v1)

Non-functional requirements:

• Response time < 100ms p99 (users perceive latency above this)
• High availability — users expect suggestions at all times
• Results can lag real-time search trends by up to 1 hour (eventual consistency acceptable)
• System must handle peak load (trending events spike query volume 10x)

Create a free account to read the full chapter — advanced chapters, progress tracking, and quizzes are free with sign-up.