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.
Greetings, I just came to RUclips 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!
@@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
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
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
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 :)
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 🦀🙏🏾
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
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.
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
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 :)
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.
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
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.
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!
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!
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.
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.
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.
*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()
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.
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!
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!
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 ruclips.net/video/0LTXCcVRQi0/видео.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 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?
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
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.
I don't understand why this search engine has to actually store the contents of each website, when it can just store the domain/ip address of where that website is.
Good point, that wasn't covered very well in this video. We usually want to keep the contents of the page in case we change things later on. Rather than having to re-crawl every page, we can used our cached copy to change site priorities, metadata, etc. But for the core functionality of this system, it's not entirely necessary. Thanks!
That must take a lot of storage to pretty much store a copy of the entire internet! Do they also scrape all of the videos on the internet and store that?@@interviewpen
Sure. There's a number of algorithms we could implement here, but the general idea is to analyze the page and how frequently it changes to determine how frequently to crawl it. The prioritizer will take in all the data and insert the page into the correct queue based on its calculated priority. Thanks for watching!
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 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!
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.
Honestly one of the best videos on the internet for system design!
Thank you!
Greetings, I just came to RUclips 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!
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
This channel is gonna explode. The content is just too good. Thank you.
Thanks for watching - we'll be posting a lot more!
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
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
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
Clean, clear, efficient. ❤
I’d love to see more videos like this from you!
Will do, 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
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
Loved the video! A video I'd love to see in the future is system design for video streaming applications e.g. RUclips, Netflix.
Will do - thanks for watching
Wooooah!!!! This is what I needed in my life 😢. I’m now complete
awesome haha - thanks for watching
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
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
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!
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!
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 :)
This is amazing! I honestly cant wait to look into your other videos!
More videos coming! Thanks for watching.
@@interviewpen eagerly waiting!
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.
2:00 This is how to make an ad, good job!
Lol thanks :)
Wow, this is information all for free. Thank you for making this video
thanks for watching - more coming
Exceptional way of explaining things , I'm subscribed to you guys now
great!!
This was amazing. Now I want to try build a search engine!
lets gooooo - thanks for watching
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!
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 :)
I was looking for something like this for a while. This content is worth the time spent.
thanks for watching
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!
I am impressed, you really deserved my sub❤
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.
Thanks! You're exactly right--Google has built an incredibly impressive system :)
Great work buddy....very detailed explanation... cheers
thanks for watching!
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.
Second Video I watch from you. It’s so good. thank you
Glad you liked it!
Great video man, wish I had found this before
Thanks!
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 :)
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.
Great video..
Keep it up folks.
Thx for watching 👍
Also important to remember that search engines are moving to Vector databases with machine learning matrixes
Good point!
It was an incredibly detailed explanation
Thanks for watching 👍
Great video, really like your way of explaining stuff.
thanks - more videos on the way!
Your Channel is very good
Thank you!
Hey awesome video. Just subd. What is the app you are using in ipad for this?
GoodNotes - thanks for watching!
really wow!!!!!!! amazing content.
thanks, more coming soon!
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.
Informative video! Very nicely explained. Could you pls do one on distributed key/value stores?
thanks for watching - yes that's in our backlog
The amount of time u put in this video is crazy 😭
Keep it up 😼😼
Thanks, more is on the way :)
terima kasih puan
sure - thanks for watching!
Which app you are using for writing?
BTW quality content 👌🏿
We use GoodNotes on an iPad 👍
This is high quality content.
Thanks, glad you enjoyed it!
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.
Very Simple and Good
Thanks!
Wow...Super impressed
Thanks! A lot more coming! We will be posting consistently.
This channel is amazing
thanks - we have a lot more coming!
Very nicely explained
Thx for watching!
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!
The video is really awesome and helpful ❤.
thanks for watching!
recognised the B2B SWE voice :)
Yep :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!
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.
cool guide, thanks
sure - thanks for watching, more videos coming
Bro developed Google Search in 19 minutes
hahaha - thanks for watching.
Well thats an instant sub!!
yes! 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.
Thanks
sure
Awesome!
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.
*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!
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.
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!
The fact that when you crunch the numbers, the metadata is only
Amazing!!!
Thanks for watching.
awesome
thanks for watching - more videos coming soon!
Piece of cake !!!
ye
@@interviewpen I'm gonna build one now to smash Google !!! kkk :-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!
Only if it was this simple hahahahaha But it is really cool to see the thought process and the basic mind map
Thanks for watching!
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!
nice content thank you
Thanks!
🎉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?
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 ruclips.net/video/0LTXCcVRQi0/видео.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.
kindly make a video systems design for algorithms
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!
woooooow
thanks for watching - more videos coming soon!
oh my goodddddddddeddd
Yep.
Now make it into a neural network that is trained to fetch the best thing just for you!
ye
@@interviewpen TF-IDF (Term Frequency - Inverse Document Frequency) is what is normally used.
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
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.
I don't understand why this search engine has to actually store the contents of each website, when it can just store the domain/ip address of where that website is.
Good point, that wasn't covered very well in this video. We usually want to keep the contents of the page in case we change things later on. Rather than having to re-crawl every page, we can used our cached copy to change site priorities, metadata, etc. But for the core functionality of this system, it's not entirely necessary. Thanks!
That must take a lot of storage to pretty much store a copy of the entire internet! Do they also scrape all of the videos on the internet and store that?@@interviewpen
The internet is estimated to be 64 Billion TerraBytes!@@interviewpen
What software do you use for the UI for the workflow and to highlight pen?
We use GoodNotes on an iPad. Thanks!
Please explain how the prioritizer works here
Sure. There's a number of algorithms we could implement here, but the general idea is to analyze the page and how frequently it changes to determine how frequently to crawl it. The prioritizer will take in all the data and insert the page into the correct queue based on its calculated priority. Thanks for watching!
what is the tool you are using for presentation? thank you
We're using GoodNotes on an iPad. Thanks!
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!