Step 7: Link extractor extracts links from HTML pages. Step 8: Extracted links are passed to the URL filter. Step 9: After links are filtered, they are passed to the URL Seen? component. Step 10: URL Seen component checks if a URL is already in the storage, if yes, it is processed before, and nothing needs to be done. Step 11: If a URL has not been processed before, it is added to the URL Frontier. Step 3 Design deep dive Up until now, we have discussed the high-level design. Next, we will discuss the most important building components and techniques in depth: Depth-first search (DFS) vs Breadth-first search (BFS) URL frontier HTML Downloader Robustness Extensibility Detect and avoid problematic content

DFS vs BFS You can think of the web as a directed graph where web pages serve as nodes and hyperlinks (URLs) as edges. The crawl process can be seen as traversing a directed graph from one web page to others. Two common graph traversal algorithms are DFS and BFS. However, DFS is usually not a good choice because the depth of DFS can be very deep. BFS is commonly used by web crawlers and is implemented by a first-in-first-out (FIFO) queue. In a FIFO queue, URLs are dequeued in the order they are enqueued. However, this implementation has two problems: Most links from the same web page are linked back to the same host. In Figure 9-5, all the links in wikipedia.com are internal links, making the crawler busy processing URLs from the same host (wikipedia.com). When the crawler tries to download web pages in parallel, Wikipedia servers will be flooded with requests. This is considered as impolite.

Standard BFS does not take the priority of a URL into consideration. The web is large and not every page has the same level of quality and importance. Therefore, we may want to prioritize URLs according to their page ranks, web traffic, update frequency, etc. URL frontier URL frontier helps to address these problems. A URL frontier is a data structure that stores URLs to be downloaded. The URL frontier is an important component to ensure politeness, URL prioritization, and freshness. A few noteworthy papers on URL frontier are mentioned in the reference materials . The findings from these papers are as follows:

Politeness Generally, a web crawler should avoid sending too many requests to the same hosting server within a short period. Sending too many requests is considered as impolite or even treated as denial-of-service (DOS) attack. For example, without any constraint, the crawler can send thousands of requests every second to the same website. This can overwhelm the web servers. The general idea of enforcing politeness is to download one page at a time from the same host. A delay can be added between two download tasks. The politeness constraint is implemented by maintain a mapping from website hostnames to download (worker) threads. Each downloader thread has a separate FIFO queue and only downloads URLs obtained from that queue. Figure 9-6 shows the design that manages politeness. Queue router: It ensures that each queue (b1, b2, bn) only contains URLs from the same host. Mapping table: It maps each host to a queue.