Thank you tushar, you were my number 1 guy to learn data structures and algorithms, now after graduating and working i am getting back to you to learn about system design Again thanks a lot
I’m loving these new videos. You’re obviously an amazing human being. I’m a little saddened that you’re into the nfl but I think I’ll survive. Thanks Tushar!
You replied! I'm NBA/WNBA all the way. I have a hard time with how dangerous football is. But in Seattle you don't have NBA so I can't blame you too much! Thanks again Tushar!
@@tusharroy2525 In my mind you went to the weekend game and started making 'system design' video right after you are home. Respect for engineers like you!
You rock as usual, I can see your improvements from solving a problem from single machine to a distributed machines techniques, like zookeeper, load balancer, aggregators... Keep teach us these we are also forwarding with you! Again thanks for the TIPS like CDN and caching future items before the requests.
Hi Tushar, Could you please make design videos on some of the common questions like Elevator, bookmyshow, social media website like Facebook, etc. Looking for things like how do we process the request, class diagrams and the type of database, etc used. Also, I wanted to thank you for all your videos, have watched many of them and learnt a lot.
I used to come to Ashish sir's class in Seattle and you used to teach us there. There used to be another person teaching along with you, who kinda looked like an angry lad lol. I learned a lot from those weekly sessions. Please make more videos. Thanks for the great work!
Nice video! One suggestion: can we also talk about single point failure and possible solutions for that? This topic seems to help a lot on making design decisions and weighing tradeoffs.
Since you're sharding your distributed trie, you could also shard/resource intelligently, for example have a larger pool (and larger instances) for frequently accessed tries, since the access patterns definitely won't be uniform.
when you say trie nodes, are these created in the application layer or the back-end(lets say a relational database)? Can we store data in a trie data structure in the database?
it should be the backend which helps you to store and access the data in some specific structure way, using some hashing technique to access those nodes(address) where data is stored
I think for distributed storage and cache, Redis could be useful in which the trie data can be partition into multiple shard redis servers . No need for zookeeper in maintaining the trie metadata which is bit a complicated and creates some overhead
Hi Tushar dada, I liked your solution. One thing I wanted to mention is that the cache and the zookeeper are the single point of failures in the proposed design. For caches, we could cluster Redis (instead of memcached), and make them highly available by introducing redundancy. We could add more passive zookeepers as well. Let me know how you think of it. - Bishwa
A couple questions I have 1) From what I understand N1, N2, ...are replicated server nodes to improve the scalability of the system and T1, T2, T3 are replicated trie data structure to implement the auto-complete feature, but do they occupy in two separate sets of physical machines or could each of the server node has its own of trie data structure. What is the pro and con of two different set up? 2) You mention about optimizing the system by leveraging CDN, where would the CDN sit in the system diagram? Between the client machine and the load balancer or between the load balancer and the N1, N2..server nodes. If it is the latter, how is the CDN different from the server nodes themselves?
watched your tiny url and this video. thanks for sharing knowledge. the kind of application and companies used elastic search. request goes to LB, then to app server, server pull data from solr/lucene/elasticsearch/sphinx. this worked for us in terms of scale, latency, availability. data get refreshed every few hours based on the need. internally all these works based on inverted index.
I would use a debounce in the search textbox handler and make calls only after a certain timeout. This network bandwidth and a lot of server cpu cycles.
Awesome, in the next design videos please provide more details which no-sql db or cache to choose in this condition. I mean which cache/db could be beneficial to have in this scenario over any-other.
Thanks Tushar. Appreciate your video. 1. Rationale behind choosing the technologies is missing ex: Zookeeper (also list alternatives) 2. How did you arrive that the data retrieval needs caching ? Also how is cache invalidated when trie is built is missing. 3. Instead of T1,t2,t3, there could be one more load balancer ? 4. Applier complexity needs to be explained better. Its not simple to query all the words from a data store and build a trie. 5. How do you replace the trie on live nodes needs better explaination.
This is awesome!! Thanks Tushhar for these system designing videos. I was waiting for them for long time. Are you from Seattle? Your shirt says that. 😊 I was in Redmond for 1.5 yrs. now moved to Portland. Preparing for interviews in Microsoft and Amazon. Want to come back there. So, thank you again for these wonderful tutorials.
I was asked in Microsoft Design round: Design a system to allocate memory for queues. Operations like create, enqueue , dequeue should happen in O(1). Memory efficiency should over 90%. Similar question was asked in adobe. Please make a video on memory allocation. I could not find much content about memory allocation on ytube.
The proper way to handle this question is to ask more questions before you approach the problem. Are the required memory same size? e.g 512 k per query? Or there are different size queries? The basic under laying approach is not to allocate and release memory randomly. Memory allocation can be expensive. Bottom level data structure should be memory pool with fixed size chunk memory which you allocate at initialization. and chop up based on the query size. You manage the the allocate and release manually by maintain a pointer to the valid memory address. If there are 3 types of queries, you should have 3 memory pools chopping up with 3 different sizes. On the upper level logic, yes, you do round robin with a queue.
Great video using Trie structures. Thank you. In a real solution for companies using SOLR or Elastic Search, would they use the n-gram analyzer or pre-compute the best tries and use that as part of the index (instead of a custom trie structure and plumbing) ?
Thank you for taking your time to break these things down. This is helping me a lot to prepare for design interviews and helping me learn how to design scalable systems.
17:51 Why build a trie structure in the applier node? Why not just submit a list of phrases paired with top-k auto-completed phrases into the nodes containing the trie structure?
they asked me this question in one of the interviews, the emphasis was on, 1. how will you store messages? data structure? I said tree of hashmaps. 2. how will you manage scrolling up through the messages? 3. how will you decide how much will be stored in users device and then on the cloud (if you want cloud)? 4. how will you search in the past like messages from 2 years ago? all these questions are again unanswered after watching this video... can you please make a video or give a most correct answer? Thank you so much for all your videos...you have helped a lot of people.
Yep, I was browsing many videos at a time and was too lazy to change the comment. I was also sure that I am not going to get any answer so did not bother changing at all...
When you are explaining the "Request Flow", Google just had one big trie which could be fit into one machine (T1 T2 T3). And you used Zookeeper to store the mapping ("A-$"=>T1,T2,T3). Then you mentioned as the trie size grows, you need T4, T5, T6, then the mapping of Zookeeper changed to ("A-L"=>T1, T2, T3, "M-$"=>T4,T5,T6). My question is, how will the data of "M-$" on T1, T2, T3 before the expansion be migrated to T4, T5, T6? Thank you!
Hi Tushar. It's a great video you have come up with. A big thumbs up for this. I hope that the splitting of the data in zookeeper is done with help of indexing techniques like SOLR. It would be really great if you can do a video on indexing or suggest some good links for the same.
Hi Tushar, can you please do a video on "Median of 2 Sorted Arrays" from Leetcode, where they are of lengths m and n? This is the hardest problem on the leetcode portal
Did you ever figure this problem out? It took me a while, but the Geeks for Geeks piece here helped me out on my path: www.geeksforgeeks.org/median-two-sorted-arrays-different-sizes-ologminn-m/
Tries are covered, but how many real world systems are backed by tries compared to databases whether the be relational, NoSQL, or dedicated search like Solr or Elasticsearch? As an example, suppose you had a set of stories, one with the phrase, "Tushar went for a stroll" and another with "Tushar pushed the stroller." Both "tu" and "str" should match, but only if the stories start with those phrases will even "tu" match. The one narrow but practical use I see is if you want to match phrases that others have searched for, e.g. it's a nice day so everyone wants to see how you spent the day.
you have valid point. If some company was building it they would probably use solr but remember this is an interview. And yes I have seen trie used in real world usecases.
Hi Tushar bhaiya please upload all your data structure and algorithm video with test cases in hindi also.this will be useful for us for competitive examinations and interview
Hey Tushar - Thank you for all you do! In this scenario, I understand how you are building the Trie to autocompete a word based on the prefix and top k words for a given prefix. But how are we adding words to a search phrase, i.e. with "ba", you return "bath" and "ball", but once "bath" is selected, how do you return the phrases "bath time" and say "bath towel"? Thank you.
Thanks for the great video, Tushar. Could you talk a little about how phrase is implemented in this Trie module? Because in real world, ppl often search phrases like "batman movies", "batman and robin", etc instead of just one word "batman". When "batman" is searched in Trie, 'n' will be the leaf node and Trie search is terminated there. How is phrase handled by your design? Thanks.
I had the similar question instantly after listening to this. But immediately realized Trie is built based on all searches done previously. Hence all trie paths are based on complete search sentence. The works stored at each char in Tree is based on weights given to subsequent words in the sentence user is searching for. Share your thoughts if that makes sense and kind of addresses your question.
Can you explain how splitting of ranges works in little bit more depth , like how we are move range between nodes? Also how applier sitting on a diff node can move the in-memory Trie on to another node , say T1? .
Very nice explanation Tushar. I just would like to understand how we can store trie in Database in Redis? or do we maintain the entire trie in memory by with the help of typical trie operations whenever there is new entry to be added to the trie? Is there any other blog or suggestion available? Hope to hear from you.
For the data collection session, I think it would be good to use Hadoop to do some batch processing, then we can have the words with frequencies, the build the trie tree database from there.
For the aggregation, I would probably go ahead with something like HBase and run map reduce as it is a typical "word (phrase) count" problem and we can store the aggregated data into a relational DB or even in a NoSQL one like Cassandra with a TTL.
Would zookeeper be a bottleneck in this design since every query and applier has to go through and, given, its not good for high throughput applications? How about using a KV store like Redis instead of trie which provides prefix search of keys?
Great video! Could you share a little bit more about how an Applier batch job takes the phrases and weights in its range and turns them into the top K terms for each phrase? Thanks!
But how do you know the size of your trie? I fear this solution was too easy to assume we’re needing to implement sharding before considering whether the data can feasibly be incorporated in-memory.
Tushar could you please post a video on the following design question " Design facebook live streaming". I have mostly found ideas and half-baked solutions elsewhere. Your videos are pretty comprehensive about how things should be explained in an interview so I would like to know your perspective about approaching this problem.
I am just a beginner at system design, but I imagine the following points can be used for Facebook live streaming. 1) HTTPS so all livestreamed-data is secure. 2) Blob storage container such as AWS S3 to store video 3) CDN to optimize others watching the livestream. The CDN would need an algorithm to analyze the locations of the live-streamers audience. The algorithm would take into account number of audience members, their locations, the locations of CDN servers etc. to decide which CDN locations should get a copy. The algorithm could save its results in a database and use that data in the future instead of running the algorithm for each livestreamed video. When the CDN algorithm reruns itself to get new data will have to be based on another algorithm. 4) Load balancers, availability, consistency, etc. could be mentioned. If someone is watching the livestream on the other side of the globe, is it okay for their 'live' video to have a delay of several seconds? The answer to that depends on the business requirements. 5) Something needs to maintain the constant connection between the livestreamer's camera and the host server while the video is broadcasted. Web Sockets would be good for this. 6) The audience would need some way of receiving the video from the Blob storage container. I believe Web Sockets between the client and server would allow the audience to watch the video via a constant connection. But I do not know enough to say whether or not there are better solutions for this than web sockets.
Good questions 1) yes I would want to store trie in memory to be super fast. Remember we can split trie as much as we want based on the algorithm I described in the video. So if trie is bigger than memory then split it. Memory these days are 200GB easy so I m not worried too much about keeping things in memory. But you are right in worst case trie could be serialized into hard drive if needed. I would store them as simple key value pair e.g b -> {bat, bit}, ba -> {bath, bat} and so on. Basically keeping data for each prefix combination. 2) When I m keeping data in CDN I m not storing trie. Instead I m storing what users are asking for. e.g if user asked for "ba" I would store "ba" -> {bat, bath} in the CDN so that next prefix query for ba returns those autocomplete values.
Tushar, once you have the data in cdn or in memcache, you would have to refresh that one with the latest phrases that have higher weight. If we don't refresh, it would end up showing the old results. How would that work? We might need background process to refresh that. Any thoughts around that?
Superb ! thanks a ton Tushar. I had some dumb doubts on trie part. Where is the trie data structure defined and stored . Would that be in cassandra itself ?
+gaurav srivastava Cassandra will store data in the format I described. Applier will take that data and create trie locally and push them to trie nodes. Trie can stay inmemory in trie nodes as they are not source of truth.
Nice video Tushar. Really helped a lot to me. I have a small question,Is Trie structure(T1,T2,T3....) will be stored in the DB as a pieces or replicas of original. Eg: Zoo Keepr has a distributed mapping like T1 ->a to f.... So, T1 DB holds only the combinations starts from a to f?
Hi Tushar, You said we would split the trie across multiple machines. Would each of of these subparts reside in the main memory of these machines? In this case, wouldn't it require too much main memory for the scale of Google?
Hi, thanks for the video. Can you please tell why we need to use distributed cache like redis in this case since the tries will also be in-memory only?
One more thing is missing in your lecture. You should categorize how you actually store a trie in the DB. What DB is used? A proper justification for the learners should have been followed.
where will you store trie? It should be stored in memory data store i think as we want our results to be fast,and if thats case, we dont need any more in memory cache. Since we will store only 1 or two year data in trie so in memory store can accommodate it nicely
Thanks for the nice explanation. One question. wouldn't dumping the entire data into DB cause performance issues for both read and write ? Just a thought maybe acquire locks at node level that needs to be updated and update only those and the relevant parents to that node (top K items) ?
I probably need to rewatch, but where does he address the client side communication that results in updates with each new keystroke? I assume it's AJAX or Websockets, but where did he discuss that?
Thank you tushar, you were my number 1 guy to learn data structures and algorithms, now after graduating and working i am getting back to you to learn about system design
Again thanks a lot
the legend is back 😍😍
i forgot what love felt like
And he disappeared again
I’m loving these new videos. You’re obviously an amazing human being. I’m a little saddened that you’re into the nfl but I think I’ll survive. Thanks Tushar!
you are not nfl fan?
You replied! I'm NBA/WNBA all the way. I have a hard time with how dangerous football is. But in Seattle you don't have NBA so I can't blame you too much! Thanks again Tushar!
@@tusharroy2525 In my mind you went to the weekend game and started making 'system design' video right after you are home. Respect for engineers like you!
You rock as usual, I can see your improvements from solving a problem from single machine to a distributed machines techniques, like zookeeper, load balancer, aggregators... Keep teach us these we are also forwarding with you! Again thanks for the TIPS like CDN and caching future items before the requests.
hey tushar! i'm new to system design and have an interview tomorrow. This video saved me man. Very clear and precise. Keep up the good work!!!
good luck with the interview.
your videos are much awaited! Please keep them coming
Thanks
I watched several autocomplete tutorials and this was the most conceptually complete in terms of coverage e.g using time as weight.
Hi Tushar, Could you please make design videos on some of the common questions like Elevator, bookmyshow, social media website like Facebook, etc. Looking for things like how do we process the request, class diagrams and the type of database, etc used. Also, I wanted to thank you for all your videos, have watched many of them and learnt a lot.
+Arunabh Hejib I will try.
This is my first time that I am watching you and you explanined whole design in very easy and convenient way. Count me in as your fan :)
very good video about Design Autocomplete or Typeahead Suggestions for Google search I love it. The teaching quality is awesome!
Thanks
This is great video which covers both pre-processing data flow as well search, great job Tushar bhai!
I used to come to Ashish sir's class in Seattle and you used to teach us there. There used to be another person teaching along with you, who kinda looked like an angry lad lol. I learned a lot from those weekly sessions. Please make more videos. Thanks for the great work!
Thanks for all the great work you do Tushar, it's always a pleasure to see your amazing yet humble videos.
Nice video!
One suggestion: can we also talk about single point failure and possible solutions for that? This topic seems to help a lot on making design decisions and weighing tradeoffs.
Since you're sharding your distributed trie, you could also shard/resource intelligently, for example have a larger pool (and larger instances) for frequently accessed tries, since the access patterns definitely won't be uniform.
can't believe this doesn't have more upvotes! It's what we do too at work
You really are giving a precious knowledge to all of us, i am greatly grateful to you on all your help and time.
Excellent video. Thanks Tushar for sharing
when you say trie nodes, are these created in the application layer or the back-end(lets say a relational database)? Can we store data in a trie data structure in the database?
u got an answer for the above?
it should be the backend which helps you to store and access the data in some specific structure way, using some hashing technique to access those nodes(address) where data is stored
you can store a trie in MongoDB with its support for Tree based structures
I think for distributed storage and cache, Redis could be useful in which the trie data can be partition into multiple shard redis servers . No need for zookeeper in maintaining the trie metadata which is bit a complicated and creates some overhead
Why do you not make any more videos? These videos are literally gems! I wish you had made more videos on the system design!
Hi Tushar, I want to say thank you for all your beautiful work. Keep them coming.
As always, you dig into the details with your explanation. Very helpful
Hi Tushar dada,
I liked your solution.
One thing I wanted to mention is that the cache and the zookeeper are the single point of failures in the proposed design. For caches, we could cluster Redis (instead of memcached), and make them highly available by introducing redundancy.
We could add more passive zookeepers as well.
Let me know how you think of it.
- Bishwa
Nice video. Giving some tips to make the design better is even better. Thank you Tushar!
Its really great to see you back with the design questions.
A couple questions I have
1) From what I understand N1, N2, ...are replicated server nodes to improve the scalability of the system and T1, T2, T3 are replicated trie data structure to implement the auto-complete feature, but do they occupy in two separate sets of physical machines or could each of the server node has its own of trie data structure. What is the pro and con of two different set up?
2) You mention about optimizing the system by leveraging CDN, where would the CDN sit in the system diagram? Between the client machine and the load balancer or between the load balancer and the N1, N2..server nodes. If it is the latter, how is the CDN different from the server nodes themselves?
thanks, tushar sir. you are doing great work. please give us more knowledge.
More more more ... more videos on system design plzzzzzz !!
watched your tiny url and this video. thanks for sharing knowledge. the kind of application and companies used elastic search. request goes to LB, then to app server, server pull data from solr/lucene/elasticsearch/sphinx. this worked for us in terms of scale, latency, availability. data get refreshed every few hours based on the need. internally all these works based on inverted index.
Fair enough.
Hi Tushar,
Very neat explanation.
Thanks.
dont let this great content distracted you from the fact that settle should have ran the ball
I would use a debounce in the search textbox handler and make calls only after a certain timeout. This network bandwidth and a lot of server cpu cycles.
Awesome, in the next design videos please provide more details which no-sql db or cache to choose in this condition.
I mean which cache/db could be beneficial to have in this scenario over any-other.
+Shivam Rohilla feedback taken.
Thanks Tushar. Appreciate your video.
1. Rationale behind choosing the technologies is missing ex: Zookeeper (also list alternatives)
2. How did you arrive that the data retrieval needs caching ? Also how is cache invalidated when trie is built is missing.
3. Instead of T1,t2,t3, there could be one more load balancer ?
4. Applier complexity needs to be explained better. Its not simple to query all the words from a data store and build a trie.
5. How do you replace the trie on live nodes needs better explaination.
Nice, simple explanation. Thank you very much.
Truly amazing content. Watching your videos is significantly adding to my knowledge.
Crisp and on point videos. Thanks for delivering high quality content :)
This is awesome!! Thanks Tushhar for these system designing videos. I was waiting for them for long time. Are you from Seattle? Your shirt says that. 😊 I was in Redmond for 1.5 yrs. now moved to Portland. Preparing for interviews in Microsoft and Amazon. Want to come back there. So, thank you again for these wonderful tutorials.
love this my dude
thanks for your videos
Very helpful videos and I love it and I appreciate it on the TH-cam!
I was asked in Microsoft Design round: Design a system to allocate memory for queues. Operations like create, enqueue , dequeue should happen in O(1). Memory efficiency should over 90%. Similar question was asked in adobe. Please make a video on memory allocation. I could not find much content about memory allocation on ytube.
hello Rahul,
can you please tell me what other questions did they ask to you?
What DS question and how did you approach for this questiona too?
Linked List Implementation should do for that
keeping two pointers head and tail....enqueue at head and dequeue at tail
The proper way to handle this question is to ask more questions before you approach the problem. Are the required memory same size? e.g 512 k per query?
Or there are different size queries?
The basic under laying approach is not to allocate and release memory randomly.
Memory allocation can be expensive. Bottom level data structure should be memory pool with fixed size chunk memory which you allocate at initialization. and chop up based on the query size. You manage the the allocate and release manually by maintain a pointer to the valid memory address.
If there are 3 types of queries, you should have 3 memory pools chopping up with 3 different sizes.
On the upper level logic, yes, you do round robin with a queue.
You are back!!! YAY!!! Thank you!!!
Great video using Trie structures. Thank you.
In a real solution for companies using SOLR or Elastic Search, would they use the n-gram analyzer or pre-compute the best tries and use that as part of the index (instead of a custom trie structure and plumbing) ?
You are right. Probably they are using SOLR or something like SOLR.
Can you elaborate on why did you keep N1 , N2 different than T1, T2 etc? Are you considering Trie as a datastorage?
Same question. If it's a data storage - what kind of data storage ?
Those are application servers.
Same question. I feel N1, N2, N3 are servers; while T1, T2, T3 are database storing the Trie?
@@gabrielxu2087 i think im late answering the question, Yes. they are the databases which will have serialized Trie Structure
Great! Out of the box! Thanks Tushar 🤗
Tushar rocks!!!
The implementation with RNN will be smarter.
Thank you for taking your time to break these things down. This is helping me a lot to prepare for design interviews and helping me learn how to design scalable systems.
17:51 Why build a trie structure in the applier node? Why not just submit a list of phrases paired with top-k auto-completed phrases into the nodes containing the trie structure?
I guess you could do in this way, but it seems would take of resource from the Tries nodes that are serving user requests.
Thanks for the video! Question I have is what are you using for persistent storage?
they asked me this question in one of the interviews,
the emphasis was on,
1. how will you store messages? data structure? I said tree of hashmaps.
2. how will you manage scrolling up through the messages?
3. how will you decide how much will be stored in users device and then on the cloud (if you want cloud)?
4. how will you search in the past like messages from 2 years ago?
all these questions are again unanswered after watching this video...
can you please make a video or give a most correct answer?
Thank you so much for all your videos...you have helped a lot of people.
Shouldn't this be a comment on this video: th-cam.com/video/zKPNUMkwOJE/w-d-xo.html ?
Yep, I was browsing many videos at a time and was too lazy to change the comment. I was also sure that I am not going to get any answer so did not bother changing at all...
When you are explaining the "Request Flow", Google just had one big trie which could be fit into one machine (T1 T2 T3). And you used Zookeeper to store the mapping ("A-$"=>T1,T2,T3). Then you mentioned as the trie size grows, you need T4, T5, T6, then the mapping of Zookeeper changed to ("A-L"=>T1, T2, T3, "M-$"=>T4,T5,T6). My question is, how will the data of "M-$" on T1, T2, T3 before the expansion be migrated to T4, T5, T6? Thank you!
I guess that should be done by applier as part of data collection flow.
Hi Tushar. It's a great video you have come up with. A big thumbs up for this. I hope that the splitting of the data in zookeeper is done with help of indexing techniques like SOLR. It would be really great if you can do a video on indexing or suggest some good links for the same.
Hi Tushar, can you please do a video on "Median of 2 Sorted Arrays" from Leetcode, where they are of lengths m and n? This is the hardest problem on the leetcode portal
Soon.
Did you ever figure this problem out? It took me a while, but the Geeks for Geeks piece here helped me out on my path: www.geeksforgeeks.org/median-two-sorted-arrays-different-sizes-ologminn-m/
th-cam.com/video/LPFhl65R7ww/w-d-xo.html
Hello Mr. Tushar. This is a satisfying video. Thanks.
This is a really good solution
I'm working at a autocomplete feature. But I'm here mainly for the jersey. GO HAWKS!
Tries are covered, but how many real world systems are backed by tries compared to databases whether the be relational, NoSQL, or dedicated search like Solr or Elasticsearch? As an example, suppose you had a set of stories, one with the phrase, "Tushar went for a stroll" and another with "Tushar pushed the stroller." Both "tu" and "str" should match, but only if the stories start with those phrases will even "tu" match. The one narrow but practical use I see is if you want to match phrases that others have searched for, e.g. it's a nice day so everyone wants to see how you spent the day.
you have valid point. If some company was building it they would probably use solr but remember this is an interview. And yes I have seen trie used in real world usecases.
Cassandra stores timestamp for all the columns/rows (during insert/update) so basically we don't need to store the date time explicitly
Hi Tushar bhaiya please upload all your data structure and algorithm video with test cases in hindi also.this will be useful for us for competitive examinations and interview
Hey Tushar - Thank you for all you do!
In this scenario, I understand how you are building the Trie to autocompete a word based on the prefix and top k words for a given prefix. But how are we adding words to a search phrase, i.e. with "ba", you return "bath" and "ball", but once "bath" is selected, how do you return the phrases "bath time" and say "bath towel"?
Thank you.
Hey, I think its out of scope of this problem however if you want to do this then you have to consider "bath towel" as a single word.
Add space as a character and then the same solution will work
Thanks, very informative. I just understood simple request flow and server distributed caching. 😊
Thanks for the great video, Tushar. Could you talk a little about how phrase is implemented in this Trie module?
Because in real world, ppl often search phrases like "batman movies", "batman and robin", etc instead of just one word "batman". When "batman" is searched in Trie, 'n' will be the leaf node and Trie search is terminated there. How is phrase handled by your design? Thanks.
I had the similar question instantly after listening to this. But immediately realized Trie is built based on all searches done previously. Hence all trie paths are based on complete search sentence. The works stored at each char in Tree is based on weights given to subsequent words in the sentence user is searching for. Share your thoughts if that makes sense and kind of addresses your question.
For the zookeeper, we can still use load balancer here, why we choose zookeeper, it has some benefits ?
Can you explain how splitting of ranges works in little bit more depth , like how we are move range between nodes? Also how applier sitting on a diff node can move the in-memory Trie on to another node , say T1? .
Very nice explanation Tushar. I just would like to understand how we can store trie in Database in Redis? or do we maintain the entire trie in memory by with the help of typical trie operations whenever there is new entry to be added to the trie? Is there any other blog or suggestion available? Hope to hear from you.
Great video Tushar..Can you put some video which is covering authentication concepts too..
100% better than
Grokking the System Design Interview
For the data collection session, I think it would be good to use Hadoop to do some batch processing, then we can have the words with frequencies, the build the trie tree database from there.
For the aggregation, I would probably go ahead with something like HBase and run map reduce as it is a typical "word (phrase) count" problem and we can store the aggregated data into a relational DB or even in a NoSQL one like Cassandra with a TTL.
i knew my man Tushar was a seahawks fan
I m big fan.
Thanks this is a great video and very nice ideas
Would zookeeper be a bottleneck in this design since every query and applier has to go through and, given, its not good for high throughput applications? How about using a KV store like Redis instead of trie which provides prefix search of keys?
etcd can be the same and it's distributed
Redis can be used in case you need real time autocomplete - it has got support for sorted sets.
Great insights and explanation
Hi, Tushar, your videos are awesome. Would you make more on system design? Thanks
I have to say your content is thorough and deep. I just don't like the way you spell words with 'T' :D but i can bear with that.
Great video! Could you share a little bit more about how an Applier batch job takes the phrases and weights in its range and turns them into the top K terms for each phrase? Thanks!
Good job 👍🏼, It would be great if you made videos about ML
But how do you know the size of your trie? I fear this solution was too easy to assume we’re needing to implement sharding before considering whether the data can feasibly be incorporated in-memory.
How the trie is implemented in the discussed architechture. Is it in memory?? or some Database. which database supports trie?
Thanks, great explanation
Thanks Tushar. You are videos helps a lot :)
Tushar could you please post a video on the following design question " Design facebook live streaming". I have mostly found ideas and half-baked solutions elsewhere. Your videos are pretty comprehensive about how things should be explained in an interview so I would like to know your perspective about approaching this problem.
I am just a beginner at system design, but I imagine the following points can be used for Facebook live streaming. 1) HTTPS so all livestreamed-data is secure. 2) Blob storage container such as AWS S3 to store video 3) CDN to optimize others watching the livestream. The CDN would need an algorithm to analyze the locations of the live-streamers audience. The algorithm would take into account number of audience members, their locations, the locations of CDN servers etc. to decide which CDN locations should get a copy. The algorithm could save its results in a database and use that data in the future instead of running the algorithm for each livestreamed video. When the CDN algorithm reruns itself to get new data will have to be based on another algorithm. 4) Load balancers, availability, consistency, etc. could be mentioned. If someone is watching the livestream on the other side of the globe, is it okay for their 'live' video to have a delay of several seconds? The answer to that depends on the business requirements. 5) Something needs to maintain the constant connection between the livestreamer's camera and the host server while the video is broadcasted. Web Sockets would be good for this. 6) The audience would need some way of receiving the video from the Blob storage container. I believe Web Sockets between the client and server would allow the audience to watch the video via a constant connection. But I do not know enough to say whether or not there are better solutions for this than web sockets.
Nice video!! But how these Trie nodes are stored...whether they are stored in relational db or nosql db ?
Since my source of truth is in Cassandra I can keep trie inmemory as I have 3 replicas.
Storing that big data inmemory will not add more cost? And also are you talking about these inmemory databases be stored in CDN's ?
Good questions
1) yes I would want to store trie in memory to be super fast. Remember we can split trie as much as we want based on the algorithm I described in the video. So if trie is bigger than memory then split it. Memory these days are 200GB easy so I m not worried too much about keeping things in memory. But you are right in worst case trie could be serialized into hard drive if needed. I would store them as simple key value pair
e.g b -> {bat, bit}, ba -> {bath, bat} and so on. Basically keeping data for each prefix combination.
2) When I m keeping data in CDN I m not storing trie. Instead I m storing what users are asking for.
e.g if user asked for "ba" I would store "ba" -> {bat, bath} in the CDN so that next prefix query for ba returns those autocomplete values.
Thanks for the replies :)
Tushar, once you have the data in cdn or in memcache, you would have to refresh that one with the latest phrases that have higher weight. If we don't refresh, it would end up showing the old results. How would that work? We might need background process to refresh that. Any thoughts around that?
Superb ! thanks a ton Tushar. I had some dumb doubts on trie part. Where is the trie data structure defined and stored . Would that be in cassandra itself ?
+gaurav srivastava Cassandra will store data in the format I described. Applier will take that data and create trie locally and push them to trie nodes. Trie can stay inmemory in trie nodes as they are not source of truth.
Amazing Video!
This was super useful thanks
Nice video Tushar. Really helped a lot to me.
I have a small question,Is Trie structure(T1,T2,T3....) will be stored in the DB as a pieces or replicas of original. Eg: Zoo Keepr has a distributed mapping like T1 ->a to f.... So, T1 DB holds only the combinations starts from a to f?
Tushar, may we have videos on Saga transaction pattern, session storage/caching as well as api key storage/caching? Anyways great work as usual.
Hi Tushar, You said we would split the trie across multiple machines. Would each of of these subparts reside in the main memory of these machines? In this case, wouldn't it require too much main memory for the scale of Google?
Hi, thanks for the video. Can you please tell why we need to use distributed cache like redis in this case since the tries will also be in-memory only?
Brilliant as always. thanks
keep uploading videos they are great
definitely.
One more thing is missing in your lecture.
You should categorize how you actually store a trie in the DB. What DB is used? A proper justification for the learners should have been followed.
Bishwajit Purkaystha I think trie should be stored in memory. We have an Applier who can restore a trie in memory when all replicas died
where will you store trie? It should be stored in memory data store i think as we want our results to be fast,and if thats case, we dont need any more in memory cache. Since we will store only 1 or two year data in trie so in memory store can accommodate it nicely
Great Video
Thanks for the nice explanation. One question. wouldn't dumping the entire data into DB cause performance issues for both read and write ? Just a thought maybe acquire locks at node level that needs to be updated and update only those and the relevant parents to that node (top K items) ?
I probably need to rewatch, but where does he address the client side communication that results in updates with each new keystroke? I assume it's AJAX or Websockets, but where did he discuss that?
Thanks Tushar for nice video. Had you thought about OOPS design questions like Design an elevator, chess game ?. Any suggestions for that
+Piyush Tiwari Honestly not my kind of questions.
Thank you so much for such a clear explanation!
Amazing explaination.