Detecting Crawler Traps by Budget per Host

A crawler that discovers new URLs faster than it fetches them never finishes. The frontier grows without bound, memory or disk fills, and the fraction of the crawl that has been fetched tends toward zero. This is not a pathological case confined to adversarial sites. A calendar that links to the next month, a forum with pagination and a sort parameter, a search page that returns links to its own search results, a session identifier appended to every internal link — each generates URLs faster than any polite crawler can consume them.

A trap in the strict sense is a URL space with a productive rule that has no terminal condition. A trap in the practical sense is any site whose contribution to the frontier outgrows its contribution to the index. The same accounting detects both, and the detection has to happen early enough that the wasted fetches stay bounded.

The shapes of the problem

Calendar and pagination generators. A date-based archive that offers “next month” from every month page produces an infinite chain of future months, all returning either a 404 or an empty listing. Pagination with an unbounded page number has the same form. The distinguishing feature is that the URLs are sequential and the content is either empty or repetitive; a bounded generator stops, but the crawler cannot tell from one page whether the chain continues.

Session and tracking identifiers. Every link carries ?sid= or ?ref=, and every page generates a fresh value, so no two URLs in the crawl are equal. The site is finite; the URL space is not. This case defeats string-based deduplication entirely, and it also defeats the frontier’s memory bound, because each URL is legitimately new by any syntactic test — the only partial defence is normalization that removes the parameters the site does not use for routing.

Parameter permutations. A page with five filter parameters that each accept several values exposes the full product of their combinations. A URL with parameters in any order multiplies that product again unless the crawler orders them. The content behind most combinations is a subset or superset of the unfiltered listing, so the crawl pays full price for pages with no unique content.

Mirror and alias loops. A site reachable under several hostnames, each linking to the others, produces cycles that revisit the same content under different authorities. Per-host deduplication does not catch these because the keys differ, and per-URL deduplication does not catch them because the strings differ.

Deep link graphs with no back edges. A directory tree that links only downward from a root page, with a large branching factor, expands as b^depth. At b = 20 and depth 5 that is 3.2 million URLs from a site that may have only a few thousand pages worth indexing.

Why URL-level deduplication is not enough

The frontier’s dedup set answers one question: have I seen this exact normalized URL before. For the calendar case it answers “no” forever, because each month is a distinct URL. For the session case it answers “no” forever for the same reason. Dedup bounds the crawl only when the URL space is finite and the crawler’s normalization collapses the aliases, and traps are exactly the cases where one of those fails.

The additional signal needed is per-site accounting: how many URLs this authority has contributed, how many have been fetched, how many produced content that was actually new. A site that has contributed ten thousand URLs and yielded fifty distinct documents is not a site worth continuing at the current rate. The ratio is the trap signal, and it requires tracking the association between a URL and the site that produced it, which the frontier already has through its host binding.

The subtlety is what “new content” means. Comparing raw bytes marks every page with a rotating banner as new. Comparing extracted text or a digest of the main content is closer, and comparing against the index rather than against the crawl’s own store is closer still, since the index is what the crawl is for. A site whose pages all reduce to the same template and a different item name may be worth crawling deeply if the items are the point, and worthless if the template is.

Budget accounting that terminates

The mechanism that works is a per-host budget with two counters and a ratio test, evaluated after every fetch from that host.

class HostBudget:
    def __init__(self, limit=5000, min_yield=0.05, window=200):
        self.limit = limit          # hard cap on URLs fetched from this host
        self.min_yield = min_yield  # fraction of useful pages required
        self.window = window
        self.fetched = 0
        self.useful = 0
        self.recent = []            # booleans, most recent last

    def record(self, useful):
        self.fetched += 1
        if useful:
            self.useful += 1
        self.recent.append(bool(useful))
        if len(self.recent) > self.window:
            self.recent.pop(0)

    def exhausted(self):
        if self.fetched >= self.limit:
            return True
        if len(self.recent) >= self.window:
            return sum(self.recent) / len(self.recent) < self.min_yield
        return False

Two design choices in that sketch matter more than the constants. The windowed ratio, rather than the lifetime ratio, lets a site recover: a site that was deep in a trap but has now started yielding real pages is judged on its recent behaviour. The hard cap, rather than only a ratio, bounds the damage when the ratio never falls — a site that generates infinite unique content passes every yield test and still must be stopped.

The cap should be generous enough that a legitimately large site is not truncated. A site with a hundred thousand pages and a five-thousand-URL cap is a site the crawler will never index fully, and the cap turns a completeness problem into a silent omission. The usual resolution is to set the cap from the crawl’s overall budget divided by the number of authorities it intends to cover, then to raise it for sites that demonstrate high yield.

Detecting the generator rather than the instance

Ratio accounting is retrospective: it notices a trap after the crawler has already spent budget inside it. Detecting the shape of the URL space is prospective, and it is cheaper because it works on the URL strings before any fetch.

Three cheap tests catch most generators:

• Depth. The number of path segments beyond the entry point. A crawl that follows links more than a fixed number of segments deep from any seed is usually in a generated space, and the limit can be per-site rather than global.
• Repetition. The same path segment repeated — /a/a/a/ — or a path whose segments are monotonically increasing integers or dates. A pattern that matches a known generator form can be capped without fetching.
• Parameter cardinality. The number of distinct values observed for one parameter name on one site. A parameter that has taken ten thousand distinct values is either a session token or a search query, and in both cases the crawl should not enumerate it.

The tests are heuristics and will sometimes reject real content. A site with a genuine deep hierarchy of product categories will look like a depth trap; a site with a legitimate large parameter space, such as a library catalogue with a numeric item identifier, will look like a session trap. That is why the tests should cap contribution to the frontier rather than forbid fetching: a capped URL is deferred, and if the site’s yield is high the cap rises.

Traps that the crawler creates for itself

Some traps are not on the site at all.

A crawler that follows rel="next" and rel="prev" links without recognizing that they form a cycle will loop on a two-page set forever unless deduplication is exact. A crawler that treats a redirect chain as a set of new URLs will expand one target into every alias that points at it. A crawler that re-fetches after a soft 404 — a 200 response with an error page body — will count the same dead URL as a fresh page each time it is rediscovered, because the dedup set keyed on URL does not record that the URL was a dead end.

Soft 404 detection is worth separating from trap detection because the mechanisms differ. A soft 404 is recognized by the content, not by the URL: a page whose text matches the site’s error template, or whose title is the site’s generic not-found title, is a dead end regardless of status. Recording that verdict in the frontier prevents the URL from re-entering the queue, which is what stops a site with a large set of dead links from consuming budget on every pass.

Redirect loops are the other self-inflicted case. Following redirects is required to reach content, and a chain that returns to its own start is a cycle the crawler must detect by remembering the visited set within a single fetch, not across the crawl. The bound on chain length is the backstop: a crawler that follows at most a small number of hops and treats longer chains as failures avoids spending unbounded requests on a site whose redirect configuration is broken.

What the budget does to coverage

Every mechanism described here reduces the crawl’s coverage of some site. The question that makes the reduction acceptable is whether the omitted pages would have contributed distinct documents to the index. For a calendar trap, the answer is no — the omitted months are empty. For a session trap, the answer is no — the omitted URLs are aliases of pages already fetched. For a depth trap on a large real site, the answer may be yes, and that is the case where the budget is genuinely lossy.

The mitigation is to make the omission visible rather than silent. A crawl that records, per host, how many URLs were deferred by a cap and how many were fetched gives an operator the information to raise a cap for a site that mattered. A crawl that quietly stops at five thousand URLs gives no such signal, and the loss surfaces later as a recall complaint with no traceable cause.

The other half of the coverage problem is the frontier’s growth rate relative to the fetch rate, which is a property of the whole crawl rather than of one site. When discovery outpaces fetching, the frontier accumulates URLs that will never be fetched before the crawl’s deadline, and the ordering among them decides what is lost. That is a scheduling question with its own economics, and it is where the choice of which URLs to prefer stops being about correctness and starts being about what the index is for.