notexOPENOverview
Notex/Systems/Design a search autocomplete system

Design a search autocomplete system

Always free to read

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…

1313 LESSONS · 20 MIN
  1. 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…READING1 MIN
  2. 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:…READING1 MIN
  3. 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…READING1 MIN
  4. 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…READING1 MIN
  5. 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…READING1 MIN
  6. 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…READING1 MIN
  7. 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,…READING1 MIN
  8. 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…READING4 MIN
  9. 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…READING3 MIN
  10. 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…READING2 MIN
  11. 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…READING1 MIN
  12. 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…READING1 MIN
  13. 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…READING2 MIN

References

Step 4 - Wrap up
  1. The Life of a Typeahead Query: https://www.facebook.com/notes/facebookengineering/the-life-of-a-typeahead-query/389105248919/
  2. 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
  3. Prefix Hash Tree An Indexing Data Structure over Distributed Hash Tables: https://people.eecs.berkeley.edu/~sylvia/papers/pht.pdf
  4. MongoDB wikipedia: https://en.wikipedia.org/wiki/MongoDB
  5. Unicode frequently asked questions: https://www.unicode.org/faq/basic_q.html
  6. Apache hadoop: https://hadoop.apache.org/
  7. Spark streaming: https://spark.apache.org/streaming/
  8. Apache storm: https://storm.apache.org/
  9. Apache kafka: https://kafka.apache.org/documentation/
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K