Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

System Design HLD-19.09

Design a web crawler

Design a web crawler: a URL frontier with priorities and per-host politeness, robots.txt, DNS caching, Bloom filter and content-hash dedupe.

Intermediate 20 min Last reviewed

The problem

A search engine, an archive or a training-data pipeline needs copies of web pages. A crawler gets them: start from some seed URLs, download each page, find the links in it, and repeat with the new links, forever. In ten lines of code it works on a laptop. At a billion pages a month it becomes a design problem with an unusual twist: the system you are calling is not yours.

That twist shapes everything. Web servers belong to other people, so the crawler must be polite: never hammer one site, obey its robots.txt. The web is full of duplicates, mirrors and infinite link mazes, so the crawler must remember billions of URLs it has seen and recognise pages it already has. And it must decide what to fetch next out of billions of candidates.

Requirements

Functional

  • Start from seed URLs; fetch pages, extract links, and crawl new links.
  • Store fetched HTML with metadata (URL, fetch time, status, content hash) for downstream indexing.
  • Obey robots.txt and per-site crawl delays.
  • Re-crawl pages periodically, more often for pages that change often.

Non-functional

  • Scale: 1 billion pages a month.
  • Politeness: at most one request at a time to each host, with a delay between requests.
  • Robustness: survive malformed HTML, slow servers, spider traps and crawler machine failures.
  • Extensibility: new content types or processing steps without redesigning the pipeline.

Out of scope

Estimates

  • Fetch rate: 1 billion pages a month is 1e9 / (30 x 86,400), about 390 pages per second on average. Plan for about 800 per second to catch up after outages.
  • Bandwidth: at about 100 KB per page, 390 pages per second is 39 MB/s, a little over 300 Mbit/s.
  • Storage: 1 billion x 100 KB = 100 TB of raw HTML a month, before compression, which suits object storage.
  • Seen URLs: the crawler will discover far more URLs than it fetches, say 10 billion. A Bloom filterA compact bit array that answers 'definitely not seen' or 'probably seen', with a tunable false-positive rate and no false negatives. for 10 billion URLs with a 1 percent false-positive rate needs about 9.6 bits per URL, so 96 billion bits, about 12 GB, with 7 hash functions. Storing the URLs themselves would take hundreds of GB.
  • Concurrency: if a fetch takes 1 second on average (slow servers, timeouts), 800 fetches per second needs about 800 in flight at once, which is a job for asynchronous I/O on a modest number of machines ( Processes, threads and concurrency ).

API

A crawler has no public API, but its components talk through narrow interfaces:

frontier.add(url, priority)         # from link extraction
frontier.next(worker_id) -> url     # respects per-host politeness
fetcher.fetch(url) -> (status, headers, body)
store.put(url, fetch_time, body)    # returns a content id

Data model

  • URL frontier: priority queues of URLs to crawl, plus one FIFO queue per host. Too large for memory, so mostly on disk with in-memory heads.
  • URL seen set: a Bloom filter over normalized URLs, with an exact store of crawled URLs (url_hash -> last_fetch, next_due, content_hash) for re-crawl scheduling.
  • Content store: compressed pages in object storage, keyed by content hash, with an index from URL to the latest content id.
  • Host table: host -> robots rules, crawl delay, next allowed fetch time, cached IP address.

High-level design

Web crawler: fetch, process and discover paths Fetch path: the URL frontier hands a URL to a fetcher only when its host may be contacted; the fetcher resolves the host through a DNS cache, checks cached robots.txt rules, and downloads the page from the web. Process path: the parser checks the page's content hash, stores new content in the page store, and extracts links. Discover path: extracted links are normalized and filtered, checked against the Bloom filter of seen URLs, and new ones are added to the frontier with a priority. next URL GET page HTML store links new URLs URL frontier priority + per host Fetchers async I/O DNS cache robots.txt cache The web other people's servers Parser content hash Page store object storage Link extractor normalize, filter URL seen? Bloom filter Figure 1. A loop. The frontier decides what to fetch and when; fetchers talk to the web through DNS and robots caches; new links flow back through the seen-URL filter. Step through the three paths.
  1. Fetch path The frontier gives a fetcher a URL only if its host's politeness delay has passed. The fetcher resolves the host from a local DNS cache, checks the host's cached robots.txt rules, and downloads the page with a timeout and a size limit.
  2. Process path The parser computes a hash of the page content. If the same content was stored before (a mirror or a duplicate URL), it records the alias and skips storage; otherwise it stores the compressed page in object storage.
  3. Discover path Links are extracted, made absolute and normalized (lowercase host, no fragments, sorted query parameters), then filtered for traps. URLs the Bloom filter has not seen are added to the frontier with a priority.

Deep dives

Deep dive 1: The URL frontier, priority and politeness

The frontier answers two questions: what should be crawled next (priority), and is it allowed to be crawled now (politeness). A common design splits it in two:

  • Front queues by priority. A prioritizer scores each URL, using signals such as the site's importance, how often the page has changed, and how long since it was last fetched, and puts it in one of several priority queues.
  • Back queues, one per host. A selector moves URLs from front queues into per-host queues, and a heap ordered by each host's next allowed fetch time decides which host is served next. After fetching from a host, its next time is set to now plus its crawl delay.

Here is why per-host queues matter. Twelve URLs, eight of them on one site, two workers:

politeness.pyruns with python3 (standard library)
# Two fetch workers, 12 URLs, mostly from one host. Each fetch takes 1 s.
# Compare a plain FIFO with per-host queues and a 3 s politeness delay.
from collections import deque

urls = ["big.example/p%d" % i for i in range(8)] + \
       ["a.example/", "b.example/", "c.example/", "d.example/"]
host = lambda u: u.split("/")[0]

def fifo():
    q, t, log = deque(urls), 0, []
    while q:
        for _ in range(2):                    # two workers per second
            if q:
                log.append((t, q.popleft()))
        t += 1
    return log

def polite(delay=3):
    queues = {}
    for u in urls:
        queues.setdefault(host(u), deque()).append(u)
    ready = {h: 0 for h in queues}            # next time each host may be hit
    t, log = 0, []
    while any(queues.values()):
        due = [h for h in queues if queues[h] and ready[h] <= t]
        for h in due[:2]:                     # two workers per second
            log.append((t, queues[h].popleft()))
            ready[h] = t + delay
        t += 1
    return log

for name, log in [("FIFO", fifo()), ("per-host", polite())]:
    hits = [t for t, u in log if host(u) == "big.example"]
    gap = min(b - a for a, b in zip(hits, hits[1:]))
    small = max(t for t, u in log if host(u) != "big.example")
    print(f"{name}: min gap on big.example {gap}s, "
          f"small sites done t={small}s, all done t={log[-1][0] + 1}s")

Output

FIFO: min gap on big.example 0s, small sites done t=5s, all done t=6s
per-host: min gap on big.example 3s, small sites done t=2s, all done t=22s

The FIFO crawler hit big.example twice in the same second, again and again: from that site's point of view, a small attack. The per-host frontier never hit it more than once every 3 seconds, and it finished the small sites sooner because they no longer waited behind the big one. It took longer overall, which is the real lesson: politeness caps the rate per host, so a crawler's throughput comes from crawling many hosts in parallel. Assign hosts to crawler machines by hashing the host name ( Consistent hashing ), so one machine owns each host's politeness state.

Deep dive 2: Not fetching twice

Duplicates come in two kinds:

  • Same URL discovered from many pages. Normalize URLs first, then check a Bloom filter ( Probabilistic data structures ). A false positive means a URL that was never crawled is skipped, which at 1 percent is acceptable for a crawler; a false negative never happens, so a URL is never crawled twice by mistake. The exact table of crawled URLs exists for re-crawl scheduling, not for the hot check.
  • Same content under different URLs: mirrors, session ids in URLs, ?utm_source= variants. Hash the page content and look the hash up before storing. Exact hashes catch identical pages; near-duplicate techniques (such as SimHash) catch pages that differ only in a timestamp or an ad.

Deep dive 3: DNS, robots.txt and traps

DNS can dominate fetch time: resolving a host may take tens of milliseconds, and standard resolvers are often synchronous and serialize lookups. Run a local caching resolver per crawler machine and keep resolved addresses in the host table, respecting TTLs ( DNS in depth ).

robots.txt is fetched once per host, cached for about a day, and checked before every fetch. It may also specify a crawl delay, which feeds the host's politeness interval.

Spider traps are URL spaces that never end: calendars with a "next month" link forever, session ids that make every link unique, /a/b/a/b/a/b/.... Defend with a maximum URL length and path depth, a cap on pages per host per crawl cycle, and by treating parameters that only change session state as the same URL.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Insert more items without adding bits. Watch the false positive rate climb. In the crawler, what does a false positive cost?
  2. Find the number of hash functions that gives the lowest false positive rate for your bits and items. Compare with (bits / items) x 0.69.
  3. Use the 12 GB estimate above: if the crawler discovered 20 billion URLs instead of 10 billion, what would you change to keep the rate at 1 percent?

Bottlenecks and failure modes

FailureImpactMitigation
One huge site dominates the frontierWorkers idle while waiting for politenessPer-host queues; cap pages per host per cycle
Slow or hanging serversFetch slots tied upStrict connect and read timeouts, size limits, async I/O
Spider trapInfinite URLs from one siteDepth and length limits, per-host caps, parameter normalization
Crawler machine diesIts hosts stop being crawledFrontier persisted on disk; hosts reassigned via the hash ring
DNS slowThroughput collapsesLocal caching resolvers, cached IPs in the host table
Bloom filter fullFalse positive rate rises, pages skippedSize for expected URLs; rebuild larger periodically

Trade-offs we made

OptionWins whenLoses when
Per-host back queues (chosen) Politeness enforced by design; fairness across sites More complex frontier; throughput needs many hosts
Bloom filter for seen URLs (chosen) About 12 GB for 10 billion URLs 1 percent of new URLs wrongly skipped
Exact seen-URL store No skipped URLs Hundreds of GB and a disk lookup per link
Hosts partitioned across machines by hash (chosen) Each host's politeness state in one place Rebalancing when machines join or leave

Extensions

  • Freshness-driven re-crawl: estimate each page's change rate and schedule re-fetches to match.
  • JavaScript rendering with headless browsers for pages that build content client-side, at many times the cost per page.
  • Focused crawling that only follows links likely to be on topic.
  • Conditional requests (If-Modified-Since, ETags) so unchanged pages cost a tiny response.

In the wild

Where you will see this: web search engines, web archives, price and SEO monitoring tools, and the crawlers that collect training data for language models. They differ in what they prioritize and how often they return, but all of them meet the same constraints: politeness to other people's servers, robots.txt, DNS cost, and a web full of duplicates and traps.

Check yourself

  1. Why does the frontier keep one queue per host?

    Show answer

    B. To enforce a delay between requests to the same site while keeping other sites busy Per-host queues with next-allowed times make politeness a property of the design rather than luck.

  2. The Bloom filter says a new URL was 'probably seen' but it never was. What happens?

    Show answer

    B. The URL is skipped this time A false positive skips a URL. Bloom filters never give false negatives, so nothing is fetched twice by mistake.

  3. Two URLs serve exactly the same page. How does the crawler avoid storing it twice?

    Show answer

    B. Comparing content hashes before storing Different URLs can point to identical content; hashing the content catches that.

  4. A site's calendar links to the next month forever. What protects the crawler?

    Show answer

    B. Limits on URL depth and pages per host, and parameter normalization Spider traps are infinite URL spaces; caps per host and on URL shape stop them.

Recap

  • A crawler is a loop: frontier, fetch, parse, extract links, filter, back to the frontier.
  • The frontier handles priority with front queues and politeness with per-host back queues.
  • Throughput comes from crawling many hosts in parallel, never from hitting one host harder.
  • Normalize URLs and use a Bloom filter for seen URLs; hash content to catch duplicate pages.
  • Cache DNS and robots.txt, and defend against spider traps with depth and per-host limits.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up