Concurrent same-host web crawler

This is a graph traversal. Pages are nodes and links are edges. The parser call is the slow part, and it is I/O-bound, so we run many fetches at the same time. The traversal itself stays simple.

Single-threaded baseline (write this first). Use BFS from start_url. Keep a seen set. For each URL popped from the queue, fetch its links, normalize each one, keep it only if its hostname equals the start hostname, and enqueue it if it is new. This is correct and takes O(V + E) work, but every fetch waits for the one before it. With 1,000 pages at 100 ms each, that is 100 seconds.

Concurrent version. We keep the same BFS, but fetches run in a thread pool:

• Only the coordinator thread touches seen and decides what to submit. Workers only call get_urls and return the result. No lock is needed, because nothing shared is mutated off the coordinator thread.
• Mark a URL as seen when you submit it, not when it finishes. Otherwise two pages that both link to /a can schedule /a twice.
• Termination: we are done when no fetch is still running. An empty queue alone does not mean done: a fetch still in flight may return new links. We track the set of pending futures and loop until it is empty. wait(..., FIRST_COMPLETED) lets us expand links as soon as any fetch returns, so one slow page does not hold back a whole BFS level.
• Normalization: drop the #fragment (it is the same page) before the hostname check and dedupe. Compare urlparse(url).hostname exactly, so blog.example.com is not the same host as example.com.
• Failures: a fetch that raises is treated as a page with no links. The page still counts as discovered, and the crawl goes on.

Invariant: every URL in seen has the start hostname and was submitted exactly once. When pending is empty, every URL in seen has been expanded, so seen is the full reachable set.

Python threads work well here despite the GIL, because the GIL is released while a thread waits on network I/O.

from __future__ import annotations

from collections import deque
from concurrent.futures import FIRST_COMPLETED, Future, ThreadPoolExecutor, wait
from typing import Callable, Iterable
from urllib.parse import urldefrag, urlparse

GetUrls = Callable[[str], Iterable[str]]


def normalize(url: str) -> str:
    """Drop the #fragment; it points at the same page."""
    return urldefrag(url)[0]


def hostname(url: str) -> str | None:
    return urlparse(url).hostname


def crawl_sequential(start_url: str, get_urls: GetUrls) -> list[str]:
    start = normalize(start_url)
    host = hostname(start)
    seen = {start}
    queue = deque([start])
    while queue:
        url = queue.popleft()
        for link in get_urls(url):
            link = normalize(link)
            if hostname(link) == host and link not in seen:
                seen.add(link)
                queue.append(link)
    return sorted(seen)


def crawl(start_url: str, get_urls: GetUrls, max_workers: int = 8) -> list[str]:
    """Concurrent BFS. Only this (coordinator) thread reads or writes `seen`."""
    start = normalize(start_url)
    host = hostname(start)
    seen: set[str] = {start}

    def fetch(url: str) -> list[str]:
        try:
            return list(get_urls(url))
        except Exception:
            return []  # a failed page still counts as found; it has no links

    with ThreadPoolExecutor(max_workers=max_workers) as pool:
        pending: set[Future[list[str]]] = {pool.submit(fetch, start)}
        while pending:  # done only when nothing is in flight
            done, pending = wait(pending, return_when=FIRST_COMPLETED)
            for future in done:
                for link in future.result():
                    link = normalize(link)
                    if hostname(link) == host and link not in seen:
                        seen.add(link)  # mark on submit, never on finish
                        pending.add(pool.submit(fetch, link))
    return sorted(seen)

• Let V be the number of same-host pages reached and E the number of links on them.
• Time (CPU work): O(V + E) for parsing, hashing and set lookups. Sorting the result adds O(V log V).
• Wall-clock time: about (V / max_workers) × fetch latency when pages are evenly slow. The lower bound is the longest chain of links times the fetch latency, because a page cannot be fetched before a page that links to it.
• Space: O(V) for seen, plus at most O(V) pending futures. Each future holds one page's link list until the coordinator reads it.

• Start http://a.com/ links to /x, /y; /x links to /y and back to /. Expected: ["http://a.com/", "http://a.com/x", "http://a.com/y"]. Each page is fetched exactly once.
• Cycle /1 → /2 → /3 → /1: terminates, returns all three.
• Start page has no links: returns [start_url].
• Links to http://blog.a.com/p and http://b.com/: both excluded (exact hostname match only).
• Link http://a.com/x#top when /x is also linked: counted once as http://a.com/x.
• get_urls raises for /x: /x is still in the result and the crawl finishes.
• Diamond of 50 pages that all link to every other page, max_workers=8: 50 results, and a counter shows exactly 50 fetches.
• Slow fetches (100 pages, 50 ms each, 10 workers): the concurrent version runs about 10x faster than crawl_sequential and returns the same list.

1. Max depth or max pages. Store depth with each submitted URL (pool.submit(fetch, link) maps to depth + 1) and skip submitting past the limit. For a page cap, stop submitting once len(seen) reaches the cap. The pending fetches still drain.
2. Politeness and rate limits. Add a per-host token bucket or a threading.Semaphore that limits in-flight requests per host. Read robots.txt once per host and filter on it. With a single host, a global limit of N requests per second can be a shared token bucket that each worker checks before it fetches.
3. asyncio instead of threads. Make get_urls an async function and replace the pool with asyncio.Semaphore(max_workers) plus asyncio.wait(tasks, return_when=FIRST_COMPLETED). The structure stays the same. Threads are the choice when the parser is blocking code you cannot change. CPU-heavy parsing would need processes, because of the GIL.
4. Retries and timeouts. Wrap fetch with a timeout and retry transient errors with exponential backoff and jitter. Record pages that keep failing instead of dropping them silently.
5. Distributed crawl across machines. Partition URLs by hash(host) so that one worker owns each host's politeness. Keep the frontier in a durable queue and the seen set in a shared store such as Redis SADD, which also gives atomic test-and-set. Termination then needs a count of in-flight work, or a coordinator that checks all queues are empty and no leases are held.

Mid-level (L4)

• Writes the correct sequential BFS with a seen set and an exact hostname filter.
• Makes it concurrent with a thread pool and avoids crawling a URL twice (lock or single coordinator).
• Terminates correctly and can explain why.

Senior (L5)

• Marks URLs as seen at submit time, and explains the race that occurs otherwise.
• Gets termination right with in-flight tracking, not "queue is empty".
• Handles fragments, fetch errors and cycles. Explains why the GIL does not hurt here and when asyncio is the better choice.

Staff (L6+)

• Talks about politeness, rate limits, robots.txt, retries with backoff, and memory limits on the frontier.
• Extends the design to a distributed crawler: host-based partitioning, a shared dedupe store, durable frontier, and distributed termination detection.
• Discusses observability (pages per second, error rate, queue depth) and how to test concurrency (deterministic fake parser, fetch counters, latency injection).