The primer’s use cases and estimates: 4 billion crawls and 100 billion searches a month, 1,600 pages per second, 2 PB a month, and the crawl loop.
What you will learn
State the web crawler's use cases and assumptions as the primer does.
Estimate its crawl rate, search rate, storage and bandwidth.
Name the parts every crawler needs, and follow the primer's crawl loop.
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 an inverted index of words to pages (the primer calls it a reverse index) 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 PageRank.
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):
4×400=1,600 pages crawled per second
100×400=40,000 searches per second
500 KB×4×109=2 PB of page content per month,72 PB in 3 years
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 (6.4 billion bits a second) 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 sharing 160 Mbit/s (160 million bits a second) of bandwidth.
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:
Take the highest-ranked link from links_to_crawl.
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.
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-valueNoSQLdatabase, with a Redissorted set holding the ranked links to crawl.
Being polite and obeying robots.txt
The primer suggests honoring robots.txt, the file in which a site lists the paths crawlers may not visit. RFC 9309, the Robots Exclusion Protocol, says crawlers may cache a site's robots.txt, but should not use a cached copy for more than 24 hours. Politeness also means not overloading any one server, which is the frontier's job (lesson 2).
Crawler service3× instancesLinks to crawl(ranked)2× instancesDNS cache2× instancesWebsites1× instanceCrawled links andsignatures2× instancesObject store (pages)1× instanceMessage queue (jobs)2× instancesReverse index service3× instancesDocument service3× instancesCrawler service3× instancesLinks to crawl(ranked)2× instancesDNS cache2× instancesWebsites1× instanceCrawled links andsignatures2× instancesObject store (pages)1× instanceMessage queue (jobs)2× instancesReverse index service3× instancesDocument service3× instances
Figure 1
The primer’s crawler at 1,600 pages a second: the crawler service takes the highest-ranked link, downloads the page, records it, and queues jobs for the services that index it.
Follow one link. The crawler service takes the highest-ranked link from the links to crawl, resolves its host name, and looks in the crawled links for a page with a similar signature; if there is one, it lowers the link’s priority and moves on. Otherwise it downloads the page from its website, stores it, puts a job for the reverse index service and one for the document service on the message queue, and records the link and the page’s signature in the crawled links. The three services are counted at about 1,000 a second per server, the lab’s figure, plus one spare: 1,600 pages a second needs three. The links to crawl, the DNS cache, the crawled links and the queue each need one node at the lab’s figures (12,000 a second per cache node, 4,000 per NoSQL node, 10,000 per queue node), plus a spare.
Crawler service: 3 × App server
Links to crawl (ranked): 2 × Cache
DNS cache: 2 × Cache
Websites: 1 × Users
Crawled links and signatures: 2 × NoSQL store
Object store (pages): 1 × Object store
Message queue (jobs): 2 × Queue
Reverse index service: 3 × App server
Document service: 3 × App server
Crawler service sends requests to Links to crawl (ranked)
Crawler service sends requests to DNS cache
Crawler service sends requests to Websites
Crawler service sends requests to Crawled links and signatures
Crawler service sends requests to Object store (pages)
Crawler service sends requests to Message queue (jobs)
Message queue (jobs) sends requests to Reverse index service
Message queue (jobs) sends requests to Document service
Key takeaways
4 billion crawls a month is about 1,600 pages a second; at 500 KB a page that is 2 PB a month and about 6.4 Gbit/s of downloads.
A crawler needs a URL frontier, a DNS resolver, a downloader, a link extractor and a check for URLs and content already seen.
The primer breaks cycles by lowering the priority of a link whose page signature matches one already crawled.
Be polite: honor robots.txt (cached for at most 24 hours) and do not overload any server.