Design a Web Crawler

The core features we need to support:

• Start from seed URLs and discover new pages by following links.
• Fetch and store the HTML of each page (for a search index, an archive, or an ML dataset).
• Respect robots.txt: never fetch paths a site disallows, and honor a crawl delay if one is given.
• Be polite: never overload a single host, no matter how many of its URLs are queued.
• Avoid duplicates: don't fetch the same URL twice in one cycle, and recognize pages whose content is the same or nearly the same.
• Recrawl pages so the stored copy stays reasonably fresh, visiting pages that change often more often.

Example. The seed is https://news.com/. The crawler fetches it, finds 300 links, and queues the new ones. A link to https://NEWS.com:443/story?id=7&utm_source=x#top normalizes to the same URL as one already seen, so it's skipped. Links to wikipedia.org go into wikipedia's own queue, which is fetched about once a second at most.

Out of scope for a first pass: rendering JavaScript-heavy pages in a headless browser, indexing and ranking (the search engine's job), and crawling content behind logins. Mention them so the interviewer knows you're scoping on purpose.

Rough numbers to anchor the design:

• 1 billion pages per month. A 30-day month is 30 × 86,400 ≈ 2.6 million seconds.
• 1B / 2.6M ≈ ~400 pages/sec on average; plan for peaks of ~2× (≈800 pages/sec).
• An average page is about 100 KB of HTML → 400 × 100 KB ≈ 40 MB/s of download bandwidth on average.
• Storage: 100 KB × 1B ≈ 100 TB per month of raw HTML (compression typically cuts that by several times). Keep a few months and you're in the petabyte range, so it goes to object storage.
• Seen-URL set: the frontier will discover several times more URLs than it fetches. A Bloom filter at a 1% false-positive rate needs about 9.6 bits per URL, so ~1.2 GB per billion URLs, small enough for memory.

The takeaway: 400 fetches a second is not a lot of CPU. The design is dominated by politeness (most of that capacity sits waiting on per-host delays), network latency (each fetch takes hundreds of milliseconds, so you need thousands of concurrent fetches), and dedup at scale.

• Politeness is a hard requirement. At most one connection per host and a delay between requests. A crawler that gets banned or takes down a small site is broken, however fast it is.
• Robustness. The web is full of malformed HTML, slow servers, redirect loops, huge files and spider traps. One bad host must never stall the whole crawl.
• Scalability. Add fetcher workers to go faster, without reshuffling every host.
• Extensibility. New content types (PDFs, images) or new processing steps plug in after the parser.
• Freshness over completeness. It's fine to never reach every page on the web; it's not fine for the important pages to be weeks stale.
• Eventual consistency is fine. If two workers race and a page is fetched twice, that's wasted work, not a correctness bug.

A crawler is a pipeline rather than a request/response service, so the "API" is the contract between stages:

frontier.add(url, priority)            // after normalize + seen-set check
frontier.next(worker_id) -> url        // respects host heap + crawl delay
fetcher.fetch(url) -> { status, headers, body, final_url }
parser.parse(page) -> { links[], content_hash, simhash }
scheduler.record(url, changed: bool)   // updates recrawl interval

Operators also want a small admin surface: add seed URLs, block or throttle a host, and see per-host stats (queue length, error rate, last fetch). The throttle control matters in practice, because the fastest fix for an angry site owner is lowering their crawl rate right away.

The core loop:

1. Seed URLs go into the URL frontier, the to-do list of pages to crawl.
2. A fetcher asks the frontier for the next URL. The frontier only hands out a URL whose host is allowed to be fetched now.
3. The fetcher resolves the host through the DNS cache, checks the cached robots.txt rules, and downloads the page.
4. The parser writes the page to the content store, computes its content hash and SimHash, and extracts every link.
5. Each link is normalized and checked against the seen-URL set. New URLs go back into the frontier with a priority.
6. The recrawl scheduler records whether the page changed and decides when it's due again; due pages re-enter the frontier.

At ~400 pages a second, that loop runs on a fleet of fetcher workers. Hosts are assigned to workers with consistent hashing, so each host's queue, robots rules and DNS entry live on exactly one worker.

The frontier answers one question: which URL should we fetch next? It has two layers.

Layer 1: front queues, one per priority. A news homepage goes in a high-priority queue; a deep link to an old blog post goes in a low one. Priority can come from PageRank-like importance, how often the page changes, or how close it is to a seed.

Layer 2: back queues, one per host. Every URL from wikipedia.org waits in wikipedia's back queue. A router moves URLs from the front queues into the back queues, picking from high-priority queues more often (weighted random), so important pages flow through first without starving the rest.

The host heap. Each host has a next allowed fetch time. Those times sit in a min-heap, earliest on top. A fetcher:

1. Pops the top of the heap, for example wikipedia.org at time 0.
2. Takes one URL from wikipedia's back queue and fetches it.
3. Pushes wikipedia.org back with next_fetch_at = now + crawl_delay (say 1 s).

Now news.com at 0.4 s is on top, so it's next. A host can never be fetched again before its delay has passed, and a fetcher never busy-waits: if the top of the heap is in the future, it sleeps until then.

Sizing. The frontier holds billions of URLs, far more than memory. Keep the head and tail of each queue in memory and the middle on disk (or in a log like Kafka per partition), refilling the in-memory buffer as it drains.

• robots.txt first. Before crawling a host, fetch /robots.txt, parse it, and cache the rules per host for about a day. Every URL is checked against the cached rules before it is fetched. If robots.txt itself returns a 5xx, back off from the whole host rather than assuming everything is allowed.
• Crawl delay. If robots.txt sets Crawl-delay: 2, wait at least 2 seconds between requests to that host. Otherwise use a default (about 1 second), and adapt it: if the host's response time climbs, increase the delay.
• One connection per host. Per-host concurrency is 1. The back-queue design gives this for free: one back queue per host, drained by exactly one worker.
• Identify yourself. Use a clear User-Agent with a contact URL, so site owners can reach you instead of blocking you.
• Respect signals. 429 Too Many Requests and 503 with Retry-After push the host's next fetch time out.

Step 1: normalize URLs. Lowercase the scheme and host, drop default ports (:443, :80), drop the #fragment, remove tracking parameters (utm_*) and session IDs, and sort the remaining query parameters. https://NEWS.com:443/a?b=2&a=1&utm_source=x#top becomes https://news.com/a?a=1&b=2.

Step 2: a seen-URL set. Before queueing, check whether the normalized URL was seen.

• A Bloom filter holds a billion URLs in about 1.2 GB at a 1% false-positive rate. A false positive means we wrongly think a new URL was seen and skip it, which is usually acceptable for a crawler.
• If you can't afford to skip anything, use a hash set in a key-value store (keyed by a 64-bit URL hash), sharded the same way as hosts.

Step 3: content dedup. Different URLs can still serve the same page.

• Exact copies: hash the content (e.g. SHA-256 of the normalized body) and look it up in a fingerprint store.
• Near copies: compute a SimHash (a 64-bit fingerprint where similar documents get similar bits). Two pages whose fingerprints differ in only a few bits (Hamming distance ≤ 3, say) are near-duplicates. Finding them quickly uses a few tables keyed by different bit blocks of the fingerprint.

Near-duplicates are usually still stored as a pointer to the canonical page, but their links aren't re-extracted and they get a low recrawl priority.

• DNS is a hidden bottleneck. A lookup can take tens of milliseconds, and system resolvers are often synchronous. Each worker keeps its own DNS cache (host → IPs, honoring TTLs, refreshed in the background) and uses an async resolver.
• Consistent hashing on the host. Hash each host onto a ring; the next worker clockwise owns it. One host lives on one worker, so its back queue, robots rules, DNS entry and politeness timer are all local, and per-host concurrency of 1 is enforced without any distributed locking.
• Adding a worker only moves the hosts between the new worker and its predecessor on the ring, not a full reshuffle. Use virtual nodes so the load spreads evenly.
• Concurrency inside a worker. Fetches are network-bound, so each worker runs hundreds or thousands of concurrent async fetches across different hosts.
• Failure. If a worker dies, its hosts move to the next worker on the ring, which rebuilds their queues from the durable frontier log.

Spider traps are sites that generate an unbounded number of URLs:

• A calendar with a "next month" link that goes on forever.
• Session IDs in the URL, so every visit looks like a brand-new page.
• Paths that repeat (/a/b/a/b/a/b/...) from relative-link bugs, or faceted search with endless filter combinations.

Defenses:

• Max crawl depth from the seed (e.g. 20 hops).
• Max URL length (e.g. 2,000 characters) and a cap on repeated path segments.
• Page budget per host per crawl cycle (e.g. 100k pages), raised manually for big trusted sites.
• Strip known session-ID parameters during normalization.

Failures and retries. Timeouts, 5xx errors and connection resets are normal. Retry with exponential backoff (1, 2, then 4 minutes), then mark the URL dead for this cycle. Cap redirects (say 5) to avoid redirect loops, and cap page size so one 2 GB file doesn't stall a fetcher.

Pages change at wildly different rates: a news homepage changes every hour, an old blog post almost never.

A simple adaptive policy:

• Start every page at a 24-hour recrawl interval.
• On each visit, compare the content hash with the last one. Changed → halve the interval. Unchanged → double it. Clamp between, say, 1 hour and 30 days.
• After five visits, a news homepage that always changes is at every hour; a blog post that never changes is at every 30 days.

The recrawl scheduler stores next_due per page and feeds due pages back into the frontier, with a priority that reflects importance. Conditional requests (If-Modified-Since, ETag) make unchanged revisits cheap: the server answers 304 Not Modified with no body.

A solid answer hits these points:

• The core loop: seed → frontier → fetcher → parser → links back to the frontier.
• A two-layer URL frontier: priority front queues, one back queue per host, and a min-heap of next allowed fetch times for politeness.
• robots.txt cached per host, crawl delay, and one connection per host.
• Dedup: URL normalization, a Bloom filter (or KV hash set) for seen URLs, content hashes for exact copies and SimHash for near copies.
• Scale out: DNS caching, and hosts assigned to workers by consistent hashing so each host lives on one worker.
• Robustness: depth, URL length and per-host limits against spider traps; exponential backoff on failures.
• Freshness: adaptive recrawl intervals based on how often each page changes.

Common follow-ups: crawling JavaScript-rendered pages (a separate, much more expensive headless-browser pool for the pages that need it), prioritizing which pages to crawl first, geographically distributed crawling, and handling hosts that share an IP (politeness should then be per IP, not just per host name).