How does a web crawler avoid crawling the same page twice?

It normalises each URL first, so case, fragments, default ports, dot-segments and parameter order stop creating false differences, then checks a seen-set such as a fingerprint table or a Bloom filter. For different URLs that serve the same page, it compares a content hash for exact copies and a simhash for near copies. Each layer trades memory against the chance of a missed or wrongly skipped page.

What does a polite web crawler do about robots.txt?

It fetches robots.txt before anything else on a host and applies RFC 9309: the most specific matching rule wins, a 4xx response means no rules apply, and a 5xx or unreachable file means assume complete disallow. The RFC says not to use a cached copy for more than 24 hours unless the file is unreachable. RFC 9309 does not define Crawl-delay, so per-host rate limits are the crawler's own policy.

What is a crawler trap and how do you avoid it?

A crawler trap is a part of a site that generates an effectively endless set of URLs, such as a calendar with a next-month link that never ends or session IDs in every address. Because each URL is genuinely new, URL dedup cannot stop it. Cap crawl depth, set a page budget per host, limit URL length and demote hosts whose new pages are mostly duplicates by content hash.

Design a Web Crawler: URL Frontier, robots.txt and Dedup

Q: How do you design a web crawler that scales?

Build a URL frontier with priority queues in front and one politeness queue per host behind them, then add robots.txt handling, URL normalisation, content fingerprinting, DNS caching and budgets against crawler traps. Size it from pages per second: queues needed equal pages per second times the per-host gap, and bandwidth equals pages per second times average page size. Schedule recrawls by how often each page actually changes.

Q: What is a URL frontier in a web crawler?

The URL frontier is the data structure that decides which URL to fetch next. In the design described in the Stanford IR book, front queues implement prioritisation and back queues implement politeness, with each back queue holding URLs from one host only. A heap of earliest-allowed times tells workers which host may be contacted next.

How do you design a web crawler that scales? A worked design: URL frontier, robots.txt under RFC 9309, dedup, DNS caching, crawler traps and recrawl scheduling.

Key Takeaway

To design a web crawler that scales, split the URL frontier into priority queues and per-host politeness queues, obey robots.txt under RFC 9309, normalise URLs and fingerprint content to skip duplicates, cache DNS, cap crawler traps with depth and host budgets, and schedule recrawls by observed change rate. Size everything from pages per second.

The first version of a crawler is always a loop: pop a URL, fetch it, extract links, push them back. It works on a demo site and fails on the real web in four predictable ways. It hammers one host, it fetches the same page under six addresses, it wanders into a calendar that never ends, and it goes stale the moment it finishes.

This is a worked design, not a benchmark report, and I have not run a billion-page crawler. Every number below is derived from assumptions stated up front, the protocol facts come from RFC 9309, RFC 3986 and the Stanford IR book, and the one piece worth building first on a single VPS, the politeness queue, is written out in TypeScript and was run against a few URLs to check its behaviour.

What does a web crawler have to do, and how big is it?

A crawler is four loops joined together: choose a URL, fetch it politely, extract links and content, then decide what to fetch next and when to fetch the page again. Scale comes from the arithmetic of the whole loop, so write the assumptions down first. Here the crawler must keep a billion-page index fresh, where 10% of pages change daily, 30% weekly and 60% monthly.

Assumed inputs (a design exercise, not a measurement):
  index size              = 1,000,000,000 pages
  average page (HTML)     = 100 KB
  fetch latency           = 0.5 s (DNS cached, connection setup included)
  change classes          = 10% daily, 30% weekly, 60% monthly (30 days)
  stored copy, compressed = 25% of raw

Fetches per day (every page revisited at its own cadence)
  daily class   = 100,000,000 / 1  = 100,000,000
  weekly class  = 300,000,000 / 7  =  42,857,143
  monthly class = 600,000,000 / 30 =  20,000,000
  total                            = 162,857,143 per day

Rate
  average pages / s        = 162,857,143 / 86,400 = 1,885
  connections in flight    = 1,885 x 0.5 s        = 942   (Little's law: rate x latency)
  bandwidth                = 1,885 x 100 KB       = 188.5 MB/s = 1.51 Gbit/s
  raw ingest per day       = 162,857,143 x 100 KB = 16.3 TB

Storage
  snapshot, raw            = 1e9 x 100 KB = 100 TB
  snapshot, compressed     = 100 TB x 25% = 25 TB

The shape of the result matters more than the digits. The 10% of pages that change daily generate 100 million of the 162.9 million daily fetches, about 61%, so the recrawl policy rather than discovery sets your bill. And 942 connections in flight means the fetchers mostly wait on the network, which is why they run well as many lightweight workers instead of a few heavy ones.

These are assumptions I chose for a design exercise, not measurements of any real crawler. Change one and the block recomputes in a minute: halve the average page to 50 KB and the bandwidth halves to about 94 MB/s, and double the revisit frequency of every class and the fetch rate doubles.

How does a URL frontier decide what to fetch next?

The URL frontier is the data structure that answers what to fetch next. The Stanford IR book splits it in two: front queues implement prioritisation and back queues implement politeness. A prioritiser assigns each URL an integer from 1 to F, for example from how often the page has changed, and URLs flow from the front queues into back queues, each of which holds URLs from a single host only.

The back queues are paired with a heap holding the earliest time each host may be contacted again. A worker takes the root, waits if needed, fetches, then reinserts the queue with a new time. The book suggests a gap of about ten times the duration of the last fetch from that host. The snippet below is a stripped version of that idea: one queue per host, a minimum gap, the 10x rule, and a dispatched host marked unavailable until done is called, so two workers can never hit it at once.

type HostQueue = { host: string; urls: string[]; nextAllowedAt: number };

export class PolitenessScheduler {
  private hosts = new Map<string, HostQueue>();
  private minGapMs: number;
  private gapFactor: number;

  // Gap after a fetch = max(minGapMs, gapFactor x how long that fetch took).
  constructor(minGapMs = 1000, gapFactor = 10) {
    this.minGapMs = minGapMs;
    this.gapFactor = gapFactor;
  }

  enqueue(url: string): void {
    const host = new URL(url).host;
    const q = this.hosts.get(host) ?? { host, urls: [], nextAllowedAt: 0 };
    q.urls.push(url);
    this.hosts.set(host, q);
  }

  // Returns a URL, or how long to sleep, or null when everything is drained.
  // Linear scan for clarity; at scale this is a min-heap keyed on nextAllowedAt.
  next(now: number): { url: string } | { waitMs: number } | null {
    let earliest = Infinity;
    for (const q of this.hosts.values()) {
      if (q.urls.length === 0) continue;
      if (q.nextAllowedAt <= now) {
        // In flight: unavailable until done() runs, so two workers never share a host.
        q.nextAllowedAt = Infinity;
        return { url: q.urls.shift()! };
      }
      earliest = Math.min(earliest, q.nextAllowedAt);
    }
    return earliest === Infinity ? null : { waitMs: earliest - now };
  }

  done(url: string, fetchMs: number, now: number): void {
    const q = this.hosts.get(new URL(url).host);
    if (!q) return;
    q.nextAllowedAt = now + Math.max(this.minGapMs, this.gapFactor * fetchMs);
    if (q.urls.length === 0) this.hosts.delete(q.host);
  }
}

// Run against a.com/1, a.com/2, b.com/1 with a 500 ms fetch finishing at t = 500:
//   next(0)    -> a.com/1          next(0)    -> b.com/1       next(0) -> null
//   next(600)  -> { waitMs: 4900 } (a.com is cooling down for 5,000 ms)
//   next(5500) -> a.com/2

Now size it. The back-queue count is where a frontier quietly fails, so derive it from rate and gap before choosing a number.

Politeness gap = 10 x 0.5 s fetch = 5 s  ->  each host serves 1 / 5 = 0.2 pages per second

Back queues needed         = 1,885 pages/s x 5 s   = 9,425
Mercator rule of thumb     = 3 x 942 threads       = 2,826 queues
  what those can sustain   = 2,826 x 0.2           =   565 pages/s  (30% of the target)
With a fixed 1 s gap       = 1,885 pages/s x 1 s   = 1,885 queues

The block exposes a sizing trap. The Mercator rule of thumb quoted in the book is about three back queues per crawler thread, but with a 10x gap that ratio is too small for this workload: 2,826 queues sustain only 565 pages per second, 30% of the 1,885 target. Size the queue count from rate times gap, then check it against the number of distinct hosts you actually have ready, because a frontier full of one big site starves everything else.

Sizing rule: back queues needed equals target pages per second times the politeness gap in seconds. Check it before anything else, because a frontier that is too narrow looks exactly like a slow network.

How should a crawler handle robots.txt?

robots.txt is the first request to any host, and RFC 9309 defines what a crawler must do with each possible answer. Fetch it before anything else on that host, cache the result, and treat the response status as part of the rules rather than an error to retry blindly.

Response	What RFC 9309 says	What the crawler does
2xx, file found	Parse it; the parsing limit MUST be at least 500 kibibytes	Apply the group for your product token, else the star group; the longest matching rule wins
3xx, redirect	SHOULD follow at least five consecutive redirects	Follow up to five hops; beyond that the file MAY be treated as unavailable
4xx, unavailable	The crawler MAY access any resources on the server	Crawl as if no rules exist
5xx or unreachable	The crawler MUST assume complete disallow	Fetch nothing from that host until a robots.txt request succeeds

Matching is by specificity: the match with the most octets MUST be used, and the user-agent group is chosen by case-insensitive product token, falling back to the star group. The RFC says crawlers SHOULD NOT use a cached copy for more than 24 hours unless the file is unreachable, so schedule a refresh rather than caching forever. In the example below, Allow /cart/help (10 octets) beats Disallow /cart/ (6 octets).

# https://shop.example/robots.txt
User-agent: MWBot
Disallow: /cart/
Allow: /cart/help
Disallow: /search

User-agent: *
Disallow: /private/

Sitemap: https://shop.example/sitemap.xml

# MWBot asks for /cart/help: Allow (10 octets) beats Disallow /cart/ (6 octets) -> allowed.
# MWBot asks for /cart/items: only Disallow /cart/ matches -> blocked.
# Any other bot falls back to the * group: /private/x is blocked, /search is allowed.

RFC 9309 does not define Crawl-delay, so a per-host delay is your own policy rather than part of the protocol; the gap from the frontier section is where that policy lives. Parse only what you must, too: the limit is at least 500 kibibytes, so a larger file can be truncated by the crawler.

robots.txt is a convention for cooperating crawlers, not access control. The file is public and lists exactly the paths its owner wanted left alone, so anything that must stay private needs authentication, not a Disallow line.

How do you avoid crawling the same page twice?

Two questions hide here: have I seen this address, and have I seen this content under another address. Answer the first cheaply and early with URL normalisation. RFC 3986 defines equivalences a plain string comparison misses: scheme and host are case-insensitive, an empty path is equivalent to a single slash, dot-segments are resolved, a default port can be dropped, and percent-encoded unreserved characters such as %7E and the tilde identify the same resource.

const DROP_PARAMS = /^(utm_[a-z]+|fbclid|gclid|sessionid|phpsessid)$/i;

// RFC 3986 section 6.2.2.2: %7E and ~ are the same resource, and hex digits are
// case-insensitive. The URL parser leaves both alone, so do it by hand.
const UNRESERVED = /[A-Za-z0-9._~-]/;
function normalisePercent(s: string): string {
  return s.replace(/%([0-9a-fA-F]{2})/g, (_, hex: string) => {
    const ch = String.fromCharCode(parseInt(hex, 16));
    return UNRESERVED.test(ch) ? ch : "%" + hex.toUpperCase();
  });
}

export function normaliseUrl(raw: string, base?: string): string | null {
  let u: URL;
  try {
    u = new URL(raw, base); // resolves relative links against the page they came from
  } catch {
    return null;
  }
  if (u.protocol !== "http:" && u.protocol !== "https:") return null; // mailto:, javascript:

  u.pathname = normalisePercent(u.pathname);
  u.hash = "";      // fragments never reach the server
  u.username = "";
  u.password = "";

  const kept = [...u.searchParams.entries()]
    .filter(([name]) => !DROP_PARAMS.test(name))
    .sort(([a], [b]) => (a < b ? -1 : a > b ? 1 : 0));
  u.search = "";
  for (const [name, value] of kept) u.searchParams.append(name, value);

  return u.href;
}

// normaliseUrl("HTTP://Example.COM:80/a/./b/../c?b=2&utm_source=x&a=1#top")
//   -> "http://example.com/a/c?a=1&b=2"
// normaliseUrl("https://example.com")                 -> "https://example.com/"
// normaliseUrl("../x?z=1&a=2", "https://example.com/p/q/r")
//   -> "https://example.com/p/x?a=2&z=1"
// normaliseUrl("https://example.com/%7euser/%e4")     -> "https://example.com/~user/%E4"
// normaliseUrl("mailto:a@b.c")                        -> null

The platform URL parser handles the host case, the default port, dot-segments and the empty path. The snippet adds the three things it does not: percent-escape normalisation, dropping a short list of tracking and session parameters, and sorting the remaining parameters so two orderings collapse into one. The drop list is a policy choice. Removing a parameter that really changes the page loses content, so grow the list from traps you observe, not from guesses.

Technique	Question it answers	What it catches	What it misses
Normalised URL string	Have I seen this exact address?	Case, fragments, default ports, dot-segments, parameter order	Different addresses serving the same page; costs the most memory
64-bit URL fingerprint	The same question in 8 bytes per URL	Everything the string set catches	A collision silently drops a real URL
Bloom filter	Have I probably seen this address?	The same as the set, in about 15% of the fingerprint memory	False positives skip about 1% of new URLs for good; entries cannot be deleted
Content hash	Is this body byte-identical to one I hold?	Mirrors and one page reachable under many URLs	One changed byte defeats it, so a timestamp or ad ruins it
Simhash	Is this body nearly identical to one I hold?	Boilerplate, counters and small edits	Needs a Hamming distance threshold you must tune

Normalisation shrinks the set, but different URLs can still serve the same page, so fingerprint the content as well. A hash of the extracted main text catches exact copies and simhash catches near copies. Manku, Jain and Das Sarma presented simhash for near-duplicate detection in web crawling at WWW 2007: similar documents get fingerprints with a small Hamming distance, so the test compares bits rather than text. The threshold is a tuning decision, so label a few hundred pairs from your own crawl and pick it from those.

Assumed: 10,000,000,000 distinct URLs discovered (10x the 1 billion indexed).
Average URL = 80 bytes (assumed).

Exact set of strings         = 10e9 x 80 B   = 800 GB
64-bit URL fingerprints      = 10e9 x 8 B    =  80 GB
Bloom filter, 1% false pos.  : bits per URL  = -ln(0.01) / (ln 2)^2 = 4.605 / 0.4805 = 9.58
                               10e9 x 9.58 bits = 95.8e9 bits = 12.0 GB
Page content hash (SHA-256)  = 1e9 x 32 B    =  32 GB
Page simhash (64-bit)        = 1e9 x 8 B     =   8 GB

Fingerprint collisions, birthday approximation n^2 / 2N with N = 2^64 = 1.845e19:
  (1e10)^2 / (2 x 1.845e19) = 1e20 / 3.69e19 = about 2.7 colliding pairs in 10 billion URLs

Bloom false positives: up to 1% of 10e9 = about 100 million new URLs wrongly skipped.

The Bloom filter row deserves one more sentence. It trades a known false-positive rate for memory, and every false positive is a URL you never crawl. Here the trade is 12 GB against 80 GB, which may be fine for a search index and wrong for a compliance archive; how the filter works inside is out of scope for this post.

How do DNS caching and per-host rate limits fit in?

Every new host costs a DNS lookup, and a naive fetcher pays it on every request. Cache the answer per host for the record TTL, keep a short negative cache for names that failed, and group fetches by host so one lookup serves many pages, which a host-per-queue frontier already does. Resolve through your own process or a local caching resolver so lookups do not queue behind unrelated traffic.

DNS
  no cache, one lookup per fetch            = 1,885 lookups / s
  per-host cache, 20 pages per host visit   = 1,885 / 20 = 94 lookups / s
  in flight at an assumed 100 ms per lookup = 94 x 0.1 = about 9

One large site, 1,000,000 pages, one request in flight at a time
  1 request per second                      = 1,000,000 s / 86,400 = 11.6 days
  10x gap on a 0.5 s fetch (5 s per page)   = 5,000,000 s / 86,400 = 57.9 days

The same arithmetic explains why politeness, not bandwidth, bounds how fast you can crawl one big site. Parallelism across hosts is free; parallelism within a host is the thing you are not allowed to buy. Many hostnames can also share one server, so when you notice sharing, key the limit on the resolved IP address as well as the hostname.

What are crawler traps and how do you escape them?

A crawler trap is a part of a site that generates an effectively infinite set of URLs, by accident or on purpose, so the crawler burns its budget there. URL dedup cannot help because every URL really is new. The defence is budgets, not cleverness.

Trap	How it shows up	Defence
Infinite calendar or pagination	A next-month link that never runs out	Depth limit from the seed plus a page budget per host
Session IDs and tracking parameters	One page under endless unique URLs	Drop known parameters and sort the rest in the normaliser
Repeating path segments	A relative-link bug that produces paths like a, b, a, b, a, b	URL length cap and a limit on repeated segments
Generated pages	The server invents content for any path you request	Per-host budget plus the duplicate rate from content hashes

Combine three limits: a maximum depth from the seed, a maximum number of pages per host per day, and a cap on URL length. The 2,048 character figure is an arbitrary ceiling you tune, not a standard. Then watch the signal no single rule gives you, the share of fetches on a host whose content hash or simhash matches something already stored. When it passes a threshold you choose, demote the host in the priority queues instead of banning it, so a genuinely large site loses priority but not coverage.

How often should a crawler revisit a page?

Do not recrawl on a fixed timer. Adapt the interval per URL from what each fetch observed: shorter when the content changed, longer when it did not. The Stanford frontier chapter names fetch history, such as how often a page has changed, as a priority input, which is the same signal used here.

state per URL: interval (days), content_hash, etag, next_fetch_at

after each fetch:
  if status == 304 or content_hash == stored_hash:   # unchanged
      interval = min(30, interval * 2)
  else:                                              # changed
      interval = max(1, interval / 2)
  next_fetch_at = now + interval

trace, starting interval 7 days:
  unchanged, unchanged, unchanged :  7 -> 14 -> 28 -> 30    (capped at 30)
  changed, changed, changed       :  7 -> 3.5 -> 1.75 -> 1  (floored at 1)

Compare the content hash of the extracted text, not the raw HTML, or rotating ads and timestamps make every page look changed. Where the server supplied an ETag, send it back as If-None-Match: a 304 Not Modified response is defined by RFC 9110 and carries no body, so an unchanged page costs headers instead of 100 KB. The halving and doubling factors are a starting policy I chose for the example; tune the bounds against your own change log.

Where do you store it all, and what do you build first?

Keep three stores apart because their access patterns differ. The frontier holds small records and is written constantly. The page store is large, append-mostly and rarely read, so it belongs in object storage as compressed batches: 25 TB for the snapshot in the capacity block. The link graph and per-URL metadata, meaning the hashes and the last status, feed dedup and scoring. On a single VPS the frontier can start as one Postgres table.

CREATE TABLE urls (
  url_hash        bigint PRIMARY KEY,           -- 64-bit fingerprint of the normalised URL
  url             text        NOT NULL,
  host            text        NOT NULL,
  next_fetch_at   timestamptz NOT NULL,
  interval_s      integer     NOT NULL DEFAULT 604800,  -- 7 days
  content_simhash bigint,
  status          smallint    NOT NULL DEFAULT 0        -- 0 = idle, 1 = claimed
);

-- Only idle rows are indexed, so claimed and finished rows cost nothing here.
CREATE INDEX urls_due_idx ON urls (next_fetch_at) WHERE status = 0;

-- Each worker claims a batch; SKIP LOCKED means workers never wait on each other.
UPDATE urls SET status = 1
WHERE url_hash IN (
  SELECT url_hash FROM urls
  WHERE status = 0 AND next_fetch_at <= now()
  ORDER BY next_fetch_at
  LIMIT 100
  FOR UPDATE SKIP LOCKED
)
RETURNING url, host;

That partial index keeps the due-URL query cheap, and FOR UPDATE SKIP LOCKED lets several workers claim different rows without waiting on each other. The ceiling is honest arithmetic: 50 hosts in flight at a 1 second gap is 50 pages per second, 4.32 million pages per day, about 2.7% of the 162.9 million fetches per day in the capacity block. That is a useful personal crawler and a long way from a search engine. Before the first unattended run, check this list.

Politeness first: one request in flight per host and the gap enforced in code, before any parallelism.
robots.txt fetched per host, refreshed within 24 hours, and a 5xx treated as disallow.
URLs normalised before the seen-check, with the drop-parameter list grown from observed traps.
Depth and per-host budgets set before the crawler runs unattended.
A recrawl interval stored per URL and changes decided from the content hash of extracted text.

The rule I take from this: size a crawler from rates and gaps, not from page counts. Pages per second times the politeness gap gives the queues, pages per day times the revisit cadence gives the bandwidth, and every duplicate or trap you refuse to fetch is bandwidth kept for pages that actually changed.

Sources and further reading

Frequently Asked Questions

Design a Web Crawler: URL Frontier, robots.txt and Dedup

Frequently Asked Questions

Design a Web Crawler: URL Frontier, robots.txt and Dedup

What does a web crawler have to do, and how big is it?

How does a URL frontier decide what to fetch next?

How should a crawler handle robots.txt?

How do you avoid crawling the same page twice?

How do DNS caching and per-host rate limits fit in?

What are crawler traps and how do you escape them?

How often should a crawler revisit a page?

Where do you store it all, and what do you build first?

What does a web crawler have to do, and how big is it?

How does a URL frontier decide what to fetch next?

How should a crawler handle robots.txt?

How do you avoid crawling the same page twice?

How do DNS caching and per-host rate limits fit in?

What are crawler traps and how do you escape them?

How often should a crawler revisit a page?

Where do you store it all, and what do you build first?