Cracking The System Design Interview Together – Problem 9.3: Web Crawler

Picture this: You are sitting in a senior system design interview, and the interviewer leans forward and drops a deceptively simple prompt on the table: "Design a web crawler." At first glance, it sounds like a weekend scripting project using Python and Beautiful Soup. But as you start thinking about the sheer scale of the internet—billions of pages, dynamic JavaScript rendering, duplicate content, and malicious trap links—you realize we are standing at the edge of a massive distributed systems engineering challenge.

If our crawler is too slow, we miss fresh content. If it is too fast, we nuke a small business's web server with denial-of-service traffic. If we don't handle cycles and duplicates, our queue explodes into infinity. Today, we are going to build a mental and technical model that tackles these exact trade-offs head-on. Let us dive in.

Problem Statement

Our objective is to design a scalable, robust, and extensible web crawler system. Given a set of seed URLs, our crawler must systematically traverse the web, download web pages, extract new links, and store or index the content. We need to satisfy the following operational goals:

• Scale: Ability to crawl hundreds of millions or billions of pages per month.
• Extensibility: Support for new types of content parsers and storage backends.
• Politeness: Never hammer a single host with concurrent requests; respect robots.txt rules.
• Robustness: Handle malformed HTML, infinite traps, and server timeouts gracefully.

Analyze the Problem Together

When designing a distributed crawler, the naive approach is to use a single multithreaded application that pulls URLs from an in-memory queue and fetches pages over HTTP. While this works for a portfolio project, it falls apart at production scale. Why? Because an in-memory queue isn't durable, a single machine has bandwidth limits, and managing polite request rates across thousands of threads on one node introduces massive thread-contention bottlenecks.

The "Aha!" conflict in web crawling isn't just fetching HTML—it is managing state. We need to answer three hard questions continuously: Have we seen this URL before? Are we allowed to crawl this host right now? and Where do we store the newly discovered links without overwhelming our system? To solve this, we must decouple our architecture into specialized components communicating asynchronously.

Questions for the Interviewer

Before jumping into drawing boxes and arrows, a senior engineer always clarifies scope and non-functional requirements. Here are the questions we should ask:

• What is the scale of our crawl? Are we crawling the entire internet, or just a specific domain subset (focused crawler)?
• Do we need to render JavaScript-heavy Single Page Applications (SPAs), or is static HTML parsing sufficient?
• How fresh does the data need to be? Are we running a one-time snapshot or continuous incremental crawls?
• How should we handle duplicate content (boilerplate text, syndicated articles)?

Think About the Solution

Our production-ready architecture revolves around a centralized coordinator and a distributed worker model. Let us break down the core components:

• URL Frontier: The heart of the crawler. It manages the queue of URLs to be fetched, split into two tiers: the priority queues (deciding what to fetch next) and the politeness queues (ensuring we don't spam specific domains).
• HTML Downloader: Fetches web pages from the internet using asynchronous networking libraries.
• DNS Resolver: Caches DNS lookups to avoid blocking worker threads during network calls.
• Content Parser: Validates, parses, and extracts links and text from raw HTML bytes.
• Deduplication Service: Uses Bloom filters and database lookups to ensure we never crawl the same URL or content hash twice.

Write Code and Explain

Let us write a clean, concurrent Java implementation illustrating the core logic of a worker thread pulling from a polite URL queue and managing content extraction and deduplication.

import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class WebCrawlerEngine {

    // Thread-safe set to keep track of visited URLs and prevent duplicate work
    private final Set<String> visitedUrls = ConcurrentHashMap.newKeySet();
    
    // The URL frontier queue holding pending links
    private final BlockingQueue<String> urlFrontier = new LinkedBlockingQueue<>();

    public void addSeedUrl(String url) {
        if (visitedUrls.add(url)) {
            urlFrontier.offer(url);
        }
    }

    public void startCrawling() {
        while (!urlFrontier.isEmpty()) {
            String currentUrl = urlFrontier.poll();
            if (currentUrl == null) break;

            try {
                // 1. Fetch web page content
                String htmlContent = fetchPage(currentUrl);

                // 2. Parse HTML and extract new links
                Set<String> extractedLinks = parseAndExtractLinks(htmlContent);

                // 3. Filter and push new links to frontier
                for (String link : extractedLinks) {
                    if (visitedUrls.add(link)) {
                        urlFrontier.offer(link);
                    }
                }

            } catch (Exception e) {
                System.err.println("Failed to crawl URL: " + currentUrl + " due to " + e.getMessage());
            }
        }
    }

    private String fetchPage(String url) {
        // Mock network fetch implementation
        System.out.println("Fetching content from: " + url);
        return "<html><body><a href='http://example.com/page2'>Next</a></body></html>";
    }

    private Set<String> parseAndExtractLinks(String html) {
        // Mock parser returning discovered links
        return Set.of("http://example.com/page2");
    }
}

Walkthrough: In this snippet, we use a ConcurrentHashMap.newKeySet() to ensure thread-safe atomic checks for URL deduplication. The LinkedBlockingQueue acts as our basic URL frontier. When a worker polls a URL, it simulates fetching the page, extracts new links, and atomically checks and adds newly discovered links back into our tracking set and frontier queue.

Time & Space Complexity

• Time Complexity: O(N) where N is the total number of unique valid URLs discovered and processed. Each URL lookup and insertion in our concurrent set takes O(1) average time.
• Space Complexity: O(N) to store the visited URLs set and the active URL frontier in memory. At massive scale, memory is saved by substituting in-memory sets with probabilistic data structures like Bloom filters combined with disk-backed storage.

Why This Problem Matters (The Senior Perspective)

Designing a web crawler touches almost every pillar of large-scale distributed systems. In production environments, simple in-memory queues are replaced by distributed message brokers like Apache Kafka or Redis clusters. Politeness is enforced via token bucket rate limiters per domain. Furthermore, dealing with malicious traps—such as infinite calendar loops generating endless unique URLs—requires intelligent heuristics, URL normalization, and depth limits.

Final Thoughts

Building a web crawler bridges theoretical data structures with real-world networking constraints. By breaking down state management, politeness, and concurrency, you can design systems that scale effortlessly. Keep experimenting, stay curious, and happy coding!