When searching on Google or shopping at Amazon, as you type in the search box, one or more matches for the search term are presented to you. This feature is referred to as…
- 13.01Design a search autocomplete systemWhen searching on Google or shopping at Amazon, as you type in the search box, one or more matches for the search term are presented to you. This feature is referred to as…
- 13.02Step 1 - Understand the problem and establish design scopeThe first step to tackle any system design interview question is to ask enough questions to clarify requirements. Here is an example of candidate-interviewer interaction:…
- 13.03Back of the envelope estimationAssume 10 million daily active users (DAU).An average person performs 10 searches per day.20 bytes of data per query string:Assume we use ASCII character encoding. 1 character…
- 13.04Step 2 - Propose high-level design and get buy-inAt the high-level, the system is broken down into two: Data gathering service: It gathers user input queries and aggregates them in real-time. Real-time processing is not…
- 13.05Data gathering serviceLet us use a simplified example to see how data gathering service works. Assume we have a frequency table that stores the query string and its frequency as shown in Figure…
- 13.06Query serviceAssume we have a frequency table as shown in Table 13-1. It has two fields. Query: it stores the query string.Frequency: it represents the number of times a query has been…
- 13.07Step 3 - Design deep diveIn the high-level design, we discussed data gathering service and query service. The high-level design is not optimal, but it serves as a good starting point. In this section,…
- 13.08Trie data structureRelational databases are used for storage in the high-level design. However, fetching the top 5 search queries from a relational database is inefficient. The data structure…
- 13.09Data gathering serviceIn our previous design, whenever a user types a search query, data is updated in real-time. This approach is not practical for the following two reasons: Users may enter…
- 13.10Query serviceIn the high-level design, query service calls the database directly to fetch the top 5 results. Figure 13-11 shows the improved design as previous design is inefficient. A…
- 13.11Trie operationsTrie is a core component of the autocomplete system. Let us look at how trie operations (create, update, and delete) work. Create Trie is created by workers using aggregated…
- 13.12Scale the storageNow that we have developed a system to bring autocomplete queries to users, it is time to solve the scalability issue when the trie grows too large to fit in one server. Since…
- 13.13Step 4 - Wrap upAfter you finish the deep dive, your interviewer might ask you some follow up questions. Interviewer: How do you extend your design to support multiple languages? To support…
References
Step 4 - Wrap up
- The Life of a Typeahead Query: https://www.facebook.com/notes/facebookengineering/the-life-of-a-typeahead-query/389105248919/
- How We Built Prefixy: A Scalable Prefix Search Service for Powering Autocomplete: https://medium.com/@prefixyteam/how-we-built-prefixy-a-scalable-prefix-search-servicefor-powering-autocomplete-c20f98e2eff1
- Prefix Hash Tree An Indexing Data Structure over Distributed Hash Tables: https://people.eecs.berkeley.edu/~sylvia/papers/pht.pdf
- MongoDB wikipedia: https://en.wikipedia.org/wiki/MongoDB
- Unicode frequently asked questions: https://www.unicode.org/faq/basic_q.html
- Apache hadoop: https://hadoop.apache.org/
- Spark streaming: https://spark.apache.org/streaming/
- Apache storm: https://storm.apache.org/
- Apache kafka: https://kafka.apache.org/documentation/