CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 6 of 7 · 3 min read

Problem content

Duplicates, traps and noise.

Problem content, sizes and trade-offs

Redundant content. About 30 per cent of pages are copies. Hashes or checksums catch them.

Spider traps. A spider trap is a page structure that sends a crawler into an endless loop, such as a folder tree that repeats /foo/bar/foo/bar/… without end. A maximum URL length helps. No single rule finds all traps. A site that suddenly yields an unusually large number of pages is a suspect. A person can check it and either exclude the site or add a custom filter.

Data noise. Advertisements, code snippets and spam pages have little value. Filter them out when possible, with an anti-spam step, to save storage and crawl time.

Sizes for the seen-checks (made up, checked by script). Over 5 years at 1 billion pages per month, the crawler meets about 60 billion pages.

  • A Bloom filter with about 10 bits per URL has roughly a 1 per cent false positive rate. 60 billion × 10 bits = 600 billion bits, which is 75 GB. That fits in the memory of a few machines.
  • A false positive here means a new URL is mistaken for a seen one and skipped. At 1 per cent, a few pages are never fetched, which is acceptable for a search crawl but not for an archive that must be complete.
  • A content hash table of 16-byte hashes for 60 billion pages needs 60,000,000,000 × 16 bytes = 960 GB, so it needs sharding by hash.

Extra points the book lists for the wrap-up.

  • Pages that build their links with scripts need to be rendered first, or the links are not seen.
  • A spam filter keeps low-quality pages out.
  • Database replication and sharding for the data layer.
  • Servers kept stateless so they can scale out, to hundreds or thousands.
  • Analytics to tune the system.

Common mistake

Using one big queue of URLs. Crawler threads then hammer a single site with many requests at once, and the site blocks the crawler or goes down. Keep one queue per host and a delay between requests.

Interview angle

Answer in your head first, then open it.

What are the components?

Seeds, frontier, downloader, DNS, parser, content-seen check, storage, extractor, filter, URL-seen check.

How do you stay polite?

One queue and one worker per host, with a delay, and obey robots.txt.

BFS or DFS?

BFS with a queue. DFS can go very deep.

How do you avoid duplicates?

A hash of the content and a Bloom filter or table of URLs.

How do you handle traps?

A URL length cap, a limit on pages per site, and manual blocking after review.

One follow-up to try. "Crawl pages that need JavaScript to show their links." A reply: render the page first in a headless browser, which is far slower, so use it only for sites flagged as needing it, and give those their own smaller, separate downloader pool. Say that rendering costs perhaps 10 to 100 times more per page, so it changes the capacity maths.

Check yourself: 1. What is a spider trap and how can it be limited? 2. What does a Bloom filter false positive cost the crawler? 3. Why use a separate downloader pool for rendered pages?

Words you will meet

Word Meaning
Seed URL A starting address for the crawl
URL frontier The queue structure of URLs still to fetch
Politeness Limiting requests to one site
robots.txt A site's file that says what crawlers may fetch
Spider trap A page structure that makes a crawler loop forever
Bloom filter A compact set check with rare false "yes" answers
Re-crawl Fetching a page again to catch changes