Web Crawler System Design Interview: Frontier, Politeness, and Dedup

A web crawler fetches a page, extracts the links on it, and repeats on everything it finds. That makes it a graph traversal where the graph is the web and every edge costs a network round trip, which is why "design a web crawler" is really two interview questions wearing one name. The coding round wants breadth-first search over a getUrls interface with a visited set, in forty-five minutes. The design round barely looks at the traversal. It wants the URL frontier, per-host politeness, deduplication, and a recrawl policy.

The traversal is the easy half. Most of the round goes to what happens when one host is 40% of your frontier, and to whether you can say precisely why your crawler stops.

Key Takeaways

• Mark a URL seen when you push it, not when you pop it. Marking on pop lets the same URL sit in the queue several times and get fetched twice, and the bug is invisible on the three-node example in the prompt.
• Wrap every urlparse call on a discovered link. urlparse("http://a[b].com/x") raises ValueError, and one bad href from a real page takes down an unguarded crawl.
• An empty queue is not a termination condition. Count work claimed but not yet finished, claim each child before its parent releases itself, and put the decrement in a finally.
• Rate limits key on hostname. A global cap of 100 requests per second is perfectly consistent with sending all 100 of them to one small server.
• Dedup twice: normalize URLs before enqueue, fingerprint content after fetch. Neither layer catches the other's case.

Get the visited-set discipline right first

Asked at Anthropic — Implement hostname-restricted web crawler One thread, one seed URL, and a getUrls(url) interface that hands back the links on a page. Return every reachable page whose hostname exactly matches the seed's, with nothing fetched twice and no infinite loop when the links form a cycle. You pick BFS or DFS and defend the choice, then state complexity, explain how you pull a hostname out of a URL string, and describe what happens when a request fails.

That prompt is the whole coding round in six requirements, and the visited set answers four of them.

from collections import deque
from urllib.parse import urlparse

def same_host(link: str, host: str) -> bool:
    try:
        return urlparse(link).netloc == host
    except ValueError:
        # urlparse raises on malformed authorities: http://a[b].com/x
        return False

def crawl(start_url: str, html_parser) -> list[str]:
    host = urlparse(start_url).netloc   # your own seed; let a bad one raise
    seen = {start_url}
    queue = deque([start_url])
    order = []

    while queue:
        url = queue.popleft()
        order.append(url)
        for link in html_parser.getUrls(url):
            if link in seen:            # membership first; it is the cheap check
                continue
            seen.add(link)              # off-host links go in seen too, so a link
            if same_host(link, host):   # to twitter.com is parsed once, not once
                queue.append(link)      # per page that carries it
    return order

Time is O(V + E): every in-host page is fetched once, every link is inspected once. Space is O(V + E) in the worst case, and it is worth saying why rather than reflexively answering O(V). The queue holds at most V, but seen retains every distinct URL you have looked at, off-host ones included, and there can be one of those per edge.

Two mistakes cost people this round. The first is marking a URL visited when you pop it instead of when you push it, which lets the same URL sit in the queue several times and re-fetch. The second is a list for seen, turning each membership check into a linear scan and the crawl into O(V·E) in the worst case. Both are invisible on a three-node example and obvious on the grader's dense graph.

The hostname check has its own sharp edges. netloc carries the port and any userinfo, so example.com and example.com:80 compare unequal. Under a strict reading www.example.com is a different host from example.com, which is usually what the problem wants and almost never what a real crawler wants. Say which one you are doing out loud.

Real link extraction hands you garbage

Asked at Anthropic — Implement a same-host web crawler The same shape as above, with one requirement stacked on top: the crawler has to survive bad input. Duplicate links, cycles, and URLs that simply do not parse all arrive through the same get_links call, and none of them may take the run down. The follow-up pushes it onto several workers at once, still fetching each page exactly once, still pacing itself per host.

This is what the try around urlparse is for. It is not defensive padding. urlparse("http://a[b].com/x") raises ValueError: Invalid IPv6 URL, and so does an unterminated http://[::1. Link extraction over real HTML produces exactly this kind of debris, and an uncaught parse error ends the crawl over one malformed attribute.

Note where the guard sits. It wraps the per-link parse, so a single bad URL is skipped and its siblings still get queued. Wrapping the whole loop instead would throw away every link on the page because of one of them.

The seed is different. urlparse(start_url) on line one is deliberately unguarded, because that URL came from you rather than from the web. If it is malformed you want the crash immediately, not a crawl that quietly returns an empty list.

Retries decide whether the crawl is correct or merely quiet

Asked at Amazon — Build a BFS Web Crawler The fetch call here either returns HTML or raises. Traverse one domain breadth-first, but the graded requirements sit off to the side of the traversal: retry a transient failure up to three times, then skip that page and keep going, and resolve relative paths and strip fragments so two spellings of one page count as one. It is the traversal question with the network's real behavior bolted on.

The distinction to draw is retryable versus not. Timeouts, connection resets, 429 and 5xx are transient, so back off and try again. A 404 or a 403 is an answer, and retrying it burns your per-host budget on a page that will never load.

import random
import time

RETRYABLE = (TimeoutError, ConnectionError)   # status codes need their own branch;
                                              # a 503 is a return value, not a raise

def fetch_with_retry(url: str, html_parser, attempts: int = 3) -> list[str]:
    for i in range(attempts):
        try:
            return html_parser.getUrls(url)
        except RETRYABLE:
            if i == attempts - 1:
                raise                      # give up, let the caller record it
            time.sleep(0.2 * 2 ** i + random.uniform(0, 0.2))
    raise RuntimeError("unreachable")

Three attempts, exponential backoff, and jitter on top. The jitter starts mattering the moment you have many workers: without it, a host that 503s once gets every worker retrying in lockstep.

The raise on the final attempt is the load-bearing line. Swallowing a failed fetch and moving on is the version that loses points, because a crawl that silently drops 3% of its pages looks identical to a crawl that worked. The caller records the URL as failed; it does not pretend the page returned zero links.

Two things this snippet does not do. It catches exceptions, so an HTTP layer that returns a 503 object rather than raising needs a status check of its own. And it retries a page-level failure, which is the wrong tool for a host that is failing every request — that case belongs to adaptive backoff, below.

Concurrency turns this into a termination problem

Asked at Anthropic — Build a concurrent web crawler Take the same-host crawl and run it on a thread pool. fetch_links blocks, the graph is finite, and every eligible page must be fetched exactly once no matter how many pages link to it. Then explain your synchronization: what the lock protects, and how the whole thing knows it has finished.

Fetches take 200ms of network each, so parallelism is the obvious win. Termination is the part people get wrong. The queue being momentarily empty means nothing while workers are in flight and about to push more.

import threading
from concurrent.futures import ThreadPoolExecutor
from urllib.parse import urlparse

def crawl(start_url: str, html_parser, workers: int = 16, timeout: float = 60.0):
    host = urlparse(start_url).netloc
    lock = threading.Lock()
    seen = {start_url}
    crawled: list[str] = []
    failed: dict[str, str] = {}
    outstanding = 0                     # claimed but not yet finished
    done = threading.Event()
    pool = ThreadPoolExecutor(max_workers=workers)

    def finish() -> None:
        nonlocal outstanding
        with lock:
            outstanding -= 1
            if outstanding == 0:
                done.set()

    def spawn(url: str) -> None:
        nonlocal outstanding
        with lock:
            outstanding += 1            # claim the child BEFORE submitting it
        try:
            pool.submit(visit, url)
        except Exception as exc:        # e.g. pool already shutting down
            with lock:
                failed[url] = repr(exc)
            finish()                    # release the claim we just made

    def visit(url: str) -> None:
        try:
            children = fetch_with_retry(url, html_parser)
            fresh = []
            with lock:
                crawled.append(url)
                for link in children:
                    if link in seen:
                        continue
                    seen.add(link)
                    if same_host(link, host):   # cannot raise: guarded internally,
                        fresh.append(link)      # so no throw ever escapes the lock
            for link in fresh:
                spawn(link)
        except Exception as exc:
            with lock:
                failed[url] = repr(exc)
        finally:
            finish()                    # runs no matter what broke above
    spawn(start_url)
    if not done.wait(timeout):
        pool.shutdown(wait=False)
        with lock:
            stuck = outstanding
        raise TimeoutError(f"crawl did not finish, outstanding={stuck}")
    pool.shutdown(wait=False)
    with lock:
        return list(crawled), dict(failed)

Two things hold this together, and both are easy to leave out.

Claim-before-submit: a child is counted while its parent still holds its own claim, so outstanding cannot touch zero while a descendant is pending. And the finally. If anything in visit throws after the claim, the decrement still runs. Move that decrement to the bottom of the function body instead and one malformed URL leaves outstanding stuck above zero, done.wait() blocks forever, and you have reintroduced one level down exactly the bug the counter existed to prevent. The timeout on wait is the last line of defense: if a claim ever does leak, you want a loud failure over a hung process.

There is a third property here that is worth naming out loud, because it is the difference between this design and the one most candidates reach for. No worker ever waits on a child's result. Write it the natural recursive way, with each task calling future.result() on the children it submits, and a pool with 16 workers deadlocks as soon as 16 tasks are blocked on children that have no thread left to run them. Fire-and-forget plus a counter avoids that entirely.

Total work is still O(V + E). Wall clock drops by roughly the worker count, right up until politeness caps it. A single-host crawl at one request per second takes V seconds whether you run 16 threads or 1,600. Parallelism buys you host diversity rather than depth.

The usual follow-up is "now do it with coroutines." The asyncio shape is smaller: an asyncio.Queue, N worker tasks, await queue.join() for termination because the queue already tracks unfinished work, and task_done() in a finally for the same reason as above. Shared state is still shared, but a single event loop means seen needs no lock as long as you never await between the membership check and the insert.

Visit order is where the coding round becomes the design round

Asked at Google — Implement a Web Crawler with BFS and DFS Write both traversal orders against one link graph, with a hard cap on how many pages you are allowed to visit. State plainly what order each version produces. The follow-up goes after recursive DFS specifically: which bugs it invites, and where Python's recursion limit stops you.

Both orders run off one visited set, and the only difference is popleft versus pop. Two details earn the points. Recursive DFS dies on a deep site around Python's default recursion limit of 1,000 frames, so write it with an explicit stack. And max_pages has to be checked when you pop rather than when you push, or you stop counting the pages you visited and start counting the ones you merely queued.

That cap is the seed of the design-round answer. Once a budget exists, something has to decide which pages spend it.

Nothing in production stays on either pure form for long. The pop order becomes a score function, and BFS is what that degrades to when every score is equal.

The frontier is where priority and politeness collide

Asked at Glean — Implement Rate-Limited Wikipedia Crawler Crawl Wikipedia from a starting article under a rate limit, with an AI coding assistant open and the expectation that you can explain and modify whatever it produces. The interesting constraint is the pop order: prefer the next title whose first letter you have not covered yet. It is a scoring function on the queue, dressed up as an alphabet game.

Strip the Wikipedia framing and that is the frontier problem in miniature. Something scores the candidates, something else paces the fetches, and the two are separate mechanisms that have to share one queue. At web scale they actively fight. You want to fetch high-value URLs first, a news homepage before the fourteenth page of a forum archive. You must also never hammer one host, no matter how much of your high-value set lives there. A single global priority queue gives you the first and destroys the second, because the top of the heap will be 500 URLs from one domain.

The standard resolution is two tiers. Front queues hold URLs bucketed by priority. Back queues hold URLs bucketed by host, one host per queue. A router drains front queues, sampling by priority, into back queues, and a small heap keyed by "next time this host is allowed" tells fetchers which back queue to pop.

The invariant that makes this work: one host lives in exactly one back queue, and one back queue is served by at most one fetcher at a time. Politeness then needs zero coordination. It becomes a local property of a queue.

Politeness itself is three obligations, and candidates usually name only the first.

Fetch and cache robots.txt per host, respect Disallow for your user-agent, and honor Crawl-delay where present. Cache it with a TTL, and cache the failure cases too, so a host that 500s on /robots.txt does not get re-probed on every URL. Once a host's rules are cached, filter links against them at enqueue time, so a disallowed URL never occupies frontier space. The first URL you ever see for a new host is the exception, since there is nothing cached to check it against; that one gets checked at fetch time, and it is what triggers the /robots.txt fetch in the first place.

Second, the rate limiter keys on host.

import threading
import time

class HostRateLimiter:
    """At most one fetch per `interval` seconds per host."""

    def __init__(self, interval: float = 1.0):
        self.interval = interval
        self.next_ok: dict[str, float] = {}
        self.lock = threading.Lock()

    def acquire(self, host: str) -> None:
        while True:
            with self.lock:
                now = time.monotonic()
                ready = self.next_ok.get(host, 0.0)
                if now >= ready:
                    self.next_ok[host] = now + self.interval
                    return
                wait = ready - now
            time.sleep(wait)   # sleep outside the lock, then re-check

Sleeping outside the lock matters. Hold it across the sleep and you have serialized every host behind the slowest one. The loop re-checks because another thread may have claimed the slot while you slept. monotonic rather than time.time keeps an NTP correction from handing out a free burst.

Be honest about what this class does and does not guarantee. The rate limit holds. Fairness does not: the next slot goes to whichever thread reacquires the lock first, so with several threads contending for one host a thread can be passed over indefinitely. If that matters, hand out per-host tickets from a FIFO queue and have each thread wait its turn. In the frontier design above the question is moot, since one back queue is served by one fetcher.

The third obligation is adaptive backoff. A host returning 429 or 503 across many URLs is telling you the interval is wrong. Widen it, and narrow it slowly on success.

DNS deserves its own slide

Resolution is a blocking network round trip sitting in the fetch path, and it can cost more than the fetch. Standard resolvers are synchronous, so an unresolved host ties up a fetcher thread doing nothing. Cache resolutions with their TTL and cache negative results with a shorter one. The failure mode worth naming: a stale entry across a host's migration means you keep hammering a dead IP and mark a healthy host down.

Infinite URL spaces will eat the budget

Large parts of the web generate URLs forever, and a crawler with no defenses spends its entire budget there while looking perfectly healthy.

A calendar with a "next month" link is an infinite chain of distinct, non-duplicate pages. Faceted search produces a combinatorial explosion of filter permutations, most of them near-identical result lists. Session IDs baked into paths make every visit look like a new page. Broken relative links produce /a/b/a/b/a/b/… until something overflows.

No single mechanism catches all of these, so stack cheap ones: a depth cap from the seed, a per-host URL budget that has to be re-earned, a cap on path segment repetition and total URL length, a cap on query parameter count, and a per-host measure of how much genuinely new content the last N fetches produced. Hosts that keep returning near-duplicates get their priority cut. That last signal is the one that catches faceted search, because the pages are new URLs but their fingerprints cluster.

Dedup is two problems wearing one name

Asked at Anthropic — Implement crawler and file deduplication Two exercises in one loop. The first is the single-domain crawler, single-threaded and then multithreaded, with the discussion turning to duplicate suppression, termination, and slow pages. The second drops the web entirely: find duplicate files in a directory tree by grouping on size first and hashing contents only when sizes collide, then argue about I/O versus CPU bound work and what changes for very large files.

That second exercise is the content-fingerprinting half of a crawler with the network removed, and the size-first trick is the part that transfers. A SHA-256 over a normalized response body catches byte-identical duplicates for the cost of one hash, and comparing lengths before hashing skips most of that cost. Whether the hashing is even worth optimizing depends on which resource you are short of, which is why the interviewer pushes on I/O versus CPU. Stream large bodies rather than loading them, for the same reason the file version does.

The other half runs before you ever fetch

Asked at Anthropic — Crawl Same-Domain Links Return the unique pages reachable from a seed without leaving its domain, handling cycles and repeated links along the way. BFS or DFS is your call. The line worth preparing for is the last one: be ready to explain how you would normalize URLs so that one page under two spellings does not get visited twice.

Normalization runs before you enqueue. Lowercase the scheme and host, drop the default port, resolve . and .. segments, strip the fragment, normalize percent-encoding, and pick a trailing-slash rule that you then apply everywhere. Then the judgment call, which is query parameters. Stripping them all is the common wrong answer, because it collapses every paginated listing and every product page into a single URL. Strip known tracking parameters, keep the rest, and sort them only if you have decided order is not semantic for your targets.

Exact hashing does nothing about two pages that differ by a timestamp in the footer, which is why near-duplicate detection exists. Simhash gives each document a 64-bit fingerprint built from weighted feature hashes, and near-duplicates land within a small Hamming distance of each other; distance 3 is the threshold people usually reach for.

Comparing a new fingerprint against every stored one is linear in the corpus, so you index it. Split the 64 bits into four 16-bit blocks and keep four copies of the table, each permuted so a different block sits in the high bits, each sorted on that prefix. Two fingerprints within distance 3 differ in at most 3 bit positions, which cannot cover four blocks, so at least one block matches exactly. Probe all four tables and no true near-duplicate escapes. This is the scheme from Manku, Jain and Das Sarma's WWW 2007 paper on near-duplicate detection for web crawling.

Be careful how you describe the payoff. Sixteen bits is 65,536 buckets, so on a billion-document corpus a single probe still returns roughly fifteen thousand candidates, and you are doing four probes. Production deployments trade memory for shorter candidate lists by using more permuted tables with longer matching prefixes. Table count against candidates checked per lookup is the parameter you are actually tuning.

What changes on many machines

One URL through the pipeline looks like this, and it is the unit you shard.

The robots check appears in two places on purpose. Node K is the enqueue-time filter that keeps disallowed URLs out of the frontier entirely. Node B handles the case K cannot: a host discovered for the first time, whose rules nobody has fetched yet.

Shard the frontier by a hash of the hostname, using consistent hashing so adding a node reshuffles a slice instead of everything. That one decision keeps politeness, robots caching, and DNS caching node-local, because a host lives on exactly one node and nothing about rate limiting needs a distributed lock. Link extraction produces URLs for other hosts, which get routed to the owning node. That cross-node hop is the main internal traffic in the system and worth naming before you are asked.

The seen-URL set is the piece that outgrows a single machine first. A Bloom filter in front of a sharded key-value store absorbs almost all lookups; accept the false-positive rate as a small number of pages you will never crawl, and pick your bit budget accordingly. Content goes to blob storage keyed by content hash, which makes storage dedup free.

Everything here is at-least-once. A fetcher can die between storing a page and acking the URL, so make the write idempotent on URL plus content hash and stop worrying about it.

Freshness competes for the same budget

A crawler that only discovers is a crawler whose index is wrong within a week. Recrawl draws on the same politeness allowance as discovery, so make the split explicit: a fixed share of each host's budget goes to refresh, the rest to new URLs.

Per-URL, estimate a change rate and let the interval adapt. Unchanged on recrawl, multiply the interval up to a ceiling; changed, cut it toward a floor. Conditional requests make an unchanged page nearly free: send If-None-Match with the stored ETag or If-Modified-Since with the stored timestamp, and a 304 tells you to reschedule without transferring a body. Sitemap lastmod values are a useful prior, though plenty of publishing systems stamp them on every deploy regardless of what changed, so let them nudge the interval instead of setting it.

At this stage the component list is table stakes. What gets remembered is naming the invariant each choice protects, and answering "what if one host is 40% of your frontier" with "it is one back queue on one node, so it self-throttles and the other shards never notice."

Practice these on PracHub

The design answer gets much sharper once the traversal is muscle memory. These are real questions from real loops.

Traversal and scope

• Implement hostname-restricted web crawler (Anthropic) — start here. Forces you to state complexity and justify BFS over DFS rather than assume it.
• Implement a same-host web crawler (Anthropic) — same shape, but malformed URLs are an explicit requirement, so the parse guard is graded.
• Crawl Same-Domain Links (Anthropic, premium) — the scope rule stated as domain rather than host, with URL normalization as the discussion. Worth doing right after the previous one to see how much of your answer was pattern-matching the wording.
• Implement a BFS web crawler (Nooks, premium) — the interface returns duplicate links on purpose. Cheap check that your dedup sits on enqueue.

When the network misbehaves

• Build a BFS Web Crawler (Amazon, premium) — retries, skipping permanent failures, and normalization are first-class requirements here. Write the backoff, not just the queue.

Ordering and pacing

• Implement Rate-Limited Wikipedia Crawler (Glean, premium) — a 75-minute AI-assisted assignment. One host, so it drills the limiter's mechanics and the pop-order rule instead of per-host fairness, and it is the closest thing here to how the work actually happens.
• Implement a Web Crawler with BFS and DFS (Google, premium) — both traversals against one visited set, a page budget, and then Python fundamentals on top: recursion limits, instance versus class state, hashing bugs.

Concurrency and dedup

• Build a concurrent web crawler (Anthropic) — termination detection and shared-state locking are what break here, with a coroutine follow-up.
• Implement crawler and file deduplication (Anthropic) — a crawler plus a separate size-then-hash dedup question, with follow-ups on I/O versus CPU bound work and very large files.

If you only do two, take the hostname-restricted Anthropic crawler and the concurrent one back to back. Both are free. The first drills visited-set discipline and makes you defend a complexity claim out loud; the second makes you actually write the termination detection that a design answer only ever gets to summarise in a bullet.

FAQ

Should a web crawler use BFS or DFS?

BFS for anything general. Breadth-first tends to reach important pages early, since pages near a seed are usually higher value, and it keeps you from disappearing down one deep branch. DFS is reasonable when you are deliberately archiving a single site and want low memory, but it walks straight into calendar-style infinite URL spaces. Production crawlers use a priority frontier, and BFS is the sane default that degrades to.

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

At two layers. URL normalization plus a seen-set, usually a Bloom filter in front of a persistent store, stops the same page being enqueued under different URL spellings. Content fingerprinting after the fetch catches distinct URLs serving the same body: an exact hash for byte-identical pages, and simhash or minhash for near-duplicates that differ only in a timestamp or sidebar.

How do you handle robots.txt in a crawler design?

Fetch it once per host, parse the rules for your user-agent, and cache it with a TTL, including caching failures so a broken host is not re-probed constantly. Once a host's rules are cached, filter links against Disallow at enqueue time, so a disallowed URL never occupies frontier space or fetch budget. The first URL from a newly discovered host is the exception, since there is nothing to check it against until you have fetched /robots.txt. Honor Crawl-delay as a floor on your per-host interval.

How do you know when a concurrent crawler is finished?

Keep a counter of tasks claimed but not yet completed, and claim each child before its parent releases itself, so the counter cannot reach zero while descendants are pending. Signal an event when it hits zero. The decrement must sit in a finally block: if a worker throws after claiming work, a missed decrement means the counter never reaches zero and your wait blocks forever. An empty queue is not a termination condition, because workers still in flight are about to refill it.

Why does per-host rate limiting matter more than a global limit?

A global cap of 100 requests per second permits all 100 of them to land on one small server, which is how crawlers get blocked and how they take sites down. Keying the limiter by hostname bounds your impact on any single operator. The two-tier frontier makes this nearly free, since one host maps to one back queue served by one fetcher, so the pacing needs no shared state.

How do you scale a web crawler across many machines?

Shard by a hash of the hostname, with consistent hashing so adding capacity moves a slice rather than everything. Because a host maps to exactly one node, per-host rate limiting, robots caching, and DNS caching all stay node-local and need no distributed coordination. Extracted links for other hosts get routed to their owning node, which is the main cross-node traffic in the system.