Katkat
Back

Design Search And Web Crawling Systems

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This question tests the ability to design a scalable web crawler capable of handling billions of pages while maintaining freshness and avoiding redundant work.

Problem Statement

Design a distributed web crawler system that can discover, download, and index content from the public internet. The system needs to support a scale of 10 billion pages, with a refresh rate of one week for the entire corpus.

Functional Requirements

  1. URL Discovery: Efficiently discover new URLs from crawled pages.
  2. Fetch Service: Retrieve content from target hosts while being respectful of robots.txt and server load.
  3. Deduplication: Avoid redundant downloads and indexing of identical content.
  4. Indexing: Prepare content for a search engine backend.

Non-Functional Requirements

  1. Scalability: Handle a throughput of approximately 15,000 pages per second.
  2. Freshness: Prioritize frequently updated sites over static content.
  3. Politeness: Ensure the system does not overwhelm a single domain with requests.

Requirements for your design:

  1. High-level architecture: Provide a diagram or flow description of the components (e.g., URL frontier, fetchers, content store).
  2. Data storage strategy: Explain how you manage the URL queue and identify seen URLs at scale.
  3. Capacity planning: Estimate the storage requirements and the number of nodes required to sustain the throughput.
  4. Trade-offs: Discuss the trade-offs between system complexity and data freshness.

Hints

Hint 1

Consider using a distributed message queue or a prioritized heap for the URL frontier to manage scheduling.

Hint 2

Think about using a Bloom filter to handle the massive 'seen URL' set in memory before performing a disk-based lookup.

Hint 3

Address the politeness constraint by partitioning the URL frontier by domain name and using worker-specific rate limiters.

Follow-up questions

  • How would you modify the system to handle pages that require JavaScript rendering?
  • What specific strategies would you use to detect and filter out spam or low-quality content during the crawl process?
  • If a major site changes its site map structure, how does your crawler detect and recover from the failure to find new links?