Step 1 - Understand the problem and establish design scope

Step 2 - Propose high-level design and get buy-in

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.

Step 3 - Design deep dive

Use trie (try) data structure.

After adding frequency info to nodes

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

Update trie weekly, save it in NoSQL, key value store.

• Every prefix in the trie is mapped to a key in a hash table. • Data on each trie node is mapped to a value in a hash table

Like this

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. “max- age=3600” means the cache is valid for 3600 seconds, aka, an hour.

Scale the storage

To mitigate the data imbalance problem, we analyze historical data distribution pattern and apply smarter sharding logic.

Step 4 - Wrap up

If real-time: Change the ranking model and assign more weight to recent search queries.