The Crawl Frontier Is a State Machine, Not a Queue

Direct answer: crawl frontier design

Reliable crawl frontier design models each URL as a versioned state transition across discovery, admission, scheduling, fetching, retry, suppression, and completion while keeping URL identity, origin politeness, leases, budgets, and evidence records explicit and replayable.

Original research artifact

A typed frontier-transition schema, lifecycle table, origin scheduler contract, and crawl-budget gap record.

What this page adds

Move beyond queue tutorials by defining identity, state invariants, host scheduling, crawl-trap bounds, and recovery evidence together.

Related research

• is robots.txt access control
• SQLite web crawler
• internal linking graph

Define URL identity before scheduling work

The first frontier decision is not priority; it is whether two references identify the same work item for this crawler. RFC 3986 permits syntax-based normalization such as lowercasing the scheme and host, normalizing percent-encoding for unreserved characters, and removing dot segments. It does not authorize arbitrary product decisions such as deleting query parameters, lowercasing a case-sensitive path, or treating a trailing slash as equivalent on every server.

Keep three fields instead of collapsing them into one string: the discovered reference exactly as observed, the absolute resolved URL used for the request, and a comparison key produced by documented crawler rules. This preserves evidence when an aggressive rule proves wrong. A parameter classifier can later mark a key as tracking-only, order-sensitive, content-bearing, or unknown without rewriting the captured source.

Fragments usually do not cause a new HTTP retrieval, but the fragment can still matter as evidence about in-page navigation. Store it on the discovered edge while excluding it from the fetch key. User information, unsupported schemes, malformed ports, and out-of-scope hosts should produce named rejection states rather than disappearing during parsing.

Model lifecycle states, not queue positions

A single pending flag cannot distinguish a URL that is waiting for its host window from one paused by robots policy, one awaiting a retry, and one rejected by scope. Use named lifecycle states such as discovered, admitted, scheduled, fetching, fetched, retryable, suppressed, and terminal. The exact vocabulary can differ, but every state needs an entry condition, an allowed successor set, and an invariant that can be checked.

Transitions should be append-only events keyed by run, URL identity, attempt, and timestamp. The materialized current state is a projection that can be rebuilt. This protects the crawler from the common failure where a worker crashes between updating a row and recording the response artifact. It also makes recovery conservative: a stale fetching lease can return to scheduled while a terminal response cannot be fetched again without an explicit new attempt or run.

Use leases rather than permanent ownership. A worker claims a scheduled item until a deadline and renews only while it is doing useful work. If the process disappears, the frontier can reclaim the item and retain the abandoned attempt. The record then shows that two attempts occurred instead of pretending that one continuous request existed.

Schedule capacity at the origin boundary

A global FIFO queue lets one large host dominate workers and makes politeness an afterthought. Partition eligible work by origin, where origin includes scheme, host, and port. Give each partition a concurrency ceiling, minimum interval, next-eligible time, and recent response-health record. A global scheduler can then select among origins while the origin scheduler selects the next URL.

Rate is only one dimension. A host returning fast successful responses may tolerate more concurrency than one returning timeouts or server errors, but an adaptive controller should move slowly and remain bounded. Apply backoff to the origin after transport failures, 429 responses, or repeated 5xx responses; do not punish unrelated origins. Persist the decision inputs so the same response history can reproduce the scheduling decision.

Robots policy belongs before dispatch, not inside the response parser. Cache the host-scoped policy with retrieval time, status, expiry, and parser version. RFC 9309 defines protocol behavior, including handling of access failures and caching, but an operator may choose a more conservative local policy. Record that choice separately from the standard-derived parse result.

• Use a fair origin selector so a deep host cannot starve smaller hosts.
• Apply random jitter within a bounded window to avoid synchronized retry bursts.
• Cap both per-origin concurrency and total active sockets.
• Re-evaluate host policy when a cached robots record expires or changes.
• Treat server health as a scheduling input, not as evidence about page quality.

Bound the address space before it becomes a crawl trap

The web graph can be finite in content and effectively infinite in URLs. Calendars can generate one month forever; faceted navigation can permute filters; sort orders can multiply equivalent inventories; session identifiers can create a new address per visit; and internal search can expose an unbounded query space. A crawler that discovers until the queue is empty has no meaningful stop condition in those environments.

Set independent budgets for total accepted URLs, depth, query-key combinations, path patterns, per-host pages, redirect hops, response bytes, render time, and wall-clock duration. A budget breach should produce a gap record containing the rule, affected pattern, first example, and count suppressed. This is materially different from silently truncating the crawl and later describing the sampled set as the site.

Trap detection is a classification problem with asymmetric costs. An overbroad rule can erase a valid product dimension; an underbroad rule can consume the run. Begin with reversible deferral, group candidates by structural signature, and promote a rule only after examples show which address components change content. Keep allow exceptions narrower and more explicit than the rule they override.

Retry only when the next attempt can mean something

A retry policy should answer three questions: is the failure plausibly transient, when is the next attempt eligible, and how many attempts can still occur? DNS timeouts, connection resets, 429 responses, and many 5xx responses can be retryable. A stable 404, a scope rejection, or a robots denial generally needs a new run or policy change rather than immediate repetition. Preserve the original response and error even when a later attempt succeeds.

Use exponential backoff with bounded jitter and a maximum delay. Honor an applicable Retry-After value within local safety limits. Store the classification rule and the computed next time, because a timestamp without its reasoning is not replayable. When the attempt budget is exhausted, transition to a terminal failure that remains visible in coverage reports.

The frontier is complete when every admitted item is terminal or represented by an explicit unresolved state, not when no worker is busy. A run summary should reconcile counts across discovery, deduplication, suppression, fetch, retry, and failure states. That accounting identity is the crawler equivalent of balancing a ledger: if accepted URLs cannot be traced to final states, the crawl report is not ready to support a site-wide claim.

type FrontierTransition = {
  runId: string;
  fetchKey: string;
  attemptId: string;
  from: FrontierState;
  event: string;
  to: FrontierState;
  occurredAt: string;
  policyVersion: string;
  evidenceRef?: string;
  reason: string;
};