Design a Web Crawler: Frontier, Politeness and Deduplication

"Design a web crawler" sounds like breadth-first search with an HTTP client, and at the core it is. The design question is everything around that loop: a billion pages in no single queue, no website hammered, no page fetched twice under different addresses, and traps that generate URLs forever. The strong answer puts almost all of that into one component, the frontier.

The problem it solves

Fetch and store a large set of pages, starting from seed URLs, following links, and revisiting pages later. The constraints that shape the design:

• Scale. With illustrative assumptions of a billion pages a month at about 100 KB each, that is roughly 386 fetches a second on average and around 100 TB of raw pages a month, before compression.
• Politeness. Every site sets rules in its robots file, and even without a crawl delay one crawler must not flood one host.
• No duplicate work. The same page appears under many URL spellings, and mirrors serve identical bytes under different hosts.
• Robustness. Slow servers, redirect loops and endless calendar pages must not stall the crawl.

The intuition

The crawl loop is BFS: take a URL from the frontier, fetch it, store it, extract links, push the new ones. Four decisions turn that loop into a system.

Partition the frontier by host, not by URL. Each host gets its own FIFO queue, and a scheduler hands a host to exactly one worker at a time, together with the earliest time that host may be contacted again. Politeness is then local: one queue, one worker, one delay. Across machines, hosts are assigned by hashing the host name, with consistent hashing so adding a machine moves only a slice of hosts. A separate priority layer in front of these queues decides which URLs matter most.

Honour robots rules before fetching. Fetch each host's robots file once, cache it, and check every path against it. As of September 2026, the protocol is standardised as RFC 9309, which asks crawlers not to rely on a cached copy for more than a day and to treat a server error on the robots file as "disallow everything". Crawl-delay is a widely seen extension that the RFC does not define; many crawlers apply their own per-host rate instead.

Deduplicate twice. Normalise every URL into one spelling (lower-case host, no default port, no fragment), then check a seen-set before enqueueing. At web scale that set is often a Bloom filter, whose rare false positives mean skipping a new URL, never fetching one twice. Then fingerprint the body: a mirror has a fresh URL and identical bytes. An exact hash catches identical copies; near-duplicates need similarity fingerprints.

Bound the traps. Cap depth and pages per host, drop URLs with session-like parameters, and watch for hosts whose URL count grows without new content.

Watch it run

The animation starts from the scale: a billion pages to fetch, and the queue of what to visit next, the frontier, is the entire design. Seeds go in, and the frontier is partitioned by host rather than by URL. One worker owns host a, which makes a crawl delay easy to honour. Its rules are read and cached first, so a disallowed path is never requested. The page is fetched and stored, and host a waits out its delay, one request a second. Links found on that page become new work, one entry per host. Two have been seen before, and one hash lookup removes them, so one of three is enqueued. A mirror has a fresh URL and identical bytes, so the body is fingerprinted too. Politeness scales because each host queue paces itself. The bill comes last: a host that answers slowly starves its own queue while other workers idle.

The code

A toy model of one crawler node: a virtual clock instead of real time, a dictionary instead of the web. The frontier is a heap of hosts keyed by the time each may next be contacted; each host appears in the heap at most once:

import hashlib
import heapq
from collections import defaultdict, deque
from urllib.parse import urlsplit, urlunsplit

def normalize(url):
    """One spelling per page: lower-case scheme and host, no default port, no fragment."""
    p = urlsplit(url)
    default = {"http": 80, "https": 443}.get(p.scheme)
    netloc = p.hostname if p.port in (None, default) else "%s:%d" % (p.hostname, p.port)
    return urlunsplit((p.scheme, netloc, p.path or "/", p.query, ""))

print(normalize("HTTPS://Shop.Example:443/tea?page=2#reviews"))
# https://shop.example/tea?page=2

class Crawler:
    """Toy model: host-partitioned frontier, per-host delay, URL and content dedupe."""
    def __init__(self, web, disallow, delay):
        self.web, self.disallow, self.delay = web, disallow, delay   # web: url -> (body, links)
        self.queues = defaultdict(deque)       # host -> its own FIFO of URLs
        self.ready = []                        # heap of (earliest next fetch, host)
        self.waiting = set()                   # hosts currently in that heap
        self.next_ok = defaultdict(float)      # host -> when its delay has passed
        self.seen_urls, self.seen_bodies = set(), set()
        self.log, self.stored, self.blocked = [], [], 0

    def add(self, url):
        url = normalize(url)
        if url in self.seen_urls:              # one set lookup drops repeats
            return
        self.seen_urls.add(url)
        host = urlsplit(url).hostname
        self.queues[host].append(url)
        self.schedule(host)

    def schedule(self, host):                  # each host is in the heap at most once
        if self.queues[host] and host not in self.waiting:
            self.waiting.add(host)
            heapq.heappush(self.ready, (self.next_ok[host], host))

    def allowed(self, url, host):              # robots rules, cached per host
        return not any(urlsplit(url).path.startswith(p) for p in self.disallow.get(host, ()))

    def run(self):
        while self.ready:
            now, host = heapq.heappop(self.ready)
            self.waiting.discard(host)
            queue = self.queues[host]
            while queue and not self.allowed(queue[0], host):
                queue.popleft()                # a disallowed path is never requested
                self.blocked += 1
            if queue:
                url = queue.popleft()
                self.log.append((now, host, url))
                self.next_ok[host] = now + self.delay
                body, links = self.web.get(url, ("", []))
                digest = hashlib.sha256(body.encode()).hexdigest()
                if digest not in self.seen_bodies:     # a mirror: new URL, same bytes
                    self.seen_bodies.add(digest)
                    self.stored.append(url)
                    for link in links:
                        self.add(link)
            self.schedule(host)                # more work: come back after the delay
        return self

web = {
    "https://a.example/":  ("home a", ["https://a.example/1", "https://B.example/", "https://a.example/private/x"]),
    "https://a.example/1": ("page a1", ["https://a.example/#top", "https://b.example/mirror"]),
    "https://b.example/":  ("home b", ["https://a.example/1"]),
    "https://b.example/mirror": ("page a1", ["https://b.example/never-reached"]),
}
c = Crawler(web, disallow={"a.example": ["/private/"]}, delay=1.0)
c.add("https://a.example/")
c.run()
for when, host, url in c.log:
    print(when, url)
# 0.0 https://a.example/
# 0.0 https://b.example/
# 1.0 https://a.example/1
# 1.0 https://b.example/mirror
print(c.stored, c.blocked)
# ['https://a.example/', 'https://b.example/', 'https://a.example/1'] 1

Hosts a and b are fetched at the same instant, but each waits a second between its own requests. B.example and #top collapse into URLs already seen, the private path is never requested, and the mirror is fetched but not stored or followed. The estimate from above:

pages_per_month = 1_000_000_000              # illustrative assumptions, not measurements
avg_page_kb = 100
print(round(pages_per_month / (30 * 24 * 3600)), "pages/s,",
      pages_per_month * avg_page_kb // 10**9, "TB/month")
# 386 pages/s, 100 TB/month

Checked on 300 seeded random webs with mirrors, robots rules and oddly spelled links, against a brute-force BFS: the crawler must fetch exactly the reachable allowed URLs, each once, store one page per distinct body, and respect every host's delay:

import random

def reference(web, disallow, seeds):
    """Brute force: BFS over allowed pages, following links from first copies only."""
    seen, bodies, order = set(), set(), deque()
    for s in seeds:
        if normalize(s) not in seen:
            seen.add(normalize(s))
            order.append(normalize(s))
    fetched = set()
    while order:
        url = order.popleft()
        host = urlsplit(url).hostname
        if any(urlsplit(url).path.startswith(p) for p in disallow.get(host, ())):
            continue
        fetched.add(url)
        body, links = web.get(url, ("", []))
        if body not in bodies:
            bodies.add(body)
            for link in links:
                if normalize(link) not in seen:
                    seen.add(normalize(link))
                    order.append(normalize(link))
    return fetched, bodies

random.seed(28)
ok = True
for _ in range(300):
    hosts = ["h%d.example" % i for i in range(random.randint(1, 5))]
    urls = ["https://%s/p%d" % (h, i) for h in hosts for i in range(random.randint(1, 8))]
    spelled = lambda u: random.choice([u, u + "#frag", u.replace(".example", ".EXAMPLE")])
    links_of = {}                                  # same bytes, same links: a mirror
    web = {}
    for u in urls:
        body = "body %d" % random.randint(0, len(urls) // 2)
        if body not in links_of:
            links_of[body] = [spelled(l) for l in random.sample(urls, random.randint(0, min(4, len(urls))))]
        web[u] = (body, links_of[body])
    disallow = {h: ["/p%d" % random.randint(0, 3)] for h in hosts if random.random() < 0.5}
    delay = random.choice([0.5, 1.0, 2.0])
    seeds = random.sample(urls, random.randint(1, min(3, len(urls))))
    c = Crawler(web, disallow, delay)
    for s in seeds:
        c.add(s)
    c.run()
    fetched, bodies = reference(web, disallow, seeds)
    ok &= {url for _, _, url in c.log} == fetched and len(c.log) == len(fetched)
    ok &= {web.get(u, ("", []))[0] for u in c.stored} == bodies and len(c.stored) == len(bodies)
    for h in hosts:
        times = [t for t, host, _ in c.log if host == h]
        ok &= all(b - a >= delay for a, b in zip(times, times[1:]))
print(ok)                                    # True

The complexity

• Per discovered link: one normalisation and one seen-set lookup, O(1) expected.
• Per fetch: one heap pop and push, O(log H) for H active hosts, plus hashing the body, linear in its size.
• Memory: the seen-set grows with every URL ever discovered, which is why large crawls use Bloom filters or a sharded key-value store.
• Throughput: bounded by politeness per host and by the number of distinct hosts ready at once, not only by the fetcher count.

Where it goes wrong

• One global queue. Politeness needs global coordination, and one busy host blocks everyone.
• Deduplicating URLs but not content. Mirrors and URL variants waste fetches and storage.
• Skipping normalisation. Without it, #top and a capitalised host look like new pages.
• No trap limits. Calendars and session parameters produce infinite URLs.
• A slow host starving its queue. Only its owner may fetch it, so set timeouts and move repeatedly slow hosts to a lower-priority lane.

When it shows up in interviews

As a classic system design prompt, and as the coding question "crawl every page under this host with a thread pool", where the answers are BFS plus a seen-set plus bounded concurrency, as in the thread pool article. Follow-ups cover recrawl frequency, distribution by host hash, and politeness, which is rate limiting applied from the client side. The traversal itself is plain BFS.

How to say it in an interview

"The frontier is the design. I partition it by host: each host has its own queue, one worker owns it at a time, and a scheduler releases it only after its crawl delay. I check cached robots rules before fetching. Every URL is normalised and checked against a seen-set, a Bloom filter at scale, and every body is fingerprinted so mirrors are stored once. Hosts are spread across machines by consistent hashing, so politeness stays local. I cap depth and pages per host to escape traps, and time out slow hosts."