Requirements, estimates and a crawler's parts

The problem

A web crawler starts from a list of URLs, downloads the pages, extracts their links and keeps going. The primer's version, Design a web crawler, also builds what a search engine needs from those pages.

Use cases (from the primer)

• The service crawls a list of URLs, generating a reverse index of words to pages and static titles and snippets for each page.
• A user enters a search term and sees relevant pages with their titles and snippets. The primer only sketches this part.
• The service has high availability.

Out of scope: search analytics, personalized results and page rank.

Assumptions (from the primer)

• Traffic is uneven: some searches are very popular, others run once.
• Generating search results should be fast.
• The crawler must not get stuck in an infinite loop, which happens when the link graph contains a cycle.
• 1 billion links to crawl. Pages are re-crawled about once a week, popular sites more often: 4 billion crawls a month.
• 500 KB stored per page on average, counting changed pages as new.
• 100 billion searches a month.

The primer also asks you to design this from traditional components rather than reuse an existing search system such as Solr or Nutch.

---

Back-of-the-envelope estimates

With the primer's conversion (400 requests per second ≈ 1 billion a month):

Bandwidth matters as much as storage. At 1,600 pages per second, 500 KB each is 800 MB/s, or about 6.4 Gbit/s of downloads. The primer warns that crawling "is bandwidth intensive".

For a sense of scale, Najork and Heydon's Mercator crawler downloaded about 50 million documents a day in 2001: about 580 per second, from four machines on a 160 Mbit/s connection.

---

The parts of a crawler

Najork and Heydon describe the components every crawler needs:

• a URL frontier that stores the URLs still to download (lesson 2);
• a component that resolves host names into IP addresses (lesson 4);
• a component that downloads documents over HTTP;
• a link extractor for HTML;
• a check for whether a URL has been seen before (lesson 3).

The primer's Crawler Service runs this loop:

1. Take the highest-ranked link from links_to_crawl.
2. Look in crawled_links for a page with a similar signature. If one exists, lower this link's priority (this is what breaks cycles) and continue.
3. Otherwise crawl it. Queue a job for the Reverse Index Service and one for the Document Service (title and snippet). Compute the page signature, remove the link from links_to_crawl, and record the link and signature in crawled_links.

The primer keeps both tables in a key-value NoSQL database, with a Redis sorted set holding the ranked links to crawl.

Being polite and obeying robots.txt

The primer suggests honoring robots.txt. RFC 9309, the Robots Exclusion Protocol, says crawlers may cache a site's robots.txt but "SHOULD NOT use the cached version for more than 24 hours". Politeness also means not overloading any one server, which is the frontier's job (lesson 2).