Web Crawler: the frontier, duplicate detection and robustness

The crawl loop from Web Crawler: requirements, scale and the crawl loop is easy to draw. The hard parts are the three things the estimate pointed at: politeness, deduplication state across billions of URLs, and surviving the hostile web. This lesson takes them in that order.

It starts with the frontier. The frontier looks like a queue and is not one. It must satisfy two requirements that pull in opposite directions, and the two-level structure that resolves them is the central idea of the design.

The frontier's two requirements

Priority. Not all URLs are equally worth fetching. A news site's front page deserves recrawling every few minutes; a dormant forum thread deserves once a year. Priority is derived from signals like inbound link count, historical change rate, and site importance.

Politeness. No more than one request in flight to a single host, with a delay between requests to that host.

A single priority queue satisfies the first and violates the second catastrophically. Consider what happens: the highest-priority URLs at any moment are frequently from the same important site, so a strict priority queue hands the fetchers fifty URLs from one host in a row, and they fetch them in parallel. That is a small denial-of-service attack on a site you wanted to stay friendly with.

Conversely, one queue per host satisfies politeness and loses priority entirely — you would round-robin across millions of hosts with no notion of what matters.

The two-level structure

Front queues — priority.

• A prioritiser assigns each incoming URL a priority level, 1 to f (say 5).
• There are f front queues, one per level.
• A front queue selector picks a queue to read from, biased towards higher priorities — for example by weighted random selection, so high-priority URLs are fetched much more often while low-priority ones are not starved forever.

Back queues — politeness.

• There are b back queues, where b is large — thousands.
• A mapping table records which host is assigned to which back queue. Every URL for a given host goes to exactly one back queue, and each back queue holds URLs for a small number of hosts.
• A back queue router takes URLs from the front queue selector and places each into the back queue for its host, creating an assignment if the host is new.
• A back queue selector decides which back queue a free worker should read from next, using a priority queue (heap) of (next-fetch-time, queue-id) entries. A worker takes the entry with the earliest time; if that time is in the future, it waits.
• After fetching, the worker computes the next permitted time for that host — now plus the politeness delay, which is Crawl-delay from robots.txt if present and a default such as one second otherwise — and reinserts the entry into the heap.

Because each host maps to exactly one back queue, and each back queue is served by at most one worker at a time, only one request per host is ever in flight. Politeness is a structural property, not something enforced by checking.

Sizing and distributing the frontier

The frontier holds billions of URLs. It cannot be in memory: 10 billion URLs at 100 bytes is 1 TB.

The standard arrangement is hybrid: keep the head of each queue in memory as a buffer, and back the rest with disk or a distributed store. Workers read from the in-memory buffer, which is topped up from durable storage in the background. The frontier is checkpointed periodically so a crash loses minutes of progress rather than everything (see checkpointing, below).

Distribute the frontier by hashing the hostname, so all URLs for one host land on the same frontier server. That preserves the one-host-one-queue property across machines with no coordination between them — which is exactly the property that makes distributing this component possible at all.

The politeness arithmetic worth stating

At one request per host per second, a site with 1 million pages takes:

1,000,000 seconds = 11.6 days to crawl completely.

That single figure explains why crawlers prioritise, why they recrawl selectively, and why Crawl-delay values of 10 seconds effectively put a large site out of reach. Say it — it turns politeness from a courtesy into a scheduling constraint with a number attached.

Duplicate detection: URLs and content

The second hard part is deduplication state. Two different questions get asked at two different points in the loop, and conflating them is a common error. "Have I seen this URL?" and "have I seen this content?" need different mechanisms.

URL normalisation comes first

Before any comparison, canonicalise the URL, or you will store the same page many times:

• Lowercase the scheme and host; strip the default port (:80, :443).
• Remove the fragment (#section) — it never reaches the server.
• Sort query parameters, and strip known tracking parameters such as campaign identifiers.
• Resolve . and .. path segments; decide a consistent policy on trailing slashes.

Skipping this step means Example.com/a?b=1&c=2 and example.com/a?c=2&b=1#top are treated as two different pages.

Exact content duplicates: hashing

Compute a cryptographic hash (SHA-256, say) of the normalised page content and keep a set of hashes. Identical content produces an identical hash, so the second copy is dropped.

This catches the common case: the same page served under www and non-www, under HTTP and HTTPS, or through a mirror. It catches nothing where a single byte differs — a timestamp, a rotating advertisement, a visitor counter.

Near-duplicates: SimHash

SimHash produces a fingerprint with a property ordinary hashes lack: similar documents produce similar fingerprints. The mechanism, briefly: extract features (words or shingles) from the document, hash each to a fixed width such as 64 bits, sum the bit positions weighted by feature frequency (+1 for a set bit, −1 for a clear one), and take the sign of each column as the fingerprint bit.

Two documents are considered near-duplicates when their fingerprints differ in at most a small number of bit positions — the Hamming distance — with a threshold of around 3 bits out of 64 being the commonly cited operating point. That catches pages differing only by an advertisement or a date while distinguishing genuinely different articles.

The cost is that finding near matches is not a hash lookup — you must search for fingerprints within a small Hamming distance, which requires an index built for that (typically by permuting and partitioning the fingerprint bits into blocks and looking for exact block matches). Mention that the lookup is the hard part; it is the detail that shows you have thought past the concept.

The seen-URL set: Bloom filters

Why it is needed here: Requirements and scale established 10 billion known URLs, which at 100 bytes each is 1 TB — not something you keep in memory, and a disk lookup per extracted link is far too slow at 385 pages per second producing tens of links each.

The arithmetic. The optimal bits per element for a target false-positive rate p is approximately −log₂(p) / ln 2 ≈ 1.44 × log₂(1/p):

Twelve gigabytes for a 1% error rate against 1 TB for exact storage — a factor of 80.

What a false positive costs. The filter says "seen" for a URL that was never crawled, so that page is never fetched. At 1% across 10 billion URLs, that is 100 million pages silently missed. At 0.1% it is 10 million, for 6 GB more memory. Since the cost of the error is permanent invisibility rather than a retry, choose the lower rate — this is a case where the cheap option is the wrong one, and being able to say why is the point of the arithmetic.

Note also that a Bloom filter cannot delete, so a URL can never be un-seen. Systems that need that use a counting variant or rebuild the filter periodically from the authoritative metadata store.

Distributing it: shard by hash of the URL, so each machine holds the filter for its slice, and the extractor routes a lookup to the right shard. Keep the authoritative set of crawled URLs in the metadata database so the filter can be rebuilt.

Robustness: surviving the open web

The third hard part is the web itself. It is adversarial and broken in equal measure, and handling it is what separates a crawler that runs for a week from one that runs for a year.

Crawler traps and infinite URL spaces

A crawler trap is a site structure that generates unlimited valid URLs. They are usually accidental:

• Calendars. /events?month=2027-03 links to April, which links to May, forever. Every page is a valid 200 response with real links. A naive crawler follows them until the heat death of the site.
• Session identifiers in URLs. Every visit produces a new identifier, so every page appears new on every fetch and the seen-URL check never fires.
• Faceted navigation. A shop with 10 filters of 10 values each generates 10^10 URL combinations, all valid, all nearly identical.
• Deliberate traps. Some sites generate endless nonsense pages specifically to punish crawlers that ignore robots.txt.

Defences, applied together:

1. Depth limit. Cap link depth from the seed, typically at a modest number. Cheap and effective.
2. Per-host page cap. No more than N pages from one host per crawl cycle. This is the single most effective defence, because every trap is confined to one host.
3. URL length and parameter caps. Reject URLs above a length threshold or with more than a handful of query parameters — trap URLs grow.
4. Pattern detection. Watch for a host producing large numbers of near-duplicate pages (via the SimHash check above) and demote or blocklist it automatically.
5. A blocklist, maintained partly by hand. Unglamorous, and every real crawler has one.

Timeouts, retries, and hostile responses

• Connect timeout of a few seconds and read timeout of tens of seconds. Without them, a server that accepts a connection and never responds holds a worker forever, and enough of those halt the crawl.
• Response size cap. Stop reading past a few megabytes. A server can stream indefinitely.
• Redirect limit. Follow at most a handful, and detect redirect loops.
• Retries on 5xx and network errors, with exponential backoff and jitter (Reliability patterns), capped at two or three attempts. Do not retry 4xx — the page is not coming back, and retrying 404s at scale is a meaningful waste.
• Honour 429 and Retry-After (Response behaviour and follow-ups, Section 6). A site telling you to slow down is doing you a favour; ignoring it gets you blocked.
• Trust content type, not extension. A URL ending .html can return an 800 MB video.

Checkpointing

The frontier is the crawler's most valuable state: it encodes everything discovered and not yet fetched. Losing it means restarting from seeds and rediscovering billions of URLs.

Checkpoint it. Persist the frontier's queues, the host-to-queue mapping, and the next-fetch times to durable storage every few minutes, and write the seen-URL set's authoritative form to the metadata database continuously so the Bloom filter can be rebuilt. On restart, load the last checkpoint and resume. The cost is bounded and known: a five-minute checkpoint interval means a crash loses at most five minutes of progress, which at 385 pages per second is about 115,000 pages — recoverable, because they are still in the frontier.

Make workers stateless and idempotent so that a crashed fetch is retried harmlessly: a URL whose worker died is refetched, and the content-seen check absorbs the duplicate.

Freshness and recrawl scheduling

Recrawling everything at one rate is the wrong design. Pages change at wildly different rates, and crawl capacity is finite.

The practical approach is adaptive scheduling: record how often each page's content hash actually changed across previous crawls, and set its next crawl interval from that history — frequently changing pages get short intervals, stable pages get long ones. Combine with page importance, so a high-traffic page that changes weekly is still checked more often than an obscure page that changes weekly.

Two mechanisms make this much cheaper:

• Conditional requests. Send If-Modified-Since or If-None-Match with the stored Last-Modified or ETag. A server that responds 304 Not Modified sends no body, so the fetch costs a round trip and a few hundred bytes instead of 500 KB. On a recrawl-heavy workload this can cut bandwidth by a large factor — the exact saving depends on how many pages actually changed, so measure rather than assume.
• Sitemaps. Many sites publish an XML file listing their URLs with last-modified dates. Reading it is far cheaper than discovering the same URLs by traversal, and it surfaces pages that are not linked from anywhere crawlable.