System requirements

Functional:

1. System should return suggestions for a given prefix based on previously searched queries
2. Should return top n relevant suggestions. n is configurable. Lets go with 5
3. Relevance calculation should take frequency and recency into consideration.

Non-Functional:

1. Should be highly available. Queries should not go unregistered and suggestions should not return unavailable error.
2. Low latancy: suggestions should be returned as fast as possible.
3. Scalable: Should be able to handle large amount of query saves and even larger amount of suggestion requests.

Capacity estimation

1. 1 billion searches per day, 200 million unique searches
2. Each search query is 3 words long on avg, each word in 5 letters long on avg.
3. So, since getting suggestions happen for every letter we have 15*1 billion calls to get suggestions.
4. We store on avg 15 * 200 million characters

API design

1. /api/v1/suggestions/{prefix} - GET
2. /api/v1/query - POST
   1. body will have query string

Database design

We can use a trie based data structure for storing the query data. Each node will represent a character in the query. Each node will also have a boolean flag representing if it is a terminal character. It also has a list of suggested queries with prefix as the string starting from the root to that node. This is order by ranking (combination of recency and frequency). So we can use a PriorityQueue here.

The schema looks like this

Trie :-

root: TrieNode

TrieNode:-

nextChars: Map

topSuggestions: PriorityQueue

terminal: boolean

frequency: Integer

Suggestion:-

query: String

frequency: Integer

lastSearched: DateTime

High-level design

QueryService handles api when a complete query is searched.

TrieService updates the Trie data when it receives a query.

SuggestionsService handles api which returns the top suggestions when user enters a prefix using the trie data.

Request flows

When query service receives a query, it sends the query data to the trie service

TrieService updates the Trie data when it receives a query.

When suggestion service receives a request to get the suggestions based on a query, it traverses the trie to get the list of suggestions for that prefix and returns the list of suggestions

Detailed component design

When query service receives a query, it sends the query data to the trie service. We can batch the requests to a fixed configurable batch size, we can aggregate the local frequencies and send them.

TrieService updates the Trie data when it receives a query. While traversing each character of the query, it traverses down the trie level by level and updates the frequency and lastSearched. And again it traverses way up in the same path (we can use stack or recursion) and at each node, it updates topSuggestions. topSuggestions is a priorityqueue which sorts itself on every update by rank. The rank is caluclated by taking frequency and timeSinceLastSearched (which we can get from lastSearched) as parameters and multiplying them with fixed weights which are configurable and adding the product. We can have negative weight for timeSinceLastSearched.

Suggestion service traverses the trie along the characters of the input prefix and returns the topSuggestions list (or priorityqueue) at the node representing the last character of the prefix.

Trade offs/Tech choices

We chose batching over sending every word, because we are dealing with high traffic scnarios. We are receiving approx 12000 queries (1b / 24*60*60) every second. The data will be eventually correct. Since we are also taking frequency into consideration, the delay in consistency may not be that critical.

Failure scenarios/bottlenecks

1. Problem: The suggestion service going down or choking on high demand situations. Solution: Autoscaling with Loadbalancer
2. Problem: The query service going down or choking on high demand situations. Solution: Autoscaling with Loadbalancer
3. Problem: The trie service going down or choking on high demand situations. Solution: Autoscaling with Loadbalancer or adding a message queue between query service and trie service. Or we can have a hybrid model where the trie service scales along with the queue size (we can have monitoring and listeners and custom autoscaling with load balancers to achieve that)
4. Problem: Data store growing over time and going down or choking on high demand situations. Solution: Partiotining by first character and replication.

Future improvements

Solutions for Failure scenarios/bottlenecks:

1. Problem: The suggestion service going down or choking on high demand situations. Solution: Autoscaling with Loadbalancer
2. Problem: The query service going down or choking on high demand situations. Solution: Autoscaling with Loadbalancer
3. Problem: The trie service going down or choking on high demand situations. Solution: Autoscaling with Loadbalancer or adding a message queue between query service and trie service. Or we can have a hybrid model where the trie service scales along with the queue size (we can have monitoring and listeners and custom autoscaling with load balancers to achieve that)
4. Problem: Data store growing over time and going down or choking on high demand situations. Solution: Partiotining by first character and replication.

Improvements:

1. Fuzzy search - We can have another parameter similar to frequency and recency call error distance which also has negative weight. While updating the trie nodes on query, we also update their nearby letters at every character of the query but we use error distance as the distance from the original character and calculate the rank.