Design a web crawler
A billion pages a month from a million hosts, and never more than one fetch a second to any of them. Fetching is the easy part. The round turns on the frontier, which releases a host only when its clock allows, and on a seen set that remembers ten billion URLs.
The round this design follows
How many machines does a crawler of a billion pages a month need?
Fewer than most people guess. A billion pages a month is 386 fetches a second, and at about a second a fetch that is 386 fetches open at once. With 200 open fetches a box and room for one box to die, that is 4 boxes, and the downloads are 38.6 MB/s, 3.09 percent of one 10 Gbit/s card. So say early that throughput does not decide this design: politeness and the seen set do.
How does a crawler stay polite to every host?
It keeps one queue of URLs per host and a heap of hosts ordered by the time each may next be fetched. A fetcher only gets a URL from the host at the top of the heap, and only once that time has passed; the host then goes back into the heap with its time moved on by its crawl delay. Hosts are sharded across nodes by a hash of the host name, so one node owns each host's queue and clock and no two nodes ever race on a host. A slow host gets a longer delay, ten times its last response.
How do you remember ten billion URLs without running out of memory?
Keep an 8-byte fingerprint of each normalised URL, 80 GB in all, in an LSM store on SSD, and a bloom filter of 10 bits a URL in memory, 12.5 GB for the whole crawl or 3.12 GB on each of four nodes. The filter's "never seen" is certain, so a new URL costs no disk read. Its "maybe seen" is wrong 0.82 percent of the time, so it is checked against the LSM, and no new URL is ever dropped by mistake.
What do you do about a site with ten million pages?
At one fetch a second it takes 115.7 days, longer than the month, and more machines do not help, because politeness limits the rate per host, not per crawler. Give every host a budget of what its rate allows in a month, 2.59 million pages, and spend it on the site's best URLs by priority. Read its sitemap and send conditional requests so each fetch counts, and let the other 7.41 million pages wait a cycle.
What happens when a crawler machine dies?
The frontier leases each URL to a fetcher, so when a fetch box dies its leases run out and its URLs go back to their hosts' queues for another box to fetch. A page fetched twice is stored once, because pages are stored under the hash of their bytes, and its links are dropped the second time by the seen set. With the fetch fleet sized at twice the average rate, the three boxes left carry the crawl and nothing waits.