I was having a feeling that I would have to crawl the youtube videos for a quality video on Google System design! But BRAVO! I find this video as the first video with the highest views. Great job!
Greetings, I just came to TH-cam to watch video about SQL optimization and your channel was offered. And I started to watch this video. It is amazing, the way you explain is brilliant and outstanding. Very clear, full of information, not boring because too obvious, not difficult because too sophisticated and convoluted - a golden middle. Thank you!
Awesome content! I liked to see some data structure (such as queue and heap) used in practice, because the simple examples are good in the beginning, but it is not that good with the time. Continue with this, really a hidden gem this channel
woow loved it by 1:48 I was in love because you ruled out everything every small detail required + planning this makes understanding alot easier rather than directly jumping into code and saying on the go
I really appreciate this video! Information was clear and concise. Levels of depth are perfect for the viewer to be able to continue educating themselves about any of the topics mentioned here. Thank you so much
keep it going! High quality content and a very solid platform! Without a doubt, I will buy the subscription soon and start learning! a hug from a new Spanish subscriber
Your course looks great. I love that you have a teaching assistant and the explaining styles are awesome. Will try it out! Only thing is I really wish you supported Rust 🦀🙏🏾
Very good video! Thanks for sharing! One tiny thing, I would prefer NFS over Blob Store like S3 to keep the downloaded pages. A webpage will keep references to lots of resources, like json/css/javascript files. The bold/highlighted words are more important than plain text. That's very important information for ranking. If we don't keep the css files, those information will be lost. So we need to keep them together with the HTML file. It will be very complex to keep those information for multiple files in a single webpage in metadata if we use S3. So I suggest just download the web page with everything to a folder in NFS, and ask indexer to help themselves.
@@interviewpen only slaves need to do this It's not worth it 🤷♂️ If you know how to build a search engine you're already the top 1% of the human population just make your own company and forget about a job lol
Dang, I never thought I could understand this whole process. I typically wrote off most of the implementation details as a black box, but this seems halfway approachable. Has me thinking a lot about single page applications, and how the crawlers handle them. A similar type of video would be awesome if you had it.
Glad you liked it! Yes, SPAs are notoriously hard to optimize for crawlers. However, strategies like static rendering and routing can make SPAs look more like typical websites to a crawler. I'm not an SEO expert though :)
How does sorting by frequency give us the most popular results? The frequency is the number of times the word occurs in that specific url. The word may appearing in that url too many times like being a common word doesn't make it the most popular search result
You're completely right! Google uses the PageRank algorithm in addition to a more advanced index to handle that--we glossed over this for our "basic" search engine since it's more of an algorithms problem than a system design one. Regardless, there's some cool infrastructure that goes into calculating PageRank at scale so that's certainly something to look into if you're curious. Thanks for watching!
You can lookup tf-idf (term frequency-inverse document frequency) to learn more about how common "filler" words are filtered out in a basic search engine.
Thank you for sharing, Good content and good work. Suggest start with core functional and non functional requirements and then capacity planning numbers and read write per sec needing to support the core functional needs. Otherwise seems we go straight into solution which is ok, some may want to know how we think ahead of an ambiguity and the problem space and have conversation around what we want to do with the interviewer. Maybe also consider adding handling copyright issues when we are extracting and rendering html, de dupe service and bloom filter, how nested cyclic loops in a site will be handed, caching strategy etc.
Thanks for watching. You're right, addressing the requirements ahead of time is very important in this process, and our more recent videos tend to be better about that :)
Thank you for sharing the great design prep video. What tools or combination of tools/software is used to create the figures (with the black blackground). Thanks
This is great content. Regarding shingles, that takes a LOT to implement - lots of space and lots of CPU to compare them. The idea of the personalized recommendations is a huge success Google has and is surely difficult to implement considering the entire search, rank (personalize) and retrieve has to be done in a second.
Could someone pls explain what text and hash indexes are? Are they separate DBs storing partial information compare to the main DB or something else? Thanks!
You're exactly right. You can think of global indexes as a copy of the database but organized onto nodes differently, and the records generally only include enough data to be able to look up the corresponding record in the primary.
Really appreciate it. I have several questions for politeness part. If there are 10k hosts, are we supposed to have 10k queues for politeness? Let's say if one host has only 3 urls, after all the 3 urls are visited. are we supposed to delete the idle queue? Each time we have a new host, are we supposed to created a new queue.
Yep, we'd need one queue for each host. There'd probably be far more than 10k in fact! Of course, these would simply be logical partitions residing on a far smaller set of physical machines. We would need to add a queue when a host is visited for the first time (this would be trivial since a queue is just a logical abstraction), but we probably wouldn't need to worry about deleting since we'll keep re-crawling hosts. Hope that helps!
Could you explain to me a thing I'm confused about here 13:35. When the router selects an element from the priority queue - it adds it to the politeness queue, by doing that wouldn't we loose the initial prioritization given that the politeness queues are sorted just by domain?
Sure. The router uses a weighted random algorithm to select a priority queue, so the higher priority queues are more likely to be selected. This ensures that higher priority pages are crawled more frequently, regardless of what politeness queue they end up in. Thanks!
One application of this solution is for horizon risk scanning. The use case is that a large multinational corporation wants to have an idea of new risks which are emerging and adopting this approach allows them to have a traceability back to the web source. Of course they won’t be crawling 100M pages but maybe 100k pages.
Don't think the schema design for the query pattern "Search for a word " is included. The video says there is a text index but I don't see "word" or "frequency" at th-cam.com/video/0LTXCcVRQi0/w-d-xo.html I think the schema needs to include these so that index automatically creates a table on top of these. Also the part about Router routing URLs to correct queue, It's mentioned that if there is no Queue corresponding to domain then it will added to "empty" queue. But then what about updating the Heap and selector. Also the mapping of a domain to queue has to be stored somewhere. Most likely in Redis cache as it seems like changing a lot in case queue becomes empty.
1. The "site content" field in the schema should hold the full text of the site, so words and their associated frequencies can be calculated when records are added/updated, and this data is what propagates to the text index. 2. Yep, when a new host is added to the second set of queues, the router is responsible for adding that host to the heap so the selector knows about it. 3. The host-to-queue mapping would be stored in the router, that way the router is able to quickly check which queue the next URL should be added to. It's worth noting that the router is low-traffic enough (
@@interviewpen for the point 1, you mentioned that the word and frequency is calculated when a record is added or updated. But then also it needs the corresponding attributes so that it can be added to Databased when record is added or updated. As per timestamp 3:32 the schema doesn't contain word or frequency. Am I missing something? It might be something dumb apologies.
great video, but can I ask? can we use elasticsearch instead? I'm not a professor but seeing a lot of system using elastic search to optimize their query performace.
Glad you liked it! ElasticSearch actually uses a very similar data structure to the "text index" we described, and this could certainly be swapped out for our database in this system. It's just about tradeoffs between ease of use in a managed service and flexibility.
Love the video but I'm perplexed as to why you want to store the site contents. I figure that you would just scrape it for word frequencies for matching later to queries?
Good question--we store the site contents so we don't have to scrape them again later if we want to change our algorithms. Google does this too! Thanks for watching.
Sure--hashing a large piece of data (such as a webpage) yields a far shorter, fixed-length string that uniquely represents that data and can be stored in a database. By checking if this hash already exists in our database, we can effectively check if the webpage has already been seen without having to compare the page content against petabytes of other pages.
Great video, but im curious is it really neccassar to sort by frequency of a word in URL? i think most well designed URL wont have key word like cat appear more than one time in Url? Also if there's cat and dog in a URL should I have two record for a URL?
Good point, but 31TB of metadata is a lot to store on one node so it's necessary in this case to scale horizontally. Our query patterns work very nicely here (always single-record reads/writes by a unique key), so it shouldn't be a problem. Thanks for watching!
Very nice walkthrough appreciate the effort. I have a question tho, maybe a stupid one. I didnt quite get if "heap" means the data structure heap or the heap as a general memory space just like it is called in Java. I mean if its the data structure, wouldnt it be very inefficient to search for the correct pointer for the politeness queue you are looking for? From your explanation I am inferring that this heap is more like a memory space and works more like a hash map. Is this correct?
We did mean the heap data structure--this works very efficiently here since the earliest timestamp will always be at the top of the heap. The heap just tells us which politeness queue to look at next; no searching necessary. Thanks!
I'm not sure if I understood correctly but why are we not using any ES cluster to speed up our search? No DB can be as efficient as ES when it comes to search.
ElasticSearch is essentially a sharded db with full text search at its core, so a properly architected database will do the same thing. But you’re absolutely right-es is certainly a viable solution if we want a pre-built solution.
Thanks for watching! It's a bit math heavy but here's a reference for shingling: nlp.stanford.edu/IR-book/html/htmledition/near-duplicates-and-shingling-1.html
*ChatGPT giving me a "rudimentary" outline of some python code for this explanation based on the youtube transcript. What do you think:* *python* class API: def __init__(self): self.load_balancer = LoadBalancer() self.text_index = TextIndex() self.metadata_db = MetadataDatabase() self.blob_store = BlobStore() def search(self, query): urls = self.text_index.search(query) results = [] for url in urls: metadata = self.metadata_db.get_metadata(url) page_content = self.blob_store.get_page_content(url) results.append((metadata, page_content)) return results class LoadBalancer: def __init__(self): self.api_servers = [] def distribute(self, query): api_server = self.select_api_server() return api_server.search(query) def select_api_server(self): # Logic to select API server based on load balancing pass class TextIndex: def search(self, query): # Implement search logic to return URLs based on query pass class MetadataDatabase: def get_metadata(self, url): # Retrieve metadata for the given URL pass class BlobStore: def get_page_content(self, url): # Retrieve page content for the given URL pass class Crawler: def __init__(self, url_frontier): self.url_frontier = url_frontier self.hash_index = HashIndex() self.metadata_db = MetadataDatabase() self.blob_store = BlobStore() def crawl(self): while True: url = self.url_frontier.get_next_url() if self.check_robots_txt(url): page = self.fetch_page(url) if not self.is_duplicate(page): self.save_page(page) new_urls = self.extract_urls(page) self.url_frontier.add_urls(new_urls) def check_robots_txt(self, url): # Check robots.txt for the given URL pass def fetch_page(self, url): # Download the page content for the given URL pass def is_duplicate(self, page): # Check if the page is a duplicate using HashIndex pass def save_page(self, page): # Save the page content and metadata pass def extract_urls(self, page): # Extract new URLs from the page content pass class HashIndex: def check_duplicate(self, page): # Check if the page content is a duplicate pass class URLFrontier: def __init__(self): self.priority_queues = [] self.host_queues = [] self.heap = [] def get_next_url(self): # Get the next URL based on priority and politeness pass def add_urls(self, urls): # Add new URLs to the appropriate queues pass # Initialize components url_frontier = URLFrontier() api = API() crawler = Crawler(url_frontier) # Start crawling and serving API requests crawler.crawl()
Can someone explain how does the priorityQueue really work for choosing the next element in the queue? Is it like a min priority queue where the top element will be having the minimum time to remove and we compare current time and minimum time and finally process the element and then if multiply rendering time by 10 and put it back to the queue and the priority queue. In that case if a 2 elements have the same time in priority queue how do we choose which one to pick?
Thanks, great video but I have 1 comment. You are saying that you are going to cache the robots.txt file. How does Google system then know that the robots.txt was updated? From what you mentioned, you always take it from cache as long as it is there but you didn't mention cache invalidation.
Thanks for watching! Really good point-in this system it’s not critical for the robots.txt to be constantly up to date, but there definitely should be some TTL set in the cache to make sure the data is re-fetched periodically.
Seems like a huge amount of complexity to avoid crawlers hitting the same URL. I would take the approach that they will rarely select the same URL anyway, so just have at it and wear that occasional doubling up for the massive speed increase it gives you on the 99% case - especially given the huge number of URLs something like google must be crawling.
When the crawler discovers a new site, it's pretty likely that several pages on that site would line up close together in the URL frontier. At the scale of thousands of crawlers, we'd basically be DDOSing every new site! But you're absolutely right that it's an important tradeoff to consider. Thanks!
Good question; the heap data structure enables us to efficiently look up the host with the smallest timestamp, i.e. the host that we crawled the longest ago. With a significant number of host queues, this operation could add notable latency without using a heap. Thanks!
@@interviewpen oh I see. I haven’t encountered any heaps and was surprised to see it can be used as a HashMap of some kind. Why are you thanking me lol I should be thanking you for the video
It depends on the requirements of the system, but in this case we'll keep the BLOB around. This is helpful since there's so much overhead involved in scraping sites--for example if we decided to change our indexing algorithm, we could do so from the saved BLOBs without having to re-crawl every page. Google does this too--in fact you can view Google's copy of a page by clicking the "cached" link on a search result. Thanks for watching!
Thanks for watching! Visit interviewpen.com/? for more great Data Structures & Algorithms + System Design content 🧎
Wnat to give interview of ai😢
needless to say.... your channel will grow superbly. this video was RECOMMENDED by youtube
Thanks for the kind words! Yeah we will be posting a lot more & hope to create more quality stuff.
Yes.
Channel currently hugely underrated, material is just delicious, especially for those who seek examples of complex system schemes.
Love it.
Thanks! We have more coming - production starts this week!
@@interviewpen Great to hear!
I was having a feeling that I would have to crawl the youtube videos for a quality video on Google System design! But BRAVO! I find this video as the first video with the highest views. Great job!
I hope this channel grows exponentially.
This is amazing content!
Thank you, and well done! :)
Dude, your content quality is superior, Keep going.
Yesterday you had 145 subscribers and now you have 245 i am so happy for you.
Thanks! haha - we'll be posting a lot more so stay tuned!
Nigga he's got 12.5k now lmaooo
18k now
24k now!
24.8k -> 25-05-2023
Honestly one of the best videos on the internet for system design!
Thank you!
This channel is gonna explode. The content is just too good. Thank you.
Thanks for watching - we'll be posting a lot more!
Greetings, I just came to TH-cam to watch video about SQL optimization and your channel was offered. And I started to watch this video. It is amazing, the way you explain is brilliant and outstanding. Very clear, full of information, not boring because too obvious, not difficult because too sophisticated and convoluted - a golden middle.
Thank you!
thanks for the kind words! and thanks for watching - more coming
Really appreciate the back-of-the-envelope calculations in between!
Great work!
Thanks, glad you enjoyed it!
Awesome content! I liked to see some data structure (such as queue and heap) used in practice, because the simple examples are good in the beginning, but it is not that good with the time. Continue with this, really a hidden gem this channel
thanks for watching - more coming
I really enjoyed the video! Thank you guys for taking your time and posting it, it was very entertaining and educational. Best regards
Thanks! Stay tuned for more content
Clean, clear, efficient. ❤
I’d love to see more videos like this from you!
Will do, thanks for watching!
One of the best walkthroughs I've ever seen, regardless of the topic or technical depth. Superb work man.
thanks for commenting & the nice words - more videos coming soon!
woow loved it
by 1:48 I was in love because you ruled out everything every small detail required + planning this makes understanding alot easier rather than directly jumping into code and saying on the go
Thanks for watching
Only a 1/3 of the way through and already one of the best I've seen. Focused, logical leaps from topic to topic, minimal digressions. Keep it up
Thanks! and thanks for watching
Wooooah!!!! This is what I needed in my life 😢. I’m now complete
awesome haha - thanks for watching
I really appreciate this video! Information was clear and concise. Levels of depth are perfect for the viewer to be able to continue educating themselves about any of the topics mentioned here. Thank you so much
Sure - thanks for watching!
keep it going!
High quality content and a very solid platform! Without a doubt, I will buy the subscription soon and start learning!
a hug from a new Spanish subscriber
cool! Thanks for watching. Let us know in Discord if u need any help.
amazing video, thanks👏👏i like how you guys dig deep into complex aspects of every system that some other content just gloss over
Thanks!
Really clear, concise and efficient explanation and narrative. 👍
Thanks!
Your course looks great. I love that you have a teaching assistant and the explaining styles are awesome. Will try it out! Only thing is I really wish you supported Rust 🦀🙏🏾
Thanks! We can add language support in under an hour. (from the engineering angle) We can push changes in a day. Just let us know in Discord.
yeae ive just started learning rust. It's such a cool language
This is amazing! I honestly cant wait to look into your other videos!
More videos coming! Thanks for watching.
@@interviewpen eagerly waiting!
Wow, this is information all for free. Thank you for making this video
thanks for watching - more coming
Loved the video! A video I'd love to see in the future is system design for video streaming applications e.g. TH-cam, Netflix.
Will do - thanks for watching
Very good video! Thanks for sharing! One tiny thing, I would prefer NFS over Blob Store like S3 to keep the downloaded pages. A webpage will keep references to lots of resources, like json/css/javascript files. The bold/highlighted words are more important than plain text. That's very important information for ranking. If we don't keep the css files, those information will be lost. So we need to keep them together with the HTML file. It will be very complex to keep those information for multiple files in a single webpage in metadata if we use S3. So I suggest just download the web page with everything to a folder in NFS, and ask indexer to help themselves.
I extremely like the video, man. Very helpful and informative. Thank you very much. It is presented so well too. Great, positive work.
Thanks, glad it helped you!
Exceptional way of explaining things , I'm subscribed to you guys now
great!!
lmao if this was the interview question I'd just not do it.. but I'm not there yet
we'll get u there 🧎🧎 be brave
@@interviewpen only slaves need to do this
It's not worth it 🤷♂️ If you know how to build a search engine you're already the top 1% of the human population just make your own company and forget about a job lol
I was looking for something like this for a while. This content is worth the time spent.
thanks for watching
Second Video I watch from you. It’s so good. thank you
Glad you liked it!
I am impressed, you really deserved my sub❤
Thanks!
Dang, I never thought I could understand this whole process. I typically wrote off most of the implementation details as a black box, but this seems halfway approachable.
Has me thinking a lot about single page applications, and how the crawlers handle them. A similar type of video would be awesome if you had it.
Glad you liked it! Yes, SPAs are notoriously hard to optimize for crawlers. However, strategies like static rendering and routing can make SPAs look more like typical websites to a crawler. I'm not an SEO expert though :)
@@interviewpen haha I appreciate the legal disclaimer
Never saw such a difficult problem explained so easily❤️ subscribed instantly
Love from India❤
Thanks for watching!
Holy shit I'm glad I found this before you've blown up 🙌
Thanks for watching! More coming!
This channel is amazing
thanks - we have a lot more coming!
How does sorting by frequency give us the most popular results? The frequency is the number of times the word occurs in that specific url. The word may appearing in that url too many times like being a common word doesn't make it the most popular search result
You're completely right! Google uses the PageRank algorithm in addition to a more advanced index to handle that--we glossed over this for our "basic" search engine since it's more of an algorithms problem than a system design one. Regardless, there's some cool infrastructure that goes into calculating PageRank at scale so that's certainly something to look into if you're curious. Thanks for watching!
ironically sorting by frequency was the original implementation of the page rank algorithm, long before it became more advanced
You can lookup tf-idf (term frequency-inverse document frequency) to learn more about how common "filler" words are filtered out in a basic search engine.
really wow!!!!!!! amazing content.
thanks, more coming soon!
This was amazing. Now I want to try build a search engine!
lets gooooo - thanks for watching
Great video man, wish I had found this before
Thanks!
This is high quality content.
Thanks, glad you enjoyed it!
Great work buddy....very detailed explanation... cheers
thanks for watching!
Great video..
Keep it up folks.
Thx for watching 👍
Thank you for sharing, Good content and good work. Suggest start with core functional and non functional requirements and then capacity planning numbers and read write per sec needing to support the core functional needs. Otherwise seems we go straight into solution which is ok, some may want to know how we think ahead of an ambiguity and the problem space and have conversation around what we want to do with the interviewer. Maybe also consider adding handling copyright issues when we are extracting and rendering html, de dupe service and bloom filter, how nested cyclic loops in a site will be handed, caching strategy etc.
Thanks for watching. You're right, addressing the requirements ahead of time is very important in this process, and our more recent videos tend to be better about that :)
Well thats an instant sub!!
yes! thanks for watching!
Great video, really like your way of explaining stuff.
thanks - more videos on the way!
Thank you for sharing the great design prep video. What tools or combination of tools/software is used to create the figures (with the black blackground). Thanks
Thanks for watching! We use GoodNotes on an iPad.
This is great content. Regarding shingles, that takes a LOT to implement - lots of space and lots of CPU to compare them. The idea of the personalized recommendations is a huge success Google has and is surely difficult to implement considering the entire search, rank (personalize) and retrieve has to be done in a second.
Thanks! You're exactly right--Google has built an incredibly impressive system :)
2:00 This is how to make an ad, good job!
Lol thanks :)
Wow...Super impressed
Thanks! A lot more coming! We will be posting consistently.
Could someone pls explain what text and hash indexes are? Are they separate DBs storing partial information compare to the main DB or something else? Thanks!
You're exactly right. You can think of global indexes as a copy of the database but organized onto nodes differently, and the records generally only include enough data to be able to look up the corresponding record in the primary.
Outstanding! Thank you!
Thanks for watching!
Really appreciate it. I have several questions for politeness part. If there are 10k hosts, are we supposed to have 10k queues for politeness? Let's say if one host has only 3 urls, after all the 3 urls are visited. are we supposed to delete the idle queue? Each time we have a new host, are we supposed to created a new queue.
Yep, we'd need one queue for each host. There'd probably be far more than 10k in fact! Of course, these would simply be logical partitions residing on a far smaller set of physical machines. We would need to add a queue when a host is visited for the first time (this would be trivial since a queue is just a logical abstraction), but we probably wouldn't need to worry about deleting since we'll keep re-crawling hosts. Hope that helps!
It was an incredibly detailed explanation
Thanks for watching 👍
The video is really awesome and helpful ❤.
thanks for watching!
Could you explain to me a thing I'm confused about here 13:35. When the router selects an element from the priority queue - it adds it to the politeness queue, by doing that wouldn't we loose the initial prioritization given that the politeness queues are sorted just by domain?
Sure. The router uses a weighted random algorithm to select a priority queue, so the higher priority queues are more likely to be selected. This ensures that higher priority pages are crawled more frequently, regardless of what politeness queue they end up in. Thanks!
One application of this solution is for horizon risk scanning. The use case is that a large multinational corporation wants to have an idea of new risks which are emerging and adopting this approach allows them to have a traceability back to the web source. Of course they won’t be crawling 100M pages but maybe 100k pages.
Interesting! Thanks for watching :)
Don't think the schema design for the query pattern "Search for a word " is included. The video says there is a text index but I don't see "word" or "frequency" at th-cam.com/video/0LTXCcVRQi0/w-d-xo.html
I think the schema needs to include these so that index automatically creates a table on top of these.
Also the part about Router routing URLs to correct queue, It's mentioned that if there is no Queue corresponding to domain then it will added to "empty" queue. But then what about updating the Heap and selector.
Also the mapping of a domain to queue has to be stored somewhere. Most likely in Redis cache as it seems like changing a lot in case queue becomes empty.
1. The "site content" field in the schema should hold the full text of the site, so words and their associated frequencies can be calculated when records are added/updated, and this data is what propagates to the text index.
2. Yep, when a new host is added to the second set of queues, the router is responsible for adding that host to the heap so the selector knows about it.
3. The host-to-queue mapping would be stored in the router, that way the router is able to quickly check which queue the next URL should be added to. It's worth noting that the router is low-traffic enough (
@@interviewpen for the point 1, you mentioned that the word and frequency is calculated when a record is added or updated. But then also it needs the corresponding attributes so that it can be added to Databased when record is added or updated.
As per timestamp 3:32 the schema doesn't contain word or frequency. Am I missing something? It might be something dumb apologies.
man it's so good content, who are personally you btw?)
The instructor is named Bobby - I am Benyam, I do our Data Structures & Algorithms. Thanks for watching.
great video, but can I ask? can we use elasticsearch instead? I'm not a professor but seeing a lot of system using elastic search to optimize their query performace.
Glad you liked it! ElasticSearch actually uses a very similar data structure to the "text index" we described, and this could certainly be swapped out for our database in this system. It's just about tradeoffs between ease of use in a managed service and flexibility.
Very Simple and Good
Thanks!
I'd like to watch a deeper explanation about how to search for data in a shard database like you explained.
we'll cover sharding in-depth soon! thanks for watching!
@@interviewpen I'm looking forward to watch it.
Your Channel is very good
Thank you!
Amazing!!!
Thanks for watching.
Love the video but I'm perplexed as to why you want to store the site contents. I figure that you would just scrape it for word frequencies for matching later to queries?
Good question--we store the site contents so we don't have to scrape them again later if we want to change our algorithms. Google does this too! Thanks for watching.
while you've been explaining Schema you mentioned hash as a way to make sure something is unique. Can you explain in detail how hash helps with that?
Sure--hashing a large piece of data (such as a webpage) yields a far shorter, fixed-length string that uniquely represents that data and can be stored in a database. By checking if this hash already exists in our database, we can effectively check if the webpage has already been seen without having to compare the page content against petabytes of other pages.
The amount of time u put in this video is crazy 😭
Keep it up 😼😼
Thanks, more is on the way :)
Very nicely explained
Thx for watching!
Great content, yours are the best system design interview mocks I've seen on here. Could you do one on a RSS feed website?
Thanks! Sure, we'll add it to the backlog :)
Awesome!
Thanks for watching 👍
Great video, but im curious is it really neccassar to sort by frequency of a word in URL?
i think most well designed URL wont have key word like cat appear more than one time in Url?
Also if there's cat and dog in a URL should I have two record for a URL?
No, we're searching the content of the pages here, not the url. Thanks for watching!
Hey awesome video. Just subd. What is the app you are using in ipad for this?
GoodNotes - thanks for watching!
Piece of cake !!!
ye
@@interviewpen I'm gonna build one now to smash Google !!! kkk :-D
Instead of sharding right off the hook, could use partioning. Sharding should be the final resort
Good point, but 31TB of metadata is a lot to store on one node so it's necessary in this case to scale horizontally. Our query patterns work very nicely here (always single-record reads/writes by a unique key), so it shouldn't be a problem. Thanks for watching!
terima kasih puan
sure - thanks for watching!
Very nice walkthrough appreciate the effort. I have a question tho, maybe a stupid one. I didnt quite get if "heap" means the data structure heap or the heap as a general memory space just like it is called in Java. I mean if its the data structure, wouldnt it be very inefficient to search for the correct pointer for the politeness queue you are looking for? From your explanation I am inferring that this heap is more like a memory space and works more like a hash map. Is this correct?
We did mean the heap data structure--this works very efficiently here since the earliest timestamp will always be at the top of the heap. The heap just tells us which politeness queue to look at next; no searching necessary. Thanks!
I'm not sure if I understood correctly but why are we not using any ES cluster to speed up our search? No DB can be as efficient as ES when it comes to search.
ElasticSearch is essentially a sharded db with full text search at its core, so a properly architected database will do the same thing. But you’re absolutely right-es is certainly a viable solution if we want a pre-built solution.
have a trouble finding that shingles technique author mentioned close to the end. can anyone give some sort of reference?
Thanks for watching! It's a bit math heavy but here's a reference for shingling: nlp.stanford.edu/IR-book/html/htmledition/near-duplicates-and-shingling-1.html
*ChatGPT giving me a "rudimentary" outline of some python code for this explanation based on the youtube transcript. What do you think:*
*python*
class API:
def __init__(self):
self.load_balancer = LoadBalancer()
self.text_index = TextIndex()
self.metadata_db = MetadataDatabase()
self.blob_store = BlobStore()
def search(self, query):
urls = self.text_index.search(query)
results = []
for url in urls:
metadata = self.metadata_db.get_metadata(url)
page_content = self.blob_store.get_page_content(url)
results.append((metadata, page_content))
return results
class LoadBalancer:
def __init__(self):
self.api_servers = []
def distribute(self, query):
api_server = self.select_api_server()
return api_server.search(query)
def select_api_server(self):
# Logic to select API server based on load balancing
pass
class TextIndex:
def search(self, query):
# Implement search logic to return URLs based on query
pass
class MetadataDatabase:
def get_metadata(self, url):
# Retrieve metadata for the given URL
pass
class BlobStore:
def get_page_content(self, url):
# Retrieve page content for the given URL
pass
class Crawler:
def __init__(self, url_frontier):
self.url_frontier = url_frontier
self.hash_index = HashIndex()
self.metadata_db = MetadataDatabase()
self.blob_store = BlobStore()
def crawl(self):
while True:
url = self.url_frontier.get_next_url()
if self.check_robots_txt(url):
page = self.fetch_page(url)
if not self.is_duplicate(page):
self.save_page(page)
new_urls = self.extract_urls(page)
self.url_frontier.add_urls(new_urls)
def check_robots_txt(self, url):
# Check robots.txt for the given URL
pass
def fetch_page(self, url):
# Download the page content for the given URL
pass
def is_duplicate(self, page):
# Check if the page is a duplicate using HashIndex
pass
def save_page(self, page):
# Save the page content and metadata
pass
def extract_urls(self, page):
# Extract new URLs from the page content
pass
class HashIndex:
def check_duplicate(self, page):
# Check if the page content is a duplicate
pass
class URLFrontier:
def __init__(self):
self.priority_queues = []
self.host_queues = []
self.heap = []
def get_next_url(self):
# Get the next URL based on priority and politeness
pass
def add_urls(self, urls):
# Add new URLs to the appropriate queues
pass
# Initialize components
url_frontier = URLFrontier()
api = API()
crawler = Crawler(url_frontier)
# Start crawling and serving API requests
crawler.crawl()
Might be a little more complex in practice :D Thanks for watching!
cool guide, thanks
sure - thanks for watching, more videos coming
4:22 anyone know how the database storage size Bytes estimates were determined?
The sizes for each field are simply estimates based on the data being stored.
Thanks!@@interviewpen
Also important to remember that search engines are moving to Vector databases with machine learning matrixes
Good point!
Informative video! Very nicely explained. Could you pls do one on distributed key/value stores?
thanks for watching - yes that's in our backlog
Can someone explain how does the priorityQueue really work for choosing the next element in the queue? Is it like a min priority queue where the top element will be having the minimum time to remove and we compare current time and minimum time and finally process the element and then if multiply rendering time by 10 and put it back to the queue and the priority queue. In that case if a 2 elements have the same time in priority queue how do we choose which one to pick?
Yep you got it right, we’re looking for the earliest timestamp. If two elements have the same timestamp, it doesn’t matter which one we pick. Thanks!
Thanks
sure
Thanks, great video but I have 1 comment. You are saying that you are going to cache the robots.txt file. How does Google system then know that the robots.txt was updated? From what you mentioned, you always take it from cache as long as it is there but you didn't mention cache invalidation.
Thanks for watching! Really good point-in this system it’s not critical for the robots.txt to be constantly up to date, but there definitely should be some TTL set in the cache to make sure the data is re-fetched periodically.
what are you using to draw on and the software to make this? i find it super helpful and would like to make my own videos using it, thank you
Cool, we're using GoodNotes on an iPad. Thanks!
awesome
thanks for watching - more videos coming soon!
What software do you use for the UI for the workflow and to highlight pen?
We use GoodNotes on an iPad. Thanks!
Which app you are using for writing?
BTW quality content 👌🏿
We use GoodNotes on an iPad 👍
nice content thank you
Thanks!
Is there some kind of open dataset to get the database going without having to crawl the whole web from 0?
There is! Check out www.commoncrawl.org/ (just one example)
@@interviewpenooooh that's incredible thank you so much 🙏🥰
The fact that when you crunch the numbers, the metadata is only
recognised the B2B SWE voice :)
Yep :D
Seems like a huge amount of complexity to avoid crawlers hitting the same URL. I would take the approach that they will rarely select the same URL anyway, so just have at it and wear that occasional doubling up for the massive speed increase it gives you on the 99% case - especially given the huge number of URLs something like google must be crawling.
When the crawler discovers a new site, it's pretty likely that several pages on that site would line up close together in the URL frontier. At the scale of thousands of crawlers, we'd basically be DDOSing every new site! But you're absolutely right that it's an important tradeoff to consider. Thanks!
For resolving politeness issue, why a heap?
Good question; the heap data structure enables us to efficiently look up the host with the smallest timestamp, i.e. the host that we crawled the longest ago. With a significant number of host queues, this operation could add notable latency without using a heap. Thanks!
@@interviewpen oh I see. I haven’t encountered any heaps and was surprised to see it can be used as a HashMap of some kind.
Why are you thanking me lol I should be thanking you for the video
🎉Great video🎉May I try to up a Chinese CC？ It s useful to someone under me❤
sure - what is an email we can use to add you as a CC moderator?
Does anyone know a list of storage requirements for things like text (diff sizes), images, etc?
This is factored into the 2MB per page that we're storing in the blob store.
what is the tool you are using for presentation? thank you
We're using GoodNotes on an iPad. Thanks!
are we going to remove the blob after creating hash index and word index ?
It depends on the requirements of the system, but in this case we'll keep the BLOB around. This is helpful since there's so much overhead involved in scraping sites--for example if we decided to change our indexing algorithm, we could do so from the saved BLOBs without having to re-crawl every page. Google does this too--in fact you can view Google's copy of a page by clicking the "cached" link on a search result. Thanks for watching!