Bloom Filters for Web Crawling: Sizing, Failure Modes

A Bloom filter lets a crawler answer "have I seen this URL?" in constant time using a small, fixed amount of memory. It never forgets a URL it has seen. It will occasionally claim to have seen one it hasn't, and in a crawler that error means a page silently never gets fetched. This guide covers how the structure works, how to size it, where it breaks, and what it can't do.

Gyrence

Build Crawlers With Clear Failure Modes

Gyrence’s web data API returns typed responses, including failures, for crawling and extracting structured data from the open web.

Explore the web data API

TL;DR

A Bloom filter says "definitely not seen" or "probably seen". It has no false negatives, but it has false positives.
Size it from two inputs: expected URL count n and target false-positive rate p. About 9.6 bits per URL gets you 1%.
A false positive means a new URL never enters the frontier. Pair the filter with an exact store if coverage matters.
Canonicalize URLs before hashing, or different spellings of one page defeat the filter.
A Bloom filter dedupes URLs, not content, and it says nothing about freshness or politeness.

How a Bloom filter works inside a crawler
Sizing the filter: n, p, m, and k
The failure mode: a skipped URL is a lost page
Canonicalize before you hash
Bloom plus an exact store
Many workers, one shared state
What a Bloom filter does not do
Where this fits in an agent or RAG pipeline
Our perspective
Run it on Gyrence
FAQ
Sources

How a Bloom filter works inside a crawler

A Bloom filter is a bit array plus several hash functions. It is a space-efficient probabilistic structure for set membership: it answers "definitely not in the set" or "possibly in the set" and never stores the items themselves.

The crawler loop looks like this:

Take a discovered URL and hash it to k bit positions.
If any of those bits is 0, the URL is definitely new. Set all k bits and queue the URL.
If all k bits are 1, the URL is only probably already seen. Skip it.

Because an inserted URL sets every bit a later lookup will test, the filter cannot return a false negative in normal use. The error runs one way only: unseen URLs can look seen.

The appeal is memory and I/O. The filter is more space-efficient than a set and avoids heavy database load for URL membership checks, which is why it shows up in nearly every large-crawler design.

Sizing the filter: n, p, m, and k

Pick n, the number of URLs you expect to insert, and p, the false-positive rate you can tolerate. The standard equations give the bit count m = -n ln(p) / (ln 2)^2 and the hash count k = (m/n) ln 2, as implemented in the open-source spire-core crate.

At a 1% target, that works out to about 9.6 bits per expected URL and roughly seven hashes. At 0.1%, it is about 14.4 bits per URL and roughly ten hashes. One design write-up puts 1 billion URLs at 1% at about 1.2 GB.

Applying those per-URL figures to a 100 million URL crawl (our arithmetic, not a benchmark):

Target `p`	Bits per URL	Hashes `k`	Memory for 100M URLs
1%	9.6	~7	~120 MB
0.1%	14.4	~10	~180 MB

Two habits save pain later:

Overestimate n. The real rate climbs when you insert more than the filter was sized for. One implementation guide reports that a filter sized for 10 million URLs and loaded with 20 million can reach roughly 14%.
Watch for overflow. Track the insert count against capacity and alert on it. The spire-core filter warns once when inserts exceed expected capacity and can report an estimated false-positive rate.

The failure mode: a skipped URL is a lost page

In a crawler, a false positive rejects a genuinely new URL before it reaches the frontier, so it is never downloaded. The Mercator crawler paper names this as the principal disadvantage of the Bloom filter for the URL-seen test, and notes the chance shrinks as you enlarge the bit vector.

How much error is acceptable depends on the crawl:

Nightly discovery crawl: p = 0.01 can be defensible, because skipped URLs may be reoffered on a later run.
One-shot archival crawl: use p = 0.0001, since there may be no second pass.
Compliance or financial research: if you need to show a source was or wasn't collected, a probabilistic gate alone is the wrong tool. Use the exact-store pattern below.

Canonicalize before you hash

The filter compares hashes of strings. HTTP://Example.com/a#top and http://example.com/a are the same page to a browser and two different entries to the filter. Normalize first: lowercase the scheme and host, strip fragments, and remove tracking parameters where appropriate. Crawler design guides list these steps as a prerequisite for deduplication.

When you are unsure whether a page declares a different canonical address than the one you crawled, a canonical tag checker shows what the page declares. For the rules we apply when canonical URLs disagree with the fetched address, see our five validation steps for canonical URLs. For the broader bandwidth case, see our write-up on URL deduplication in crawling.

Bloom plus an exact store

The common production answer is to stop treating the filter as the source of truth. Use it as a cheap gate: when it says "definitely new", queue the URL with no further lookup. When it says "possibly seen", check a durable exact URL store. This design eliminates false-positive skips while avoiding an exact lookup for every URL, because most lookups on a mature crawl hit the cheap path.

Bloom filter gate with exact URL lookup

If your constraints allow a margin of error, the filter can stand alone. If they don't, combine it with a hash table. The cost of the exact store is storage and I/O, which is the trade-off the Mercator paper describes.

Many workers, one shared state

A single in-memory filter stops working the moment you add a second crawler process. Three things matter at that point:

Shared state. All workers must see the same deduplication state. Redis BF.ADD is atomic for concurrent requests, so two workers can't both claim the same new URL.
Partitioning. One design splits a Redis-backed filter across 16 keys so no single key becomes a bottleneck.
Growth. At very large scale, a scalable Bloom filter chains additional filters as earlier ones saturate, and sharding spreads the memory and request load.

Two more details. A standard filter does not support deletion; counting Bloom filters or Cuckoo filters do, at extra memory or complexity. And checkpoint your shards: if one is lost, the affected URL range may be re-crawled, which wastes work but doesn't break the crawl.

If you shard the frontier by host, one worker owns all URLs for a hostname and can enforce that host's rate limits without cross-node coordination. Our notes on polite crawling defaults cover what those limits should be.

What a Bloom filter does not do

It answers one question: has this address been queued or visited? Everything else needs its own mechanism:

Content duplicates. Identical or near-identical pages at different URLs need content hashes or similarity hashes, not a URL filter.
Freshness. A URL marked "seen" is seen forever. Recrawl scheduling is a separate problem; see priority URL scheduling.
Traceability. The filter keeps no record of when or why a URL was fetched. If you need source-traceable data, log the URL, fetch time, status, and content hash in a store you can query.
Loops. Pagination and calendar traps generate endless unique URLs that pass the filter every time. We wrote up one case in how we stopped an AI agent looping on Wikipedia pagination.

Where this fits in an agent or RAG pipeline

In a pipeline that fetches pages, converts them to markdown, extracts JSON, and feeds a vector store, the Bloom filter sits at the front. It decides what gets fetched. Everything after it is where the quality problems appear. A few checks worth making:

Failure handling. A fetch that returns a block page or a timeout should never be stored as data and then marked "seen". Insert into the filter only after a successful fetch, or you will skip the retry. We cover this in why fetches should fail loudly.
Typed results. Gyrence returns a typed, discriminated-union response for every call, failures included, so your code can branch on the outcome instead of parsing a 200 that contains an error page.
Cost per call. Dedup saves fetches, and fetches are what you pay for. Gyrence bills per credit with spending caps, and has no separate AI extraction charge.

Our perspective

Most crawl bugs we see are not in the fetcher. They are in the bookkeeping around it: a URL marked seen before the fetch succeeded, a filter sized for a million URLs holding ten, a block page stored as content.

A Bloom filter is a good tool with one honest limit: it can lie in one direction. We think a crawler should say so in its design. Gate with the filter, confirm with an exact record, and make every outcome, including failure, a typed value your agent can reason about.

That is the idea behind Gyrence's primitives. Search, Traverse, Fetch, Extract, and Map each return a result you can branch on, and spending caps keep a runaway crawl from becoming a surprise bill.

Glen

Run it on Gyrence

If you would rather not build the frontier, the dedup state, and the failure handling yourself, Gyrence's Traverse and Map primitives crawl from a starting URL or a domain's URL graph, and the hosted MCP endpoint connects them to your agent. The Standard plan is $75 per month, and the pricing page lists the free, founders, and pay-as-you-go options.

To watch pages for change after the first crawl, WebDoppler handles monitoring with webhook alerts.

FAQ

Can a Bloom filter give false negatives in a crawler?

Not in normal use. An inserted URL sets every bit a later lookup tests, so a seen URL is always reported as possibly seen. The error you must plan for is the opposite: a new URL reported as seen.

How big should the filter be for 100 million URLs?

At a 1% false-positive rate, about 9.6 bits per URL, so roughly 120 MB with about seven hashes. At 0.1% it is about 180 MB with about ten. Size for more URLs than you expect, because the rate rises once you exceed capacity.

Can I delete a URL from a Bloom filter so it gets recrawled?

Not from a standard one. Counting Bloom filters and Cuckoo filters support deletion at extra memory or complexity cost. Many crawlers instead rebuild the filter on a schedule or use a separate recrawl queue.

Is a Bloom filter enough for content deduplication?

No. It tracks URL strings only. Pages that are identical or nearly identical under different URLs need content hashes or similarity hashes.