13 min read

Deduplicating URLs in a Distributed Crawl

Splitting a crawl across many workers solves throughput, but it introduces a new failure mode that a single-process crawler never has to think about: two workers discovering the same page from different links at nearly the same moment, both deciding independently that it looks unfetched, and both issuing a request. At any real scale this is not a rare edge case - it happens on every crawl of a site with cross-linked categories, pagination, or a footer sitemap, because those structures generate the same destination URL from dozens of source pages. This guide is part of Orchestrating Distributed Crawls Across Workers and covers the specific mechanism that keeps a distributed frontier honest: a shared, atomic visited-set over canonicalized URLs, with a Bloom filter as the scale-out path once an exact set stops fitting in memory.

The fix has to live outside any single worker's process memory. Whether each worker owns a shard of the frontier by consistent-hashed host assignment or pulls from a common queue, the question "has this exact page already been claimed?" needs one authoritative answer that every worker can check and update without a race condition. Redis's SET key value NX EX ttl gives you that atomicity in a single round trip, which is why it is the default building block here before reaching for anything heavier like a coordination service or a distributed lock manager.

Distributed Crawl Deduplication Flow A discovered URL from any worker is canonicalized, hashed with SHA-1, and checked against a shared Redis visited set using an atomic SETNX. If SETNX returns 1 the URL is new and is pushed to the frontier queue. If it returns 0 the URL was already claimed and is dropped without a fetch. Worker discovers URL from any shard Canonicalize lowercase host sort query, strip UTM Hash Key sha1(canonical) fixed-width digest Redis SETNX visited:{hash} 30-day TTL SETNX = 1 New URL key was claimed push to frontier queue SETNX = 0 Duplicate key already existed discard, no fetch

Environment Isolation and Dependency Declaration

Every worker process needs the same Redis endpoint and the same TTL policy, so pin them as environment variables read at process start rather than as literals scattered through worker code.

# /opt/audit/dedup — shared across every crawl worker process
export REDIS_URL="redis://dedup-cache.internal:6379/2"
export VISITED_TTL_DAYS=30
export DEDUP_STRATEGY="set"   # "set" for exact, "bloom" once past ~20M URLs
export BLOOM_ERROR_RATE=0.01
export BLOOM_CAPACITY=50000000
# requirements.txt — pin every direct dependency
redis==5.0.4

set -euo pipefail
cd /opt/audit/dedup
python3 -m venv .venv
.venv/bin/pip install --quiet -r requirements.txt

DEDUP_STRATEGY is the single switch that lets an operator move a running crawl from the exact set to a Bloom filter without touching worker code - both paths read the same canonicalization function, so the key space is identical across the switch.

Implementation

Every worker imports this module and calls claim(url) before fetching. The function canonicalizes the URL, hashes it, and issues the atomic claim against Redis. It returns True only for the one worker that wins the race for a given page.

#!/usr/bin/env python3
# /opt/audit/dedup/visited.py
"""
Shared URL deduplication for a distributed crawl.
Reads REDIS_URL, VISITED_TTL_DAYS, DEDUP_STRATEGY, BLOOM_ERROR_RATE,
BLOOM_CAPACITY from environment. Import claim(url) in every worker.
"""

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

import redis

# ── 1. connect once per process; redis-py pools connections internally ──────
_r = redis.Redis.from_url(os.environ["REDIS_URL"], decode_responses=True)
_TTL_SECONDS = int(os.environ.get("VISITED_TTL_DAYS", 30)) * 86400
_STRATEGY = os.environ.get("DEDUP_STRATEGY", "set")
_BLOOM_KEY = "crawl:visited:bf"

# tracking parameters that never change what page loads — strip them
_DROP_PARAMS = {"utm_source", "utm_medium", "utm_campaign", "utm_content",
                "gclid", "fbclid", "sessionid", "phpsessid"}

# ── 2. canonicalize: same page, same string, regardless of source spelling ──
def canonicalize(raw_url: str) -> str:
    parts = urlsplit(raw_url)
    scheme = parts.scheme.lower() or "https"
    netloc = parts.netloc.lower()
    if netloc.endswith(":80") and scheme == "http":
        netloc = netloc[:-3]
    if netloc.endswith(":443") and scheme == "https":
        netloc = netloc[:-4]
    path = parts.path or "/"
    if len(path) > 1 and path.endswith("/"):
        path = path.rstrip("/")
    # keep only params that affect content, sorted for a stable order
    kept = sorted(
        (k, v) for k, v in parse_qsl(parts.query, keep_blank_values=True)
        if k.lower() not in _DROP_PARAMS
    )
    query = urlencode(kept)
    # fragment is always dropped — it never reaches the server
    return urlunsplit((scheme, netloc, path, query, ""))

# ── 3. fixed-width key regardless of canonical URL length ───────────────────
def _key_for(canonical_url: str) -> str:
    digest = hashlib.sha1(canonical_url.encode("utf-8")).hexdigest()
    return f"visited:{digest}"

# ── 4. exact-set path: atomic claim via SET ... NX EX ────────────────────────
def _claim_exact(canonical_url: str) -> bool:
    key = _key_for(canonical_url)
    # SET returns True only if the key did not already exist — one winner
    return bool(_r.set(key, "1", nx=True, ex=_TTL_SECONDS))

# ── 5. bloom-filter path: RedisBloom module, no per-key expiry ──────────────
def _claim_bloom(canonical_url: str) -> bool:
    digest = hashlib.sha1(canonical_url.encode("utf-8")).hexdigest()
    # BF.ADD returns 1 if the item was newly added, 0 if it (probably) existed
    added = _r.execute_command("BF.ADD", _BLOOM_KEY, digest)
    return bool(added)

# ── 6. public entry point every worker calls before fetching ────────────────
def claim(raw_url: str) -> bool:
    """Return True if this call is the first to see raw_url; False otherwise."""
    canonical = canonicalize(raw_url)
    if _STRATEGY == "bloom":
        return _claim_bloom(canonical)
    return _claim_exact(canonical)

def ensure_bloom_filter() -> None:
    """Idempotent setup — call once at deploy time when DEDUP_STRATEGY=bloom."""
    error_rate = float(os.environ.get("BLOOM_ERROR_RATE", 0.01))
    capacity = int(os.environ.get("BLOOM_CAPACITY", 50_000_000))
    try:
        _r.execute_command("BF.RESERVE", _BLOOM_KEY, error_rate, capacity)
    except redis.exceptions.ResponseError as e:
        if "exists" not in str(e).lower():
            raise

Each worker's fetch loop calls it as a guard, not as a separate step bolted on afterward:

# inside each worker's fetch loop
from visited import claim

for raw_url in frontier.pop_batch():
    if not claim(raw_url):
        continue  # another worker already owns this page
    fetch_and_process(raw_url)

The two strategies share the same canonicalize() function on purpose - switching DEDUP_STRATEGY from set to bloom changes only how the claim is stored, never what counts as "the same URL." That consistency is what makes a mid-crawl migration safe: you are not silently redefining duplicates when you change storage backends.

Verification and Smoke Test

Run this after deploying visited.py to confirm the exact-set path is atomic under concurrent workers before trusting it in a live crawl.

set -euo pipefail
cd /opt/audit/dedup

# 1. same URL, different spellings, must canonicalize identically
.venv/bin/python -c "
from visited import canonicalize
a = canonicalize('HTTPS://Example.com:443/Products/?utm_source=x&id=9')
b = canonicalize('https://example.com/products?id=9&utm_source=y')
assert a == b, f'canonicalization mismatch: {a} != {b}'
print('PASS: canonical forms match ->', a)
"

# 2. concurrent claim race — exactly one of N parallel claims should win
.venv/bin/python -c "
from concurrent.futures import ThreadPoolExecutor
from visited import claim
url = 'https://example.com/race-test-page'
with ThreadPoolExecutor(max_workers=20) as pool:
    results = list(pool.map(lambda _: claim(url), range(20)))
wins = sum(results)
print('PASS: exactly one winner') if wins == 1 else print(f'FAIL: {wins} winners')
"

# 3. redis memory footprint per 1M visited keys
redis-cli -u "$REDIS_URL" --bigkeys 2>/dev/null | grep -A1 "biggest.*visited" || true
redis-cli -u "$REDIS_URL" DBSIZE

Expected output:

PASS: canonical forms match -> https://example.com/products?id=9
PASS: exactly one winner
(integer) 1000000

If step 2 ever reports more than one winner, the claim is not actually atomic - check that you are calling redis.Redis.set(..., nx=True) in a single command rather than a separate EXISTS check followed by a SET, which reintroduces the race it was meant to close.

Failure Modes

Canonicalization gaps let the same page slip through as "new" twice

Every parameter or path variant you don't normalize becomes a hole. Trailing-slash inconsistency, mixed-case paths on case-sensitive servers, and unlisted tracking parameters are the three most common gaps in production.

# diagnostic: sample recently fetched URLs and check canonical collisions
.venv/bin/python -c "
from visited import canonicalize
import collections
urls = open('logs/fetched_urls.txt').read().split()
counts = collections.Counter(canonicalize(u) for u in urls)
dupes = {k: v for k, v in counts.items() if v > 1}
print(f'{len(dupes)} canonical forms were fetched more than once')
"
# fix: add the offending parameter to _DROP_PARAMS and redeploy visited.py

Bloom filter false positives silently shrink crawl coverage

Once DEDUP_STRATEGY=bloom, a false positive means claim() returns False for a genuinely new page - there is no error, the page is simply never fetched. This is invisible unless you track it.

# diagnostic: compare expected vs actual crawl coverage against a sitemap
.venv/bin/python -c "
import redis, os
r = redis.Redis.from_url(os.environ['REDIS_URL'])
info = r.execute_command('BF.INFO', 'crawl:visited:bf')
print(dict(zip(info[::2], info[1::2])))
"
# fix: lower BLOOM_ERROR_RATE (e.g. 0.01 -> 0.001) and BF.RESERVE a fresh filter;
# a lower error rate costs more memory per entry but recovers coverage

Exact set memory growth outpaces the Redis instance

Every SHA-1 key plus its Redis overhead costs roughly 90-100 bytes. At 50 million URLs that is 4.5-5 GB just for the visited set, before frontier queues and other pipeline state, and it keeps growing until TTLs expire old entries.

# diagnostic: estimate current visited-set memory footprint
redis-cli -u "$REDIS_URL" MEMORY USAGE visited:$(redis-cli -u "$REDIS_URL" RANDOMKEY | sed 's/^visited://')
redis-cli -u "$REDIS_URL" DBSIZE
# fix: switch DEDUP_STRATEGY=bloom, call ensure_bloom_filter() once, then
# redeploy workers — the canonicalization layer is unchanged so no re-crawl
# of already-visited pages is needed during the cutover

FAQ

How is a canonical URL different from the raw URL a crawler discovers?

The raw URL is whatever a link, sitemap entry, or redirect target happened to spell out - it can carry mixed case, a default port, a fragment, and query parameters in arbitrary order. The canonical form normalizes all of that into one deterministic string so that two URLs which resolve to the same page also hash to the same visited-set key, even if they were written differently in the HTML.

Why use Redis instead of an in-memory set on each worker?

An in-memory set is local to one process. In a distributed crawl split across workers as described in sharding a URL frontier across crawl workers, two different workers can independently discover the same URL and both would consider it new. A shared Redis instance gives every worker one consistent view of what has already been claimed, and SET with NX makes the claim atomic so a race between two workers still produces exactly one winner.

Should I switch to a Bloom filter instead of an exact Redis set?

Switch once the exact set's memory footprint becomes the bottleneck, typically past tens of millions of distinct URLs. A Bloom filter trades a small, tunable false-positive rate for roughly an order-of-magnitude reduction in memory per entry, because it stores hashed bit positions instead of full keys. Keep the exact SETNX approach for crawls under that scale - the added complexity of tuning error rate and handling non-removability is not worth it until memory is genuinely the constraint.

What false-positive rate should I target for a Bloom filter dedup set?

0.1% to 1% is the practical range for crawl deduplication. A false positive means a genuinely new URL is skipped as if already visited, so it silently shrinks crawl coverage rather than causing a visible error - keep it low enough that the number of skipped pages is negligible relative to your crawl budget, and log the estimated skip count from BF.INFO after each run so drift is visible.