Course contentsShow
← System Design
Lesson 1853 of 1,91944. Real-World System: Web CrawlerFree lesson

Bloom Filters for URL Seen Checking

Apply probabilistic Bloom filters to quickly check if a URL has been crawled with minimal memory overhead.

Bloom Filters for URL Seen Checking

What you'll learn: How to use Bloom filters to detect already-crawled URLs with minimal memory, accepting occasional false positives for massive space savings.

The Memory Problem with URL Deduplication

In a web crawler processing billions of URLs, tracking every seen URL in a hash set becomes prohibitively expensive. If each URL averages 100 bytes and you've crawled 10 billion pages, that's ~1TB just for URL storage. You need a space-efficient way to answer "Have I seen this URL before?"

What is a Bloom Filter?

A Bloom filter is a probabilistic data structure that tells you:

  • "Definitely NOT seen" (100% accurate)
  • "Probably seen" (might be a false positive)

It uses multiple hash functions to set bits in a fixed-size bit array. When checking a URL, if all corresponding bits are set, it's "probably seen." If any bit is unset, it's definitely new.

Analogy: Think of it like checking multiple "stamps" on a passport. If even one stamp is missing, the person hasn't visited. If all stamps are present, they probably have—but stamps could coincidentally match another traveler.

Memory Savings in Practice

With just 10 bits per element and 7 hash functions, you achieve ~1% false positive rate. For 10 billion URLs, that's only 11.7GB instead of 1TB—a 99% memory reduction. The tradeoff? Occasionally re-crawling ~1% of pages (false positives say "seen" when they're new).

Integration with Content Fingerprinting

Bloom filters work alongside content fingerprinting: use the Bloom filter for fast checking, then verify true duplicates with content hashing if needed. The filter acts as a first-pass guard before expensive database lookups.

Key Takeaway: Bloom filters provide space-efficient URL deduplication for web crawlers by trading perfect accuracy for massive memory savings, making them ideal when occasional false positives are acceptable compared to the cost of tracking billions of exact URLs.