13-Design a Search Autocomplete System

Design a Search Autocomplete System

Understand the problem and establish design scope

Propose high-level design and get buy-in

At the high-level, the system is broken down into two:

• Data gathering service: It gathers user input queries and aggregates them in real-time. Real-time processing is not practical for large data sets; however, it is a good starting point. We will explore a more realistic solution in deep dive Data gathering service deep dive.
• Query service: Given a search query or prefix, return 5 most frequently searched terms.

Data gathering service

Assume we have a frequency table that stores the query string and its frequency as shown below. In the beginning, the frequency table is empty. Later, users enter queries “twitch”, “twitter”, “twitter”, and “twillo” sequentially:

Query service

Assume we have a frequency table as shown:

Query	Frequency
twitter	35
twitch	29
twilight	25
twin peak	21
twitch prime	18
When a user types “tw” in the search box, the following top 5 searched queries are displayed:
twitter, switch, twilight, twin peak, and twitch prime.

To get top 5 frequently searched queries, execute the following SQL query:

SELECT * FROM frequency_table
WHERE query LIKE `prefix%`
ORDER BY frequency DESC
LIMIT 5

This is an acceptable solution when the data set is small. When it is large, accessing the database becomes a bottleneck. We will explore optimizations in deep dive.

Design deep dive

we will dive deep into a few components and explore optimizations as follows:

• Trie data structure
• Data gathering service
• Query service
• Trie operations
• Scale the storage

Trie data structure

Prefix Hash Tree An Indexing Data Structure over Distributed Hash Tables
Relational databases are used for storage in the high-level design. However, fetching the top 5 search queries from a relational database is inefficient. The data structure trie (prefix tree) is used to overcome the problem.

Trie is a tree-like data structure that can compactly store strings. The name comes from the word re”trie”val, which indicates it is designed for string retrieval operations. The main idea of trie consists of the following:
 - The root represents an empty string.
 - Each node stores a character and has 26 children, one for each possible character. To save space, we do not draw empty links.
 - Each tree node represents a single word or a prefix string.
To support sorting by frequency, frequency info needs to be included in nodes. Assume we have the following frequency table.

Query	Frequency
tree	10
try	29
true	35
toy	14
wish	25
win	50
![[05-System Designs/System Design Interview 1/_Attachments/Screenshot 2026-08-05 at 4.03.38 PM.png	482]]

How autocomplete works with trie

Let us define some terms:

• p: length of a prefix
• n: total number of nodes in a trie
• c: number of children of a given node
  Steps to get top k most searched queries follow below:

1. Find the prefix. Time complexity: O(p)
   • e.g. “be”
2. Traverse the subtree from the prefix node to get all valid children. A child is valid if it can form a valid query string. Time complexity: O(c)
   • e.g. [bee: 20], [beer: 10], [bet: 29], [best: 35]
3. Sort the children and get top k. Time complexity: O(clogc)
   • e.g. assume k = 2, so [bet: 29], [best: 35]

The time complexity of this algorithm is the sum of time spent on each step mentioned above: O(p) + O(c) + O(clogc).

Optimization

The above algorithm is straightforward. However, it is too slow because we need to traverse the entire trie to get top k results in the worst-case scenario. Below are two optimizations:

1. Limit the max length of a prefix
2. Cache top search queries at each node

Limit the max length of a prefix

Users rarely type a long search query into the search box. Thus, it is safe to say p is a small integer number, say 50. Then, the time complexity for “Find the prefix” can be reduced from O(p) to O(small constant), aka O(1).

Cache top search queries at each node

To avoid traversing the whole trie, we store top k most frequently used queries at each node.
In our specific case, only the top 5 search queries are cached. By caching top search queries at every node, we significantly reduce the time complexity to retrieve the top 5 queries. However, this design requires a lot of space to store top queries at every node. Trading space for time is well worth it as fast response time is very important.

As the result, the updated trie data looks like below:

After applying those two optimizations:

1. Find the prefix node. Time complexity: O(1)
2. Return top k. Since top k queries are cached, the time complexity for this step is O(1).

As the time complexity for each of the steps is reduced to O(1), our algorithm takes only O(1) to fetch top k queries.

Data gathering service deep dive

In the high-level design, whenever a user types a search query, data is updated in real-time. This approach is not practical for the following two reasons:

• Users may enter billions of queries per day. Updating the trie on every query significantly slows down the query service.
• Top suggestions may not change much once the trie is built. Thus, it is unnecessary to update the trie frequently.

To design a scalable data gathering service, we examine where data comes from and how data is used. Real-time applications like Twitter require up to date autocomplete suggestions. However, autocomplete suggestions for many Google keywords might not change much on a daily basis.

Despite the differences in use cases, the underlying foundation for data gathering service remains the same because data used to build the trie is usually from analytics or logging services.

Analytics Logs

It stores raw data about search queries. Logs are append-only and are not indexed:

query	time
tree	2019-10-01 22:01:01
try	2019-10-01 22:02:05
tree	2019-10-01 22:03:30

Aggregators

The size of analytics logs is usually very large, and data is not in the right format. We need to aggregate data so it can be easily processed by our system.
For real-time applications such as Twitter, we aggregate data in a shorter time interval as real-time results are important. On the other hand, aggregating data less frequently, say once per week, might be good enough for many use cases. During an interview session, verify whether real-time results are important.

Aggregated Data

The following shows an example of aggregated weekly data:

query	time	frequency
tree	2019-10-01	12000
try	2019-10-01	8500
tree	2019-10-08	15000
try	2019-10-08	10000

Workers

Workers are a set of servers that perform asynchronous jobs at regular intervals. They build the trie data structure and store it in Trie DB.

Trie Cache

Trie Cache is a distributed cache system that keeps trie in memory for fast read. It takes a weekly snapshot of the DB.

Trie DB

Query service

In the high-level design, query service calls the database directly to fetch the top 5 results.
Below shows the improved design as previous design is inefficient:

1. A search query is sent to the load balancer.
2. The load balancer routes the request to API servers.
3. API servers get trie data from Trie Cache and construct autocomplete suggestions for the client.
4. In case the data is not in Trie Cache, we replenish data back to the cache. This way, all
   subsequent requests for the same prefix are returned from the cache.

Query Service Optimization

Query service requires lightning-fast speed. We propose the following optimizations:

<!— annoteca/review: What was AJAX?

[id=ouijzdak]
[date=2026-08-05T17:27:33]
[anchor=AJAX request]
—> AJAX request
For web applications, browsers usually send AJAX requests to fetch autocomplete results. The main benefit of AJAX is that sending/receiving a request/response does not refresh the whole web page.

Browser caching

Autocomplete suggestions can be saved in browser cache to allow subsequent requests to get results from the cache directly. For example

Trie operations

Create

Trie is created by workers using aggregated data. The source of data is from Analytics Log/DB.

Update

Option 1

Update the trie weekly. Once a new trie is created, the new trie replaces the old one.

Option 2

Update individual trie node directly. We try to avoid this operation because it is slow.
When we update a trie node, its ancestors all the way up to the root must be updated because ancestors store top queries of children.

Delete

We have to remove hateful, violent, sexually explicit, or dangerous autocomplete suggestions. We add a filter layer in front of the Trie Cache to filter out unwanted suggestions.

## Scale the storage

Wrap up

How do you extend your design to support multiple languages?

To support other non-English queries, we store Unicode characters in trie nodes.

What if top search queries in one country are different from others?

In this case, we might build different tries for different countries. To improve the response time, we can store tries in CDNs.

How can we support the trending (real-time) search queries?