Crawl Strategy and the URL Frontier

Crawling Is Prioritization#

Scraping one page is easy. Crawling a site means deciding, again and again, which of thousands of discovered but unvisited URLs to fetch next. The data structure that holds those URLs and makes that decision is the URL frontier. Its design determines your politeness, your coverage, and how quickly useful data arrives. Most crawls go wrong in strategy long before they go wrong in code: they wander into infinite calendar pages, hammer one host while another waits, or spend half their budget on duplicate URLs.

Before building a frontier, check whether you need one. A sitemap or feed often lists every URL you want (see sitemaps and feeds), which turns discovery into reading a list.

The Core Loop#

Every crawler has the same parts: a queue of URLs to visit, a record of URLs already seen, and a depth for each URL. The loop pops a URL, fetches it, extracts links, filters and normalizes them, and pushes new ones with depth + 1.

from collections import deque
from urllib.parse import urljoin, urlsplit
import httpx
from lxml import html as lh

START = "https://example.com/"
ALLOWED_HOST = urlsplit(START).hostname
MAX_DEPTH = 4

client = httpx.Client(timeout=15.0, follow_redirects=True)
frontier = deque([(START, 0)])
seen = {START}

def extract_links(resp):
    tree = lh.fromstring(resp.content, base_url=str(resp.url))
    for href in tree.xpath("//a[@href]/@href"):
        url = urljoin(str(resp.url), href.strip())
        if urlsplit(url).scheme in ("http", "https"):
            yield normalize(url)          # from the URL handling lesson

while frontier:
    url, depth = frontier.popleft()
    resp = client.get(url)
    if "text/html" not in resp.headers.get("content-type", ""):
        continue
    handle_page(url, resp)
    if depth == MAX_DEPTH:
        continue
    for link in extract_links(resp):
        if urlsplit(link).hostname == ALLOWED_HOST and link not in seen:
            seen.add(link)
            frontier.append((link, depth + 1))

Details that matter:

• Mark URLs as seen when you enqueue them, not when you fetch them. Otherwise the same URL can enter the queue hundreds of times before it is first fetched, and the queue balloons.
• Resolve links against resp.url, not the requested URL. After a redirect, relative links are relative to the final location.
• Normalize before the seen check. Without it, /p?id=1&ref=nav and /p?ref=home&id=1 are different URLs to the set. The URL handling and normalization lesson covers which rules are safe.
• Stay in scope. The host check keeps the crawler from following links to the whole internet. Scope can also be a path prefix (/docs/) or a URL pattern.
• Use a deque. list.pop(0) is O(n) and becomes a real cost with a large frontier.

Breadth-First, Depth-First, and Best-First#

The order in which you pop URLs is the strategy.

BFS is the sensible default because it degrades gracefully: if you stop the crawl early, you have the pages closest to the start, which are usually the most linked and most important. Best-first is what production crawlers use, because it lets you encode what matters:

import heapq
import itertools
import re

counter = itertools.count()          # tie-breaker keeps insertion order stable
heap = []

def score(url, depth):
    s = depth * 10                   # lower score = fetched sooner
    if re.search(r"/product/\d+", url):
        s -= 50                      # detail pages hold the data we want
    if re.search(r"/(tag|author|print)/", url):
        s += 100                     # low-value listings last
    return s

def push(url, depth):
    heapq.heappush(heap, (score(url, depth), next(counter), url, depth))

def pop():
    _, _, url, depth = heapq.heappop(heap)
    return url, depth

The counter is not decoration: without it, two entries with the same score are compared by URL string, which changes the order in surprising ways and fails outright if a later field is not comparable.

The Two-Phase Crawl#

For list-and-detail sites (catalogues, directories, job boards), separate discovery from extraction:

1. Phase one walks category and listing pages only, collecting detail-page URLs into a persistent store without fetching them. This is a small number of requests.
2. Phase two fetches the detail pages from that store with your full concurrency setup.

The split has practical advantages: you know the total workload before phase two starts, progress is measurable, phase two can be resumed and parallelized easily with the patterns from caching and resume, and you can re-run only phase one daily to find new items.

Per-Host Politeness#

A single queue mixing many hosts has a subtle flaw: if the next ten URLs are all on one host, the crawler either violates its delay or sits idle, even though other hosts have work ready. The fix is a frontier keyed by host, where each host has its own queue and its own "next allowed time", and the scheduler always picks the host that is ready soonest.

import time
from collections import defaultdict

class HostFrontier:
    def __init__(self, delay=2.0):
        self.delay = delay
        self.queues = defaultdict(deque)
        self.next_ok = defaultdict(float)        # host -> earliest next fetch
        self.ready = []                          # heap of (next_time, host)

    def push(self, url, depth):
        host = urlsplit(url).hostname
        if not self.queues[host]:                # host was idle: schedule it
            when = max(time.monotonic(), self.next_ok[host])
            heapq.heappush(self.ready, (when, host))
        self.queues[host].append((url, depth))

    def pop(self):
        while self.ready:
            next_time, host = heapq.heappop(self.ready)
            wait = next_time - time.monotonic()
            if wait > 0:
                time.sleep(wait)                 # even the earliest host must wait
            url, depth = self.queues[host].popleft()
            self.next_ok[host] = time.monotonic() + self.delay
            if self.queues[host]:
                heapq.heappush(self.ready, (self.next_ok[host], host))
            return url, depth
        return None

Each host appears in the ready heap at most once, and only while it has queued URLs. next_ok remembers the last fetch even after a host's queue runs dry, so a host that receives a new URL a moment later is still made to wait out its delay. Popping gives the host whose delay expires first, so a crawl across fifty hosts runs at full speed while each individual host sees one request every delay seconds. A per-host delay can come from robots.txt's Crawl-delay, from observed response times, or from Retry-After headers (see rate limiting and politeness). In an async crawler, replace time.sleep with await asyncio.sleep.

Crawler Traps#

A trap is a part of a site that generates unlimited distinct URLs. Common ones:

• Calendars with "next month" links forever.
• Faceted navigation: every combination of filters and sort orders is a new URL. Ten filters with a few values each produce millions of combinations of the same products.
• Session ids or tracking parameters in URLs, making every visit unique.
• Relative-link bugs that produce ever-growing paths such as /a/b/a/b/a/b/.
• Search result pages linked from every page with different queries.

Defences, in order of effectiveness:

from urllib.parse import parse_qsl

def acceptable(url, depth):
    parts = urlsplit(url)
    if depth > MAX_DEPTH or len(url) > 300:
        return False
    segments = [s for s in parts.path.split("/") if s]
    if len(segments) > 8:
        return False                              # suspiciously deep path
    if len(segments) > 4 and len(set(segments)) <= len(segments) / 2:
        return False                              # /a/b/a/b/a/b/ repetition
    params = dict(parse_qsl(parts.query))
    if set(params) & {"sort", "order", "view", "sessionid", "print"}:
        return False                              # presentation-only variants
    if len(params) > 3:
        return False                              # facet combinations
    return True

Add a per-host page budget as a final safety net, and log the most common URL patterns every thousand pages. A pattern that suddenly dominates the frontier (/events/2031/…, ?color=…&size=…) is almost always a trap. The page's <link rel="canonical"> is also useful: if many URLs declare the same canonical URL, they are variants, and you only need one.

Content-Level Deduplication#

URL deduplication cannot catch different URLs serving the same content (/item/42 and /item/42/, http and https, mirrors). Hash the extracted main content, not the full HTML, which differs in timestamps and ads, and skip link extraction for pages whose hash you have already seen. That stops duplicates from multiplying through their outgoing links.

Selection Policy Is Your Product#

Whatever you prioritise (new items first, high-value categories, pages that changed recently), put that logic in one place, the score function or the frontier's pop rule, and keep the main loop simple. Log the frontier size, per-host queue lengths, and pages fetched per URL pattern. When a crawl misbehaves, those numbers show whether the problem is the policy, a trap, or a single slow host.

Practice#

Crawl a small site you control, or a local mirror, three times: with BFS, with DFS, and with a best-first score favouring detail pages. Stop each run after 200 pages and count how many detail pages each strategy reached. Then add a calendar page with infinite "next month" links and confirm the trap filter stops it.