Loading...
Response time is very important. After a user types a letter, text suggestion should show up within 100ms.
Scalability. We can expect 10M DAU.
Availability - it is probably acceptable to not over-focus on availability. If text suggestion is unavailable for a short period of time, users probably would not suffer critical consequences.
I assume that there is a web service which can return a personalized (via email address) list of 1,000 most likely search words. Because this is an external web service, we will consider an error scenario where this service is down.
Other error scenario is the text suggestion service being unavailable. We will ensure the client will be able to operate gracefully even if the server is unreachable.
10 million DAU
An average person performs 10 searches per day.
20 bytes per search
For every character into the search box, a client sends a request to the back-end for autocomplete suggestions.
1 million * 10 queries per day * 20 characters / 24 hours / 3600 seconds = 24,000 query per seconds
Peak QPS = QPS * 2 = 48,000
Assume 20% of the daily queries are new.
The key to high performance is that the client (browser) has enough information to make suggestion recommendation, without asking server each time the user types.
Client would call:
get_words(priority_from, priority_to)
Let's say the popular words are sorted by priority, 0 to 1,000.
Upon page load, the client would ask for the most popular words, e.g., first 1,000. It will be personalized for the user.
If the client has bandwidth or resource concern, it may choose to ask for fewer number of words at a time (let's say first 100 first), and ask for more later. This would be similar to paging.
But I expect most clients to ask for all the words (e.g. 1,000). If each word is 10 letters on average, it'd amount to 10KB. Most modern browsers and networks are capable of sending and receiving this much data.
The return data (words) can be transmitted in a simple array in JSON format.
Trie Cache: Tries are a type of data structure especially well-suited for creating efficient autocomplete systems. They allow for quick lookup, insertion, and deletion of strings, making them ideal for autocomplete functionalities where prefixes of words are used to suggest whole words or phrases. The Trie Cache acts as a fast-access storage layer that holds recently or frequently accessed autocomplete data, reducing the need to query the database repeatedly.
Trie DB: This database permanently stores the complete set of data used for the autocomplete suggestions. If the Trie Cache doesn't have the data needed to respond to a query, the system will fetch it from the Trie DB, potentially updating the cache with this new information.
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
Client: This represents the user's interface, such as a web browser or a mobile app, from which the user types in text input that needs autocomplete suggestions.
Load Balancer: It distributes incoming requests from clients evenly across multiple servers to ensure that no single server becomes overwhelmed, which maintains performance and increases reliability.
CDN (Content Delivery Network): While CDNs are typically used for static assets, they can also be used to cache API responses for commonly requested autocomplete suggestions. This can reduce latency by serving suggestions from geographically closer data centers.
Words Server: This server handles the logic for processing the autocomplete queries. It likely receives partial input text from the client and interacts with the Trie Cache to fetch possible completions.
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
Once Trie is built, it enables fast look up of potential words. For example:
a-p-p-l-e
-i-c-a-t-i-o-n
This Trie gives three choices: app, apple, application, when a user types the first letter 'a'. It quickly cuts off possibilities of any words starting from other letters.
As long as the client has this Trie structure in memory, it can quickly traverse it and show word completion candidates.
As such, the client's job is to maintain this Trie (build it and store it in the client side storage). The server's job is to give this information to the client in an efficient way, from CDN and from Words Server.
Explain any trade offs you have made and why you made certain tech choices...
One common failure scenario would be the loss of network. The client would not be able to reach the Words Server.
This design handles this error case gracefully. Because the client stores the necessary information for the functionality (the popular words stores in Trie data structure), the client can function correctly.
The only issue is that it would not receive new candidate words while the network is down. This would be acceptable. The faulty network would probably cause bigger issues (such as not being able to query a search engine.)