Deduplicating URLs with Bloom Filters

A crawler has to answer "have I seen this URL?" for every link it extracts, and this page — part of Caching and Incremental Crawling — is about what to do when the obvious answer, a Python set, no longer fits in memory.

A Bloom filter replaces exact membership with a probabilistic test backed by a bit array. It never produces a false negative — if it says a URL is new, the URL is definitely new — but it can produce a false positive, claiming a URL has been seen when it has not. For a crawler a false positive costs one silently skipped page, which is why you size the filter conservatively and why the structure is only worth reaching for once a set genuinely hurts.

Why a Set Stops Scaling

A set of strings stores a full Python object per element. On CPython 3.12 a 60-character URL is a str of roughly 109 bytes, plus 8 bytes for the pointer in the set's table, plus the set's load-factor headroom of about 60 per cent. Ten million URLs therefore land somewhere around 1.2 GB of resident memory, and the number grows with the average URL length.

Hashing each URL to a 16-byte digest before inserting it helps but does not fix the problem: you still have ten million Python objects and the set's own table, so you land near 800 MB. The structural fix is to stop storing one object per URL at all. A Bloom filter's memory is a function of the count and the tolerated error rate, not of the length of what you put in it.

Sizing: From n and p to Bits

Two parameters determine everything. n is the number of items you expect to insert; p is the false-positive probability you will accept once n items are in. The optimal bit-array size and hash count follow directly:

m = -(n * ln p) / (ln 2)^2        bits
k = (m / n) * ln 2                hash functions

At p = 0.01 that works out to 9.585 bits per item and k = 7; at p = 0.001 it is 14.38 bits and k = 10. Tightening the error rate by a factor of ten therefore costs about five extra bits per URL, which is cheap — this is the property that makes the structure worth using.

import math


def bloom_size(n: int, p: float) -> tuple[int, int, float]:
    """Return (bits, hash_count, megabytes) for n items at error rate p."""
    m = math.ceil(-(n * math.log(p)) / (math.log(2) ** 2))
    k = max(1, round((m / n) * math.log(2)))
    return m, k, m / 8 / 1024 / 1024


def actual_error(m: int, k: int, n: int) -> float:
    """False-positive rate once n items are in an m-bit filter with k hashes."""
    return (1 - math.exp(-k * n / m)) ** k


if __name__ == "__main__":
    for expected, error in [(1_000_000, 0.01), (10_000_000, 0.01), (10_000_000, 0.001)]:
        bits, hashes, mb = bloom_size(expected, error)
        print(f"n={expected:>10,}  p={error:<6}  {mb:6.1f} MB  k={hashes}")

    bits, hashes, _ = bloom_size(10_000_000, 0.01)
    for inserted in (10_000_000, 15_000_000, 20_000_000):
        print(f"inserted={inserted:>10,}  actual p={actual_error(bits, hashes, inserted):.4f}")

The second loop is the important one. A filter sized for ten million items and used for twenty million does not fail loudly — its error rate climbs from 1 per cent to about 14 per cent, and the crawler starts skipping roughly one in seven new URLs without a single exception being raised. Overestimate n by a factor of two to three at construction time; the memory cost of being wrong in that direction is a few megabytes, while the cost of being wrong in the other direction is missing data you will not notice.

Choose p from what a miss costs. For a discovery crawl that will run nightly, p = 0.01 is defensible because a URL skipped tonight is likely to be re-offered tomorrow from a different page. For a one-shot archival crawl where a missed page is lost permanently, use p = 0.0001 and pay the 20 bits per URL.

Canonicalise Before You Hash

A Bloom filter compares bytes. https://Example.com/a?b=1&a=2 and https://example.com/a?a=2&b=1 are the same page and different byte strings, so without normalisation the filter dutifully reports both as new and you crawl the page twice — the failure the filter was supposed to prevent.

from urllib.parse import parse_qsl, urlencode, urlsplit, urlunsplit

TRACKING_PREFIXES = ("utm_", "fbclid", "gclid", "mc_eid", "_ga")
DEFAULT_PORTS = {"http": "80", "https": "443"}


def canonicalise(url: str) -> str:
    parts = urlsplit(url.strip())
    scheme = parts.scheme.lower()
    host = parts.hostname.lower() if parts.hostname else ""
    if parts.port and str(parts.port) != DEFAULT_PORTS.get(scheme, ""):
        host = f"{host}:{parts.port}"

    query = [
        (key, value)
        for key, value in parse_qsl(parts.query, keep_blank_values=True)
        if not key.lower().startswith(TRACKING_PREFIXES)
    ]
    query.sort()

    path = parts.path or "/"
    while "//" in path:
        path = path.replace("//", "/")

    return urlunsplit((scheme, host, path, urlencode(query), ""))


if __name__ == "__main__":
    samples = [
        "HTTPS://Books.ToScrape.com:443/catalogue//page-2.html?utm_source=x&ref=nav#top",
        "https://books.toscrape.com/catalogue/page-2.html?ref=nav",
        "https://books.toscrape.com/catalogue/page-2.html?ref=nav&gclid=abc",
    ]
    for sample in samples:
        print(canonicalise(sample))

All three print the same string. Two judgement calls hide in there. Sorting query parameters is safe for the overwhelming majority of sites but wrong for the rare endpoint whose ordering is significant — check before enabling it against an API. And stripping tracking parameters assumes the server ignores them; if a ref parameter genuinely changes the rendered content, keep it, which is why ref is absent from the strip list above.

Trailing slashes are the other trap: /catalogue/ and /catalogue are formally different resources and most sites treat them as one. Normalising them together is usually right and occasionally causes a missed page, so decide per site rather than globally.

A Runnable Filter with pybloom-live

pybloom-live is the maintained fork of the original pybloom and gives you both a fixed-size filter and a scalable one that chains filters as it fills.

python -m pip install "pybloom-live>=4.0"

from pybloom_live import BloomFilter, ScalableBloomFilter

SEEN = BloomFilter(capacity=1_000_000, error_rate=0.001)
GROWING = ScalableBloomFilter(
    initial_capacity=100_000,
    error_rate=0.001,
    mode=ScalableBloomFilter.LARGE_SET_GROWTH,
)


def enqueue(url: str, seen: BloomFilter) -> bool:
    """Return True if the URL is new. `add` returns True when already present."""
    canonical = url.strip().lower()
    return not seen.add(canonical)


if __name__ == "__main__":
    urls = [
        "https://books.toscrape.com/catalogue/page-1.html",
        "https://books.toscrape.com/catalogue/page-2.html",
        "https://books.toscrape.com/catalogue/page-1.html",
    ]
    for url in urls:
        print("queued" if enqueue(url, SEEN) else "skipped", url)

    print("bits:", SEEN.num_bits, "hashes:", SEEN.num_slices)

    for url in urls:
        GROWING.add(url)
    print("filters in the chain:", len(GROWING.filters))

Note the inverted return value: BloomFilter.add returns True when the item was already present, so not seen.add(url) is the "this is new" test. Getting that backwards produces a crawler that fetches only duplicates, and because nothing raises, it looks like a crawl that finished suspiciously fast.

ScalableBloomFilter is the safer default when you cannot estimate n. It allocates a new, larger sub-filter each time the current one reaches capacity and queries all of them, so memory grows with actual usage and the compound error rate stays bounded by the configured value. The cost is that membership tests get slower as the chain grows, since each one touches every sub-filter. A fixed filter with a generous capacity is faster if you can bound the crawl.

To persist a filter across runs, BloomFilter.tofile(fp) and BloomFilter.fromfile(fp) write and read the raw bit array — a 10 million item filter at p = 0.001 is a 17 MB file, which loads in well under a second.

Sharing the Filter Across Workers

A per-process filter is useless in a distributed crawl: four workers each build their own view and each crawls the same URL. Redis solves it with server-side bit operations, so the filter lives in one place and every worker sees the same state.

import hashlib

import redis

BITS = 95_850_584   # sized for n = 10,000,000 at p = 0.01
HASHES = 7
KEY = "crawl:seen"


def positions(url: str, bits: int = BITS, k: int = HASHES) -> list[int]:
    """Derive k positions from one digest (Kirsch-Mitzenmacher double hashing)."""
    digest = hashlib.blake2b(url.encode("utf-8"), digest_size=16).digest()
    h1 = int.from_bytes(digest[:8], "big")
    h2 = int.from_bytes(digest[8:], "big") | 1
    return [(h1 + i * h2) % bits for i in range(k)]


def mark_seen(client: redis.Redis, url: str) -> bool:
    """Return True if the URL is new. One round trip via a pipeline."""
    offsets = positions(url)
    pipe = client.pipeline(transaction=False)
    for offset in offsets:
        pipe.setbit(KEY, offset, 1)
    previous = pipe.execute()
    return not all(previous)


if __name__ == "__main__":
    client = redis.Redis(host="127.0.0.1", port=6379, db=0)
    target = "https://books.toscrape.com/catalogue/page-1.html"
    print("first:", mark_seen(client, target))
    print("second:", mark_seen(client, target))

SETBIT returns the previous value of the bit, so a single pipelined pass both records the URL and tells you whether it was already there — no read-then-write race between workers. Redis allocates the string lazily, so a 95 million bit key occupies about 11.4 MB once populated and much less while sparse.

Two operational notes. Deriving k positions from one 128-bit digest with double hashing is standard practice and gives the same error rate as k independent hashes for realistic parameters, at a seventh of the CPU. And a Redis-backed filter is not resizable — if the crawl outgrows its n, you build a second key and query both, which is the same idea ScalableBloomFilter implements locally. The rest of the shared-state plumbing is covered in Distributed Crawling with Celery and Redis.

Scrapy Already Has One (Sort Of)

Scrapy ships RFPDupeFilter, which fingerprints each request — method, canonicalised URL, body, and any headers listed in Request.dont_filter handling — with SHA-1 and keeps the hex digests in an in-memory set, optionally persisted to requests.seen in the job directory. It is exact, so it never skips a page, but it is a set of 40-character strings and costs roughly 100 bytes per request. At ten million requests that is a gigabyte in the crawler process.

Replacing it is a matter of subclassing BaseDupeFilter and pointing DUPEFILTER_CLASS at your implementation:

from scrapy.dupefilters import BaseDupeFilter
from scrapy.utils.request import request_fingerprint
from pybloom_live import ScalableBloomFilter


class BloomDupeFilter(BaseDupeFilter):
    def __init__(self, error_rate: float = 0.0001) -> None:
        self.seen = ScalableBloomFilter(
            initial_capacity=1_000_000,
            error_rate=error_rate,
            mode=ScalableBloomFilter.LARGE_SET_GROWTH,
        )

    @classmethod
    def from_settings(cls, settings) -> "BloomDupeFilter":
        return cls(error_rate=settings.getfloat("BLOOM_ERROR_RATE", 0.0001))

    def request_seen(self, request) -> bool:
        fingerprint = request_fingerprint(request)
        return bool(self.seen.add(fingerprint))

    def log(self, request, spider) -> None:
        spider.logger.debug("Filtered duplicate request: %(request)s", {"request": request})

Set DUPEFILTER_CLASS = "myproject.dupefilters.BloomDupeFilter" in settings.py. Use a much tighter error_rate here than you would elsewhere — Scrapy's filter also guards against redirect loops and infinite calendars, so a false positive can drop an entire branch of the crawl rather than one page.

Edge Cases and Caveats

• You cannot delete. Clearing a bit would erase evidence of every other URL that set it. Recrawling a URL means tracking it in your frontier store, not in the filter; a counting Bloom filter or a cuckoo filter supports deletion if you truly need it.
• The error rate is only valid at the design n. Past capacity it degrades silently. Log actual_error(m, k, inserted) at the end of each run so a growing crawl warns you before it starts skipping pages.
• hash() is salted per process. Never build positions from Python's built-in hash; PYTHONHASHSEED randomisation means a persisted filter is unreadable by the next process. Use hashlib.
• Two filters are not comparable. Filters with different m or k cannot be unioned. Two filters built with identical parameters can be merged with a bitwise OR, which is how you combine per-worker filters at the end of a run.
• A false positive is invisible. Nothing logs, nothing raises, the page is simply never fetched. If completeness matters, run a periodic exact reconciliation against a sitemap, as described in Parsing XML Sitemaps with Python.
• Under a million URLs, do not bother. A set of one million URLs is roughly 120 MB and exact. The filter's complexity is only justified when memory is genuinely the constraint.

Frequently Asked Questions

What does a false positive actually cost my crawler? One URL is treated as already seen and never fetched, so a page silently drops out of the dataset with no error anywhere. That asymmetry is why you should size for two or three times the URLs you expect and pick a tighter error rate than feels necessary.

Can a Bloom filter give a false negative? No. If any of the k bits for an item is zero, the item was definitely never inserted, so a "new" answer is always correct. This one-sided error is the property that makes the structure safe to put in front of a crawl frontier.

How do I pick the capacity when I do not know how many URLs the site has? Use a scalable filter, which chains progressively larger sub-filters and keeps the compound error rate bounded, or estimate from the sitemap and multiply by three. The memory penalty for overestimating is a few megabytes; the penalty for underestimating is missing data.

Should I replace Scrapy's default dupefilter? Only when the crawl is large enough that the default set of fingerprints is a real memory problem — think tens of millions of requests. Below that the built-in filter is exact and free of the false-positive risk, which is worth more than the memory it uses.

Related

• Caching and Incremental Crawling — the parent topic and where the seen-set fits among the other layers
• HTTP Caching with requests-cache — suppressing the fetch once a URL is known
• Incremental Crawls with ETag and Last-Modified — deciding whether a known URL has changed