Design a web crawler in HLD - System Design Exercise

Design: Web Crawler

Design focuses on the crawling system including URL management, fetching, parsing, and storage. Indexing and search functionalities are out of scope.

Functional Requirements

FR1: Crawl web pages starting from a list of seed URLs

FR2: Extract and store page content and metadata

FR3: Follow links to discover new pages

FR4: Respect robots.txt rules and crawl delays

FR5: Handle millions of URLs efficiently

FR6: Avoid crawling the same URL multiple times

FR7: Support prioritization of URLs to crawl

FR8: Provide a way to pause and resume crawling

Non-Functional Requirements

NFR1: Scale to crawl at least 10 million pages per day

NFR2: Latency for fetching a page should be under 2 seconds on average

NFR3: System availability should be 99.9%

NFR4: Respect politeness to avoid overloading websites

NFR5: Handle network failures and retries gracefully

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

❓ Question 7

Key Components

URL Frontier Manager

Fetcher (HTTP client)

Parser (HTML and link extractor)

Robots.txt Manager

URL Deduplication Store

Data Storage (for pages and metadata)

Scheduler and Prioritizer

Monitoring and Logging

Design Patterns

Producer-Consumer for fetching and parsing

Distributed Queue for URL frontier

Bloom Filters or Hash Sets for deduplication

Rate Limiting for politeness

Retry and Backoff strategies

Sharding for scaling storage

Reference Architecture

  +-------------------+       +-------------------+       +-------------------+
  | Seed URLs         |       | URL Frontier      |       | Robots.txt Manager |
  +---------+---------+       +---------+---------+       +---------+---------+
            |                           |                           |
            v                           v                           v
  +-------------------+       +-------------------+       +-------------------+
  | URL Deduplication |<----->| Scheduler &       |<----->| Politeness &      |
  | Store             |       | Prioritizer       |       | Rate Limiter      |
  +---------+---------+       +---------+---------+       +---------+---------+
            |                           |                           |
            v                           v                           v
  +-------------------+       +-------------------+       +-------------------+
  | Fetcher (HTTP)    |<----->| Parser (HTML &    |<----->| Data Storage      |
  +-------------------+       | Link Extractor)   |       | (Pages & Metadata)|
                              +-------------------+       +-------------------+

Components

URL Frontier Manager

Distributed Queue (e.g., Kafka, RabbitMQ)

Stores URLs to be crawled and manages their prioritization

Fetcher

HTTP Client Library (e.g., libcurl, Requests)

Fetches web pages from the internet respecting politeness

Parser

HTML Parser (e.g., BeautifulSoup, jsoup)

Extracts page content and discovers new URLs from fetched pages

Robots.txt Manager

Custom or existing robots.txt parser

Checks and enforces crawling rules per website

URL Deduplication Store

Bloom Filter or Distributed Hash Set (e.g., Redis, Cassandra)

Prevents crawling the same URL multiple times

Scheduler & Prioritizer

Custom scheduling logic with priority queues

Decides which URLs to crawl next based on priority and politeness

Data Storage

Distributed Storage (e.g., HDFS, S3, NoSQL DB)

Stores crawled page content and metadata for later use

Monitoring & Logging

Prometheus, ELK Stack

Tracks system health, crawl progress, and errors

Request Flow

1. Start with seed URLs loaded into the URL Frontier Manager.

2. Scheduler picks URLs from the frontier respecting priority and politeness.

3. Robots.txt Manager checks if crawling the URL is allowed.

4. Fetcher downloads the page content if allowed.

5. Parser extracts page content and finds new URLs.

6. New URLs are checked against the URL Deduplication Store to avoid repeats.

7. Unique new URLs are added back to the URL Frontier Manager.

8. Fetched page content and metadata are stored in Data Storage.

9. Monitoring tracks progress and errors throughout the process.

Database Schema

Entities: - URL: {id (PK), url, status, last_crawled, priority} - PageContent: {url_id (FK), content, content_type, fetch_time} - RobotsTxtRules: {domain, rules, fetched_time} Relationships: - URL to PageContent is 1:1 - URL to RobotsTxtRules via domain matching (not direct FK)

Scaling Discussion

Bottlenecks

URL Frontier Manager becomes a bottleneck with millions of URLs

Fetcher limited by network bandwidth and latency

URL Deduplication Store grows large and slow

Data Storage size and write throughput

Scheduler complexity with many URLs and politeness constraints

Solutions

Partition URL Frontier by domain or hash to distribute load

Use multiple fetcher instances distributed geographically

Use scalable probabilistic data structures like Bloom filters with periodic resets

Use distributed storage systems with sharding and replication

Implement domain-based scheduling to parallelize while respecting politeness

Interview Tips

Time: 10 minutes for requirements and clarifications, 15 minutes for architecture and components, 10 minutes for scaling discussion, 10 minutes for Q&A

Clarify scale and politeness requirements upfront

Explain URL frontier and deduplication importance

Discuss how to respect robots.txt and crawl delays

Describe components and their interactions clearly

Address scaling challenges with partitioning and distribution

Mention failure handling and monitoring for reliability

Practice

1. What is the primary role of a web crawler in system design?

easy

A. To manage user authentication on websites

B. To display web pages to users

C. To automatically visit and collect data from websites

D. To store user preferences for websites

Solution

1. Step 1: Understand the function of a web crawler

   A web crawler is designed to visit websites automatically and collect data for indexing or analysis.

2. Step 2: Differentiate from other web functions

   Displaying pages, managing authentication, or storing preferences are not tasks of a crawler but of browsers or web servers.

3. Final Answer:

   To automatically visit and collect data from websites -> Option C

4. Quick Check:

   Web crawler = data collection [OK]

Hint: Crawler means automatic website data collection [OK]

Common Mistakes:

• Confusing crawler with browser functionality
• Thinking crawler manages user data
• Mixing crawler with server-side tasks

2. Which component is essential for managing the list of URLs to visit in a web crawler?

easy

A. User Interface

B. URL Frontier

C. Data Storage

D. HTML Parser

Solution

1. Step 1: Identify the URL management part

   The URL Frontier is the component that keeps track of URLs to be visited next in a crawler.

2. Step 2: Exclude unrelated components

   HTML Parser processes page content, Data Storage saves data, and User Interface is unrelated to URL management.

3. Final Answer:

   URL Frontier -> Option B

4. Quick Check:

   URL list manager = URL Frontier [OK]

Hint: URL list is managed by URL Frontier [OK]

Common Mistakes:

• Confusing parser with URL manager
• Thinking storage manages URLs
• Assuming UI handles crawling logic

3. Consider a crawler fetching pages with a politeness delay of 2 seconds per domain. If it visits 5 domains concurrently, how many pages can it fetch in 10 seconds?

medium

A. 50 pages

B. 10 pages

C. 5 pages

D. 25 pages

Solution

1. Step 1: Calculate pages per domain in 10 seconds

   With 2 seconds delay, each domain can be fetched 10 / 2 = 5 times in 10 seconds.

2. Step 2: Multiply by number of domains

   5 domains * 5 pages each = 25 pages total.

3. Final Answer:

   25 pages -> Option D

4. Quick Check:

   5 domains * 5 pages = 25 [OK]

Hint: Pages = (time/delay) * domains [OK]

Common Mistakes:

• Multiplying delay by domains incorrectly
• Ignoring concurrency in calculation
• Using total time as pages directly

4. A web crawler's URL Frontier is implemented as a simple queue. What problem might arise with this design?

medium

A. It may revisit the same URLs multiple times

B. It will fetch pages too quickly without delay

C. It cannot parse HTML content correctly

D. It will store data inefficiently

Solution

1. Step 1: Understand queue behavior in URL management

   A simple queue does not track visited URLs, so duplicates can be added and revisited.

2. Step 2: Identify consequences

   This causes repeated crawling of same pages, wasting resources.

3. Final Answer:

   It may revisit the same URLs multiple times -> Option A

4. Quick Check:

   Queue alone lacks duplicate check [OK]

Hint: Queue alone misses duplicate URL checks [OK]

Common Mistakes:

• Confusing queue with parser or storage issues
• Assuming queue controls fetch speed
• Thinking queue affects data storage

5. You want to design a scalable web crawler that respects website politeness and avoids overloading servers. Which approach best achieves this?

hard

A. Use distributed crawling with domain-based rate limiting and URL deduplication

B. Fetch all URLs as fast as possible without delay to maximize speed

C. Store all URLs in a single server queue without concurrency control

D. Ignore robots.txt and crawl all pages aggressively

Solution

1. Step 1: Identify scalability and politeness needs

   Distributed crawling allows scaling; domain-based rate limiting ensures politeness; URL deduplication prevents repeated visits.

2. Step 2: Evaluate other options

   Fetching fast without delay overloads servers; single queue limits scalability; ignoring robots.txt is unethical and risky.

3. Final Answer:

   Use distributed crawling with domain-based rate limiting and URL deduplication -> Option A

4. Quick Check:

   Distributed + rate limit + deduplication = scalable polite crawler [OK]

Hint: Combine distribution, rate limits, and deduplication [OK]

Common Mistakes:

• Ignoring politeness rules
• Centralizing all URLs causing bottlenecks
• Disregarding robots.txt rules