Lets learn "About web crawler system design"

-

 


In this tutorial, we'll learn about the system design for the distributed web crawler. A web crawler is also known as a spider bot. It's a framework or tool or software which is used to collect the web pages and save them in a way to easily access them. This process is known as web indexing.

Different use-cases of web crawlers 

  1. Search Engine: E.g: whenever you search something it returns the relevant pages as we've already stored the web pages in an optimized fashion. 
  2. Copyright violation detection: This means finding users using copyright content and sue them.
  3. Keyword-based finding: This is similar to the search engine which helps to find web pages based on keywords.
  4. Web malware detection: To detect if someone has created similar pages for phishing attacks. Like amazon could be doing web scrawling to search web pages similar to its own web page that some hacker is using for phishing.
  5. Web analysis: Used by some companies/data scientists to characterize the feature of web application.
  6. Data mining: Mostly similar to web analysis and convert raw information to useful information.

Design

Features we'll be supporting and discussing in this tutorial

  1. Politeness/crawl rate
  2. DNS Query
  3. Distributed Crawling
  4. Priority Crawling
  5. Duplicate detection

Scale

  • We've around 2 Billion websites available on internet ( as of 2020 ).
  • On an average we've 100 pages per website.
  • So our target is 200Billion pages and assuming 120 Kb as average pages size, we've 24 Petabytes of data.

Goals

  1. Scalability
  2. Extensibility
  3. Freshness of pages
  4. Server side rendering
  5. Politeness: Crawer consume resources on destination servers and often visit sites without approval. Hence we need to be polite of destination servers.

Architecture

Let's learn about the different components individually.
  1. Seed URLs: These are initiator URLs that need to be provided to start crawling. One of the strategies here is to provide a few URLs from all the sectors including education, railways, movies, etc.
  2. URL Frontier: It's basically a priority queue to which seed URLs are provided. It has different built-in features including politeness, priority, etc. 
  3. Fetcher & Renderer: This is built using the threads or anything which provides concurrency. These components can be scaled by adding more and more machines.
    1. Fetching: It fetches the content of URLs. Basically, we have workers doing fetching + rendering per worker. When a worker is free it asks the URL frontier to provide the next URL to crawl. Then it uses the DNS resolver to resolve the IP address of the host. Why internal DNS? Because external DNS resolver takes some time to resolve the address. Internal DNS fastens the resolution part. Another thing is DNS resolver is single-threaded which blocks the request until the current request is being processed that all slows down things.
    2. Rendering: Why rendering is required because earlier fetching the content was sufficient before reactJS/angularJS because earlier the content was static. But with these high-level languages, content is dynamic because they make multiple ajax calls to get all the content property. Hence we need to render the page after fetching.
    3. NOTE: We need to set the USER-AGENT field in the requests header made from the crawler. Like, google web crawler set it to GOOGLE BOT. The advantage of this is that website admins configure webserver behave differently for different search engines.
    4. Caching the content: One of the executors get the content we need to cache. That is when we use Reddis and also it is persisted to storage. Why caching is required? For faster access and in permanent storage we can compress it.
  4. Queue (Response): Now after the executor processes the data and saves it to Redis, it also sends a message to the response queue containing the pointers to data persisted in Redis. The consumer of this response queue is the list of extractors ( we can add as many it is required ).
  5. Extractors: Extractors get the data from Redis and perform the extractions.
    1. URL Extractors: The URL extractor extracts the URLs from the page. 
      1. After extracting the URLs, it maps the URLs to its domain. Like mail.google.com, keep.google.com, docs.google.com are mapped to the google.com domain.
      2. Normalize the URLs to make them follow standard conventions.
    2. Duplicate Detectors: Duplicate detectors detect duplicates and exclude them.
  6. URL Filter: It filters the URL based on the type of crawler. Like if a crawler is configured to use mp3 content, the URL filter will ignore other content.
  7. URL Loader | Is Crawled: Once the URL filtering is done, we'll check if the URL is already crawled or not. To check if the URL is crawled or not we'll use BLOOMFILTERS for optimization. Then unique URLs are again sent to the URL frontier. 

System design for URL Frontier



URL Frontier ensures the following things:
  1. Priority - For some of the websites, we need to crawl frequently because the content keeps updating for those. For e.g news websites, or some sports website. For such websites we set priority to high.
  2. Recrawl - As mentioned above there are some websites which requires recrawl.
  3. Freshness - Recrawling websites ensures the freshness of the content.
  4. Politeness - This is a very important point. Any crawler should be polite on any server to ensure the crawling on that servers should not affect end users. Politeness can be in terms of visiting a particular domain or creating a limit connections to particular server.

Different components of URL Frontier

Now we've discussed the different features of URL Frontier, its time to see how different components of URL Frontier ensures these features.

1. Front Queues: These are FIFO queues which maintains the list of URLs to crawl. No. of these queues depend on the range of priorities we have. If we have priorities ranging from 0-999, the number of such queues  will be 1000.

2. Prioritizer: This component is responsible for assigning the priority to the incoming URLs. Based on the priority of the URL it sends to the corresponding queue in the front queues list. How prioritizer gives the priority? Basically we checks the older data to figure out how frequently the data had changed for given URL. More frequently the data is changing, more is the priority for that URL.

3. Back queue router: From all the front queues, data goes to the back queues via back queue routers. Basically back queue router ensures that none of the back queues remain empty by continuous polling. So this component pulls the URLs from front queues and pushes them to the back queues.

4. Back queues: Back queues like front queues are also FIFO queues. The number of back queues we have is equal to the number of executors. Every back queue contains the URLs for particular domain.

5. Back queue selector: Back queue selector selects the URL from back queues and send it to the fetcher + renderer. Back queue selector ensures the crawler should be polite against any servers i.e it shouldn't be hitting servers of particular domains much frequently.

Detecting updates and Duplicates

Now let talk about the different types of URL Extractors.

1. Updates Detector: This component detects how frequently the web page is updating which will be used by the prioritizer to set the priority of the URL. How it detects updates? Shall we need to download the page and match with the old content? The answer is NO!. What it does is make a HEAD request to the URL which returns the last modified time. And we simply match the last modified time to detect if the page is updated or not.

2. Duplicates Detector: Statistics show that 30% of the pages are duplicates. So detecting duplicates is very important as it can enhance the performance of the web crawler. Now how to detect duplicates?
    a. Brute force method: This method includes comparing each word of the page. This is inefficient, right? This will not work on scale.
    b. Hashing: This method includes calculating the hash (like md5) of each page and compares its value. While storing the page in Redis we can also store its md5 and eliminate the duplicates. 
But this method also won't work well on the scale because two pages will be having the same hash only if each and every word is the same which is not the case in reality.
   c. Probabilistic Hashing: There are some algorithms that do the probabilistic matching. These algorithm includes 1. Min hash, 2. Sim hash, 3. Fuzzy hash. These algorithms will help in doing the probabilistic matching. We will dive into the working of these algorithms in a separate tutorial.



HOPE YOU LEARNT SOMETHING NEW IN THIS TUTORIAL. FEEL FREE TO COMMENT BELOW IN CASE OF ANY DOUBTS. AAANNNNDDDDDD.... STAY TUNED FOR MORE TUTORIALS :)



Comments

Post a Comment

Popular posts from this blog

Lets learn "About kube proxy in iptables mode"

-
Image
In this tutorial, we'll learn about the Kube-proxy in iptables mode. Basically, we'll see how Kube-proxy create iptables that help in load balancing and service discovery. If you are not familiar with Linux IPTables I would recommend to check out my tutorial on IPTables here  first and then come back to read this tutorial. Kube-proxy Kube-proxy when running in iptables mode basically watch kube-apiserver for new endpoints and create corresponding iptables rules and iptables are fully responsible for service discover and proper routing of traffic to corresponding pods. Kube-proxy needs to run on all k8s worker nodes. Below is a small video describing the working of kube-proxy in iptables mode.  src:  https://www.slideshare.net/CJCullen/kubernetes-networking-55835829 Now that we know what Kube-proxy is and how it Kube-proxy works, let deep dive into the types of iptables Kube-proxy adds to the firewall. Kube-proxy added IPTables To learn this let's consider an example. Consid
Read more

Lets learn "System design for paste bin (or any text sharing website)"

-
Image
  In this tutorial, we'll learn about the system design for PasteBin. If you don't know what Pastebin is here goes its definition. Pastebin is a type of online content hosting service where users can store texts to share with others over the internet.  Pastebin system design requirements  Functional Basic - User should be able to paste the text, generate the link and share the link with other users. There should be the max size of the text that our system will support (say 10Mb) Users should be able to provide the custom URL path for the link created. Like if a user wants to create the links  www.pb.com/letlearn, he can give this URL and pastebin should create a link using this URL to share with others. The link or paste expiry feature should be there for each stored text. There can be default expiry time say 1 year but this should be configurable. Personalization means the user should be able to login to track all the pastes created by him and manage them. Non-Functional Durab
Read more

Lets learn "Factory design pattern"

-
 In this tutorial, we'll learn about the factory design pattern as in what it is, in which use cases this is being used and how it works. If you've are not familiar with what are software design patterns and what are its different types check out this tutorial. Introduction A factory design pattern is a creational design pattern that is related to object creation. In this pattern, we'll have a method to create an object without exposing its creation logic to the client. If a class method is creating an object it has to be static.  The idea is to create a static method ( factory method ) which instantiates a class without exposing its logic to the client and the client can use that method every time it needs to create an object of the class. The reason why the factory pattern is useful is that as it does not expose the logic of object creation, so if logic is changed, the client code need not to be changed. Usecases The place where this pattern is mostly used is library cod
Read more