Loading...
Scale requirements:
Other requirements:
Assumptions:
Assuming the average number of characters of a query is 10, then the number of requests per query is 10 * average searches daily per user of 20 = 200 queries/user/day.
Estimations:
Read:
QPS (Queries per second): 100M users * 200 queries / user / (24 * 3600) seconds = ~230k queries/sec.
Assume 2x peak traffic, peak QPS is 230k *2 = 460k queries/sec.
Write:
Assume 10% of the queries are new, each query is 10 character and each character is 2 bytes, then each query adds 20 bytes. This 100MM * 200 queries * 10% * 20 bytes = 40GB. For a year, it's 14,600 GB = 14.6TB, a large but managable amount of storage.
Use the resource estimator to calculate.
Performance Bottleneck
Given these numbers, the bottlenecks are likely to be in handling QPS and retrieval speed for providing suggestions in real-time
API Design
Our system can expose the following REST APIs:
GET /suggestions?q={search-term}
Response should include a list of suggested terms, ordered by relevance:
{
"suggestions": ["suggestion1", "suggestion2", ..., "suggestionn"]
}
Database Type
Because a "prefix hash table" is essentially a series of key-value pairs, we can simply store it in a key-value database like DynamoDB, MongoDB or Redis.
Data Schema
In the case of a type-ahead or autocomplete system built on Elasticsearch using an inverted index, the data schema would be fairly straightforward. These are usually keyword-based. For this reason, you primarily care about the terms themselves, and less about their relationships or other attributes. However, for the sake of being comprehensive, let's discuss a possible schema that includes some typically useful fields that can be used to rank keywords:
{
"id": "unique_document_id",
"term": "search_term",
"popularity": "term_usage_frequency",
"timestamp": "latest_usage_time"
}
Explanation of each field:
Database Partitioning
For the pre-computed prefix hash table, we can use hash partition. The basic approach is to use a hash function to transform the key into a hash value, and then use that hash value to determine which partition (or shard) the key-value pair should be stored in.
Database Replication
Key-value data stores like DynamoDB and MongoDB have replication built-in. We can configure the number of replicas to ensure high availability and data durability.
Data Retention and Cleanup
We can set a retention policy for the Elasticsearch index, to automatically delete data that is older than a certain period. This would help us manage the size of the index, and ensure that the suggestions are based on recent data.
Write Path
Approach 1: Using a Trie
A Trie (or Prefix Tree) is a tree-like data structure that is used to store a dynamic set or associative array where the keys are usually strings. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string
In the context of the typeahead system, each node in the Trie could represent a character of a word. So, a path from the root to a node gives us a word in the dictionary. The end of a word is marked by an end of word flag, letting us know that a path from the root to this node corresponds to a complete, valid word. The time complexity to get to a node is O(log(length of prefix)).
The frequency of the words are stored in the node themselves. To find the top results, we can find all the nodes in the subtree and sort them by the frequency.
Approach 2: Using Inverted Indexes
An inverted index is a data structure used to create a full-text search. In an inverted index, there is a record for each term or word, which contains a list of documents that this term appears in. This approach is used by most full-text search frameworks such as Elasticsearch.
In the context of the typeahead system, we could store all the prefixes of a word, along with the word itself, in the inverted index. The search operation would then retrieve the list of words corresponding to a given prefix.
Here is how the Inverted Index would look:
{
"c": ["car", "cat"],
"ca": ["car", "cat"],
"car": ["car"],
"cat": ["cat"],
"d": ["dog"],
"do": ["dog"],
"dog": ["dog"]
}
Each key in the index is a prefix, and the value is a list of words that have that prefix.
When searching for the prefix "ca", the system would look up "ca" in the index and retrieve the associated list, which is ["car", "cat"].
As you can see, the Trie and the Inverted Index provide the same results, but they store the data in different ways and the search operations work differently.
Approach 3: Using Predictive Machine Learning Models
Predictive models use machine learning algorithms to predict future outcomes based on historical data. In the context of the typeahead system, we could use a predictive model to suggest the most likely completions of a given prefix, based on the popularity of different completions in the past. This predictive nature is fundamentally how popular tools like ChatGPT work.
This approach could give us more relevant suggestions, but it would be more complex to implement and maintain. Moreover, the suggestions would only be as good as the quality and quantity of the historical data.
We will use the simple Trie approach in our design.
How to Use a Trie to Implement Typeahead
The basic implementation we explored earlier would work for a small amount of data. But as the data set gets large, it gets inefficient to find all children of a node and sort them. One common way to make algorithms faster is to trade space for time. We can pre-compute the results and store them in each node.
Pre-compute to make search faster
However, if the subtree is large, this can get inefficient quickly. A better way is to pre-process the data and store the top results in the node directly. We don't have to navigate down the subtree to find results, significantly improving speed. This comes at the cost of an increase in storage since the nodes are now storing more data.
{
'c': [('cat', 50), ('car', 20)],
'ca': [('cat', 50), ('car', 20)],
'car': [('car', 20)],
'cat': [('cat', 50)],
'd': [('do', 100), ('dog', 50)],
'do': [('do', 100), ('dog', 50)],
'dog': [('dog', 50)],
}
Some people like to call this a "Prefix Hash Tree" and even reference the paper but it's not quite the same as the one described in the paper. The idea is quite simple, create an entry for each prefix. Storing it becomes much simpler due to the key-value nature of the format.
Explain any trade offs you have made and why you made certain tech choices...
Loss of network. We have handled it by caching the data in client side as well.
Multi-Language Support
Handling multiple languages within a trie presents significant challenges due to the wide variety of characters and linguistic structures. Unlike English, which has a limited alphabet, many languages include accented characters, special symbols, and entirely different scripts (e.g., Chinese, Arabic, or Cyrillic). To manage this diversity, the trie must be adapted to support Unicode characters.
Unicode-Compatible Trie Nodes: Each node in the trie is designed to represent a Unicode character instead of being limited to ASCII. This allows the trie to handle all characters in a given language, as well as mixed-language queries. For example, a trie supporting English and French would correctly handle words like "café" or "jalapeño," ensuring accented characters are treated as distinct entities rather than being normalized or ignored.
Separate Tries for Languages or Regions: For large-scale systems supporting many languages, it may be more efficient to create separate tries for different languages or regions. This separation simplifies storage and traversal by confining each trie to its specific language. For instance:
Language detection algorithms are used to determine the query's language. Once identified, the system routes the query to the corresponding trie. This approach ensures optimal performance and avoids unnecessary complexity within a single trie structure.
Autocomplete systems often need to suggest phrases rather than single words. Extending a trie to handle phrases introduces new challenges, as phrases are longer and have more varied structures than individual words.
Trie Extension for Phrases: In a phrase-based trie, each node represents part of a phrase, just as it does for words. However, instead of stopping at single words, the trie continues to store sequences of words. For example, the phrase "how to bake a cake" would be stored with each word forming a node in the sequence:
The top-k suggestions at each node might also include popular phrases that start with the given prefix. For example, typing "how to" could return:
Challenges with Longer Strings: Managing longer strings, such as phrases, increases the size of the trie and its traversal complexity. To address this:
These optimizations ensure the trie remains performant while supporting phrase-based queries.
Autocomplete systems must handle scenarios where user input contains spelling variations, typos, or abbreviations. Incorporating approximation techniques into the trie allows the system to suggest relevant results even when the input does not perfectly match stored queries.
Fuzzy Matching with Levenshtein Distance: Fuzzy matching algorithms like the Levenshtein Distance measure the number of edits (insertions, deletions, substitutions) required to transform one string into another. For example:
During trie traversal, fuzzy matching allows nodes that are close to the query prefix in edit distance to be included in the results. This ensures that queries with minor errors, such as "bokk" instead of "book," still return meaningful suggestions.
Probabilistic Data Structures for Approximation: To handle large datasets and approximate frequencies efficiently, probabilistic data structures like Count-Min Sketch are used. These structures:
For example, instead of storing the exact frequency of "apple" as 1,000, the Count-Min Sketch might approximate it as 995. While this small deviation does not affect the ranking of top suggestions, it dramatically reduces storage and computational overhead.
To integrate these advanced features into the trie: