Design a web crawler

At the start we seed a few webpage which recursively add more pages from the links found on the seed pages.

Uses Cases

Used for search engine indexing, web archiving, web minining (scraping), web monitoring (copyright checks)

Estimations

To design a crawler, find it's purpose (indexing), pages per month (billion), page type (dynamic, html, pdfs), storage duration (years) and handling duplicate content (keep first).

1 billion pages per month

• Throughput: 1 billion queries / 30 days / 24 hours / 3600 secs = ~400 QPS

• Storage: 1 billion pages * 500kb / page = 500TB / month * 5 years = 30 PB

Attributes

Crawlers should be robust (flakey servers, malicious links), polite (don't abuse host servers), extensible (support new types)

Workflow

URL frontier

The component that groups and prioritizes urls that need to be processed. To ensure that the crawler respects the server, it will group urls from the same host before pushing them to a worker to process, limiting the number of requests downloaded per host by the processor. It can also reorder urls based on pagerank priority. Links are added to the frontier and processed with a BFS queue as DFS could get too deep. There could be potentially millions of urls to process. To reduce memory requirements most can be kept on disk and retrieved iteratively.

HTML downloader

There could be several which will download the actual file content. It will download the file and store it if new. It will also parse content and extract urls. They will filter out seen urls and restricted paths of the site's robots.txt file. Modern webpages would need to be server-side rendered to extract dynamic content. To reduce DNS lookup which could take between 10-200ms, the IPs are cached. To work with slow pages, a timeout has to be used, as well as handling processing errors gracefully and hashing content to skip duplicates. The state of downloaders is preserved so in the event of a node failure, it can pick up from the last known state.

References

• PageRank

This article is part of the system design series where I am summarizing chapters from The System Design Interview: Volume 1 / Volume 2 amongst other related content