notexOPENOverview
Notex/Systems/Step 4 - Wrap up
13.13LESSON 13 OF 13 · 2 MIN READ

Step 4 - Wrap up

Always free to read
SECTION VIDEOStep 4 - Wrap up

Video coming soon. Start with the reading below.

COMING SOON

After 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 other non-English queries, we store Unicode characters in trie nodes. If you are not familiar with Unicode, here is the definition: “an encoding standard covers all the characters for all the writing systems of the world, modern and ancient” [5].

Interviewer: What if top search queries in one country are different from others? In this case, we might build different tries for different countries. To improve the response time, we can store tries in CDNs.

Interviewer: How can we support the trending (real-time) search queries? Assuming a news event breaks out, a search query suddenly becomes popular. Our original design will not work because:

  • Offline workers are not scheduled to update the trie yet because this is scheduled to run on weekly basis.
  • Even if it is scheduled, it takes too long to build the trie.

Building a real-time search autocomplete is complicated and is beyond the scope of this book so we will only give a few ideas:

  • Reduce the working data set by sharding.
  • Change the ranking model and assign more weight to recent search queries.
  • Data may come as streams, so we do not have access to all the data at once. Streaming data means data is generated continuously. Stream processing requires a different set of systems: Apache Hadoop MapReduce [6], Apache Spark Streaming [7], Apache Storm [8], Apache Kafka [9], etc. Because all those topics require specific domain knowledge, we are not going into detail here.

Congratulations on getting this far! Now give yourself a pat on the back. Good job!

References

  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/
Progress is saved on this device.
KEEP EXPLORING

One note leads to another.

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