Chapter 11 checkpoint

Chapter 11 checkpoint: a web crawler

Every question from this chapter’s lessons. Your first answer to each is the one that counts; afterward you can practice again as often as you like. Passing needs 75% right on the first attempt.

0 of 18 answered0 right on the first attempt

Question 1 of 18

The primer’s crawler makes 4 billion crawls a month. Using 400 requests per second ≈ 1 billion a month, how many pages does it crawl per second?

Your answerpages/s

Answers within 5% count.

Question 2 of 18

At 4 billion crawls a month and 500 KB stored per page, how much page content is stored per month, in PB?

Your answer

Answers within 5% count, in any unit you choose.

Question 3 of 18

At 1,600 pages per second and 500 KB per page, how much download bandwidth does the crawler need, in Gbit/s?

Your answer

Answers within 5% count, in any unit you choose.

Question 4 of 18

Put the steps of the primer’s crawler loop in order, for a page that turns out to be new.

Crawl the page
Take the highest-ranked link from links_to_crawl
Look in crawled_links for a page with a similar signature
Queue indexing jobs, remove the link from links_to_crawl and record it with its signature in crawled_links

Question 5 of 18

How long does RFC 9309 say a crawler should, at most, keep using a cached copy of a site’s robots.txt?

It must fetch robots.txt before every requestIndefinitely, until the site changes itOne week, matching the re-crawl period24 hours

Question 6 of 18

Why does Mercator’s frontier have front queues and back queues?

Front queues are in memory and back queues on diskFront queues handle priority; back queues, one host each, handle politenessBack queues remove duplicate URLsFront queues hold fast hosts and back queues slow ones

Question 7 of 18

Mercator waits 10 times as long as a download took before contacting the same host again. A page from a host took 2 seconds to download. How long until the crawler may contact that host again?

Your answer

Answers within 2% count, in any unit you choose.

Question 8 of 18

A crawler never lets two threads contact the same server at once, yet site administrators still complain about it. Why?

The crawler is ignoring robots.txtOne thread can still send that server request after request with no pauseThe crawler downloads duplicate URLsDNS lookups are overloading the server

Question 9 of 18

A distributed crawler assigns each host to one crawling process by hashing the host name. What is the better way to hash, if processes will be added and removed?

Consistent hashing, so only about 1/N of hosts move when N changesAssign URLs to processes at randomSplit hosts alphabeticallyhash(host) mod N

Question 10 of 18

Why use SimHash rather than a cryptographic hash such as SHA-256 to find near-duplicate pages?

SimHash is faster to computeSimHash is more secureSimilar pages get fingerprints that differ in only a few bitsSHA-256 cannot hash web pages

Question 11 of 18

A Bloom filter must hold 1 billion URLs with a 0.1% false-positive rate. Using

m = -\frac{n \ln p}{(\ln 2)^2}

bits, about how much memory does it need, in decimal GB (

10^9

bytes)?

Your answer

Answers within 5% count, in any unit you choose.

Question 12 of 18

To find 64-bit fingerprints within 3 bits of a new one, the bits are split into 4 equal blocks so that at least one block must match exactly. How many bits is each block?

Your answerbits

Answers within 1% count.

Question 13 of 18

A table of

2^{34}

fingerprints is keyed on 16 bits. About how many candidates does one lookup return?

Your answercandidates

Answers within 5% count.

Question 14 of 18

A crawler uses a Bloom filter for “seen this URL before?”. Some brand-new pages are never crawled. Why?

False positives: the filter wrongly says “seen” for a small share of new URLsFalse negatives: it forgot URLs it had seenThe filter rejects new items once fullrobots.txt blocks them

Question 15 of 18

Mercator’s threads spent 70% of their time on DNS lookups. What fixed it?

Ignoring TTLs and caching answers foreverUsing IP addresses instead of host names in the seed listMore crawling threadsA multi-threaded resolver of their own, so many lookups run in parallel

Question 16 of 18

A site’s calendar has a “next month” link on every page, forever. How do you stop the crawler following it endlessly?

Rely on page signatures to detect the loopCache the site’s DNS answer longerA bigger Bloom filterCap link depth or pages per host per crawl cycle

Question 17 of 18

How do crawlers usually store billions of downloaded pages?

One object per page in an object storeAppended to large WARC archive files of about 1 GB eachOne row per page in a relational databaseOnly in memory, re-crawled when needed

Question 18 of 18

Some pages change every hour and others once a year. How should the crawler schedule re-crawls?

Estimate how often each page changes and re-crawl it at about that rateNever re-crawl; pages are stored onceRe-crawl random pages each dayRe-crawl every page once a day