Design a Web Crawler

Design a crawler that downloads the public web for a search engine. Starting from a list of seed URLs, it fetches pages, extracts links, discovers new pages, and keeps revisiting known pages so the index stays fresh.

The target is several billion pages, about a billion fetches a day. The crawler must be a good citizen: obey robots.txt, never overload a small website, and back off when a server slows down. It must also avoid wasting effort on duplicate pages, endless calendar links and spider traps, and it must spend its recrawl budget wisely, since a news homepage changes every few minutes while most pages barely change in a year.

In 45 minutes, size the system, design the URL frontier and how it enforces politeness, how fetchers and parsers scale, how you deduplicate URLs and content, and how you decide what to recrawl.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Data & Infrastructure · problem 43 of 70

Ask before you design. Try answering each yourself, then compare.

1. What content types do we fetch?
   Typical answer

   HTML only for the core design; images, PDFs and JavaScript rendering are follow-ups.

2. How many pages and how fast?
   Typical answer

   About 10 billion known URLs, roughly 5 billion worth keeping fresh, and 1 billion fetches a day.

3. What does politeness mean in practice?
   Typical answer

   Obey robots.txt, at most one concurrent connection and roughly one request per second per host by default, slower if robots.txt or the server asks.

4. Who consumes the output?
   Typical answer

   An indexing pipeline downstream. We store raw pages and hand over references to new or changed pages.

5. How fresh must pages be?
   Typical answer

   Depends on the page: high-value, fast-changing pages within an hour; the long tail within a few weeks.

6. Do we need to handle crawler traps and duplicates?
   Typical answer

   Yes: limit depth and URLs per host, normalise URLs, and skip near-duplicate content.

Requirements

Functional

• Fetch HTML pages starting from seeds, extract links and discover new URLs.
• Obey robots.txt and per-host rate limits.
• Store raw pages and notify the indexer of new or changed pages.
• Recrawl known pages at a rate that matches their importance and change frequency.
• Skip duplicate URLs, duplicate content and crawler traps.

Non-functional

• Sustain about 12,000 fetches per second (1 B a day) with horizontal scaling.
• Never exceed one concurrent connection per host by default; react to 429 and 5xx within seconds.
• Important pages refreshed within 1 hour; the median page within 2 weeks.
• Tolerate the loss of any machine without losing frontier state.

Out of scope

• Building the search index and ranking.
• Rendering JavaScript-heavy pages (follow-up).

Back-of-the-envelope estimates

• Fetch rate: 1 B pages a day ≈ 11,600 per second; plan for 15,000.
• Bandwidth: average page about 100 KB uncompressed, so 1.2 GB/s ≈ 10 Gbit/s inbound; about 4 Gbit/s with compression on the wire.
• Storage: 100 TB of raw HTML a day, about 20 TB compressed. Keeping the latest copy of 5 B pages is about 100 TB compressed; history is tiered to cold storage.
• Fetchers: with a typical fetch taking 1 second including slow servers, 15,000 fetches per second need 15,000 connections in flight, about 30 machines at 500 async connections each, plus headroom.
• Seen-URL filter: 10 B URLs in a Bloom filter at 1% false positives needs about 10 bits each, ≈ 12 GB, sharded by URL hash.
• Hosts: hundreds of millions of hosts, but politeness spreads the load: at 1 request per second per host, 12,000 fetches per second need at least 12,000 hosts active at any moment.

Politeness and bandwidth, not CPU, shape the design; the frontier must keep thousands of hosts busy at once without hitting any one too fast.

API

// internal RPCs and messages
Frontier.Enqueue(urls[], priority, source)        // from planner and seeds
Frontier.Lease(fetcherId, max)  -> [{url, host, leaseId}]
Frontier.Complete(leaseId, status, retryAfter?)   // updates host delay
FetchResult {url, finalUrl, status, contentRef, contentHash, fetchedAt, latencyMs}
Indexer topic: PageChanged {url, contentRef, simhash, fetchedAt}

Fetchers lease batches from the frontier and report back, so the frontier, not the fetcher, owns per-host timing and a crashed fetcher's leases simply expire and return.

Data model

• Crawl metadata (wide-column store, keyed by URL hash): url, host, status, last_fetch, next_due, content_hash, simhash, change_rate, priority, depth. The source of truth for every known URL.
• Frontier (sharded by host hash): per-host FIFO queues plus a heap of hosts ordered by next allowed fetch time; persisted to a log or local disk so a restart resumes.
• Host table: host -> robots rules, crawl_delay, ip, error_rate, urls_crawled, cached in memory with a 24-hour TTL.
• Raw page store (object storage): pages packed into large compressed files, addressed by (file, offset).
• URL seen filter: sharded Bloom filters backed by the metadata table for exact checks when needed.

High-level design

The Recrawl Planner scans Crawl Metadata for URLs whose next_due has passed and for newly discovered URLs, and publishes them to URL Intake, partitioned by host. Each URL Frontier shard owns a set of hosts. It keeps a queue per host and a heap of hosts keyed by the earliest time each may be fetched, consulting the Robots & DNS cache to drop disallowed paths and read crawl delays.

Fetchers lease ready URLs, resolve DNS from the cache, and fetch from the web servers with tight timeouts and a size cap. They write the page body to the Raw Page Store and publish a fetch result to Fetched Pages. A 429, 503 or slow response is reported back so the frontier stretches that host's delay.

Parsers consume results, normalise and extract links, check each link against the URL Seen Filter, and write genuinely new URLs and per-page data, such as content hash, SimHash and whether the page changed, into the metadata. Changed pages go to the Search Indexer. The planner then updates each URL's next due time from its change history, closing the loop.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Frontier design and politeness

Shard the frontier by host so one shard owns all URLs of a host and can enforce its limits without coordination. Inside a shard, keep a FIFO queue per host and a min-heap of hosts keyed by the next time each is allowed a request. A fetcher asking for work pops hosts whose time has come, takes one URL, and pushes the host back with time plus its delay. Priority lives in two layers: the planner decides which URLs enter the frontier first, and within a host, high-priority URLs sit at the front. Delays adapt: multiply by two on 429 or 503 and when latency rises, decay slowly back toward the default.

Deduplicating URLs and content

Normalise URLs before anything else: lowercase scheme and host, drop fragments, sort query parameters, strip known session and tracking parameters. Then a sharded Bloom filter answers 'seen before?' in memory; a false positive skips a new URL occasionally, which is acceptable, and the metadata table can confirm important ones. For content, store an exact hash to detect identical pages and a 64-bit SimHash to find near duplicates such as the same article with a different ad block; pages within a few bits of a known SimHash are marked as duplicates and their links are not re-expanded.

Spending the recrawl budget

With a fixed budget of about 1 B fetches a day, every recrawl of an unchanged page is waste. Track for each URL whether its content changed on each visit and estimate a change rate. Set the next interval roughly inversely to change rate, scaled by importance such as link-based rank or traffic, and clamp between an hour and a couple of months. Sitemaps and feeds with last-modified dates give cheap hints, and conditional requests with If-Modified-Since or ETags turn many recrawls into tiny 304 responses.

Avoiding traps and runaway hosts

Infinite spaces appear through calendars, faceted search and session IDs in paths. Cap URL length and path depth, limit the number of URLs accepted per host per day relative to its importance, and detect repeating path segments. If a host suddenly produces thousands of new near-duplicate pages, quarantine it for review. Also cap response size and fetch time, and refuse redirect chains longer than about five hops.

Failure modes

• If a fetcher crashes, its leased URLs expire after a timeout and the frontier hands them to another fetcher; the host timing stays correct because the frontier owns it.
• If a frontier shard fails, its hosts are reassigned and the replacement replays its queues from the intake log and persisted snapshot; a few URLs may be fetched twice, which is harmless.
• If DNS resolution slows, the cache serves stale entries within TTL and fetchers skip hosts that fail to resolve, retrying later.
• If a website starts returning errors, its delay grows exponentially and its URLs are rescheduled instead of hammering it.
• If the parser pipeline lags, fetchers keep storing pages and the stream buffers results; discovery slows but no fetch is lost.

Core algorithm in code

import heapq
from collections import deque
from urllib.parse import urlsplit, urlunsplit


def normalise(url):
    p = urlsplit(url.strip())
    host = p.hostname or ""
    path = p.path or "/"
    return urlunsplit((p.scheme.lower(), host.lower(), path, p.query, ""))  # drop #fragment


class PoliteFrontier:
    """Per-host FIFO queues plus a heap of (next_allowed_time, host)."""
    def __init__(self, default_delay=1.0):
        self.queues = {}            # host -> deque of URLs
        self.ready = []             # heap of (time host may be hit again, host)
        self.delay = {}
        self.default_delay = default_delay
        self.seen = set()           # a Bloom filter plus URL table at real scale

    def add(self, url):
        url = normalise(url)
        if url in self.seen:
            return False
        self.seen.add(url)
        host = urlsplit(url).hostname
        if host not in self.queues:
            self.queues[host] = deque()
            heapq.heappush(self.ready, (0.0, host))
        self.queues[host].append(url)
        return True

    def set_delay(self, host, seconds):
        self.delay[host] = seconds

    def next_url(self, now):
        while self.ready and self.ready[0][0] <= now:
            _, host = heapq.heappop(self.ready)
            q = self.queues[host]
            if not q:
                del self.queues[host]           # host drained; re-added on next discovery
                continue
            url = q.popleft()
            heapq.heappush(self.ready, (now + self.delay.get(host, self.default_delay), host))
            return url
        return None


f = PoliteFrontier(default_delay=1.0)
f.set_delay("slow.example", 5.0)                    # robots.txt asked for a 5 s crawl delay
for u in ["https://news.example/a", "https://news.example/b#top", "https://News.example/b",
          "https://slow.example/1", "https://slow.example/2", "https://shop.example/x"]:
    print("add", u, "->", f.add(u))
t = 0.0
while t <= 6.0:
    url = f.next_url(t)
    while url:
        print("t=%.1f fetch %s" % (t, url))
        url = f.next_url(t)
    t += 0.5

Trade-offs

• Sharding the frontier by host makes politeness local and simple but creates skew when a few huge hosts have most URLs.
• Bloom filters use little memory but occasionally skip a new URL; an exact table is correct but costs a lookup per link.
• Aggressive recrawling keeps the index fresh but spends bandwidth and goodwill on unchanged pages.
• Storing every page version supports change history but multiplies storage; keeping only the latest is cheap but loses diffs.
• Strict per-host limits protect websites but cap how fast large, important sites can be refreshed.

What a strong answer shows

• Designs the frontier around per-host queues and timing, sharded by host, rather than a single global queue.
• Sizes bandwidth, storage, fetcher concurrency and the seen-URL filter with numbers.
• Deduplicates URLs with normalisation and a Bloom filter, and content with exact and near-duplicate hashes.
• Has an explicit recrawl policy driven by change rate and importance within a fixed budget.
• Handles traps, adaptive back-off and fault tolerance of fetchers and frontier shards.
• Keeps fetching, parsing and planning decoupled through durable queues.

Mistakes to avoid

• Using one big FIFO of URLs, which hammers whichever host has many links queued.
• Checking 'seen before?' with a database query per extracted link at hundreds of thousands per second.
• Recrawling everything on the same schedule, wasting most of the budget on pages that never change.
• Ignoring robots.txt caching and DNS cost, doing both for every page.
• Letting fetchers own politeness, so two fetchers can hit the same small site at once.

Follow-ups to expect

• How would you crawl JavaScript-heavy sites? (A separate rendering pool with headless browsers for pages that need it, at much lower throughput.)
• How would you run the crawler across regions? (Assign hosts to the region closest to them; keep per-host ownership in exactly one place.)
• How do you prioritise a brand-new site linked from a major news page? (Priority from linking page importance; fast-track lane in the planner.)
• How do you respect a site that changes robots.txt mid-crawl? (Short TTL on robots cache; recheck before each batch for that host.)

Practice next