Concurrent Web Crawler

Overview

Build a crawler that starts from a seed URL, fetches the page, extracts its links, and keeps following them — using many worker threads to fetch in parallel. Each URL is visited at most once, and the crawl is usually restricted to a single domain.

The fetching is I/O-bound, so concurrency pays off, but the shared state is the catch. A thread-safe frontier (the queue of URLs to visit) hands work to idle workers, and a thread-safe visited set prevents two threads from crawling the same page. The subtle part is knowing when the crawl is done — the queue being momentarily empty isn't enough while workers are still discovering links.

Interfaces

class WebCrawler:
    def __init__(self, num_workers, same_domain_only=True):
        self._frontier = Queue()          # URLs waiting to be fetched
        self._visited = set()
        self._lock = Lock()               # guards _visited
        self._num_workers = num_workers

    def crawl(self, seed_url):
        """Crawl from seed_url and return the set of pages visited."""
        ...

    def _worker(self):
        # pull a URL, fetch it, enqueue new same-domain links not yet seen
        ...

    def _claim(self, url):
        """Atomically mark url visited; return False if already seen."""
        with self._lock:
            if url in self._visited:
                return False
            self._visited.add(url)
            return True

Workers loop: take a URL from the frontier, fetch it, parse out links, and for each unseen same-domain link, mark it visited and enqueue it. Marking-and-checking must be one atomic step so two workers never both claim the same URL.

Inputs and outputs

• Input: a seed URL, a worker count, and a domain restriction.
• Output: the set of pages successfully visited, each fetched exactly once.

Requirements

• Fetching runs across num_workers threads in parallel.
• Each URL is fetched at most once — claim it atomically before enqueuing.
• Only in-scope links (e.g. same domain) are followed.
• Termination is detected correctly: stop when the frontier is empty and no worker is still processing.
• Network errors on one page don't crash the crawl.

Examples

c = WebCrawler(num_workers=8, same_domain_only=True)
visited = c.crawl("https://example.com")

# fetches example.com, follows its internal links across 8 threads,
# skips external domains, and visits each internal page exactly once

Follow-ups

• How would you add politeness — per-domain rate limits and robots.txt — without leaving all your workers idle?

• Some fetches fail transiently. How would you retry with backoff without crawling the same page twice?

• How would you move the visited set and frontier out of memory (say, into Redis) so the crawl scales across machines?

• And more...