Skip to content

Deduplicating URLs in a Concurrent Crawl Frontier

A crawler discovers the same page many times, under many spellings, from many concurrent tasks. The frontier — the set of URLs seen plus the queue of URLs to fetch — has to recognise all of them as one. Three things go wrong. Spelling: tested on a four-host site whose links varied fragments, tracking parameters, trailing slashes and scheme case, 206 of 1,219 fetches (17%) were pages already fetched under another spelling; normalizing URLs before the check removed all of them. Concurrency: when 100 tasks discovered the same URL and the code awaited anything between "not seen yet" and "mark seen", the URL was scheduled 100 times; with the check and the add adjacent, once. Scale: a Python set of 1 million 78-character URLs took 149 MiB; a set of 64-bit hashes of them took 66 MiB. This guide builds a frontier that handles all three.

Prerequisites

1. Normalize URLs to one canonical form

Before checking whether a URL has been seen, rewrite it so that every spelling of the same resource becomes the same string:

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

TRACKING = {"utm_source", "utm_medium", "utm_campaign", "utm_term", "utm_content",
            "gclid", "fbclid", "mc_cid", "mc_eid"}
DEFAULT_PORTS = {"http": 80, "https": 443}


def normalize(url: str, base: str | None = None) -> str:
    if base:
        url = urljoin(base, url)                       # resolve relative links first
    s = urlsplit(url)
    scheme = s.scheme.lower()
    host = (s.hostname or "").lower().rstrip(".")
    netloc = host if s.port in (None, DEFAULT_PORTS.get(scheme)) else f"{host}:{s.port}"
    path = s.path or "/"
    if path != "/" and path.endswith("/"):
        path = path[:-1]                               # site-specific: see below
    query = urlencode(sorted((k, v) for k, v in parse_qsl(s.query, keep_blank_values=True)
                             if k not in TRACKING))
    return urlunsplit((scheme, netloc, path, query, ""))          # fragment dropped

Measured on the test crawl: 206 duplicate fetches without normalization, 0 with it, at about 7 µs per URL. Be conservative: scheme and host are case-insensitive, paths usually are not; fragments never reach the server; tracking parameters do not change content. Stripping trailing slashes is a site-specific judgement — on most sites /docs/ and /docs are the same page, on some they are not — so make it configurable per host, and prefer a page's <link rel="canonical"> when it declares one.

Verify: a test list of known variants of one URL normalizes to a single string, and genuinely different URLs stay different.

URL variants that should collapse to one A grid of 5 rows by 3 columns. URL variants that should collapse to one variant normalized rule safe? HTTP://Example.com/a lower-case scheme, host always https://example.com:443/a drop default port always /a#reviews drop fragment always /a?utm_source=x&id=1 drop tracking, sort rest always /a/ strip trailing slash per site Paths stay case-sensitive; everything else in the list is safe to fold.

2. Make check-and-add atomic

In asyncio, code between two awaits runs without interruption, so a check followed immediately by an add cannot race. Put any await between them and every concurrent discoverer passes the check:

# Wrong: an await between the check and the add
async def discover(url: str) -> None:
    if url in seen:
        return
    await robots.allowed(url)          # other tasks run here and also see "not seen"
    seen.add(url)
    queue.put_nowait(url)              # measured: one URL scheduled 100 times


# Right: claim the URL first, then do the slow work
async def discover(url: str) -> None:
    if url in seen:
        return
    seen.add(url)                      # claimed before any await: measured once
    if await robots.allowed(url):
        queue.put_nowait(url)

Tested with 100 tasks discovering the same URL at once: 100 schedules with the await in between, 1 with the add first. Claiming early means a URL that turns out to be disallowed is still marked seen — which is what you want, since checking it again would give the same answer. With multiple processes, the same rule moves to the shared store: use an atomic operation such as SADD in Redis, whose return value says whether this caller was first, or INSERT ... ON CONFLICT DO NOTHING in SQL.

Verify: a concurrency test that discovers the same URL from many tasks schedules it exactly once.

Times one URL was scheduled when 100 tasks found it 2 horizontal bars comparing check, await, add with the others. Times one URL was scheduled when 100 tasks found it check, await, add 100 schedules check, add, then await 1 schedule Python 3.14; the await stands in for a robots or DNS lookup between the check and the add. In asyncio, atomicity is about where the awaits are.

3. Size the seen set for the crawl

A set of URL strings is simple and exact, and its memory grows with every discovered URL — discovered, not fetched, which is often ten times more:

import hashlib


def url_key(url: str) -> int:
    return int.from_bytes(hashlib.blake2b(url.encode(), digest_size=8).digest(), "big")


class SeenSet:
    def __init__(self) -> None:
        self._keys: set[int] = set()

    def add_if_new(self, url: str) -> bool:
        key = url_key(url)
        if key in self._keys:
            return False
        self._keys.add(key)
        return True

Measured with 1 million URLs averaging 78 characters: 149 MiB as a set of strings (156 bytes per URL), 66 MiB as a set of 64-bit integer hashes (70 bytes per URL), at about 3.4 µs per hash. A 64-bit hash has a negligible chance of collision for crawls of millions of URLs — a collision means one page is skipped, not that wrong data is fetched. Beyond tens of millions of URLs, move the seen set out of process memory: a database table with a unique index, a Redis set, or a Bloom filter that trades a small false-positive rate for a fixed few bytes per URL.

Verify: the seen set's memory per URL, measured on a sample of your real URLs, times the expected number of discovered URLs fits the budget.

4. Separate "seen" from "queued" and "done"

A frontier tracks more than whether a URL was seen. Keeping state per URL makes the crawl observable and resumable:

from enum import IntEnum


class State(IntEnum):
    QUEUED = 0
    IN_FLIGHT = 1
    DONE = 2
    FAILED = 3
    SKIPPED = 4            # disallowed, out of scope, wrong content type


class Frontier:
    def __init__(self) -> None:
        self.state: dict[str, State] = {}
        self.queues: dict[str, asyncio.Queue[str]] = {}

    def offer(self, url: str) -> bool:
        if url in self.state:
            return False
        self.state[url] = State.QUEUED
        self.queues.setdefault(urlsplit(url).netloc, asyncio.Queue()).put_nowait(url)
        return True

    def mark(self, url: str, state: State) -> None:
        self.state[url] = state

With states, you can report progress (done versus queued), retry failures selectively, and on restart requeue anything left IN_FLIGHT. The same structure in a database is the durable frontier described in persisting crawl state to resume after a crash.

Verify: at any moment, the counts per state add up to the number of distinct normalized URLs discovered.

5. Deduplicate content, not just URLs

Different URLs can serve identical content — session ids in paths, printer-friendly versions, mirrors. After fetching, a content fingerprint catches what URL normalization cannot:

content_seen: set[bytes] = set()


def is_duplicate_content(body: bytes) -> bool:
    fingerprint = hashlib.blake2b(normalize_whitespace(body), digest_size=16).digest()
    if fingerprint in content_seen:
        return True
    content_seen.add(fingerprint)
    return False

Skip link extraction for duplicate content, which stops the crawler from wandering into infinite variants of the same page — calendar pages that link to "next month" forever, faceted search that combines filters endlessly. Exact hashes catch identical pages; near-duplicates (a changing timestamp or ad) need similarity hashing such as SimHash, which is worth adding only when exact duplicates are not enough. Pair this with scope rules — maximum depth per host, maximum pages per host — so traps cannot consume the crawl.

Verify: a test site with a calendar trap is crawled to a bounded depth, and duplicate pages are not parsed for links.

How should this crawl deduplicate? A decision on How big is the crawl, and how many processes with 4 outcomes. How should this crawl deduplicate? How big is the crawl, and how many processes? any crawl normalize + atomic claim the baseline up to millions, one process set of 64-bit hashes 70 B per URL larger, or many processes DB unique index / Redis SADD atomic, shared sites with traps content hash + per-host limits bounded Normalization and atomic claims fix correctness; storage choice fixes scale.

Verification

The frontier deduplicates correctly when:

  • Every URL is normalized before it is checked, with site-specific rules configurable.
  • Check and claim happen without an await between them, or atomically in a shared store.
  • Seen-set memory is sized from measured bytes per URL and the expected discovery count.
  • Content fingerprints and scope limits stop duplicate pages and crawler traps.

Diagnostic Hook: record the duplicate rate — fetches whose normalized URL or content fingerprint was already done — and the ratio of discovered to fetched URLs per host. A duplicate rate above zero means a variant is escaping normalization or a claim race exists; a host whose discovered count grows without bound is a trap that needs a scope rule.

Pitfalls & edge cases

  • No normalization. Measured: 17% of fetches were duplicates.
  • An await between check and add. Measured: one URL scheduled 100 times.
  • Lower-casing paths. Most servers treat them as case-sensitive.
  • Unbounded string sets. 156 bytes per URL adds up over millions of discoveries.

Frequently Asked Questions

How do I normalize URLs for a crawler in Python?

Resolve relative links, lower-case the scheme and host, drop the default port and the fragment, remove tracking parameters, sort the remaining query parameters, and apply site-specific rules such as trailing slashes. Do not lower-case the path.

Why does my asyncio crawler fetch the same URL twice?

Either the URL appears in different spellings, which normalization fixes, or an await sits between checking the seen set and adding to it, so concurrent tasks all pass the check. In testing that scheduled one URL 100 times.

How much memory does a crawler's seen set use?

In testing, 1 million 78-character URLs took 149 MiB as a set of strings and 66 MiB as a set of 64-bit hashes. Larger crawls should use a database, Redis or a Bloom filter.

How do I detect duplicate pages with different URLs?

Hash the fetched content and keep a set of fingerprints; skip link extraction for pages already seen. Use similarity hashing only if near-duplicates are a real problem.