Distributed Deduplication with Bloom Filters
What you'll learn: How to use distributed Bloom filters to efficiently detect already-crawled URLs across multiple crawler worker nodes without centralizing all state.
The Challenge of Distributed Deduplication
When you have hundreds of crawler workers operating independently, each needs to know: "Have we already crawled this URL?" In a single-machine system, one Bloom filter suffices. But in a distributed setup, workers can't share a single in-memory filter—it becomes a bottleneck and single point of failure.
The Distributed Approach
The solution is partitioned Bloom filters: divide URL space across multiple Bloom filter instances, each stored on different machines (often using consistent hashing on the URL). When a worker encounters a URL:
- Hash the URL to determine which Bloom filter partition owns it
- Query that partition's filter (via RPC or cache lookup)
- If "possibly seen," perform a definitive check (like querying a database)
- If "definitely not seen," proceed with crawl and add to the filter
Optimization: Local Caching
Workers maintain a local Bloom filter cache of recently-seen URLs from their assigned hosts. This reduces cross-network checks for immediate re-crawls within the same domain. The local filter acts as a first-line defense before consulting the distributed partition.
Handling False Positives
Bloom filters can say "maybe seen" (false positive) but never "not seen when actually seen." In distributed crawling, false positives mean occasional redundant crawls—acceptable given the massive space savings compared to storing every URL explicitly.
Key Takeaway:
Distributed Bloom filters shard URL deduplication across nodes using consistent hashing, with local worker-level filters providing fast first-pass checks and remote partitions serving as the authoritative distributed state.