Skip to main content

Design a Web Crawler

Adapted from: Alex Xu, System Design Interview – An Insider's Guide (2020), Chapter 9 — rewritten and condensed for teaching.

A web crawler, also called a robot or spider, discovers new and updated content on the web: pages, images, videos, PDFs. It starts from a few pages, follows their links to more pages, follows those links, and so on.

flowchart LR
  S((seed)) --> A((page)) & B((page))
  A --> C((page)) & D((page))
  B --> D
  B --> E((page))
  D --> F((page))

What crawlers are used for:

  • Search engine indexing. The most common use: collect pages to build a search index. Googlebot crawls for Google Search.
  • Web archiving. Preserve the web for the future. National libraries, such as the US Library of Congress and the EU web archive, run crawlers.
  • Web mining. Extract knowledge from the web. For example, financial firms crawl shareholder-meeting transcripts and annual reports.
  • Web monitoring. Find copyright and trademark infringement. Digimarc, for example, crawls to discover pirated works.

How hard this is depends on scale. A school-project crawler takes an afternoon, while a search-engine crawler keeps a dedicated team busy indefinitely.

What you'll be able to do after this lesson:

  • Size a crawler and name the qualities a good one needs: scalable, robust, polite, and extensible.
  • Trace a URL through the full pipeline, from frontier to downloader to parser to "seen?" checks and back to the frontier.
  • Design a URL frontier that enforces politeness (back queues), priority (front queues), and freshness.
  • Implement link extraction, robots.txt checks, a polite frontier, and a de-duplicating BFS crawl.

Step 1: Understand the Problem and Establish Scope​

The core algorithm fits in three lines:

  1. Given a set of URLs, download all their pages.
  2. Extract URLs from those pages.
  3. Add the new URLs to the to-download list, and repeat.

Doing that at web scale is another matter. Clarify first:

Candidate asksInterviewer answers
Purpose: search indexing, data mining, something else?Search engine indexing
How many pages per month?1 billion
Content types?HTML only
Handle new and edited pages?Yes
Store the crawled HTML?Yes, for up to 5 years
Duplicate content?Ignore pages with duplicate content

Even for a "simple" product, you and the interviewer can start with different assumptions. That's why you ask.

Qualities of a good crawler​

  • Scalability. The web has billions of pages, so crawling must be massively parallel.
  • Robustness. The web is full of traps: bad HTML, unresponsive servers, crashes, malicious links. Handle them all without falling over.
  • Politeness. Don't send a website too many requests in a short time.
  • Extensibility. Supporting a new content type, such as images, should take a new module, not a redesign.

Back-of-the-envelope estimation​

QuantityCalculationResult
Pages per second1,000,000,000 ÷ 30 days ÷ 86,400 s≈ 386, round to ~400
Peak QPS2 × 400~800
Average page sizeAssumption500 KB
Storage per month1 B pages × 500 KB500 TB
Storage over 5 years500 TB × 12 months × 5 years30 PB

(Here the "× 12 × 5" is correct, because the 500 TB is a monthly figure. Compare the double-counting slip in Lesson 8.)

Step 2: High-Level Design​

flowchart LR
  SEED[Seed URLs] --> FR[URL Frontier]
  FR --> DL[HTML Downloader]
  DNS[DNS Resolver] <--> DL
  DL --> CP[Content Parser]
  CP --> CS{Content Seen?}
  CS <--> STORE[(Content Storage)]
  CS --> LE[Link Extractor]
  LE --> UF[URL Filter]
  UF --> US{URL Seen?}
  US <--> USTORE[(URL Storage)]
  US --> FR

The components​

  • Seed URLs. Where the crawl starts. For one university's site, the seed is just its domain. For the whole web, pick seeds that reach as many links as possible by dividing the URL space: by locality (different countries have different popular sites) or by topic (shopping, sports, healthcare, …). There's no perfect answer, so think out loud.
  • URL Frontier. Crawl state splits into to be downloaded and already downloaded. The frontier holds the first group. For now, think of it as a FIFO queue. The deep dive refines it.
  • HTML Downloader. Fetches the pages at the URLs the frontier hands it.
  • DNS Resolver. Turns a hostname into an IP address before download. For example, www.wikipedia.org resolved to 198.35.26.96 in March 2019.
  • Content Parser. Parses and validates pages, because malformed HTML causes problems and wastes storage. It is a separate component so parsing doesn't slow the crawl servers down.
  • Content Seen? About 29% of web pages are duplicate content. Comparing pages character by character is far too slow at billions of pages, so compare hashes of the pages instead, and discard content that has already been stored.
  • Content Storage. Mostly on disk, because the data set is enormous, with popular content in memory to cut latency.
  • URL Extractor. Pulls links out of HTML and turns relative paths into absolute URLs. For example, /wiki/Cong_Weixi on a Wikipedia page becomes https://en.wikipedia.org/wiki/Cong_Weixi.
  • URL Filter. Drops unwanted content types, file extensions, error links, and URLs on blocklisted sites.
  • URL Seen? Tracks URLs already visited or already in the frontier, so the same URL isn't added twice. That avoids wasted load and infinite loops. It is typically a Bloom filter or a hash table.
  • URL Storage. Stores the URLs already visited.

Implement extract_links(base_url, html, max_len):

  1. Collect the href of every <a> tag. Python's html.parser.HTMLParser is in the standard library.
  2. Resolve each one against base_url with urllib.parse.urljoin, then strip any #fragment with urldefrag.
  3. Filter: keep only http/https, drop paths ending in .jpg .jpeg .png .gif .pdf .zip (case-insensitive), and drop URLs longer than max_len. The length cap is a cheap guard against spider traps.
  4. De-duplicate, keeping first-seen order.

Input: line 1 is base_url max_len, and the remaining lines are HTML.

The crawl workflow​

flowchart LR
  SEED[Seed URLs] -- "1" --> FR[URL Frontier]
  FR -- "2" --> DL[HTML Downloader]
  DNS[DNS Resolver] -- "3" --- DL
  DL -- "4" --> CP[Content Parser]
  CP -- "5" --> CS{Content Seen?}
  CS -- "6: new" --> LE[Link Extractor]
  CS -. "6: duplicate → discard" .-> X[✗]
  LE -- "7–8" --> UF[URL Filter]
  UF -- "9" --> US{URL Seen?}
  US -. "10: seen → skip" .-> Y[✗]
  US -- "11: new" --> FR
  1. Add the seed URLs to the frontier.
  2. The downloader takes a batch of URLs from the frontier.
  3. It resolves their IPs with the DNS resolver and downloads the pages.
  4. The content parser parses each page and rejects malformed ones.
  5. Valid content goes to Content Seen?
  6. If the same content is already stored (under a different URL), discard the page. Otherwise pass it to the link extractor.
  7. The link extractor pulls out the links.
  8. They go to the URL filter.
  9. Surviving links go to URL Seen?
  10. If a URL has been seen before, do nothing.
  11. Otherwise, add it to the frontier.

Check: components and workflow​

Quiz

Crawler components

1 / 3

Two different URLs return byte-for-byte identical HTML. Which component stops the second copy from being stored and re-processed?

Pick an answer to see if you are right.

Step 3: Design Deep Dive​

DFS vs. BFS​

The web is a directed graph: pages are nodes and links are edges. Crawling is a graph traversal.

  • DFS is usually a poor choice, because the depth can be enormous and the crawler disappears down one site's rabbit hole.
  • BFS, with a FIFO queue, is the standard choice, but plain BFS has two problems:
    1. It's impolite. Most links on a page point to the same host. BFS of Wikipedia fills the queue with Wikipedia URLs, and parallel downloaders then flood Wikipedia's servers.
    2. It ignores priority. Pages differ hugely in quality and importance. We'd like to rank URLs by PageRank, traffic, update frequency, and so on.

The URL frontier fixes both.

URL frontier​

The frontier stores the URLs waiting to be downloaded, and it is where politeness, priority, and freshness are enforced.

Politeness: back queues​

Sending a host too many requests at once is rude, and can look like a DoS attack. The rule is to download one page at a time per host, optionally with a delay between downloads.

flowchart LR
  IN[URLs] --> QR[Queue router]
  MT[(Mapping table<br/>host → queue)] --- QR
  QR --> B1["b1: wikipedia.com"]
  QR --> B2["b2: apple.com"]
  QR --> BN["bn: nike.com"]
  B1 & B2 & BN --> QS[Queue selector]
  QS --> W1[Worker 1]
  QS --> W2[Worker 2]
  QS --> WN[Worker N]
  • Queue router: ensures each queue (b1 … bn) holds URLs from one host only.
  • Mapping table: maps each host to its queue.
  • FIFO queues b1 … bn: one per host.
  • Queue selector: assigns each worker thread to a queue. A worker downloads only from its own queue.
  • Workers 1 … N: download one page at a time from their host, with an optional delay between downloads.

Practice: a polite frontier​

Implement PoliteFrontier with:

  • add(url): route the URL to its host's FIFO queue (the host is urlparse(url).netloc). Queues are created in first-seen order.
  • next_batch(): take one URL from each non-empty host queue, in queue creation order, and remove queues that become empty. Each batch is one "round" of parallel downloads that never hits the same host twice.

In the first test, plain BFS would have downloaded wiki.org/a, b, and c at the same time. The polite frontier never touches one host twice in a round, and the long single-host tail at the end (rounds 3–4) is the price of being polite.

Priority: front queues​

A random forum post that mentions Apple matters far less than Apple's home page, even though both contain the word "Apple." Rank URLs by usefulness: PageRank, website traffic, update frequency, and so on.

flowchart LR
  IN[URLs] --> P[Prioritizer]
  P --> F1["f1 (highest priority)"]
  P --> F2[f2]
  P --> FN["fn (lowest)"]
  F1 & F2 & FN --> QS["Queue selector<br/>(random, biased toward high priority)"]
  QS --> OUT[To back queues]
  • Prioritizer: computes each URL's priority.
  • Queues f1 … fn: one per priority level.
  • Queue selector: picks a queue at random, biased toward high priority, so important pages come first but low-priority pages are never starved.

The complete frontier​

flowchart TB
  IN[URLs] --> P[Prioritizer]
  subgraph Front["Front queues: prioritization"]
    P --> F1[f1] & F2[f2] & FN[fn]
  end
  F1 & F2 & FN --> FS[Front queue selector]
  FS --> QR[Back queue router]
  subgraph Back["Back queues: politeness"]
    QR --> B1[b1] & B2[b2] & BN[bn]
  end
  B1 & B2 & BN --> BS[Back queue selector]
  BS --> W[Worker threads]

Front queues decide what's important. Back queues decide what's allowed right now, given politeness.

Freshness​

Pages are constantly added, changed, and deleted, so the crawler must recrawl. Recrawling everything is too expensive, so:

  • Recrawl based on each page's update history: pages that change often get revisited often.
  • Recrawl important pages first and more frequently.

Storage for the frontier​

A search-engine frontier can hold hundreds of millions of URLs. Keeping them all in memory isn't durable or scalable, and keeping them all on disk makes the disk a bottleneck. Use a hybrid: store most URLs on disk, with in-memory buffers for enqueue and dequeue that are flushed to disk periodically.

Check: frontier design​

Quiz

Politeness, priority, freshness

1 / 3

Why is plain BFS considered impolite for a parallel crawler?

Pick an answer to see if you are right.

HTML Downloader​

robots.txt​

The Robots Exclusion Protocol, in the form of a site's robots.txt file, tells crawlers which paths they may fetch. Check it before crawling a site, and follow it. To avoid downloading it again and again, cache it and refresh it periodically. An excerpt in the style of Amazon's file:

User-agent: Googlebot
Disallow: /creatorhub/*
Disallow: /rss/people/*/reviews
Disallow: /gp/pdp/rss/*/reviews
Disallow: /gp/cdp/member-reviews/
Disallow: /gp/aw/cr/

Disallow rules are path prefixes. * matches any run of characters, and a trailing $ anchors the rule to the end of the path. A crawler uses the group that matches its own User-agent, falling back to the User-agent: * group.

Practice: honor robots.txt​

Implement is_allowed(robots, agent, path):

  • Parse User-agent: lines to start groups, keyed by the agent name lower-cased. Add each Disallow: value to the current group. Ignore comments (#…) and blank lines.
  • Use the group whose name equals the lower-cased agent, or else the * group, or else no rules.
  • A non-empty rule matches if it matches the start of the path, with * matching any characters and an optional trailing $ meaning end of path. An empty Disallow: blocks nothing.
  • Return False if any rule matches.

The wrapper uses a fixed ROBOTS file. Each stdin line is agent path.

Performance optimization​

  1. Distributed crawl. Split the URL space across many servers, each running many threads, so that each downloader owns a subset of URLs.
  2. Cache the DNS resolver. DNS lookups take 10–200 ms, and many DNS interfaces are synchronous, so one thread's lookup can block others. Keep a local hostname → IP cache, refreshed periodically by cron jobs.
  3. Locality. Place crawl servers geographically close to the sites they crawl, which makes downloads faster. The same idea applies to caches, queues, and storage.
  4. Short timeouts. Some servers respond slowly or never. Set a maximum wait time and move on to other pages when it expires.
flowchart LR
  FR[URL Frontier] --> S1["Crawl server 1<br/>threads 1…k"] & S2["Crawl server 2<br/>threads 1…k"] & SN["Crawl server N<br/>threads 1…k"]
  S1 & S2 & SN --> WEB((The web))

Robustness​

  • Consistent hashing spreads load across downloaders and lets you add or remove downloader servers with minimal reshuffling. See Lesson 5.
  • Save crawl state and data to storage, so a crashed crawl can resume instead of starting over.
  • Exception handling. Errors are routine at scale. Handle them without crashing the system.
  • Data validation prevents bad data from causing system errors.

Extensibility​

Design the pipeline so that new capabilities plug in as modules:

flowchart LR
  FR[URL Frontier] --> DL[HTML Downloader] --> CP[Content Parser] --> CS{Content Seen?}
  CS --> LE[Link Extractor] --> UF[URL Filter] --> US{URL Seen?} --> FR
  CS -.-> PNG["PNG Downloader<br/>(plug-in)"]
  CS -.-> MON["Web Monitor<br/>(plug-in)"]
  • A PNG Downloader module adds image crawling.
  • A Web Monitor module watches for copyright and trademark infringement.

Detect and avoid problematic content​

  1. Redundant content. Nearly 30% of pages are duplicates. Detect them with hashes or checksums, as Content Seen? does.
  2. Spider traps. Some pages send a crawler into an infinite loop, for example an endlessly deep directory structure such as spidertrapexample.com/foo/bar/foo/bar/foo/bar/…. A maximum URL length catches many traps. No single rule catches them all, but trap sites stand out by producing an abnormally large number of pages. People can verify suspects and exclude the site or add custom URL filters.
  3. Data noise. Advertisements, code snippets, and spam URLs have little value. Exclude them where you can.

Practice: a de-duplicating BFS crawl​

Put the pieces together. Implement crawl(seeds, web, max_pages) over a simulated web: web maps each URL to (content, links), and URLs missing from web fail to download.

  • Use a FIFO frontier and a URL Seen? set. Mark a URL as seen when it's enqueued, and enqueue seeds in order, skipping repeats.
  • Pop URLs until the frontier is empty or max_pages downloads have happened. Successful downloads count toward the limit; failed ones don't.
  • If the URL is missing from web, log error <url> and move on. Don't crash.
  • Otherwise, hash the content with SHA-256. If it's in Content Seen?, log duplicate <url> and discard the page without extracting its links. Otherwise record the hash, log fetch <url>, and enqueue its unseen links.

Input: line 1 is the seed URLs, line 2 is max_pages, and each remaining line is url content link1,link2 (use - for no links).

Look at the first test. Page c duplicates a, so it's discarded before link extraction, and its link to e is never followed. The cycle test shows URL Seen? doing its other job: p → q → p terminates.

Check: downloader, robustness, problem content​

Quiz

Downloader and robustness

1 / 3

Profiling shows crawler threads spending much of their time blocked before downloads even start. What is the likely fix?

Pick an answer to see if you are right.

Step 4: Wrap Up​

We covered the qualities of a good crawler (scalability, politeness, extensibility, robustness), the pipeline, and the key components in depth. Further talking points:

  • Server-side (dynamic) rendering. Many sites build links with JavaScript or AJAX. Parsing raw HTML misses them, so render the page first, then parse it.
  • Filtering unwanted pages. Storage and crawl capacity are finite, so an anti-spam component filters out low-quality pages.
  • Database replication and sharding for availability, scalability, and reliability of the data layer.
  • Horizontal scaling. Large crawls use hundreds or thousands of download servers. Keep them stateless.
  • Availability, consistency, and reliability: see Lesson 1.
  • Analytics. Collect and analyze crawl data to fine-tune the system.

Key Takeaways​

  • About 400 pages/s (800 at peak), with 500 TB per month and 30 PB over 5 years.
  • Pipeline: frontier → downloader (+ DNS) → parser → Content Seen? → link extractor → URL filter → URL Seen? → frontier.
  • Use BFS, but through a URL frontier: front queues for priority (biased random selection) and back queues for politeness (one host per worker).
  • Respect robots.txt and cache it. Speed up with a distributed crawl, a DNS cache, locality, and short timeouts.
  • Defend against duplicates (hashes), spider traps (URL length cap plus manual review), and noise.

Previous lesson: Design a URL Shortener.

Next lesson: Design a Notification System — push, SMS, and email through per-channel queues, with retries, dedupe, opt-in settings, and rate limiting.

Reference Materials​

  1. US Library of Congress: Web Archiving
  2. EU Web Archive
  3. Digimarc: Piracy Intelligence
  4. Heydon A., Najork M. "Mercator: A scalable, extensible web crawler." World Wide Web, 2(4) (1999), pp. 219–229.
  5. Christopher Olston, Marc Najork. Web Crawling.
  6. 29% Of Sites Face Duplicate Content Issues
  7. Rabin M.O., et al. "Fingerprinting by random polynomials." Center for Research in Computing Techn., Aiken Computation Laboratory, Univ. (1981).
  8. B. H. Bloom. "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM, 13(7), pp. 422–426, 1970.
  9. Donald J. Patterson. Web Crawling (lecture slides).
  10. L. Page, S. Brin, R. Motwani, T. Winograd. "The PageRank citation ranking: Bringing order to the web." Technical Report, Stanford University, 1998.
  11. Burton Bloom. "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM, 13(7), pp. 422–426, July 1970.
  12. Google: Dynamic Rendering
  13. T. Urvoy, T. Lavergne, P. Filoche. "Tracking web spam with hidden style similarity." Proc. 2nd International Workshop on Adversarial Information Retrieval on the Web, 2006.
  14. H.-T. Lee, D. Leonard, X. Wang, D. Loguinov. "IRLbot: Scaling to 6 billion pages and beyond." Proc. 17th International World Wide Web Conference, 2008.