In this article, you’ll learn about How to design and optimize a Typeahead Suggestion system using Java microservices.
Typeahead suggestion Basic concepts:
- Typeahead suggestion, also known as the autocomplete feature, allows users to search for a commonly searched query. When a user types a query into the search box, this feature activates. Based on the user’s search history, the current context of the search, and trending content across different users and regions, the typeahead system provides a list of suggestions to complete a query.
- The most frequently searched queries are always at the top of the suggestion list. The typeahead system does not speed up the search. It does, however, assist the user in forming a sentence more quickly. It is a necessary component of all search engines that improves the user experience.
Requirements of Typeahead Suggestion System
- In this blog Java application development Company examines the requirements and estimated resources required for the design of the typeahead suggestion system. The following requirements should be met by our proposed design.
Functional Aspects:
- Based on the text entered into the search box, the system should suggest the top N (say, top fifty) frequent and relevant terms to the user.
Non-functional aspects:
- Low latency: After a user types, the system should display all suggested queries in real time. The latency should not be more than 300 milliseconds. According to one study, the average time between two keystrokes is 180 milliseconds. As a result, our time-budget for suggestions should be greater than 180 ms in order to provide a real-time response.
- This is because if a user is typing quickly, they may already know what they want to search for and do not require suggestions. Simultaneously, our system response time should be greater than 180 ms. However, it should not be too high because a suggestion may become stale and less useful if it is too high.
Fault tolerance: The system should be dependable enough to provide recommendations even if one or more of its components fails
Scalability: The system should be able to support an increasing number of users over time.
Resource estimation:
As previously stated, the typeahead feature is used to improve the user experience while typing a query. We need to create a system that works on a similar scale to Google Search. Every day, Google receives over 3.5 billion searches. Designing such a massive system is a difficult task that necessitates a variety of resources. Let’s figure out how much storage and bandwidth the proposed system will need
Storage estimation:
- Assume that three billion of the five billion queries per day are unique and must be saved.
- Assume that each query has 15 characters on average and that each character requires 2 Bytes of storage. We would need the following items based on this formulation:
- To store all of the queries made in a day, multiply 5 billion * 15 * 2 = 150 GB
- Annual storage requirements: 150 GB/day * 365 = 54.75 TB/year
Estimated Bandwidth
- Every day, 5 billion queries will reach our system. Assume that the average length of a user’s query is 15 characters
- Keeping with this in mind, the total number of character reading requests per day would be as follows:
15× 5 billion=75 billion chars per day.
- Total read requests per second: 75B/86400= approx 0.868 M characters/sec. 86,400 is nothing but the number of secs per day.
- Since each character takes 2 Bytes, the system bandwidth here will need is as follows:
- 868M×2×8=13.8Mb/sec is the incoming requirement of bandwidth for the queries that have a max length of 15 characters.
- After each character a user types, our system will suggest the top ten queries that are roughly the same length as the query length.
As a result, the outgoing bandwidth requirement would be as follows: 15×10×13.8Mb/sec=2.07Gb/sec
Building blocks:
- Databases are required to store data related to query prefixes.
- Load balancers are required to distribute incoming queries across multiple active servers.
- Caches are used to store the top N suggestions for quick retrieval.
Typeahead Suggestion System high-level design
Accordingly, The system should not only suggest queries in real time with minimal latency, but it should also store new search queries in the database, according to our requirements. As a result, the user receives recommendations based on popular and recent searches.
Our proposed system should do the following:
- Make suggestions based on the user’s search history.
- Here, Store all new and trending queries in the database so that they can be included in the list of suggestions.
- When a user begins typing a query, each character is routed to one of the application servers. Assume we have a suggestions service that retrieves the top ten suggestions from the cache, Redis, and returns them to the client in addition to this it does optimization as well.
- Assume we have another service called an assembler. An assembler collects user searches, ranks them using analytics, and stores them in a NoSQL database distributed across multiple nodes.
API design
- Instead of refreshing the entire page, we only need to refresh the suggested query in the search box in real time.
- getSuggestionsForUsers(prefix): This API call queries the servers for suggestions. This call is made through the suggestion service, and the response is returned to the client.
- Prefix in this method Arugument: This is whatever the user typed into the search bar
- addValueToDatabase(query): This API call uses an assembler to add a trending query to the database if it has already been searched and has exceeded a certain threshold.
query : This is a frequently searched query that exceeds the predefined limit.
How can we Store the Prefixes:
- The trie data structure: Before we get into the details of the typeahead suggestion system, we need to choose an efficient data structure to store the prefixes. Prefixes are character groups that a user types.
- The problem we’re attempting to solve is that we have a large number of strings that must be stored in a way that allows users to search for them using any prefix. Our service suggests the following words based on the provided prefix. Assume our database includes the terms SERIAL, SILENT, SERIALNUMBER, and SERIALEPISODE. When the user types “SER,” our system should suggest “SERIAL,” “SERIALNUMBER,” and “SERIALEPISODE.”
- Because we must handle a large number of requests with minimal latency, there should be a method for efficiently storing our data and assisting us in conducting fast searches. We can’t use a database for this because it takes longer to provide suggestions from the database than it does to read suggestions from RAM. As a result, we must keep our index in memory in an efficient data structure. This data, however, is stored in the database for durability and availability.
- Here, the trie (pronounced “try”) is one of the best data structures for our needs. A trie is a tree-like data structure that stores phrases in order, with each tree node storing a character from the phrase. If we needed to save SERIAL, SILENT, and SERIALNUMBER, we could do so.
- The trie data structure here can combine nodes where only one branch exists, reducing the depth of the tree. This also decreases traversal time, which increases efficiency..
How can we track the top searches
- We store the number of times each term is searched in the trie node because our system keeps track of the top searches and returns the top suggestion..
- Here, let’s Assume a user searches for SERIAL ten times, SERIAL twenty-eight times, SERIALNUMBER twenty-five times, and SERIALEPISODE twenty-five times. These counts are saved in each node where these terms terminate in order to provide the best suggestions to the user.
Detailed Components design:
Suggestion Microservice#
At the same time that a user types a query in the search box, the getSuggestionsForUsers(prefix) API: Here API calls hit the suggestions services at the same time a user types a query in the search box. The top ten most popular queries are returned by Redis, a distributed cache.
Interpreter/Assembeler
- Previously , I have mentioned how tries data structure is created, partitioned, and stored in the database. The creation and updating of a trie, on the other hand, should not be in the critical path of a user’s query. For the following reasons, we should not update the trie in real time.
- Millions of users could be entering queries every second. During such periods of high incoming traffic, updating the trie on each query in real time can slow down our suggestion service.
- We must provide top suggestions that may not frequently change following the creation or updating of the trie. As a result, updating the trie on a regular basis is less important.
- It is because of the reasons stated above, we have a separate service called an assembler that is in charge of creating and updating tries after a configurable amount of time. The assembler is made up of the following services:
- Here, Aggregator/Collection Microservice: When a user types, this service collects the log, which includes phrases, time, and other metadata, and stores it in a database for later processing. Because this data is so large, the Hadoop Distributed File System (HDFS) is regarded as a suitable storage system for storing it
- The table below shows an example of raw data from the collection service. We keep track of the time so that the system knows when to change the frequency of a particular phrase.
Phrases Timestamp (DD-MM-YYYY HH:MM:SS)
SERIALNUMBER 11-08-2022 10:16:18
SERIALEPISODE 11-08-2022 10:20:11
SERLAC 11-08-2022 10:21:10
Aggregator component:
- The raw data collected by the Aggregator/collection microservice is rarely consolidated. We need to combine the raw data in order to process it further and create or update the tries.
- An aggregator retrieves data from HDFS and distributes it to various workers. In general, the MapReducer is in charge of aggregating the frequency of the prefixes over a given time interval, and the frequency is updated on a regular basis in the associated Cassandra/Mongo database. Because it can store large amounts of data, Mongo/Cassandra is ideal for this purpose(Data stored here is in a tabular format).
- The table below displays the processed and consolidated data for a specific time period. The aggregator updates this table on a regular basis, and it is stored in a hash table in a database like Cassandra. For the sake of simplicity, we will assume that our data is case insensitive.
Phrases Frequency Time Interval
SERIALNUMBER 400 1st 10 minutes
SERIALEPISODE 1040 1st 10 minutes
SERLAL 1000 1st 10 minutes
Satisfying our Non-Functional requirements
- Low latency: There are several levels at which we can reduce system latency. We can reduce latency by using the following options:
- Shorten the traversal time by decreasing the depth of the tree so that the performance of the search functionality will be increased and latency will be reduced.
- Update the trie offline, which means that the time spent on the update operation is not on the critical path of the clients.
- Make use of geographically dispersed application and database servers. This way, the service is provided close to the user, which reduces communication delays and helps to reduce latency.
- On top of NoSQL database clusters, use Redis and Mongo/Cassandra cache clusters. Appropriate partitioning tries, resulting in proper load distribution and improved performance.
- Fault tolerance: Because tree replication and partitioning are provided, the system is highly resilient. If one server fails, others are ready to provide services.
- Scalability: Since this the main factor in any system designing part, here because our proposed system is adaptable, more servers can be added or removed as demand grows. For example, as the number of queries grows, so does the number of partitions or shards in the trees.
Conclusion
- The Typeahead suggestion system is an effective service with multiple advantages. Our design of this service is simple, yet it fulfills all the requirements of Java developer jobs openings Pune for freshers a performing design. The key features offered by our design are:
- A responsive Web application which can give results for all cities across Globe with Improved readability
FAQs:
Subject: orchestrate and design a Typeahead Suggestion System using Springboot in Java Microservices Applications
- What is a Typeahead Suggestion System and why it is used?
Ans: Typeahead suggestion is a functionality which allows users to search for a commonly searched query. When a user types a query into the search box, this feature activates. Based on the user’s search history, the current context of the search, and trending content across different users and regions, the typeahead system provides a list of suggestions to complete a query
- What are the functional and nonfunctional requirements for Typeahead Suggestion backend system?
Ans: Functional: Based on the text entered into the search box, the system should suggest the top N (say, top fifty) frequent and relevant terms to the user.
Non Functional: The system should be Fault tolerant and dependable enough to provide recommendations. The system should also be scalable to support an increasing number of users over time
How to design and develop the rest API for the backend system of Typeahead Suggestion?
Ans: You have to getSuggestionsForUsers(prefix): This API call queries the servers for suggestions. This call is made through the suggestion service, and the response is returned to the client. Here, Prefix in this method Arugument: This is whatever the user typed into the search bar
addValueToDatabase(query): This API call uses an assembler to add a trending query to the database if it has already been searched and has exceeded a certain threshold
- What are the end-to-end components required for designing a Typeahead Suggestion Application in Java microservices?
Ans: High level functionalities should includ:
Make suggestions based on the user’s search history.Here, Store all new and trending queries in the database so that they can be included in the list of suggestions.
When a user begins typing a query, each character is routed to one of the application servers. Assume we have a suggestions service that retrieves the top ten suggestions from the cache, Redis, and returns them to the client in addition to this it does optimization as well.
In this blog, I have explained clearly with high level and detailed component diagram.
- How can you track the top searches in the Typeahead Suggestion backend system?
Ans: We have to use Trie Datastrcuture here. We store the number of times each term is searched in the trie node because our system keeps track of the top searches and returns the top suggestion.
Here, let’s Assume a user searches for SERIAL ten times, SERIAL twenty-eight times, SERIALNUMBER twenty-five times, and SERIALEPISODE twenty-five times. These counts are saved in each node where these terms terminate in order to provide the best suggestions to the user.
