Lesson 11.4• 9 min read

Fetching, DNS caching and fault tolerance

DNS as a bottleneck, connection pooling, freshness, spider traps, WARC files and recovering from failures.

What you will learn

  • Remove DNS as a crawler bottleneck.
  • Fetch efficiently, keep pages fresh and avoid spider traps.
  • Store pages in WARC files, and recover from a crawler machine failing.

DNS is a bottleneck

Every download starts with a host-name lookup. Najork and Heydon found that the standard Unix resolver (gethostbyname) was synchronized, so "only one DNS request per address space on an uncached name could be outstanding at once": one lookup at a time per process. That caused "a severe bottleneck".

Their fix was a multi-threaded resolver of their own that forwards requests to a local name server and lets many lookups run in parallel. Before the change, DNS lookups took 70% of each thread's elapsed time; afterward, 14%.

The primer gives the same advice: "the Crawler Service can keep its own DNS lookup that is refreshed periodically". Cache each answer for the record's own TTL, and partition the cache with the hosts (lesson 2).


Fetching efficiently

The primer suggests:

  • Connection pooling: keep many connections open at a time, which "can improve performance and reduce memory usage".
  • Enough bandwidth: at the primer's 1,600 pages per second, about 6.4 Gbit/s (lesson 1).
  • Sharding and federation for the Reverse Index Service and Document Service, given the data size and request load.
  • A memory cache for popular searches, which also absorbs uneven traffic and spikes.

Freshness

Pages change, so the crawl never ends. The primer keeps a timestamp per crawled page and refreshes every page after a default period, such as a week, and popular or frequently updated sites more often. With some data mining, you can estimate how often a page changes and re-crawl it at that rate. Mercator's continuous crawling puts a downloaded URL back in the frontier with a priority based on its download history.


Spider traps and cycles

The primer's loop breaks cycles by lowering the priority of a link whose page signature matches one already crawled. Some sites are spider traps: they generate unlimited distinct URLs, such as calendars with a "next month" link forever or repeating path segments. Common defenses, each a policy you tune:

  • a maximum link depth from the seed URLs;
  • rejecting URLs whose path repeats the same segments;
  • a cap on pages per host per crawl cycle;
  • checking Content-Type and Content-Length before downloading a body.

Storing pages: WARC files

Writing billions of separate small objects is slow and expensive. Crawlers append pages to large archive files instead. The WARC format, whose specification the IIPC publishes, records each response with its metadata. It recommends "1 GB (10⁹ bytes) as a practical target size for WARC files".


When a crawler machine fails

Mercator checkpoints the crawl: a background thread writes the crawler's state to stable storage on a schedule (1 to 4 times a day), and after a failure the crawler reads the last checkpoint and resumes from there, losing only the work done since. Distributed crawlers also need to detect dead workers and hand their hosts to another process. A host's URLs live with its frontier, so moving the frontier partition moves its work too.

A URL fetched twice because of a crash produces a duplicate page. The content signature check (lesson 3) catches it before it is indexed again.

A distributed crawler pipeline

Follow one URL through the eight stages: the frontier queue, DNS cache, politeness check, fetch, SimHash deduplication, object storage, link extraction and back to the frontier.

Target: https://en.wikipedia.org/wiki/Raft_(algorithm)
  1. 1. Frontier
  2. 2. DNS cache
  3. 3. robots.txt
  4. 4. HTTP fetch
  5. 5. SimHash
  6. 6. Object store
  7. 7. Link extractor
  8. 8. Bloom filter

Pick a URL, then run a crawl cycle.

Pages saved0
Object storage0 MB
SimHash drops0
Robots blocked0
Ready. Pick a URL and run a crawl cycle.
Fetchers3× instancesDNS cache2× instancesrobots.txt cache2× instancesWebsites1× instanceObject store (WARCfiles)1× instanceCrawl records2× instancesFetchers3× instancesDNS cache2× instancesrobots.txt cache2× instancesWebsites1× instanceObject store (WARCfiles)1× instanceCrawl records2× instancesFetchers3× instancesDNS cache2× instancesrobots.txt cache2× instancesWebsites1× instanceObject store (WARCfiles)1× instanceCrawl records2× instances
Figure 4

Fetching a page: a DNS cache and a robots.txt cache before the download, the page appended to a WARC file, and its crawl time kept for re-crawling.

Follow one fetch. The fetcher resolves the host name from its own DNS cache, asking a name server only for a name it has not cached, and checks the site’s robots.txt from its cache, fetching the file again once its copy is 24 hours old. If the path is allowed, it downloads the page over one of its pooled connections, appends the page to the current WARC file in the object store, and records when it crawled the page, so the page is crawled again after the default period. The fetchers are counted for the primer’s 1,600 pages a second at about 1,000 a second per server, plus one spare; the two caches and the crawl records are one node each at the lab’s figures, plus a spare.

  • Fetchers: 3 × App server
  • DNS cache: 2 × Cache
  • robots.txt cache: 2 × Cache
  • Websites: 1 × Users
  • Object store (WARC files): 1 × Object store
  • Crawl records: 2 × NoSQL store
  • Fetchers sends requests to DNS cache
  • Fetchers sends requests to robots.txt cache
  • Fetchers sends requests to Websites
  • Fetchers sends requests to Object store (WARC files)
  • Fetchers sends requests to Crawl records

Key takeaways

  • A synchronized resolver allowed one lookup at a time; Mercator's parallel resolver cut DNS from 70% of each thread's time to 14%. Cache answers for their TTL.
  • Pool connections, budget the bandwidth, re-crawl on a schedule (popular sites more often), and cap depth and pages per host to escape traps.
  • Append pages to large WARC archives rather than writing billions of small objects.
  • Checkpoint the crawl and hand a dead worker's hosts to another; a page fetched twice is caught by the content signature.
Sources4