System requirements

Functional:

• Implement autocomplete functionality to suggest completions as users type.
• Ensure that the suggestions are updated in real-time as new data becomes available.

Non-Functional:

• System should not be too slow, it should be able to respond with some suggestions within about half a second
• The system should be highly available and reliable, with minimal downtime.
• The system should be able to handle a large number of concurrent users making search queries.

Capacity estimation

Traffic Estimation:

• 5 million daily users, each user uses this system 10 times a day

Bandwidth estimation:

• 50 million requests a day -> 2.1 million requests an hour -> 35000 requests an= min -> 600 requests a second
• Assuming each response is about 1KB -> 600KB per second

Storage estimation:

• Assuming that we only keep queries for 5 years
• 50 million requests / day -> 18 billion / year -> 180 billion / 10 years
• out of the 180 billion requests, assuming that only 10% of these queries are unique, we have to keep 18 billion unique queries in our storage = 17 TB of data

API design

send_query(text), text would be the prefix, meaning that this is what the user has typed in so far, the system will then return 5 of the most highly suggested phrases

Database design

We want to keep our data in such a way that it would be quick to query the top 5 suggestions given a prefix. We want to keep it in a Trie. We can keep the trie in the main memory, this allows for fast querying given a prefix.

High-level design

Client -> Backend Server (That contains the Trie)

Request flows

When the user begins typing on the text box, it begins sending the prefixes to the system. The system will take the prefix and start looking for the node in which the query ends, the system then returns the top suggestions from each node

Detailed component design

Lets go deeper into some components

Firstly, the Trie. How the Trie structure would work is that the leaves of the Tries would contain the number of times it has been searched. Meaning lets say you search 'Happy Dog Playing', the node that contains the last letter 'g' has an additional count to it. Then it traverses back from the leaf to the root across various nodes, each time it traverses a node, the node will take the text and the count of the top 5 most searches queries and return it to its parents. Here, you can see how each node in the Trie will each have 5 of the top searched queries.

However, if we keep all the queries in the Trie, it would overwhelm the system due to the sheer number of different combinations and permutations of letters possible. The Trie would be way too big. So how can we mediate this? We want to keep count of the number of times a particular query has been searched, only when a query has been searched over 1000 times, then we will add it to the Trie, we can do this by using a NoSQL key-value pair DB like Dynamo DB. However, then again if we keep querying the DB after every time a user sends a query request, it would overwhelm the system. Hence we will keep an in memory key-value buffer, where the key is the query and the count is the number of times the query has been searched. Every 5 seconds or so, we will dump the data into the NoSQL DB. This will be useful to reduce the number of times we query the DB.

Secondly, when the client starts typing in the text box, the client will wait until the client pauses for a moment (0.2 seconds) before sending the query to the backend, we dont want to send a query each and every time the client types in a letter in the text box, it would overwhelm the system. When the client begins typing, it establishes a WebSocket with the system, this is so that they can persistently send queries without establishing a new connection every time, which wastes a lot of time.

When the system receives the query, it will start going through the Trie to find the top 5 suggestions, however it will only respond to the client once it has stopped receiving requests from this client through the WebSocket for more than 0.2 seconds, this prevents the system from responding too many times when the client stops and starts typing in quick succession.

What would be the best way to do data sharding? We cannot keep a singular Trie in a singular server, it has to be distributed into multiple different servers. We could potentially distribute it by the first letter of each query, however this would lead to uneven distribution because letters like 't', 'a' or 'e' are some very popular first letters of a query while 'x' 'q' or 'v' are much more uncommon, this would lead to uneven distribution of load between servers. Random distribution would also not be ideal as it does not take advantage of the state of the Tries between each server. What I suggest is to distribute based on the first two characters of the query. If a two letter combination has not been searched before, then allocate it to the server with the smallest Trie at the moment

We will also have a server that will do cleaning up. Meaning if a query has not been searched for more than 5 years, they will not only be cleared from the DB, they will also be cleared from the Trie in the particular server, this is to ensure better storage management

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

We must prevent single points of failures by having back up servers that contains duplicates of the main server's Tries. Every 5 seconds or so, the back up servers will do passive copying of the main server's Tries

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?