Distributed web crawler

01 · CONTEXT AND SCOPE

What a web crawler needs to do

A web crawler, also called a robot or spider, is the program that discovers new or updated content on the web. It starts from a few pages, follows the links it finds on them, and collects whatever shows up. The most common use is to feed a busca.

The basic algorithm fits in three steps: given a set of URLs, download the pages; extract the URLs from those pages; and add the new ones to the list of pages to download, repeating the cycle. Despite its simplicity, designing a large-scale crawler is an extremely complex task, and this case is about why.

Four properties guide the design. Scalability: the web is huge, so crawling needs to be parallel. Robustness: the web is full of traps, such as malformed HTML, unresponsive servers, crashes, and malicious links. Politeness: the crawler should not make too many requests to the same site in a short time. Extensibility: supporting a new content type should require few changes.

02 · SCALE ESTIMATION

Back-of-the-envelope math

The ByteByteGo book assumes one billion pages downloaded per month, which gives about 400 pages per second, with a peak of 800, double the average. With pages of 500 KB on average, that is 500 TB per month and, storing five years of content, 30 PB.

The System Design Primer starts from different assumptions: 4 billion links crawled per month, with an average refresh of about once a week and more frequent for popular sites. This gives 1,600 writes per second, and the Primer adds 40,000 searches per second, because it includes the query side.

The two sources diverge on volume, and that is expected: an estimate is a hypothesis. What matters is to show the assumptions and arrive at the order of magnitude: with this much data, one server is not enough and the work needs to be distributed.

03 · HIGH-LEVEL DESIGN

Frontier, downloader, and parser

The design has few pieces. The fila of URLs to download, the URL Frontier, holds what remains to be crawled; the book describes it as a FIFO queue. The HTML downloader fetches the pages and queries a DNS resolver to get the IP of each URL. Then a parser validates the page; it is a separate component because, inside the crawl server, it would slow down the crawling.

1. The seed URLs enter the queue of URLs to download and the downloader takes one of them.

2. The downloader fetches the page from the origin server.

3. The downloaded page goes to the parser, which checks whether the HTML is well formed.

4. Valid pages are written to the content storage.

5. The parser extracts the links from the page and returns the new ones to the queue, closing the cycle.

This design works, but leaves three questions open: in what order to crawl, how not to overload a single site, and how not to repeat work. The next sections answer each one.

04 · THE URL QUEUE

Order, politeness, and freshness

The natural order is breadth-first search (BFS), implemented with a FIFO queue. Depth-first search is usually a bad choice, because the depth can be enormous.

The simple queue has two problems. First, most links on a page point to the same server, and downloading in parallel floods that server with requests, which is considered impolite. Second, it ignores URL priority, and not every page has the same quality and importance.

For politeness, the idea is to download one page at a time from each host, with a delay between downloads. A table maps each host to a queue, and each downloader only consumes its own. For priority, a prioritizer measures the URL's usefulness, for example by PageRank, and the higher-priority queues are chosen with higher probability.

The result is two modules: the front queues handle prioritization and the back queues handle politeness.

1. The extractor hands the new links to the prioritizer, which measures the importance of each URL.

2. Each URL enters one of the front queues, according to priority.

3. The selector draws a front queue at random, biased toward the higher-priority ones.

4. The chosen URL goes through the router, which sends it to the back queue of its host.

5. Each back queue holds URLs from a single host.

6. One downloader per queue downloads one page at a time and can wait between downloads.

Pages change all the time, so the crawler needs to recrawl the ones already downloaded to keep the data fresh. Redoing everything is expensive. Two strategies: crawl important pages earlier and more often, and use each page's mean time between updates, as the Primer suggests, to decide the frequency.

The frontier can reach hundreds of millions of URLs. Everything in memory is neither durable nor scalable, and everything on disk is slow. The book's hybrid solution keeps most of it on disk and maintains in-memory buffers to enqueue and dequeue URLs.

05 · NOT REPEATING WORK

Repeated content and repeated URLs

Part of the web is duplicate content: a study cited by the book indicates that 29% of pages are repeated. Comparing two HTMLs character by character is slow, so the Content Seen component compares the pages' hashes. If the content is already in storage, the page is discarded; if not, it goes on to link extraction.

The extracted links go through the URL filter, which excludes certain content types, file extensions, and erroring links. Next, the URLs Seen component records what has been visited or is already in the frontier, so as not to enqueue the same URL twice, which would increase the load on the servers and could cause infinite loops. Only never-processed URLs enter the frontier. Bloom filter and hash table are common techniques to implement this component.

The Bloom filter is a probabilistic, space-efficient data structure that tests whether an element belongs to a set. It allows false positives, but not false negatives: it answers "possibly present" or "definitely absent". Applied to seen URLs, this means the filter may wrongly flag a new URL as already seen, but never forgets a URL that was in fact recorded.

1. The downloader hands the page to the parser.

2. After validation, the page goes to Content Seen, which compares its hash with those already stored.

3. If the hash is new, the content is written to storage.

4. With new content, the link extractor reads the HTML; if the content already existed, the page is discarded here.

5. The extracted links go through the URL filter and then through the URLs Seen component.

6. Only never-seen URLs enter the frontier, and the cycle starts over.

The Primer takes another route: a table of crawled links stores each page's signature, and, if a page with a similar signature already exists, the crawler lowers the link's priority, which avoids cycles. The Primer itself admits that detecting duplicate content is more complex than detecting duplicate URLs.

06 · PERFORMANCE AND ROBUSTNESS

Robots.txt, DNS, failures, and traps

Before crawling a site, the crawler should read robots.txt, the Robots Exclusion Protocol, and follow its rules. So as not to download the file every time, it stores the result in cache. The Primer adds that the file gives webmasters control over the crawl frequency.

The DNS resolver is usually a bottleneck, because many DNS interfaces are synchronous: the response takes 10 ms to 200 ms and, while one thread waits, the others are blocked. The way out is to keep your own cache of name to IP, updated periodically.

Other optimizations: distribuir the crawling across several servers, each one responsible for a subset of the URLs; placing the servers close to the sites, which speeds up the download; and setting a maximum wait time, abandoning hosts that do not respond.

For robustness, the book suggests consistent hashing to distribute the load among the downloaders, saving the crawl state and data to resume after a failure, and handling exceptions without bringing the system down.

A spider trap is a page that holds the crawler in an infinite loop. Limiting the maximum URL length avoids some of them, but there is no universal solution to detect them. Sites with traps usually have an abnormally large number of discovered pages, and a person can check them and exclude the site or apply their own URL filters.