Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
User Base and Traffic Estimation:
Request Frequency:
Storage Requirements:
Query Cache and Frequency Data:
Define what APIs are expected from the system...
The most basic API is a request to fetch autocomplete suggestions based on the currently typed query.
When a search query has been fully executed, our service should also accept a POST request so that it can store the query. This is not an essential part of completing a user's search, so we would likely have this step happen as part of background processing. Whatever part of the system is responsible for actually handling searches could place the search query onto a message queue, where it would later be processed by an ingestion system which would store the query for further analytics and to inform query rankings going forward.
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...
As a start, let's cover the basic entities we need for our auto-complete system. The main entity we need is a searchQuery. The most essential items we need from a search query are the literal string of the query and some indication of how common the query is, either as a total number of times query or as some rank in the most common queries.
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
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...
To understand how request flows through the system, we can start with the processing of completed search queries. After a full search query is executed, the full text of the search can be placed on a message queue where some number of workers will be processing those queries. When the full text is picked up by a worker, we may consider applying some data transformation at this point, such as making all letters lowercase, removing whitespace and non-alphanumeric characters, or possibly fixing typos. Once any data cleansing has been applied, we would store the query in our datastore.
In addition to simply storing the queries in our datastore, we will need to analyze which queries occur most frequently. If we use a NoSQL database as our datastore that uses key/value pairs, we could use the query text itself as the key and keep a count as one of the fields associated to the query text. We may also be interested in recording the geographic location where the query was made from, a timestamp of when the query was searched, and other metadata that may be useful.
In addition to the datstore where we store all queries and their associated metadata, we will likely want a separate datastore that stores the most common queries, such as the top 100,000 queries. This datastore will be optimized for fast reads based on the prefix search queries that need to be autocompleted.
When a user is actively entering text into a search bar in a client, the client will send the text as it is being entered to an instance of the autocomplete service, which will send back some number of the most relevant autocompletions, such as the 10 most common searches containing the prefix already entered.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
One of the key design choices will be making sure the cache of the most common search queries is optimized for extremely low latency reads based on the prefix already typed by the user. We may want to store the cache in memory on the auto-complete service as a trie or prefix-tree, which can be searched very quickly based on the prefix.
Explain any trade offs you have made and why you made certain tech choices...
We need to consider what kind of connection between the client will best facilitate the low latency return of auto-complete suggestions. One good choice might be websockets for real time communication between the client and service. Using typical HTTP requests and responses involve much more overhead for each request/response cycle. We don't need the benefits here of HTTP, and the overhead of setting up new connections for each request would significantly impair out ability to make this service low latency. By using websockets, the connection can be established as soon as the client is open on the site and left alive, reducing the need to establish new connections every time the user types another character,
Try to discuss as many failure scenarios/bottlenecks as possible.
We need replicas of the datastore and cache to ensure high availability and also to act as backups in the case of failures of other instances.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
The system could be enhanced by having the most frequent searches take into account the client's location. Users in the same countries and regions may find suggestions also searched by people near them to be more relevant. We could also use make sure instances of our auto-complete service are available in many different geographic locations to further reduce latency between client and service.