Crawler Dedup Frontier Lab (Interactive)
Balance politeness, workers, and Bloom-filter false positives against RAM and lost pages. Compute pages/sec from worker and politeness math while sizing a URL-dedup Bloom filter and counting wasted false dedups.
Distributed Crawler: Frontier Politeness vs Bloom-Filter Dedup
Trade crawl throughput against per-domain delay, and size the Bloom filter that deduplicates billions of seen URLs in RAM.
› Per-domain queues enforce the delay AND robots.txt compliance; priority = PageRank + freshness so high-value pages crawl first.
› Strong dedup (exact seen-set) rejects re-crawls; SimHash 64-bit fingerprints catch near-duplicate content served at different URLs.
› Spider traps (infinite calendar/honeypot URLs) are capped by path-depth limits and crawl-delay backoff on 429/503 responses.
The Bloom filter is the scaling trick: 5 billion seen URLs at a 1% FP rate cost ~5.7 GB of RAM instead of a 300+ GB exact hash set. False positives mean occasionally skipping a never-crawled page (acceptable); false negatives never happen. DNS resolution and robots.txt fetches are cached aggressively — otherwise the crawler bottleneck flips from bandwidth to thousands of tiny network roundtrips.
How It Works Under the Hood
A crawler must be fast, courteous, and exact about not re-fetching. Throughput is bounded by politeness: with per-domain delay D, each worker fetches 1/(politeness + fetch) pages/sec, so more workers beat ignoring robots.txt. Frontier ordering is a priority queue of URLs, but the dedup check defines correctness — a Bloom filter sized by m = -n ln(p)/(ln2)^2 gives tiny per-URL RAM at the cost of false positives, and every false positive is a real page you will never crawl. Tune the target corpus and FP rate to see filter memory and lost pages explode.
Core Architectural Principles
- Pages/sec = workers / (politeness_delay + fetch_time) — courtesy, not raw workers, sets throughput.
- Bloom bits approximately equal -n ln(p)/(ln2)^2 per URL, converted to RAM for the whole corpus.
- False positives times pages/day equal genuinely-unique pages wrongly skipped forever.
Lead with politeness and robots.txt as first-class constraints — interviewers want to hear you will not DDoS a domain. Then present the dedup problem and justify a Bloom filter over an exact set by RAM math, acknowledging the false-positive risk and how to mitigate it with a secondary exact check or a larger filter. Discuss priority frontier ordering by PageRank or freshness.
A Bloom filter dedups at a fraction of the memory of an exact set but probabilistically drops a small share of unique URLs.