Design a Web Crawler

Search-Engine Crawler System Design

Overview

A web crawler is the program that walks the web for a search engine. Starting from a set of seed URLs, it fetches a page, extracts the links on it, and adds those links back into a queue of pages still to visit — repeating forever across millions of sites. The result is a growing collection of fetched pages that a separate indexing system turns into search results.

The product sounds like a simple loop — "download a page, find its links, download those" — but at web scale it hides three problems that separate a shallow answer from a strong one. First, you must be polite — never hammer one website with thousands of requests a second, and obey each site's rules about what may be crawled. Second, you must not re-crawl pages you've already seen, and at billions of URLs even remembering what you've seen is a storage problem. Third, you must do all of this across a fleet of machines without two workers fighting over the same site.

It's labeled "Medium" because the naive design — one queue, one loop, a set of visited URLs in memory — breaks the moment you scale it. One shared queue can't enforce per-site politeness; an in-memory visited-set can't hold billions of URLs; and a single worker can't fetch the whole web. A strong answer builds a URL frontier that prioritizes and paces URLs, a bloom filter for the seen-set, and a partitioned fleet of fetchers where one host is owned by one worker.

In this walkthrough you'll scope the crawler, size it, pick the core data structures, define the component interfaces, draw the crawl loop and the distributed fleet, then go deep on the URL frontier, deduplication, and running the fleet at scale (including crawler traps).

Out of scope (say so): building the search index and ranking (that consumes the crawler's output but is a separate system), rendering JavaScript-heavy pages in a headless browser, and vertical crawlers that only scrape one site. We keep the general, polite, large-scale crawl.

Functional requirements

• Crawl from seeds. Start from a set of seed URLs and fetch pages, following links to discover new pages across many hosts.
• Extract links. Parse each fetched page, pull out its outbound links, normalize them, and feed the new ones back into the frontier.
• Skip already-seen pages. Never fetch the same URL twice, and avoid storing duplicate copies of the same content served under different URLs.
• Be polite. Obey each site's robots.txt (including any crawl-delay), and rate-limit requests per host so no single site is overloaded.
• Store fetched pages. Persist the raw page content (for the indexer) plus metadata (fetch time, status, content hash).
• Prioritize. Crawl more important or more frequently-changing pages sooner, rather than treating every URL equally.

Out of scope (state it): the search index and ranking, JavaScript rendering, and per-site scrapers. This system owns discovering, fetching politely, deduplicating, and storing pages — nothing about how they're later searched.

Non-functional requirements

• Politeness is a hard constraint, not a nice-to-have. Overloading a website gets your crawler blocked (or worse, is treated as an attack). Per-host rate limits and robots.txt compliance must hold across the whole fleet, not just within one machine.
• Massive scale. The crawler must handle billions of pages and a seen-set of a similar size, spread across many machines — no single node holds the queue or the visited-set.
• Fault-tolerant. A crashed worker must not lose URLs or silently drop a host. The frontier and seen-set must survive restarts.
• Freshness. Pages change; the crawler must re-visit changing pages so the index doesn't go stale — but must not waste fetches re-crawling static pages too often.
• Extensible. New URL priorities, content types, or politeness rules should be addable without a redesign.

Estimations

State assumptions; the goal is to justify the frontier, the seen-set structure, and the storage, not to be exact.

Rounded assumptions

• Pages to crawl: ~1B (one billion) per crawl cycle, refreshed over time. The full web of interest is billions of pages.
• Crawl window: ~1 month to fetch them all → fetch rate = 1B ÷ (30 × 86,400 s) ≈ ~400 pages/sec average, call it ~1–2K/sec at peak. (Real large crawlers run higher; the point is the shape, not the exact rate.)
• Page size: ~100 KB average of raw HTML. 1B pages × 100 KB = ~100 TB of raw pages per crawl → a blob store, sharded, not one disk.
• URLs discovered ≫ pages fetched. Each page has tens of links, so the crawler encounters far more URLs than it fetches — many are duplicates it must reject. The seen-set is sized by the discovered count, not the ~1B fetched: 1B pages × tens of links each ⇒ on the order of tens of billions of distinct URLs tested for membership.
• Seen-set size. A URL is ~100 bytes; an exact set at the discovered scale (tens of billions) is hundreds of GB+ even hashed to 8 bytes each (~80 GB+ for 10B, before index overhead) — far past what an in-memory exact set on one node can hold, which is why the seen-set uses a bloom filter backed by durable storage. (Sizing this off the ~1B fetched count instead makes the memory/FPR figures optimistic by roughly an order of magnitude.)

How the numbers affect the design

Core entities / data model

Four things are stored: the URL frontier (what to crawl next), the seen-set (what we've already crawled), the page store (fetched content), and per-host metadata (robots rules + politeness state).

The frontier is the queue of URLs still to fetch, organized for prioritization and politeness (deep dive 1). The seen-set is a fast membership test that keeps the crawler from re-fetching a URL it has already handled (deep dive 2). The page store holds fetched content — raw bodies in a blob store, with metadata (URL, content hash, fetch time, status) in a smaller table; the extracted links flow back into the frontier. HostMeta caches each host's robots.txt and the timing state that paces requests to that host.

Component interfaces

A crawler is an internal pipeline, not a public REST service — there are no client-facing endpoints. What matters is the contract between components: the small set of operations the frontier, fetcher, and seen-set expose to each other. (Per the authoring convention, we title this "Component interfaces" rather than "API design" because there are no callable HTTP routes.)

enqueue(url) — add a URL to the frontier

enqueue(url) -> void
Effect: canonicalize(url); if seen?(url) is false, mark it seen and add it to
        the frontier with a computed priority, routed to its host's queue.

Called by the link extractor for every link found on a page (and once for each seed). It canonicalizes the URL, checks the seen-set, and — only if new — inserts it into the frontier under the right host and priority. A URL that fails seen? is dropped here, before it ever reaches a fetcher.

next(worker) -> url — pull the next URL to fetch

next(worker) -> url
Returns: the highest-priority URL from a host that is due (its per-host
         delay has elapsed), assigned to this worker. Disallowed paths were
         already filtered out at enqueue time, so everything here is allowed.

Called by a fetcher worker when it's ready for more work. The frontier hands back a URL from a host that is allowed to be fetched right now — respecting the host's crawl-delay and ownership. This is where politeness is enforced: a host that was fetched too recently simply isn't offered yet.

fetch(url) -> Page — download a page

fetch(url) -> Page
Returns: { status, raw_body, fetched_at }, resolving the host via cached DNS.
         (robots.txt was already applied at enqueue time — fetch does not re-fetch it.)

Called by a fetcher worker. It resolves the host (from cached DNS), downloads the body, and returns the page for parsing. The robots.txt disallow check already happened at enqueue/prioritization time using the cached per-host rules, so fetch does not re-fetch or re-check robots.txt. Its result is stored and its links are extracted and enqueued.

seen?(url) -> bool — has this URL been handled?

seen?(url) -> bool
Returns: true if canonicalize(url) is (probably) already in the seen-set.

The membership test at the heart of dedup. Backed by a bloom filter, so a true is "almost certainly seen" and a false is "definitely not seen" (deep dive 2). Called inside enqueue to reject duplicates before they enter the frontier.

High-level architecture

Two things are worth drawing: the crawl loop (how one URL becomes a fetched page and more URLs), and the distributed fleet (how many workers run that loop without colliding on hosts). We'll walk each, then combine them.

1. The crawl loop

One pass through the pipeline: take a URL from the frontier, fetch it, parse it, extract and dedup its links, and feed the new ones back into the frontier.

flowchart LR
    F["URL Frontier<br/>(prioritized, per-host)"] -->|"next() due URL"| Fetch["Fetcher<br/>(cached DNS)"]
    Fetch -->|"raw page"| Store[("Page Store<br/>(blob + metadata)")]
    Fetch -->|"raw page"| Parse["Parser +<br/>Link Extractor"]
    Parse -->|"outbound links"| Canon["Canonicalize"]
    Canon -->|"seen?(url)"| Dedup{"Seen-set<br/>(bloom filter)"}
    Dedup -->|"new URL → enqueue()"| F
    Dedup -.->|"already seen → drop"| X["discard"]
    classDef neutral fill:#e0f2fe,stroke:#0284c7,color:#0c4a6e;
    class F neutral

1. The frontier hands the fetcher the next URL from a host that is due to be crawled (politeness already enforced by which URL it offers).
2. The fetcher resolves the host via cached DNS and downloads the page (the host's robots.txt was already applied at enqueue time, so no re-check here).
3. The raw page is written to the page store (body in the blob store, metadata in a table).
4. The parser extracts outbound links from the page.
5. Each link is canonicalized (normalized to a standard form) so the same page under different URLs collapses to one.
6. The seen-set (a bloom filter) is checked: if the URL is new, enqueue() adds it back to the frontier; if it's already seen, it's dropped.

The loop's correctness rests on step 6: a URL enters the frontier only if the seen-set says it's new. That's what stops the crawler from looping forever over the same pages.

2. The distributed fleet

One machine can't fetch a billion pages. Many fetcher workers run the loop in parallel — but they must not both crawl the same host, or per-host politeness breaks.

flowchart LR
    F["URL Frontier<br/>(partitioned by host)"]
    F -->|"host A URLs"| W1["Worker 1<br/>owns hosts {A, D, …}"]
    F -->|"host B URLs"| W2["Worker 2<br/>owns hosts {B, E, …}"]
    F -->|"host C URLs"| W3["Worker 3<br/>owns hosts {C, F, …}"]
    W1 --> DNS["Shared DNS cache"]
    W2 --> DNS
    W3 --> DNS
    W1 --> SS[("Seen-set<br/>(sharded bloom filter)")]
    W2 --> SS
    W3 --> SS
    classDef neutral fill:#e0f2fe,stroke:#0284c7,color:#0c4a6e;
    class F neutral

1. The frontier is partitioned by host: every URL for example.com routes to the same partition, and that partition is owned by exactly one worker.
2. Because one host is owned by one worker, that worker alone paces requests to it — so the per-host rate limit holds across the whole fleet, not just per machine.
3. Workers share a DNS cache so they don't re-resolve the same hosts repeatedly (DNS is a common bottleneck — deep dive 3).
4. All workers read/write the seen-set, which is itself sharded (by URL hash) so no single node holds the whole billion-entry structure.

The key invariant: all URLs of a host live in one partition owned by one worker. That is the only way per-host politeness survives running on hundreds of machines.

3. Combined architecture

Putting it together: a partitioned, prioritized frontier feeds a fleet of fetchers; each fetch is stored, parsed, deduped, and its new links flow back into the frontier.

flowchart LR
    Seed["Seed URLs"] -->|"enqueue"| F["URL Frontier<br/>(priority + per-host queues,<br/>partitioned by host)"]
    F -->|"next() due URL"| WPool["Fetcher Fleet<br/>(one host owned by one worker)"]
    WPool --> DNS["DNS cache"]
    WPool --> Robots["HostMeta<br/>(robots.txt, crawl-delay)"]
    WPool -->|"raw page"| Store[("Page Store<br/>(blob + metadata)")]
    WPool -->|"raw page"| Parse["Parser + Link Extractor"]
    Parse --> Canon["Canonicalize"]
    Canon -->|"seen?"| SS{"Seen-set<br/>(sharded bloom filter)"}
    SS -->|"new → enqueue"| F
    SS -.->|"seen → drop"| X["discard"]
    Store -.->|"content hash"| CD["Content dedup<br/>(hash + simhash)"]
    classDef neutral fill:#e0f2fe,stroke:#0284c7,color:#0c4a6e;
    class F neutral

Seeds prime the frontier. Fetchers pull due URLs (already screened against cached robots.txt at enqueue time), resolve DNS, store the page, and hand it to the parser. Extracted links are canonicalized and checked against the seen-set; new ones return to the frontier, seen ones are dropped. A separate content-dedup step (deep dive 2) catches the case where two different URLs return the same content. The frontier and seen-set are the two structures that scale hardest — the next three deep dives are exactly those, plus running the fleet.

Deep dives

1. The URL frontier — prioritization & politeness (the headline)

The URL frontier is the queue of URLs still to be fetched. It looks like "just a queue," but it carries the two hardest requirements in the whole system: politeness (never overload a host) and prioritization (crawl important pages sooner). A plain FIFO queue delivers neither.

Politeness: never hammer one host. Two rules combine here:

• Obey robots.txt. On first encountering a host, the crawler fetches its /robots.txt once over the network and stores the parsed rules in the per-host metadata with a TTL (re-fetched only when the TTL expires), which lists paths that are disallowed and may specify a crawl-delay (minimum seconds between requests). The disallow check then happens at enqueue/prioritization time against those cached rules — a disallowed path is never queued, so the fetcher never re-fetches or re-checks robots.txt. The crawler must respect both the disallow list and the delay.
• Rate-limit per host. Even where robots.txt allows crawling, the crawler must space out its requests to a single host — typically one request every few seconds — so it never looks like an attack. This limit is per host, not global: crawling 10,000 different hosts at once is fine; sending 10,000 requests to one host is not. The effective delay is max(default_delay, robots crawl-delay) — obey whichever is more polite — but capped so a hostile or absurd crawl-delay (e.g. 3600s) can't freeze a host forever; past the cap you clamp the delay and rely on per-host count limits instead.

The standard structure that delivers this is the two-level (Mercator) queue: a set of front queues by priority, and a bounded pool of back queues (roughly one per fetcher thread), each pinned to a single host at a time via a host→back-queue mapping. A fetcher picks which host is due through a priority queue / min-heap keyed by each host's next-eligible fetch time — pop the earliest, fetch it, then re-insert with an updated timestamp. This avoids the trap of "billions of live per-host queues": only hosts currently assigned to a back queue are materialized, and the heap makes "which host may I fetch now?" an O(log n) lookup.

flowchart LR
    In["new URLs (enqueue)"] --> P["Prioritizer<br/>(assigns priority)"]
    P --> FQ1["Front queue: high priority"]
    P --> FQ2["Front queue: normal"]
    P --> FQ3["Front queue: low"]
    FQ1 --> Router["Host router<br/>(URL → its host's back queue)"]
    FQ2 --> Router
    FQ3 --> Router
    Router --> BQa["Back queue: host A<br/>(paced by crawl-delay)"]
    Router --> BQb["Back queue: host B"]
    Router --> BQc["Back queue: host C"]
    BQa -->|"one URL when host A is due"| Out["Fetcher pulls"]
    BQb --> Out
    BQc --> Out
    classDef neutral fill:#e0f2fe,stroke:#0284c7,color:#0c4a6e;
    class BQa,BQb,BQc neutral

1. A new URL gets a priority from the prioritizer and lands in the matching front queue (high / normal / low).
2. A router moves URLs from front queues into the back-queue pool, where each back queue is pinned to one host at a time — so every URL for host A sits in host A's single back queue while that host is assigned.
3. A min-heap keyed by each host's next-eligible fetch time decides which host is due: the fetcher pops the earliest host, is handed one URL from that host's back queue, and the host is re-inserted with now + crawl-delay. A host having exactly one back queue at a time is what enforces politeness — its release rate is trivially controlled, and the heap makes "which host is due?" cheap rather than a scan over billions of queues.
4. Priority is honored when filling back queues (high-priority URLs move through faster), while politeness is honored when draining them (paced per host). The two requirements are separated across the two levels.

Prioritization: crawl what matters sooner. By default the crawler does breadth-first traversal (BFS) — fetch all links at the current depth before going deeper — which naturally spreads coverage. But not all pages are equal:

• Importance. A page with many inbound links, or on a high-authority domain, is worth crawling sooner (an approximation of its rank).
• Freshness. A frequently-changing page (a news homepage) should be re-crawled sooner than a static page (an old blog post). The prioritizer raises priority for pages that historically change often.

The frontier is distributed. At billions of URLs the frontier doesn't fit on one machine — it's a distributed priority queue, partitioned by host. The partition rule is not optional: all URLs of a host must route to the same partition, so that one host's back queue (and therefore its politeness pacing) lives in one place and is owned by one worker. If host A's URLs were spread across partitions on different workers, each worker would pace host A independently and the combined rate would exceed the limit — exactly the overload you're trying to prevent.

2. Deduplication — URLs and content

The crawler encounters far more URLs than it should fetch, because the same page shows up many times. Dedup happens at two levels: the URL (same address seen again) and the content (different addresses, identical page).

URL canonicalization. Before checking whether a URL is seen, normalize it to a canonical form so trivially-different URLs collapse to one:

• lowercase the scheme and host (HTTP://Example.com → http://example.com),
• drop the fragment (page#section → page — the fragment doesn't change what's fetched),
• remove default ports and index.html, sort or strip recognized tracking query params (?utm_source=…) and known session-id patterns (arbitrary/unknown session ids are only heuristically caught — see traps in deep dive 3),
• resolve relative links against the page's URL.

Without this, http://Example.com/, http://example.com/index.html, and http://example.com/?utm=x all look distinct and you crawl the same page three times.

The URL seen-set. After canonicalizing, check membership in the seen-set. At billions of URLs, how you store this set is the whole problem — here it is, worst to best.

seen?(url):
  canonicalize(url)
  if bloom.contains(url):        # k bits all set
      # "probably seen" — skip (accept ~1% false-positive skips)
      return true
  else:
      # "definitely new"
      bloom.add(url)
      return false

Content deduplication. Two different URLs can serve identical or near-identical content — mirror sites, printer-friendly versions, the same article under ?ref= variants. URL dedup won't catch these because the URLs differ. So dedup the content too:

• Exact duplicates: hash the page body (e.g. a content hash / checksum). If a newly-fetched page's hash matches one already stored, it's an exact duplicate — skip storing, indexing, and link extraction for it. Skipping extraction matters: a mirror serves the same links, so re-extracting them just re-floods the frontier with URLs the seen-set has already handled — the content-hash hit short-circuits that whole downstream path.
• Near-duplicates: pages that differ only in ads, timestamps, or navigation. A plain hash won't match because a single byte differs. Use shingling or simhash — fingerprints designed so that near-identical documents produce near-identical fingerprints, letting you detect "basically the same page" even with small differences.

3. Distributed workers, scale & crawler traps

Fetching a billion pages means a fleet of fetcher workers pulling from the frontier in parallel. Two things dominate at this scale: keeping the fleet efficient (and polite), and surviving hostile or accidental crawler traps.

DNS is a bottleneck — cache it. Every fetch needs the host's IP, which means a DNS lookup. DNS resolution is relatively slow (often tens of milliseconds, sometimes more) and, done naively, the crawler would resolve the same popular hosts millions of times. A shared DNS cache (with sensible TTLs) turns most lookups into instant hits; without it, DNS resolution alone can cap your fetch rate well below what the network could sustain.

One host, one owner — so rate limits hold. As in the fleet diagram: the frontier is partitioned by host and each host is owned by one worker/partition. This is what makes the per-host rate limit real across the fleet — if two workers could both fetch example.com, their combined rate would break the limit even though each thinks it's being polite. Host ownership is the mechanism; per-host back queues (deep dive 1) are where the pacing lives.

Crawler traps — infinite URL spaces. Some sites generate unbounded URLs, either by accident or to trap bots:

• Calendars: "next month" links go on forever (/calendar/2027/01, /2027/02, …).
• Faceted navigation: every combination of filters is its own URL (?color=red&size=9&sort=price&page=2 × thousands of combinations).
• Session IDs / infinite params: a new ?sid=… on every visit makes every URL look new to the seen-set.

Left unchecked, a trap makes the crawler fetch millions of near-worthless URLs from one site forever, starving the rest of the web. Mitigations:

• Depth and URL-count caps per host: stop after N pages or D link-hops into a single host, so no one site can consume the crawl.
• Canonicalization: stripping recognized tracking params and known session-id patterns (deep dive 2) collapses many trap URLs into one, so the seen-set rejects them — but arbitrary session ids are only heuristic, so the ones canonicalization misses are ultimately caught by the trap heuristics and per-host URL-count caps below.
• Trap heuristics: detect suspicious patterns — very long URLs, many query params, deep repetitive paths, or a host producing endless new-but-thin pages — and deprioritize or skip them.

Storing fetched pages. Raw page bodies (~100 KB each, ~100 TB total) go to a blob store — cheap object storage for large opaque files. Only the searchable parts (extracted text, title, links, content hash, fetch metadata) go into the smaller store the indexer reads. Keeping bulky raw HTML out of the index keeps the index lean and fast.

Re-crawl / freshness scheduling. The web changes, so crawling is never "done." Each page gets a re-crawl schedule based on how often it actually changes: a news homepage might be re-fetched every few minutes, a static reference page every few weeks. The crawler tracks observed change frequency (did the content hash change since last time?) and adjusts each page's re-crawl interval — spending fetch budget where content actually moves, not re-downloading static pages.

Tradeoffs & bottlenecks

• Bloom filter vs exact seen-set. The bloom filter is ~10× smaller and fits in memory, but its false positives skip a small fraction of real pages. An exact (sharded) set never skips but is far larger and costs a network lookup per link. Most crawlers accept the bloom filter's rare skips.
• Politeness vs throughput. Per-host rate limits deliberately slow crawling of any one site. You buy total throughput by crawling many hosts in parallel, not by going faster at any single host — which is exactly why host-partitioned parallelism matters.
• Priority vs coverage. Chasing high-priority pages first improves freshness of what matters but can starve the long tail. BFS with priority weighting balances broad coverage against importance.
• Freshness vs cost. Re-crawling often keeps the index fresh but wastes fetches on static pages; re-crawling rarely saves fetches but lets the index go stale. Per-page change-frequency scheduling is the compromise.
• Storage split. Raw pages in a blob store (~100 TB) vs a lean index of text/metadata keeps the searchable store fast, at the cost of a two-store system to manage.
• DNS. A shared DNS cache is essential; uncached, DNS resolution alone becomes the crawl's rate ceiling.

Extensions if asked

If the interviewer wants to push beyond the core crawler, add only the extension that changes the design discussion:

• JavaScript rendering. Many pages build their content client-side, so the raw HTML is nearly empty. Rendering them needs a headless-browser fetcher pool — far more expensive per page, so it's applied selectively.
• Priority / rank signals. Feeding a real importance score (inbound-link-based rank) back into the frontier's prioritizer, so the crawl order approximates page importance rather than plain BFS.
• Distributed frontier durability. Making the frontier itself fault-tolerant — persisting per-host queues so a crashed worker's hosts are reassigned without losing URLs or double-crawling.
• Politeness beyond robots.txt. Honoring Crawl-delay, sitemap hints, and adaptive backoff when a host returns errors or slows down (treat 429/503 as "slow down").
• Focused / vertical crawling. Crawling only pages matching a topic — adds a relevance classifier at the link-extraction step to decide what to enqueue. There's no dedicated guide yet.

What interviewers look for & common mistakes

What interviewers usually reward:

• Designing the URL frontier as prioritized + polite, with per-host back queues so requests to one host are paced — not a single FIFO queue.
• Enforcing politeness fleet-wide by partitioning the frontier by host and giving one host to one worker, plus obeying robots.txt and crawl-delay.
• Using a bloom filter for the seen-set and knowing the error direction — a false positive skips a page, never causes a re-crawl — plus canonicalizing URLs first.
• Deduping content, not just URLs — content hashing for exact dupes and simhash/shingling for near-dupes.
• Naming DNS caching and crawler traps as scale problems, and capping per-host depth/count to contain infinite URL spaces.

Before you finish, do a quick mistake check:

• Did you make the frontier prioritized and polite, with per-host queues — not one shared FIFO?
• Did you partition the frontier by host (not URL hash), so per-host rate limits hold across the whole fleet?
• Did you obey robots.txt and per-host crawl-delay as hard constraints?
• Did you canonicalize URLs before the seen-set check, and use a bloom filter (explaining the false-positive direction) instead of an exact in-memory set?
• Did you dedup content (hash + simhash) as well as URLs?
• Did you cache DNS, and cap per-host depth/count to defend against crawler traps?
• Did you store raw pages in a blob store and keep only text/metadata in the index, with a re-crawl schedule for freshness?