Autocomplete is a popular feature of search engines. As the user types something in the search box, this feature creates suggestions to complete the sentence for what the user has already typed. These suggestions come from the queries that users have already searched in that search engine and the popularity of these searches. A query that has been searched several times will appear among the top suggestions. A typeahead benefits the user by helping them form sentences faster. It’s an important part of all search engines and many search boxes as it enhances the user experience.
Let’s learn how to design an autocomplete system, also called a search typeahead, for a search box.
What Are The Requirements Of A Search Autocomplete System
Functional Requirements
- The service should return a list of, say, 3 top suggestions, based on what the user types in the search box.
- The suggestions are ordered according to the frequency and recency of their appearance in user searches.
Non-Functional Requirements
- The service should be able to deliver the suggestions in real-time, as the user types in the query. This means that the latency should be very low.
- The system should be able to scale to a large number of requests without any degradation in performance.
- The system should be highly available.
Capacity Constraints Of The System
We need to design a search autocomplete system that works on a scale similar to Google and returns the top suggestions for a phrase that the user types. Google receives around 5 billion queries per day. Assuming about 30% of these queries are unique, this amounts to about 1.5 billion unique queries per day. If each query comprises 15 characters on average each character takes 2 bytes of storage, you’ll need 45GB to store the queries made in a day.
Choice Of Data Structure
The system involves the storage of a large number of strings. What the user enters into the search box is taken by the autocomplete system as an input prefix. This prefix is matched against the strings stored in the database and the most closely related, recent and popular matches are returned to the user.
The database will be queried several times each second and the system must return the response with minimum latency. The indexes need to be stored in a database that can be scanned quickly to retrieve strings to return to the querying user.
Taking into account the basic requirements of the system, the data structure ‘Trie’ is the most appropriate choice. A trie is a tree-like data structure that stores phrases in the form of a tree. Each node carries a character from the phrase in the order that it appears in the word.
If you are preparing for tech interviews at FANGs, you may want to check out the course Grokking the System Design Interview by Educative.
Take for example the set of phrases, “be”, “bee”, “bell”, “bent”, “belt”. If this set is to be stored, this is how it will appear in a trie data structure:

If the user types “be” in the search box, our search typeahead system will scan the trie and reach the node shaded darker in the image above. All the nodes that fall below this shaded node start with the prefix “be” and are returned to the user. The user will see suggestions including terms like be-e, be-ll, be-nt, be-lt and all other terms stored in the trie that start with the prefix “be”.

To save space and the time that our system takes to traverse the database, the trie can also combine nodes as one where only a single branch exists. For example, a space and time-efficient model of the above trie can be:

Check out the course Coderust: Hacking the Coding Interview for Facebook and Google coding interviews.
Tracking Top Searches
The typeahead system keeps track of the top searches and returns the top suggestions to the user based on the prefix that the user enters. Suppose our system returns the top 3 terms for every prefix that the user enters. For this, we will also store the number of times that each term was searched. For example, let’s assume that the users searched for “bell” 21 times, “bee” 11 times, “bent” 10 times and “belt” 30 times, this information will also need to be stored by the system in order to return the top 3 searches to the user.
So the number of times a term is searched can be stored in the node where that term terminates. The terminating node for each term will also store the number of searches along with the characters. This is how our trie will appear with terms and their ranks stored in it:

Now if the user types “be”, the system will locate the root node for “be” and traverse the tree for the child nodes under it. Comparing all the terms originating from the root node, the top 3 results, “belt”, “bell” and “bee” (with the highest number of searches) are returned to the user. Since the term “belt” was searched the most times (30 times), it appears on top, “bell”, with 21 searches appears next and “bee” with 11 searches appears last. If the user picks “bell” from the suggestions and searches for it, the number of searches against “bell” will be incremented and updated to 22 in the terminating node for “bell”.
Land a higher salary with Grokking Comp Negotiation in Tech.
Reducing Latency In Traversing The Trie
Our search autocomplete system has strict latency requirements since we need to create a real-time experience in returning suggestions to the users as they type the prefix. Though we reduced the time to traverse the trie by combining nodes with single branches and reducing the number of levels, it is possible to make the system even more efficient.

One way to increase efficiency is to precompute and save the top 3 suggestions for every prefix in the node for that prefix. This means that instead of traversing the trie each time a user types in “be” into the search box, the system will have pre-computed, sorted and stored the solution to the prefix “be”, i.e. “belt”, “bell” and “bee” inside the node that carries “be”.
If you are preparing for tech interviews at FANGs, you may want to check out the course Grokking the System Design Interview by Educative.

The image above shows how the suggestions for prefix “be” are stored in the node for “be” so they can be instantly returned to the user just after they type “be” in the search. Since the trie in the image is just an example, it is much smaller than the ones developed for actual implementations. Assuming that there are several branches and several levels in the actual trie, we will have to precompute and store suggestions for every node. If the user types “bel”, our system will move to the second level node that carries “l” in the image, and return the suggestions stored in that node for the prefix “bel”.
Although the system returns top 3 suggestions, it’s possible that a node towards the bottom of the trie has only 2 suggestions. A terminating node will have only 1 suggestion, i.e., the prefix of the node itself. For example, if no other term originates from the prefix “belted”, the node for the prefix “belted” will carry only one suggestion which will be returned to the user as the only suggestion.
So pre-computing the top suggestions for every prefix allows us to return them to the querying user without any delay.

So we know that trie is the best data structure to store suggestions for prefixes entered by the user. If the trie data structure is stored in a single server and the server goes down, the system will be unavailable. To increase availability and reliability of the system, the trie will be replicated across multiple servers. Now, if one server goes down, or is overloaded with requests, the other nodes that carry the same information can continue serving the requests. Replicating the information across multiple nodes also makes the system reliable since even if a node is lost, the autocomplete information is not lost and can be accessed from the other storage servers. The replicated instances of trie can be stored in Apache Zookeeper. Zookeeper is a good choice for storage since it is highly available and can effectively serve high volumes of reads and some writes. You can also use a different distributed database, such as Cassandra for the purpose.

All the database nodes are stored in Zookeeper. Each database node carries all the phrases from ‘a’ to ‘z’. The user’s request to autocomplete a prefix goes through the load balancer to any of the available application servers based on round-robin, or any other mechanism, as shown in the diagram above.
Suppose the user enters “be”. Once the request reaches an available application server, the application will check the Redis, or cached database to see if it has suggestions against the prefix “be”. If the suggestions for “be” are not present in the Redis, the request from the application server will scan the Zookeeper instances to see where the suggestions for “be” are stored. Since all the node replicas carry the same trie for phrases from “a” to “z”, any of the nodes can be randomly picked to return the suggestions for “be”. So the request from the application server 1 goes to database node 2 which stores the complete trie. The trie is traversed to find the node for “be”. The same trie node also stores the top 3 suggestions for the prefix “be”.

Splitting Trie Into Multiple Nodes
With a popular search engine such as Google, there can be billions of phrases to store. Storing all these phrases in a single trie is not ideal for availability, scalability or durability of the system. A better solution is to split trie across multiple servers for a durable system and better user experience.
Suppose we split the trie into two parts and each part also has a replica for durability. Phrases starting from characters “a” to “k” are stored in Trie 1 and its replica is stored in Trie 2. Phrases starting from “l” to “z” are stored in Trie 3 and its replica is stored in Trie 4.

Now, when the user types something into the search box, the request goes to the load balancer, which forwards it to any of the available application servers. The application server that gets the request, searches the appropriate trie depending upon the prefix typed by the user. If the user types something that starts with “b”, the application server will access either Trie 1 or Trie 2 because both of them hold the phrases starting with “b”.

Check out the course Coderust: Hacking the Coding Interview for Facebook and Google coding interviews.
How To Update The Trie
So the trie holds searched phrases along with the number of times they were searched, i.e., their popularity. This information will change with every new query. If “bell’ was searched 30 times and a user types in “bell” in the search box, the popularity needs to change from 30 to 31.
Taking into account a popular search engine, such as Google, that serves billions of searches each day, it is resource and time-intensive to update the trie with every new query. Instead we can log the queries and their frequency in a hash table and aggregate the data, let’s say, every hour. After a day passes, we will have the aggregate frequency of each search phrase for a period of 24 hours.

For this purpose, let’s assume that we have a microservice called aggregator. The aggregator collects the information from searches and dumps them in a hash table in a database such as Cassandra. We’ll use this data for updating our trie.

Two types of optimization are possible on this logged data:
- We can discard the data older than a certain number of days if it is not relevant to our search autocomplete system. For example, the application might not need to incorporate search queries older than a month.
- Our search autocomplete system might not have use for phrases with low search frequencies. For example if the aggregate daily or hourly frequency of a phrase is less than a certain number, let’s say 100, we might want to lose that phrase from the hash table because we know that the phrase does not fulfill the criteria to show up in the autocomplete search results.
Once we have the data log in the form of a table for thousands or millions of phrases based on the day the queries were made and their frequency as shown in the diagram above, we can incorporate the entire data into our trie. The microservice called ‘applier’ incorporates the temporary data logs into the trie in the database. It can run every hour, half an hour, or at any predetermined interval.
The applier will fetch the phrases from the hash table together with their frequency and build the trie internally based on some mathematical formula. Once the new trie is ready, it is dumped in place of the old trie in Zookeeper. Once the new trie is available at the Zookeeper, any new request made by a user will receive a response of top phrases based on the newly created trie.
Top YouTube Videos On Designing A Search Autocomplete System
- System design : Design Autocomplete or Typeahead Suggestions for Google search by Tushar Roy — Coding Made Simple
- Amazon interview question: System design / Architecture for auto suggestions | type ahead by Tech Dummies Narendra L
- LeetCode 642. Design Search Autocomplete System Explanation and Solution by happygirlzt
- System Design Google Autocomplete | Typeahead Suggestion | HLD Auto Suggestion | TRIE Data Structure by The Tech Granth
- System Design for Google Typeahead Suggestions by Avneesh Sharma

Conclusion
This is how you design a basic search autocomplete system for a search box, be it for a search engine or a simpler application. Further optimizations are possible in the design, depending on your exact application. You may want to optimize the autocomplete response based on the specific user’s search history. This feature will require the system to maintain a separate table for user specific search results and incorporate the data into the top suggestions that appear when a user queries a keyword.


If you enjoyed the article, kindly support us and consider following. Thank you :)
Your Comprehensive Interview Kit for Big Tech Jobs
0. Grokking the Machine Learning Interview
This course helps you build that skill, and goes over some of the most popularly asked interview problems at big tech companies.
1. Grokking the System Design Interview
Learn how to prepare for system design interviews and practice common system design interview questions.
2. Grokking Dynamic Programming Patterns for Coding Interviews
Faster preparation for coding interviews.
3. Grokking the Advanced System Design Interview
Learn system design through architectural review of real systems.
4. Grokking the Coding Interview: Patterns for Coding Questions
Faster preparation for coding interviews.
5. Grokking the Object Oriented Design Interview
Learn how to prepare for object oriented design interviews and practice common object oriented design interview questions
6. Machine Learning System Design
No comments:
Post a Comment