Tag: web crawling

  • URL Frontier Design: Dedup, Politeness and Recrawls at Scale

    The fetchers in a large crawler are the easy part. The hard part is the URL frontier: the component that decides what to fetch next, avoids duplicate fetches, stays polite to every host and survives crawler traps. This guide covers a practical URL frontier design: canonicalization, seen-URL sets with real Bloom filter math, Mercator-style per-host queues, sitemaps, conditional recrawls, Scrapy's built-in pieces and trap defenses, with runnable Python.

    TL;DR

    • Canonicalize before you dedupe (RFC 3986 section 6): lowercase scheme and host, drop default ports and fragments, remove dot segments, normalize percent-encoding. Sorting and stripping query parameters are heuristics, not standards.
    • Use the canonical form as a lookup key, and fetch the original URL.
    • Size the seen-set with arithmetic: a Bloom filter needs -ln(p) / (ln 2)^2 bits per URL, about 9.6 bits at 1% false positives. A false positive means a URL is silently skipped.
    • Separate priority from politeness: front queues for priority, one back queue per host, and a heap of next-allowed fetch times (the Mercator design).
    • Recrawl with validators (If-None-Match, If-Modified-Since) and budget every host so traps cannot eat the crawl.

    What a URL frontier does

    The standard reference is the section The URL frontier in chapter 20 of Manning, Raghavan and Schütze's Introduction to Information Retrieval, which describes the frontier of the Mercator crawler (Heydon and Najork, "Mercator: A scalable, extensible Web crawler", World Wide Web 2(4), 1999). It balances two goals:

    • Priority: important pages, and pages that change often, get fetched first and refetched more often.
    • Politeness: most links point to the same host, so a plain priority queue produces bursts against one server.

    In front of the queues sit a canonicalizer and a seen-URL set; behind them, a URL database with fetch history for recrawls.

    URL canonicalization: safe rules and guesses

    RFC 3986 section 6 notes that extensive normalization "is often used by spiders and indexing engines to prune a search space", and that comparison methods are "designed to minimize false negatives while strictly avoiding false positives". Keep that mindset: every rule merges more URLs, and a wrong merge is a page you never fetch.

    Safe by the spec

    • Case: scheme and host are case-insensitive; lowercase them. Uppercase hex digits in percent-encodings (%3a to %3A). Path and query are case-sensitive.
    • Percent-encoding: decode encoded unreserved characters (letters, digits, -._~), so %7Euser equals ~user.
    • Dot segments: resolve . and .. with remove_dot_segments (section 5.2.4).
    • Port and empty path: RFC 9110 section 4.2.3 says the normal form omits the default port (80 or 443) and uses / for an empty path.
    • Fragments: RFC 3986 section 6.1 says fragments should be excluded when comparing URIs to select a network action such as retrieval.

    Heuristics with caveats

    • Sorting query parameters suits most sites but no standard guarantees it. Scrapy's w3lib.url.canonicalize_url sorts by key, then value, and drops fragments by default.
    • Stripping parameters: utm_*, gclid and fbclid are usually safe to drop. Session and view parameters are site-specific; use per-host rules.
    • Trailing slash, www., index.html, http versus https are different URLs. Let the server's redirects tell you, and mark both source and target as seen.
    • Hash routes in single-page apps may matter if you render pages; see Playwright headless browser scraping at scale.

    A stdlib-only canonicalizer with the safe rules plus sorted, de-tracked queries:

    import re
    from urllib.parse import parse_qsl, urlencode, urlsplit, urlunsplit
    
    DEFAULT_PORTS = {"http": 80, "https": 443}
    UNRESERVED = set("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-._~")
    TRACKING = re.compile(r"^(utm_[a-z]+|gclid|fbclid|msclkid)$", re.IGNORECASE)
    PCT = re.compile(r"%([0-9A-Fa-f]{2})")
    
    
    def normalize_pct(s):
        def fix(m):
            ch = chr(int(m.group(1), 16))
            return ch if ch in UNRESERVED else "%" + m.group(1).upper()
        return PCT.sub(fix, s)
    
    
    def remove_dot_segments(path):  # segment-stack form of RFC 3986 5.2.4
        segments = path.split("/")
        out = []
        for seg in segments:
            if seg == ".":
                continue
            if seg == "..":
                if len(out) > 1:
                    out.pop()
                continue
            out.append(seg)
        if segments[-1] in (".", ".."):
            out.append("")  # "/a/b/.." -> "/a/"
        return "/".join(out)
    
    
    def canonicalize(url, drop=TRACKING, sort_query=True):
        parts = urlsplit(url.strip())
        scheme = parts.scheme.lower()
        if scheme not in DEFAULT_PORTS:
            raise ValueError(f"unsupported scheme: {scheme!r}")
        host = parts.hostname  # lowercased, userinfo removed
        if not host:
            raise ValueError(f"no host in {url!r}")
        if ":" in host:
            host = f"[{host}]"  # IPv6 literal
        port = parts.port  # ValueError on a malformed port
        netloc = host if port in (None, DEFAULT_PORTS[scheme]) else f"{host}:{port}"
        path = remove_dot_segments(normalize_pct(parts.path)) or "/"
        pairs = [(k, v) for k, v in parse_qsl(parts.query, keep_blank_values=True)
                 if not drop.match(k)]
        if sort_query:
            pairs.sort()
        return urlunsplit((scheme, netloc, path, urlencode(pairs), ""))
    
    
    print(canonicalize("HTTP://www.Example.com:80/a/./b/../c/%7euser?utm_source=x&b=2&a=1#top"))
    # http://www.example.com/a/c/~user?a=1&b=2

    Userinfo is dropped (RFC 9110 section 4.2.4 deprecates it). Because urlencode re-encodes the query, fetch the original URL, not the key; w3lib's docstring gives the same warning.

    Seen-URL sets: Bloom filters and exact stores

    A Bloom filter (Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", CACM 1970, which the Mercator paper cites) stores set membership in m bits with k hash functions. With n items inserted:

    false positive rate     p ≈ (1 - e^(-k*n/m))^k
    optimal hash count      k = (m/n) * ln 2
    bits for a target p     m = -n * ln(p) / (ln 2)^2
    Target p Bits per URL Memory for n = 10^9 k
    1% 4.605 / 0.4805 ≈ 9.59 ≈ 1.2 GB 7
    0.1% 6.908 / 0.4805 ≈ 14.38 ≈ 1.8 GB 10

    An exact set of 64-bit URL hashes needs 8 bytes × 10^9 = 8 GB before index overhead, and the birthday bound puts expected colliding pairs at about n² / 2^65 ≈ 0.03. So the Bloom filter saves roughly 4–7× memory for a known loss rate.

    Know which way the error goes: a Bloom filter sometimes says "seen" for a new URL, so about p of new URLs are silently skipped. Size it for the final n, because the rate climbs fast past it, and a plain Bloom filter cannot delete or resize.

    import hashlib
    import math
    
    
    class BloomFilter:
        def __init__(self, n, p):
            self.m = math.ceil(-n * math.log(p) / math.log(2) ** 2)  # bits
            self.k = max(1, round(self.m / n * math.log(2)))          # hash functions
            self.bits = bytearray((self.m + 7) // 8)
    
        def _positions(self, item):
            d = hashlib.blake2b(item.encode(), digest_size=16).digest()
            h1 = int.from_bytes(d[:8], "little")
            h2 = int.from_bytes(d[8:], "little") | 1
            return [(h1 + i * h2) % self.m for i in range(self.k)]  # double hashing
    
        def add(self, item):
            """Set the item's bits; return True if it was (probably) present already."""
            present = True
            for pos in self._positions(item):
                byte, bit = divmod(pos, 8)
                if not (self.bits[byte] >> bit) & 1:
                    present = False
                    self.bits[byte] |= 1 << bit
            return present

    In our check, probing 100,000 new URLs against BloomFilter(100_000, 0.01) filled with 100,000 others gave about 1.0% false positives, as predicted.

    Exact stores

    • RocksDB or another embedded key-value store: key = hash of the canonical URL, value = fetch state. It doubles as the recrawl database; a Bloom filter in RAM in front keeps most lookups off disk.
    • Redis: SADD on a set of hashes is an atomic "add and tell me if it was new" across workers. Redis also has Bloom filters (BF.RESERVE, BF.ADD) and cuckoo filters (CF.*, which support deletion). It is all RAM, so the memory math still applies.
    • Distributed crawls: partition by host so each node owns its hosts' state.

    URL dedup is not content dedup: mirrors and parameter variants serve the same page under different URLs. Catch those after fetching; see MinHash deduplication for LLM training data.

    Per-host queues and politeness, Mercator style

    In the IR book's account of Mercator, a prioritizer assigns each URL to one of F front queues. Each back queue holds URLs from one host, and a heap holds the earliest time each back queue's host may be contacted again. A fetcher pops the heap, waits if needed, fetches one URL and pushes the host back with a new time. Two rules of thumb from the book: wait about ten times the last fetch duration before the next request to that host, and keep about three times as many back queues as crawler threads.

    The sketch below keeps that structure but uses a dictionary of per-host back queues instead of a fixed number of them. Put it in one file with the two blocks above.

    import heapq
    import random
    import time
    from collections import deque
    from urllib.parse import urlsplit
    
    
    class Frontier:
        def __init__(self, priorities=3, min_delay=1.0, delay_factor=10.0,
                     expected_urls=10_000_000, fp_rate=0.001):
            self.front = [deque() for _ in range(priorities)]  # 0 = highest priority
            self.back = {}         # host -> deque of URLs
            self.ready = []        # heap of (earliest_next_fetch, host)
            self.not_before = {}   # host -> earliest next fetch
            self.seen = BloomFilter(expected_urls, fp_rate)
            self.min_delay, self.delay_factor = min_delay, delay_factor
    
        def add(self, url, priority=1):
            if self.seen.add(canonicalize(url)):
                return False
            self.front[priority].append(url)
            return True
    
        def _refill(self, max_moves=1000):
            weights = [2 ** (len(self.front) - i) for i in range(len(self.front))]
            for _ in range(max_moves):
                nonempty = [i for i, q in enumerate(self.front) if q]
                if not nonempty:
                    return
                i = random.choices(nonempty, [weights[j] for j in nonempty])[0]
                url = self.front[i].popleft()
                host = urlsplit(url).hostname
                if host not in self.back:
                    self.back[host] = deque()
                    t = max(time.monotonic(), self.not_before.get(host, 0.0))
                    heapq.heappush(self.ready, (t, host))
                self.back[host].append(url)
    
        def next_url(self):
            if not self.ready:
                self._refill()
            if not self.ready:
                return None
            t, host = heapq.heappop(self.ready)
            return self.back[host].popleft(), host, max(0.0, t - time.monotonic())
    
        def done(self, host, fetch_seconds):
            t = time.monotonic() + max(self.min_delay, self.delay_factor * fetch_seconds)
            self.not_before[host] = t
            if self.back[host]:
                heapq.heappush(self.ready, (t, host))
            else:
                del self.back[host]
            self._refill(max_moves=100)
    
    
    f = Frontier(min_delay=0.2)
    for u in ["https://example.com/", "https://EXAMPLE.com:443/#top",
              "https://example.org/a?utm_source=news", "https://example.org/a",
              "https://example.org/b"]:
        print(u, "->", "queued" if f.add(u) else "duplicate")
    while (item := f.next_url()) is not None:
        url, host, wait = item
        time.sleep(wait)
        print(f"fetch {url} (waited {wait:.2f}s)")
        f.done(host, fetch_seconds=0.01)

    This queues three URLs, flags two variants as duplicates, and delays the second example.org fetch by 0.2 seconds. A host leaves the heap while its fetch is in flight, so there is one request per host at a time. Production versions keep most of each queue on disk (as the IR book notes) and add robots.txt, Retry-After and adaptive rates, covered in web scraping rate limiting, retries and backoff.

    Priority signals and sitemaps

    Useful priority signals: depth from seeds, the host's track record, URL patterns and sitemaps. The sitemaps.org protocol specifies:

    • At most 50,000 URLs and 50MB (52,428,800 bytes) uncompressed per sitemap; gzip is allowed. Index files may list up to 50,000 sitemaps with the same size limit, and carry a lastmod per sitemap so you can skip unchanged ones.
    • <loc> must be under 2,048 characters, and URLs must share the sitemap's host and protocol.
    • <changefreq> is "a hint and not a command"; <priority> (0.0–1.0, default 0.5) only ranks URLs within one site.
    • Sites can advertise sitemaps with a Sitemap: line in robots.txt.

    Use sitemaps for discovery and lastmod to order recrawls within a host.

    Recrawl scheduling with conditional requests

    A long-running frontier also schedules revisits. Store the ETag and Last-Modified from each response and send them back as If-None-Match and If-Modified-Since (RFC 9110 section 13). An unchanged page can then come back as 304 Not Modified with no content. RFC 9110 says a recipient must ignore If-Modified-Since when If-None-Match is present, so the ETag wins. Many servers send neither validator, so also compare your own content hash.

    import hashlib
    
    import httpx
    
    
    def revisit(client: httpx.Client, url, state):
        """Use httpx.Client(follow_redirects=True). state holds etag, last_modified, sha256, interval."""
        headers = {}
        if state.get("etag"):
            headers["If-None-Match"] = state["etag"]
        if state.get("last_modified"):
            headers["If-Modified-Since"] = state["last_modified"]
        r = client.get(url, headers=headers)
        interval = state.get("interval", 86_400)
        if r.status_code == 304:
            changed = False
        else:
            r.raise_for_status()
            digest = hashlib.sha256(r.content).hexdigest()
            changed = digest != state.get("sha256")
            state.update(sha256=digest, etag=r.headers.get("ETag"),
                         last_modified=r.headers.get("Last-Modified"))
        # heuristic: revisit changing pages sooner, stable ones later, within 1 h to 30 days
        state["interval"] = max(3_600, min(30 * 86_400, interval / 2 if changed else interval * 1.5))
        return changed

    The halve-or-grow rule is a heuristic; the IR book warns that spam pages can change on every fetch, so weigh quality too.

    Scrapy's built-in frontier

    Scrapy's scheduler and dupefilter form a small URL frontier. From the settings reference and jobs docs (Scrapy 2.20 at the time of writing):

    • DUPEFILTER_CLASS defaults to scrapy.dupefilters.RFPDupeFilter, which fingerprints the canonicalized URL, method and body and keeps fingerprints in memory. Scrapy 2.20 added scrapy.dupefilters.DiskDupeFilter, which keeps them in SQLite.
    • JOBDIR persists pending requests (requests.queue/), fingerprints (requests.seen) and spider state, so a cleanly stopped crawl resumes. Use one directory per job and the same Scrapy version.
    • SCHEDULER_PRIORITY_QUEUE defaults to DownloaderAwarePriorityQueue, which the docs recommend for crawling many domains in parallel.
    • JOBDIR_SYNC_EVERY (2.20+) also saves state during the crawl; surviving a hard kill needs the SQLite disk queue types (2.19+).
    # settings.py
    JOBDIR = "crawls/frontier-1"   # or: scrapy crawl myspider -s JOBDIR=crawls/frontier-1
    DUPEFILTER_CLASS = "scrapy.dupefilters.DiskDupeFilter"               # 2.20+
    JOBDIR_SYNC_EVERY = 1000                                              # 2.20+, default 0
    SCHEDULER_DISK_QUEUE = "scrapy.squeues.PickleLifoSQLiteQueue"         # 2.19+
    SCHEDULER_START_DISK_QUEUE = "scrapy.squeues.PickleFifoSQLiteQueue"   # 2.19+
    DEPTH_LIMIT = 20               # default 0 = unlimited
    URLLENGTH_LIMIT = 2083         # the default

    Requests with dont_filter=True bypass the dupefilter; unpicklable requests are lost on pause.

    Crawler traps

    Traps generate unique URLs without new content: endless calendars, faceted search, session IDs, relative-link bugs producing /a/b/a/b/a/b/. Dedup cannot catch them. Defenses, cheapest first:

    • Hard limits: depth, URL length, query parameter count.
    • Per-host budgets: cap URLs queued per host, and raise the cap only for hosts that keep yielding distinct, useful documents.
    • Pattern counters: replace digits and IDs with placeholders (/calendar/{n}/{n}) and cap URLs per pattern; cap distinct values per query key.
    • Repetition checks: reject paths whose segment sequence repeats.
    • Content feedback: demote patterns whose new URLs keep hashing to content you already have.

    For the full text pipeline, see the Common Crawl LLM pretraining data pipeline.

    Compliance

    The frontier is the natural place for robots.txt checks and opt-out lists. Site terms of service often restrict automated access (YouTube's Terms of Service, for example, restrict automated access and downloading). Copyright and licensing apply to what you collect and redistribute, privacy law such as GDPR applies to personal data including faces and voices, and you should honor takedown and opt-out requests. Get legal review for your jurisdiction and use case.

    If you would rather not run the egress yourself

    If your frontier is in good shape and egress capacity is the bottleneck, Corpora offers dedicated 1–40 Gbps unmetered proxy capacity (HTTP(S) and SOCKS5, works with custom crawlers) and a separate residential proxy product. Keep politeness keyed on the target host either way.

    FAQ

    What is a URL frontier?

    The structure that holds URLs waiting to be fetched and decides their order, combining deduplication, priority and per-host politeness.

    How big a Bloom filter do I need for a billion URLs?

    About 1.2 GB at 1% false positives (7 hashes) and 1.8 GB at 0.1% (10), from m = -n ln(p) / (ln 2)^2.

    Should I sort query parameters when normalizing URLs?

    For dedup keys, usually yes; Scrapy's canonicalize_url does. No standard guarantees it, so fetch the original URL and add per-host exceptions when order matters.

    Does Scrapy remember seen URLs between runs?

    Only with JOBDIR set; rerunning with the same JOBDIR restores fingerprints and pending requests.