CS Fundamentals Trainer · Guides

Design a web crawler

The URL frontier with per-host politeness (code in four languages), URL normalisation, a measured Bloom filter, robots.txt, near-duplicate detection, spider traps tested on a local site, and freshness.

37 min read

A web crawler is a program that starts from a few known pages, downloads them, finds the links inside, and follows those links to download more, over and over. Search engines use crawlers to collect the web; so do price trackers, archives, link checkers, and the data pipelines behind machine learning. "Design a web crawler" is a favourite system design question because the basic loop fits in ten lines and everything around it is hard: the web is huge, hostile, duplicated, and full of traps, and the sites you visit are owned by people who did not agree to be visited at full speed. This guide builds the design in layers and tests each piece: a measured Bloom filter, URL normalisation, robots.txt rules, near-duplicate detection, a per-host politeness scheduler (in four languages), and a small crawl against a local site with a spider trap.

1. What we are building

Functional requirements

• Given seed URLs, discover and download pages (HTML first; images and other types are a later extension).
• Extract links and follow them, without downloading the same page twice.
• Store the downloaded content for later processing (indexing, analysis).
• Re-visit pages over time to stay fresh.

Non-functional requirements

• Politeness: never overload a site, and obey robots.txt. This is both ethics and survival: sites block rude crawlers.
• Robustness: survive broken HTML, huge files, slow servers, redirects loops, and traps built by accident or on purpose.
• Scalability: crawl a billion pages a month by adding machines.
• Extensibility: add new content types and new processing steps without rewriting the core.

Back-of-the-envelope numbers

Assume 1 billion pages a month, an average HTML page of 100 KB (an assumption; measure your own), and 10 links per page.

The fetch rate is modest: a few dozen machines. The hard parts are the seen-URL check over billions of entries, politeness across millions of hosts, and everything the web does to confuse you.

2. The architecture

Diagram: The crawler pipeline

Each box is a separate service or stage, joined by queues, which is what makes it scale and extend (a new content type is a new parser; a new check is a new filter). The rest of this guide goes through the stages that carry the design: the frontier, normalisation and the seen set, politeness and robots, fetching, duplicate detection, traps, and freshness.

3. The URL frontier

The frontier is the to-do list of URLs, and it has two jobs that pull in opposite directions.

Priority: crawl important and fast-changing pages first. A news front page matters more than the 40,000th page of a forum archive. Priority comes from signals such as link-based importance (PageRank-like scores), how often a page has changed in the past, and the depth from a seed.

Politeness: hit any one host slowly. Fetching a billion pages is easy; fetching them without making a small site fall over is the real constraint. A common rule is at most one request at a time to a host, with a delay between requests (often one second or more, longer if robots.txt asks).

The classic design, from the Mercator crawler, separates the two with two layers of queues [1]. The second layer has far fewer queues than there are hosts: each back queue holds URLs of one host at a time, and the number of back queues is chosen as a multiple of the number of fetcher threads, so a thread nearly always finds a host that is ready (the multiplier is a tuning knob: size it by measuring how often threads sit idle). When a back queue empties, it is refilled with the next host from the front queues.

Diagram: Two layers of queues in the frontier: priority first, then politeness

The back half is the interesting part: one FIFO queue per host, and a heap ordered by the earliest time each host may be contacted again. A fetcher asks "which host is ready?"; it takes that host's next URL; when the fetch ends, the host goes back on the heap with now + delay. A host with a slow server or a long Crawl-delay simply comes up less often, and a million hosts share the fetchers fairly.

Here is that scheduler. I ran it with three hosts of three pages each and a one-second delay: it made 9 fetches in 2.0 virtual seconds (at times 0, 1 and 2), and no host was ever contacted twice within a second. The Python, Go and JavaScript versions all ran and gave the same result (pick a language on the tabs; your choice is remembered):

import heapq
from collections import deque
from urllib.parse import urlsplit

class Frontier:
    """One FIFO queue per host, plus a heap that says which host may be contacted next."""
    def __init__(self, delay=1.0):
        self.delay = delay
        self.queues = {}      # host -> deque of urls
        self.heap = []        # (earliest time we may contact it, host) for hosts that have work and are idle
        self.active = set()   # hosts that are in the heap or being fetched right now

    def add(self, url, now):
        host = urlsplit(url).netloc
        self.queues.setdefault(host, deque()).append(url)
        if host not in self.active:
            self.active.add(host)
            heapq.heappush(self.heap, (now, host))

    def next(self, now):
        """Returns (url, None) when a host is ready, else (None, seconds_to_wait), or (None, None) if empty."""
        if not self.heap:
            return None, None
        ready_at, host = self.heap[0]
        if ready_at > now:
            return None, ready_at - now
        heapq.heappop(self.heap)
        return self.queues[host].popleft(), None      # the host stays "active" while its page is fetched

    def done(self, url, now, delay=None):
        host = urlsplit(url).netloc
        if self.queues[host]:
            heapq.heappush(self.heap, (now + (self.delay if delay is None else delay), host))
        else:
            self.active.discard(host)
            del self.queues[host]

type slot struct {
	readyAt float64
	host    string
}
type slotHeap []slot

func (h slotHeap) Len() int           { return len(h) }
func (h slotHeap) Less(i, j int) bool { return h[i].readyAt < h[j].readyAt }
func (h slotHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *slotHeap) Push(x any)        { *h = append(*h, x.(slot)) }
func (h *slotHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// Frontier keeps one FIFO queue per host and a heap saying which host may be contacted next.
type Frontier struct {
	Delay  float64
	queues map[string][]string
	heap   slotHeap
	active map[string]bool // in the heap, or being fetched right now
}

func NewFrontier(delay float64) *Frontier {
	return &Frontier{Delay: delay, queues: map[string][]string{}, active: map[string]bool{}}
}

func hostOf(raw string) string { u, _ := url.Parse(raw); return u.Host }

func (f *Frontier) Add(raw string, now float64) {
	h := hostOf(raw)
	f.queues[h] = append(f.queues[h], raw)
	if !f.active[h] {
		f.active[h] = true
		heap.Push(&f.heap, slot{now, h})
	}
}

// Next returns a URL when a host is ready; otherwise how long to wait (wait < 0 means empty).
func (f *Frontier) Next(now float64) (raw string, wait float64) {
	if len(f.heap) == 0 {
		return "", -1
	}
	if top := f.heap[0]; top.readyAt > now {
		return "", top.readyAt - now
	}
	s := heap.Pop(&f.heap).(slot)
	raw, f.queues[s.host] = f.queues[s.host][0], f.queues[s.host][1:]
	return raw, 0
}

// Done is called when the fetch of raw has finished.
func (f *Frontier) Done(raw string, now float64) {
	h := hostOf(raw)
	if len(f.queues[h]) > 0 {
		heap.Push(&f.heap, slot{now + f.Delay, h})
		return
	}
	delete(f.active, h)
	delete(f.queues, h)
}

class Frontier {
  constructor(delay = 1.0) {
    this.delay = delay;
    this.queues = new Map(); // host -> array of urls
    this.ready = [];         // [readyAt, host], kept sorted; hosts that have work and are idle
    this.active = new Set(); // in `ready`, or being fetched right now
  }
  #push(readyAt, host) {
    let i = this.ready.findIndex(([t]) => t > readyAt);
    if (i < 0) i = this.ready.length;
    this.ready.splice(i, 0, [readyAt, host]);
  }
  add(url, now) {
    const host = new URL(url).host;
    if (!this.queues.has(host)) this.queues.set(host, []);
    this.queues.get(host).push(url);
    if (!this.active.has(host)) { this.active.add(host); this.#push(now, host); }
  }
  /** { url } when a host is ready, { wait } seconds otherwise, {} when empty. */
  next(now) {
    if (this.ready.length === 0) return {};
    const [readyAt, host] = this.ready[0];
    if (readyAt > now) return { wait: readyAt - now };
    this.ready.shift();
    return { url: this.queues.get(host).shift() };
  }
  done(url, now, delay = this.delay) {
    const host = new URL(url).host;
    if (this.queues.get(host).length > 0) this.#push(now + delay, host);
    else { this.active.delete(host); this.queues.delete(host); }
  }
}

public class Frontier
{
    private readonly double _delay;
    private readonly Dictionary<string, Queue<string>> _queues = new();
    private readonly PriorityQueue<string, double> _ready = new();   // host, earliest time we may contact it
    private readonly HashSet<string> _active = new();                // in _ready, or being fetched right now

    public Frontier(double delay = 1.0) => _delay = delay;

    public void Add(string url, double now)
    {
        var host = new Uri(url).Authority;
        if (!_queues.TryGetValue(host, out var q)) _queues[host] = q = new Queue<string>();
        q.Enqueue(url);
        if (_active.Add(host)) _ready.Enqueue(host, now);
    }

    /// <summary>A url when a host is ready; otherwise how long to wait; both null when empty.</summary>
    public (string? Url, double? Wait) Next(double now)
    {
        if (!_ready.TryPeek(out var host, out var readyAt)) return (null, null);
        if (readyAt > now) return (null, readyAt - now);
        _ready.Dequeue();
        return (_queues[host].Dequeue(), null);
    }

    public void Done(string url, double now, double? delay = null)
    {
        var host = new Uri(url).Authority;
        if (_queues[host].Count > 0) _ready.Enqueue(host, now + (delay ?? _delay));
        else { _active.Remove(host); _queues.Remove(host); }
    }
}

At real scale the frontier does not fit in memory: the per-host queues live on disk, with a small in-memory buffer at the front of each. The frontier is also partitioned by host (a hash of the host name picks the crawler machine), so all URLs of one host live on one machine and that machine alone enforces the politeness delay. Use consistent hashing, so adding a machine moves few hosts (see the consistent hashing guide).

4. URL normalisation and the seen set

The same page has many spellings. If the crawler treats them as different pages it wastes work and can loop forever. Before checking "have I seen this?", normalise the URL. I wrote a normaliser and ran it on this list (relative to https://example.com/dir/index.html). My first version decoded every escape and then re-encoded the path, which turned a%2Fb into a/b, a different URL, and it dropped the brackets of IPv6 hosts; a reviewer caught both, the version below fixes them, and the appendix contains the test table (14 cases, all pass):

The rules it applies: lowercase the scheme and host; drop the default port; resolve . and ..; decode only the escapes of unreserved characters (%7E becomes ~), upper-case the hex of the rest and keep reserved ones such as %2F as they are, and encode raw non-ASCII characters; sort the query parameters; drop the fragment (#top is never sent to the server); resolve relative links against the page's own address (or its <base href> if it has one); keep only http and https.

from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode, quote, urljoin
import re

TRACKING = {"utm_source", "utm_medium", "utm_campaign", "utm_term", "utm_content", "fbclid", "gclid", "ref"}
UNRESERVED = frozenset("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-._~")

def fix_escapes(text, safe):
    """RFC 3986 safe normalisation: decode only unreserved characters, upper-case the hex of every
    other escape (so %2F stays %2F: it is not the same as /), and encode raw non-ASCII text."""
    text = re.sub(r"%(?![0-9A-Fa-f]{2})", "%25", text)                  # a lone % is data, not an escape
    def fix(m):
        ch = chr(int(m.group(1), 16))
        return ch if ch in UNRESERVED else "%" + m.group(1).upper()
    return quote(re.sub(r"%([0-9A-Fa-f]{2})", fix, text), safe=safe + "%")

def normalize(url, base=None):
    if base:
        url = urljoin(base, url)
    s = urlsplit(url.strip())
    scheme = s.scheme.lower()
    if scheme not in ("http", "https"):
        return None
    host = (s.hostname or "").lower().rstrip(".")
    if not host:
        return None
    if ":" in host:                                                     # an IPv6 address needs its brackets back
        host = f"[{host}]"
    default = 80 if scheme == "http" else 443
    netloc = host if s.port in (None, default) else f"{host}:{s.port}"
    path = fix_escapes(s.path or "/", "/:@!$&'()*+,;=-._~")
    out = []
    for seg in path.split("/"):                                         # resolve . and ..
        if seg == ".":
            continue
        if seg == "..":
            if len(out) > 1:
                out.pop()
            continue
        out.append(seg)
    path = re.sub(r"/{2,}", "/", "/".join(out) or "/")
    query = sorted((k, v) for k, v in parse_qsl(s.query, keep_blank_values=True) if k.lower() not in TRACKING)
    return urlunsplit((scheme, netloc, path, urlencode(query), ""))

Two of those rules are heuristics, not standards: dropping tracking parameters and collapsing // into / are right for most sites and wrong for a few (some sites really do give ?ref= a meaning, or treat // differently). RFC 3986 defines the safe normalisations (case, percent-encoding, dot segments) [2]; anything beyond that is a trade-off you choose per crawl, and the cost of being too aggressive is missing pages. A common refinement is to learn, per site, which parameters never change the content (fetch twice with and without, compare the content hashes).

The seen set at scale

After normalising, ask "have I queued this URL before?". With 10 billion candidate URLs, a hash set of 8-byte hashes needs about 80 GB; a Bloom filter answers "definitely not seen" or "probably seen" in a fraction of the space. Its errors are one-sided: it never says "not seen" for a URL that was added, but it sometimes says "seen" for one that was not (a false positive), which here means skipping a page you could have crawled. For a crawl that is an acceptable loss when the rate is small. I measured it with a filter holding 1 million URLs and testing 200,000 URLs that were never added:

The measured rates match the textbook formula, (1 - e^(-kn/m))^k for n items, m bits and k hash functions, and I also checked that every URL that was added is reported as present (no false negatives). The cost of a false positive is a missed page, so choose the size from the miss rate you can accept: for 10 billion URLs, 8 bits each is about 10 GB for a 2% miss rate, 16 bits each about 20 GB for 0.05%. Split the filter by host partition so each crawler holds only its share. Bloom filters cannot delete and fill up over time, so a long-running crawl rebuilds or rotates them.

import hashlib

class Bloom:
    def __init__(self, m, k):
        self.m, self.k, self.bits = m, k, bytearray((m + 7) // 8)

    def _positions(self, item):
        h = hashlib.blake2b(item.encode(), digest_size=16).digest()
        a = int.from_bytes(h[:8], "big")
        b = int.from_bytes(h[8:], "big") | 1
        return [(a + i * b) % self.m for i in range(self.k)]      # double hashing: k positions from 2 hashes

    def add(self, item):
        for p in self._positions(item):
            self.bits[p >> 3] |= 1 << (p & 7)

    def __contains__(self, item):
        return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._positions(item))

If a missed page is not acceptable (for example, a legal archive), use an exact structure instead: a key-value store keyed by the URL hash, sharded by host. It costs more space and more lookups, and it is the safe answer.

5. Politeness and robots.txt

The Robots Exclusion Protocol is a plain text file at /robots.txt with rules for crawlers, now an IETF standard (RFC 9309) [3]. The rules that matter:

• A rule group names a User-agent and lists Disallow and Allow paths. The most specific matching rule wins, and an Allow can open a hole in a Disallow.
• Fetch robots.txt before any page of a host, cache it (RFC 9309 says at most 24 hours unless it cannot be reached), and check every URL against it.
• If robots.txt returns 4xx the file is "unavailable" and the crawler may access anything; if the server returns 5xx or the file is unreachable, the crawler must assume everything is disallowed and retry later, not "allowed" (RFC 9309, sections 2.3.1.3 and 2.3.1.4). 429 is a judgement call: it is a 4xx, so the letter of the RFC says "unavailable", but it means "slow down", and treating it as "everything allowed" would reward the crawler for hammering a site. My recommendation, not part of the standard: treat 429 on robots.txt like a 5xx, back off (honour Retry-After) and do not fetch pages of that host until you have a real answer.
• Crawl-delay is not part of the standard and some crawlers ignore it; Google's crawlers do not support it (its 2019 note names crawl-delay, nofollow and noindex as rules it does not support in robots.txt) [4]. Many crawlers honour it anyway, as a courtesy. Decide your own rule: your configured delay, or the larger of that and the site's Crawl-delay.
• Sitemap: lines list sitemap files, a good source of URLs.
• robots.txt is a request, not a security control. Do not use it to protect secrets, and do not crawl private data because a path is not listed.

I tested Python's standard parser on a file with a Disallow: /private/, an Allow: /private/public.html, Crawl-delay: 2, and a group that bans badbot entirely:

The parser also reported the crawl delay of 2 for mybot.

Good manners beyond robots.txt:

• Identify yourself with a User-Agent that names the crawler and a URL or email where an owner can reach you.
• Limit the rate per host (section 3) and the number of concurrent connections, and back off when you see 429 or 503 responses (honour Retry-After).
• Respect noindex/nofollow, both in <meta name="robots"> and in the X-Robots-Tag response header (see section 7) where it applies to what you do with the data, and the legal and licensing side (terms of service, copyright, personal data rules such as the GDPR and LGPD) which a crawler's owner is responsible for.
• A very large site is slow to crawl politely: at one request per second, 10 million pages of one host take 10,000,000 s, about 116 days. That is the arithmetic behind per-host budgets, sitemaps, and asking big sites for a bulk feed or a higher rate.

6. Fetching

The fetcher is where the web's mess arrives. Defensive rules:

• Timeouts on connect and on the whole response, and a maximum size (stop reading after, say, 5 MB), so a slow or endless response cannot tie up a worker.
• Redirects: do not let the HTTP library follow them silently. Treat a redirect target as a new URL that goes through the frontier, so normalisation, the seen set, robots, and politeness all apply. In my first version of the mini-crawler the library followed a redirect inside one fetch, and the smallest gap between two requests to the host was 1 ms, far below the delay; after I sent redirect targets back through the frontier the smallest gap rose to about 50 ms. Limit the chain length to avoid loops.
• Status codes: 200 parse; 301/308 update the stored URL; 404/410 mark gone; 429/503 back off and retry later; other 5xx retry a few times with exponential backoff and jitter, then give up for now.
• Content type and encoding: check Content-Type before parsing (skip binary types unless you want them); detect the character set from the header, the <meta> tag, or by sniffing; handle gzip and Brotli.
• Conditional requests: on a re-crawl send If-None-Match (the stored ETag) or If-Modified-Since. A 304 Not Modified answer costs almost nothing, and is the basis of cheap freshness checks (RFC 9111) [5].
• DNS: cache lookups (without a cache the crawler makes one per fetch, about 386 a second in the estimate above), respect TTLs, run the resolver locally or in a dedicated pool so a slow DNS server does not stall fetchers.
• JavaScript-rendered pages: a plain HTTP fetch sees only the initial HTML. A headless browser sees the final page and costs 10 to 100 times more CPU and memory per page, so render selectively (pages that look empty without scripts, or sites you know need it).
• Connection reuse: keep-alive connections to the same host cut handshakes (see TLS and HTTPS), which fits the one-connection-per-host politeness rule.

7. Parsing and link extraction

• Parse leniently; real HTML is broken. Use a robust HTML parser, not regular expressions.
• Take links from <a href>; resolve each against the page URL or <base href>; look at rel="nofollow" (a hint about whether the site vouches for the link) and <link rel="canonical"> (the site's preferred address for this content, a strong dedupe signal).
• Page-level directives: robots.txt says whether you may fetch; a page can also say what to do with it. Read <meta name="robots" content="noindex, nofollow"> in the HTML and the X-Robots-Tag HTTP header (the only way to say it for a PDF or an image). noindex means do not put the page in the search index, nofollow means do not queue its links; both are usually honoured even by crawlers that fetch the page, and they cost nothing to check while you parse. The header can also be scoped to a user agent (X-Robots-Tag: mybot: noindex). Note the trap: a page blocked by robots.txt is never fetched, so its noindex is never seen. Store the directives with the page so the indexing stage can obey them.
• Extract the text and the metadata (title, language, headings) for the next stage. Keep the original bytes too, so you can reprocess later without re-crawling.
• Filter links before they reach the frontier: allowed schemes and domains, maximum URL length (very long URLs are almost always traps or garbage), and a per-site rule set if your crawl is scoped.

8. Duplicate detection

There are two different kinds, and the crawler needs both.

Same URL, many spellings: handled by normalisation and the seen set (section 4).

Different URLs, the same or nearly the same content: mirrors, print versions, session ids in URLs, pages with a rotating "related articles" box, boilerplate pages. Skipping them saves storage and index space.

• Exact duplicates: hash the normalised content (a SHA-1 or similar of the text with whitespace collapsed) and look it up. Cheap, and it catches true copies.
• Near duplicates: a page that differs by a date, a counter, or a footer has a different hash but is the same document. Simhash (Charikar) turns a document into a short fingerprint where similar documents get fingerprints that differ in only a few bits: each word group votes a bit up or down, and the fingerprint is the sign of each total [6]. Manku, Jain and Das Sarma showed that comparing 64-bit fingerprints, with a Hamming distance threshold, finds near-duplicates in a crawl of billions of pages [7].

I measured it on a short paragraph (84 words) with 3-word shingles and a 64-bit fingerprint:

Be careful with the lesson here. The tight threshold used for web-scale crawling in the paper (a distance of 3 for long pages) would not have caught the footer or the two-word edit in my short text; the distances grow as the document gets shorter, because each change moves a larger share of the votes. Choose the threshold per document length from labelled examples, strip boilerplate (menus, footers, ads) before fingerprinting, and use a looser threshold only where a false match is cheap. To search fingerprints quickly, split the 64 bits into blocks and index each block, so two fingerprints within a small distance must agree on at least one block (the idea in the paper).

import hashlib, re

def simhash(text, k=3, bits=64):
    words = re.findall(r"\w+", text.lower())
    shingles = [" ".join(words[i:i + k]) for i in range(max(1, len(words) - k + 1))]
    votes = [0] * bits
    for s in shingles:
        h = int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")
        for i in range(bits):
            votes[i] += 1 if (h >> i) & 1 else -1
    return sum(1 << i for i in range(bits) if votes[i] > 0)

def distance(a, b):
    return bin(a ^ b).count("1")

9. Spider traps

A spider trap is a part of a site that generates an endless supply of new URLs: a calendar with a "next month" link that goes on for ever, a session id in every link, filter combinations (?color=red&size=m&sort=price…) that multiply, a relative link that appends itself (/a/b/a/b/a/b/…). Some are accidents; a few are deliberate. A naive crawler never finishes.

I built a local test site (code in the appendix) with 40 real pages arranged as a tree, an alias URL (/about?utm_source=home), a redirect, a robots.txt that disallows /private/, and a calendar trap. Then I ran the mini-crawler (4 worker threads, a 50 ms per-host delay, robots checked, redirects sent back through the frontier) three ways:

The undefended crawl found all 40 real pages and then spent 158 of its 200 fetches on the calendar; it was still finding new calendar months when my hard stop ended it, and it would have kept going for ever. Both defences found all 40 real pages and stopped by themselves. Other results from the same runs: robots.txt was honoured (no request to /private/), the alias /about?utm_source=home collapsed into /about by normalisation (no duplicate content), the redirect was followed through the frontier, and the crawler made 19 requests per second to the one host, which is what a 50 ms delay allows. The smallest gap between two requests was 49 to 50 ms in runs 2 and 3, but only 15 to 27 ms in run 1 (15 ms the first time, 25 to 27 ms in two re-runs with the corrected normaliser; the other numbers did not change); a likely cause is that the test site and the crawler share one Python process and its scheduler, so arrivals can bunch even though the delay is applied when each URL is taken. In production, enforce the delay on the server that talks to the host and measure the real gaps.

The defences, from simplest to most elaborate:

1. A maximum depth from the seed (the number of links followed).
2. A budget per host (maximum pages or URLs per site, per crawl). It also bounds the damage of any one site.
3. A maximum URL length and a maximum number of path segments or query parameters.
4. Pattern detection: many URLs that differ only in one numeric or date segment (/cal/2026/10, /cal/2026/11, …) look like a trap; cap each pattern, or lower the priority as the count grows.
5. Content-based detection: a new URL whose content hash or simhash matches pages already seen on that site is a sign of aliases or a loop.
6. Priority decay: pages found only through very long chains get low priority and may never be reached.
7. A human override: a blocklist of hosts and patterns that operators can update without a deploy.

10. Freshness: re-crawling

The web changes. A crawler that visits each page once ends up with a stale copy. Re-crawl policy decides what to fetch again, and when:

• Estimate each page's change rate from history (how often the content hash differed on past visits), and revisit changing pages more often. A homepage might need hourly visits, an old blog post once a month, a dead page almost never.
• Importance matters too: a page many people see costs more when stale.
• Use conditional requests (section 6) to make "has it changed?" cheap.
• Use sitemaps with lastmod, and feeds (RSS and Atom), as hints for what changed.
• Budget the whole thing: with a fixed fetch rate, every re-crawl of a stable page is a first-time page you did not get. Aim to spend visits where changes are likely and visible.

11. Scaling out and failing safely

• Partition by host: hash(host) mod N (or consistent hashing) decides which crawler instance owns a host. All its URLs, its robots.txt cache, and its politeness timer live there, so no two machines can hit the same host at once by accident. URLs found by one machine for another machine's host go through a queue to the owner (see message queues and delivery guarantees).
• Delivery is at least once, so the same URL may arrive twice; the seen set and idempotent storage make that harmless. A page stored twice under the same key just overwrites itself.
• Checkpoint the frontier (the queues, the heap, and the seen filter) regularly, so a crashed machine resumes where it was instead of starting over. Because the content is already in durable storage, the worst case after a crash is repeating a little work.
• Storage: content goes to an object store or a distributed file system, keyed by URL hash or content hash, with metadata (fetch time, status, ETag, headers) in a database. Do not put 100 TB a month in a relational database.
• Hot hosts and slow hosts: a machine whose hosts are all slow wastes capacity; fetchers should be asynchronous (thousands of requests in flight per machine, each waiting on the network), not one thread per fetch.
• Rate-limit yourself globally as well as per host, so a bug cannot turn the crawler into a denial of service against someone.

12. Monitoring and testing

• Metrics: pages per second, errors by status code and by cause (DNS, connect, timeout, TLS), bytes per second, frontier size and age of the oldest URL, politeness delay actually achieved (the gap histogram), robots denials, duplicate rate (URL-level and content-level), the share of fetches that hit trap-like patterns, and per-host budgets used.
• Alert on a sudden drop in successful fetches, a spike of 429 or 403 responses (you are being blocked), and a frontier that only grows.
• Testing: unit-test normalisation with a table of tricky URLs (like the one above), the frontier with a virtual clock (like my test), and the robots.txt logic against the examples in RFC 9309. Then run an integration test against a local test site with the awkward cases built in: a trap, redirects, a slow page, an oversized response, a broken-HTML page, a robots.txt with rules. That is how the table in section 9 was produced, and it is what stops a regression from becoming an incident on someone else's server.

13. Common mistakes

• No politeness, or politeness per URL instead of per host. One site gets hundreds of simultaneous requests and blocks you or goes down.
• Ignoring robots.txt failure modes: treating a 5xx on robots.txt as "allow everything".
• Following redirects inside the HTTP client, which skips normalisation, robots, and the delay for the target.
• Weak or no normalisation, so ?utm_source= variants of every page are crawled separately.
• No trap defences (depth, budget, URL length). A single calendar can consume the crawl.
• Using a single exact-match hash for duplicates and missing near-duplicates; or using simhash with a threshold copied from a paper without testing it on your text.
• Storing everything in a relational database and one thread per fetch.
• A global seen-set on one machine, a bottleneck and a single point of failure; partition it by host.
• No identification in the User-Agent, so site owners cannot contact you and simply block the whole range.
• No kill switch for a host, a pattern, or the whole crawl.

14. Questions interviewers like to add

"How do you avoid crawling the same page twice?"

Normalise the URL, then check it against a seen set (a Bloom filter or a sharded key-value store); and at the content level, hash for exact duplicates and use simhash for near-duplicates. Say the Bloom filter's trade-off: false positives mean skipped pages.

"How do you make sure you do not overload a website?"

One queue per host, one request at a time per host, a delay between requests (and the site's Crawl-delay if you choose to honour it), a heap of "next allowed time" per host, back-off on 429/503, and partitioning by host so one machine owns each host.

"What is a spider trap and how do you defend against it?"

An endless URL space (calendars, session ids, filter combinations). Defend with depth limits, a per-host budget, URL length and pattern limits, content-based checks, and priority decay.

"How would you crawl JavaScript-heavy sites?"

A headless browser pool for the pages that need it, used selectively because of the cost; or find the site's JSON API or sitemap. Cache rendered results and re-render only on change.

"How do you keep the index fresh?"

Estimate change rates from past visits, revisit changing and important pages more often, use conditional requests to make "unchanged" cheap, and use sitemaps and feeds as hints.

"How would you scale it to 100 times the size?"

Partition the frontier and the seen set by host, add machines, use asynchronous I/O, keep the content in object storage, and watch the per-host politeness limit: it is the real ceiling for big sites, which is why very large sites are crawled with agreements and feeds, not just more machines.

"How do you crawl this site with a login or one that blocks bots?"

You should not, unless the owner has agreed. Authentication and bot blocking are the site telling you no. The ethical and legal answer is to ask for access or an API.

15. Things to mention in an interview

• Clarify the purpose and scale; do the numbers (about 386 pages per second for a billion a month).
• Draw the pipeline: seeds, frontier, DNS, fetchers, parser, dedupe, storage.
• Explain the frontier's two jobs, priority and politeness, and the one-queue-per-host design with a heap of next-allowed times.
• Normalise URLs; use a Bloom filter for the seen set and say what its error means.
• Obey robots.txt (and its failure rules), identify yourself, and back off.
• Detect duplicates at two levels; know simhash and its limits.
• Defend against traps with depth, budgets, and patterns.
• Partition by host for scaling; checkpoint; use object storage.
• Close with freshness (change rates, conditional requests) and monitoring.

Quick recap

1. A crawler is a loop: take a URL from the frontier, fetch, parse, filter, and add new URLs, with a lot of care at each step.
2. The frontier balances priority (what matters first) and politeness (one request at a time per host, with a delay); the classic design is one queue per host plus a heap of next-allowed times.
3. Normalise URLs, then use a Bloom filter for the seen set: 8 bits per URL gave a 2.1% false-positive rate in my test, and a false positive means a skipped page.
4. Read robots.txt (RFC 9309) before any page, cache it, treat a server error as "disallowed", and identify your crawler.
5. Handle redirects through the frontier, and use timeouts, size limits, backoff, and conditional requests.
6. Detect duplicates by exact hash and by simhash, whose threshold depends on document length.
7. Defend against traps with depth caps, per-host budgets, and URL limits: in my test, the undefended crawl spent 158 of its 200 fetches on a calendar.
8. Partition by host to scale, checkpoint the frontier, store content in object storage, and re-crawl by change rate.

Appendix: the experiment code

Everything measured above can be re-run. Save the three files in one folder (normalize.py is the listing in section 4, followed by its if __name__ == "__main__": test table), then run python3 normalize.py for the normaliser tests and python3 crawl.py for the three trap runs. Python 3 standard library only. Timings depend on your machine; the page counts should match.

testsite.py: the local site (40 real pages in a tree, an alias, a redirect, a robots.txt that disallows /private/, a calendar trap):

# A local test site: a real tree of pages, alias URLs, a redirect, a robots.txt, and a calendar spider trap.
import http.server, socketserver, threading, time, re
from urllib.parse import urlsplit, parse_qs
HITS=[]; LOCK=threading.Lock()
N_DOCS=40
def page(title,links,body=""):
    a="".join(f'<li><a href="{l}">{l}</a></li>' for l in links)
    return f"<html><head><title>{title}</title></head><body><h1>{title}</h1><p>{body}</p><ul>{a}</ul></body></html>".encode()
class H(http.server.BaseHTTPRequestHandler):
    def log_message(self,*a): pass
    def do_GET(self):
        u=urlsplit(self.path); p=u.path
        with LOCK: HITS.append((time.time(),self.path))
        if p=="/robots.txt":
            return self.send(200,b"User-agent: *\nDisallow: /private/\nCrawl-delay: 0.05\n","text/plain")
        if p=="/old": 
            self.send_response(301); self.send_header("Location","/docs/0"); self.end_headers(); return
        if p=="/": return self.send(200,page("Home",["/docs/0","/cal/2026/1","/private/secret","/old","/about?utm_source=home","/about"]))
        if p=="/about": return self.send(200,page("About",["/","/docs/1"],"About this site."))
        m=re.fullmatch(r"/docs/(\d+)",p)
        if m:
            i=int(m.group(1))
            if i>=N_DOCS: return self.send(404,b"nope")
            kids=[f"/docs/{2*i+1}",f"/docs/{2*i+2}"]
            return self.send(200,page(f"Doc {i}",kids+["/"],f"Unique text number {i} about topic {i*7919%97}. "*5))
        m=re.fullmatch(r"/cal/(\d+)/(\d+)",p)      # the trap: every month links to the next, forever
        if m:
            y,mo=int(m.group(1)),int(m.group(2)); ny,nm=(y+1,1) if mo==12 else (y,mo+1)
            return self.send(200,page(f"Calendar {y}-{mo}",[f"/cal/{ny}/{nm}","/"],"No events."))
        if p.startswith("/private/"): return self.send(200,page("Secret",[]))
        self.send(404,b"nope")
    def send(self,code,body,ctype="text/html"):
        self.send_response(code); self.send_header("Content-Type",ctype); self.send_header("Content-Length",str(len(body))); self.end_headers(); self.wfile.write(body)
class S(socketserver.ThreadingMixIn,http.server.HTTPServer): daemon_threads=True
def start(port=8765):
    s=S(("127.0.0.1",port),H); threading.Thread(target=s.serve_forever,daemon=True).start(); return s

crawl.py: the mini-crawler (4 threads, per-host delay, robots checked, redirects sent back through the frontier) and the three runs:

import urllib.error, threading, time, heapq, hashlib, re, urllib.request, urllib.robotparser, collections
from urllib.parse import urlsplit
from html.parser import HTMLParser
import testsite as S, normalize as norm
class NoRedirect(urllib.request.HTTPRedirectHandler):
    def redirect_request(self,*a,**k): return None          # hand 3xx back to us: the target goes through the frontier like any URL
OPENER=urllib.request.build_opener(NoRedirect)

class Links(HTMLParser):
    def __init__(s): super().__init__(); s.out=[]
    def handle_starttag(s,t,a):
        if t=="a": s.out+= [v for k,v in a if k=="href" and v]
def crawl(seed, workers=4, max_depth=None, host_budget=None, delay=0.05, respect_robots=True, hard_stop=300):
    frontier=[(0,0,seed)]; seen={norm.normalize(seed)}; lock=threading.Lock(); tick=[0]
    next_ok=collections.defaultdict(float); per_host=collections.Counter()
    robots={}; hashes=set(); stats=collections.Counter(); fetched=[]
    done=threading.Event()
    def allowed(url):
        h=urlsplit(url).netloc
        if h not in robots:
            r=urllib.robotparser.RobotFileParser(); 
            try: r.parse(urllib.request.urlopen(f"http://{h}/robots.txt",timeout=5).read().decode().splitlines())
            except Exception: r.parse([])
            robots[h]=r
        return robots[h].can_fetch("mybot",url)
    def worker():
        while not done.is_set():
            with lock:
                if stats["fetched"]>=hard_stop: done.set(); return
                item=None
                if frontier:
                    item=heapq.heappop(frontier)
                    h=urlsplit(item[2]).netloc
                    wait=next_ok[h]-time.time()
                    if wait>0: heapq.heappush(frontier,item); item=None       # politeness: not yet
                    else: next_ok[h]=time.time()+delay; stats["busy"]+=1      # counted as busy from the moment it is taken
            if item is None:
                time.sleep(0.005)
                with lock:
                    if not frontier and stats["busy"]==0: done.set()
                continue
            depth,_,url=item
            if respect_robots and not allowed(url):
                with lock: stats["blocked by robots"]+=1; stats["busy"]-=1
                continue
            try:
                r=OPENER.open(url,timeout=5); body=r.read(); final=r.geturl()
            except urllib.error.HTTPError as e:
                loc=e.headers.get("Location") if e.code in (301,302,307,308) else None
                with lock:
                    stats["redirects" if loc else "errors"]+=1; stats["busy"]-=1
                    n=norm.normalize(loc,url) if loc else None
                    if n and n not in seen: seen.add(n); tick[0]+=1; heapq.heappush(frontier,(depth,tick[0],n))
                continue
            except Exception:
                with lock: stats["errors"]+=1; stats["busy"]-=1
                continue
            digest=hashlib.sha1(re.sub(rb"\s+",b" ",body)).hexdigest()
            p=Links(); p.feed(body.decode("utf8","ignore"))
            with lock:
                stats["busy"]-=1; stats["fetched"]+=1; fetched.append(url)
                if digest in hashes: stats["duplicate content"]+=1
                else: hashes.add(digest)
                if max_depth is not None and depth>=max_depth: continue
                for l in p.out:
                    n=norm.normalize(l,final)
                    if not n or n in seen: continue
                    seen.add(n); h=urlsplit(n).netloc
                    if host_budget and per_host[h]>=host_budget: stats["over host budget"]+=1; continue
                    per_host[h]+=1; tick[0]+=1; heapq.heappush(frontier,(depth+1,tick[0],n))
    ts=[threading.Thread(target=worker) for _ in range(workers)]
    t0=time.time(); [t.start() for t in ts]; [t.join() for t in ts]
    return stats, fetched, time.time()-t0
if __name__=="__main__":
    srv=S.start()
    for name,kw in [("1. naive: no depth cap, no budget",dict(hard_stop=200)),
                    ("2. depth cap 6 only",dict(max_depth=6)),
                    ("3. budget of 50 URLs per host only",dict(host_budget=50))]:
        S.HITS.clear()
        st,f,dt=crawl("http://127.0.0.1:8765/",**kw)
        cal=sum(1 for u in f if "/cal/" in u); docs=len({u for u in f if "/docs/" in u})
        priv=sum(1 for t,p in S.HITS if p.startswith("/private/"))
        times=sorted(t for t,p in S.HITS if p!="/robots.txt"); gaps=[b-a for a,b in zip(times,times[1:])]
        print(name); print("  fetched %d | distinct docs %d of 40 | calendar-trap pages %d | /private/ requests %d | redirects followed via frontier %d | duplicate content %d | %s"%(
              st["fetched"],docs,cal,priv,st["redirects"],st["duplicate content"],"stopped by the hard stop" if st["fetched"]>=200 else "frontier emptied by itself"))
        print("  %.1f s, %.0f requests/s to the one host, smallest gap between requests %.0f ms (delay asked for: 50 ms)"%(dt,len(times)/dt,1000*min(gaps)))

The Bloom filter test is the Bloom class in section 4, filled with 1,000,000 URLs and probed with 200,000 others that were never added; the simhash test uses the listing in section 8.

Sources

1. Allan Heydon and Marc Najork, Mercator: A Scalable, Extensible Web Crawler, World Wide Web, 1999. The frontier with priority queues and per-host queues, the seen-URL check, and the modular design.
2. IETF, RFC 3986: Uniform Resource Identifier (URI): Generic Syntax, section 6 (normalization and comparison).
3. IETF, RFC 9309: Robots Exclusion Protocol. The rules, caching, and what to do when robots.txt cannot be fetched.
4. Google Search Central, A note on unsupported rules in robots.txt (2019). The 2019 post names crawl-delay, nofollow and noindex as rules not supported in robots.txt.
5. IETF, RFC 9111: HTTP Caching and RFC 9110: HTTP Semantics (conditional requests, ETag, If-Modified-Since, Retry-After).
6. Moses Charikar, Similarity estimation techniques from rounding algorithms, STOC 2002. The idea behind simhash.
7. Gurmeet Singh Manku, Arvind Jain and Anish Das Sarma, Detecting near-duplicates for web crawling, WWW 2007. Simhash and Hamming distance on billions of pages.
8. Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 1970. The Bloom filter.
9. Sergey Brin and Lawrence Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, 1998. An early description of a large crawler and link-based importance.
10. Sitemaps.org, The Sitemaps protocol. Listing URLs and lastmod for crawlers.

Practise this topic: System Design Networking

More guides