Skip to main content

Design a Web Crawler

A web crawler is a different flavor of medium problem — there's no human user waiting on a response at all; the entire system is a distributed background job whose correctness hinges on not visiting the same URL twice and not overwhelming any single website it crawls. Following the framework from How to Answer a System Design Interview Question.

1. Requirements​

Functional:

  • Starting from a set of seed URLs, discover and fetch pages, extract new links from each, and continue recursively.
  • Store fetched page content for downstream use (e.g. search indexing).

Non-functional:

  • Must not re-crawl a URL it's already visited.
  • Must be polite — never overwhelm a single domain with too many concurrent requests, regardless of how many links to it were discovered.
  • Must scale horizontally across many crawler workers operating on the same overall frontier of URLs to visit.

Scale estimate: assume a target of crawling 1 billion pages, with many multiples of that in discovered-but-not-yet-visited URLs sitting in the frontier at any time — the "have we seen this URL before" check has to stay fast even against a set of that size, which is the deep dive below.

2. API Design​

This system has no external client-facing API in the usual sense — it's an internal pipeline. The closest thing to an interface is the contract between its own stages:

frontier.pop() -> url
fetcher.fetch(url) -> { html, status }
extractor.extract_links(html) -> [url, ...]
frontier.push(url)  -- only if not already seen

3. Data Model​

seen_urls        -- Bloom filter (probabilistic set membership)
frontier         -- queue of URLs not yet crawled, partitioned by domain
pages
  url            VARCHAR PRIMARY KEY
  content_hash   VARCHAR
  fetched_at     TIMESTAMP

4. High-Level Design​

System Design Lab

5. Deep Dive: has this URL already been seen?​

At the scale of billions of discovered URLs, "check whether this URL is already in the seen set" is executed constantly, and a straightforward database lookup or in-memory hash set either doesn't fit in memory or is too slow to run on every single discovered link. This is precisely the problem Bloom Filters exist to solve cheaply: a fixed-size, constant-memory structure that can answer "definitely not seen" instantly and correctly, at the cost of occasionally answering "maybe seen" for a URL that's actually new — which just means an occasional unnecessary skip or a fallback check, not a correctness failure, since it never wrongly re-adds something already crawled.

The other structurally important decision is partitioning the frontier by domain, not randomly — this is what makes politeness enforceable at all: if every worker pulled from one global, undifferentiated queue, nothing would stop many workers from simultaneously hammering the same popular domain purely by chance. Keeping a separate queue per domain, with a rate limit applied per domain (the exact mechanism from Rate Limiting), guarantees no single website ever receives more than its configured share of concurrent requests, regardless of how many links to it the crawler has discovered.

6. Deep Dive: deciding what to recrawl, and detecting real change​

A crawl is never really "done" — pages change after they're first fetched, and a crawler that only ever visits each URL once produces an index that gets staler by the day. That raises two questions the design so far doesn't answer: which already-crawled pages get revisited, and how does the crawler tell a page that genuinely changed from one that's byte-for-byte identical to what it fetched last time?

Recrawl scheduling. Naively recrawling every known URL on the same fixed interval wastes most of the crawl budget on pages that rarely change (a company's "About" page) while under-serving pages that change constantly (a news homepage). The frontier generalizes to handle this cleanly: alongside newly discovered URLs, it also holds already-crawled URLs due for a revisit, each with its own adaptive delay — a page whose last few fetches showed no change earns a longer wait before its next revisit; a page that keeps changing gets rescheduled sooner. This is the same "spend limited resources where they actually pay off" reasoning Cache Eviction Policies applies to what stays resident in a cache, just applied to crawl frequency instead of memory.

Change detection. Even once a page is due for a revisit, re-running full link extraction and re-indexing on content that hasn't actually changed wastes the same downstream processing this system exists to avoid duplicating. This is what content_hash in the Data Model is for: after each fetch, hash the page's content and compare it against the hash stored from the previous crawl. A mismatch means real content changed, and downstream processing (re-extracting links, re-indexing) needs to run again; a match means nothing changed, and the crawl can stop at "confirmed still fresh" without paying for extraction or indexing a second time on identical bytes.

System Design Lab

7. Tradeoffs​

The Bloom filter's occasional false positive means a small fraction of genuinely new URLs get skipped rather than crawled — an acceptable, deliberate cost given the alternative (an exact but far more memory- and time-expensive set) doesn't fit the scale this system operates at. Per-domain queue partitioning adds real coordination overhead compared to one global queue, but it's the only structure that makes politeness enforceable rather than accidental.

Adaptive recrawl scheduling has its own version of the same tension: too long a delay for a page assumed stable risks missing a real change and serving stale results until the next scheduled visit catches it; too short a delay wastes crawl budget re-fetching pages that turn out unchanged yet again. The content_hash check keeps that second cost cheap — comparing a hash is nearly free next to the actual cost this design is trying to avoid, which is redundant link extraction and re-indexing, not the fetch itself.

Bloom filter vs. an exact seen-URL set: pros and cons​

Bloom filter

  • Constant, small memory footprint regardless of how many billions of URLs are tracked
  • Extremely fast membership checks that keep up with high-throughput crawling
  • Never wrongly re-crawls a URL that was actually already seen

Exact set (hash set / database)

  • Memory or storage grows linearly with the number of URLs tracked
  • Becomes slow or impractical to query at billions of entries without heavy sharding
  • Costs far more to hold in fast memory at this scale than a probabilistic structure

Further Reading​

Share this lesson

Saved locally in your browser — visible in the sidebar as you go.