Design a Web Crawler (Googlebot)

URL Frontier: Priority + Politeness Architecture

The URL Frontier acts as the central scheduler and is built as a two-tier system: **Front Queues (Priority)** and **Back Queues (Politeness)**. Together they balance finding the most important pages early while respecting domain rate limits.

1. Front Queues (Priority Allocation):

• URLs are classified into multiple priority levels from critical to low:
  • Queue P1 (Critical): e.g., [google.com/news, bbc.com/latest]
  • Queue P2 (High): e.g., [wikipedia.org/..., nytimes.com/]
  • Queue P3 (Normal): e.g., [example.com/about, blog.io/post]
  • Queue P4 (Low): e.g., [random-site.xyz/page42]
• Priority Assignment Signals:
  • PageRank: Pages on domains with higher PageRank get prioritised first.
  • Freshness Need: Frequently updated directories (e.g. news sites) are scheduled on higher-priority tiers.
  • Sitemap Hints: Explicit <priority> hints in sitemaps (e.g. 0.8 high vs 0.2 low).
  • Historical Change Frequency: If historical scans show a page mutates daily, its priority is increased.
• Selection Process: The prioritizer selects URLs using a weighted random probability distribution: P1: 40% chance, P2: 30% chance, P3: 20% chance, and P4: 10% chance.

2. Back Queues (Politeness Rate Limiting):

• To avoid crashing web servers (Denial-of-Service), the crawler maintains exactly **one FIFO queue per target domain**.
• Each domain queue tracks performance states:
  • Queue [google.com]: Last fetch timestamp, and active crawl_delay (e.g. 2s) → Next crawl window is calculated dynamically.
  • Queue [wikipedia.org]: Long crawl delay (e.g. 5s) → next fetch scheduled 5s after the last successful download.
• Worker Loop: Worker threads scan the back queues to find domains where next_fetch_time ≤ now(), dequeue one URL, issue the HTTP fetch, and set the next available window.

Crawl Execution Flow: One URL End-to-End

Processing a single target URL (e.g., https://example.com/products/shoes) follows a strictly ordered synchronous timeline to maximize efficiency while validating constraints:

1. Step 1: Dequeue from Frontier (0.1 ms)
   Checks eligibility of the back queue (e.g., [example.com]). If last_fetch was 3s ago and crawl_delay is 2s, the queue is eligible. Pops the URL from the queue.
2. Step 2: DNS Resolution (1 ms: Cached)
   Checks the local DNS cache for the host ip (e.g., example.com → 93.184.216.34). On a cache miss, queries recursive DNS resolvers and updates the cache with a standard TTL (e.g., 300s).
   Optimization: Custom batch DNS prefetching executes in the background for upcoming back-queue items.
3. Step 3: Robots.txt Constraint Validation (0.1 ms: Cached)
   Fetches cached robots rules from Redis (e.g., key robots:example.com). If the URL is matched against a block pattern (e.g. Disallow: /products/shoes) for our user agent, the crawler drops the URL instantly, logs a rejection, and moves to the next candidate.
4. Step 4: HTTP Fetch (200 ms: Network)
   Leases a connection from the HTTP client pool for the domain. Transmits a `GET` request declaring a distinct User-Agent:
   User-Agent: MyCrawler/1.0 (+https://mycrawler.com/about)
   Follows HTTP redirects (301, 302, 307) up to 5 levels max. Imposes a 30-second absolute timeout and caps response sizes at 10 MB to prevent crawler bloat.
5. Step 5: Content Deduplication (1 ms)
   Computes the SimHash on the downloaded body. Checks the value against a seen-pages Bloom filter. If the Hamming distance is < 3 (near-duplicate), the page is skipped to prevent indexing duplicate content. Otherwise, it is written to the filter and processing continues.
6. Step 6: Parsing and Link Extraction (5 ms)
   Runs robust HTML parsers to pull structured headers, meta tags, and all child anchor links (<a href="...">) along with JSON-LD micro-data and language parameters.
7. Step 7: Distributing Storage (10 ms)
   Persists the raw HTML, headers, URL, and time metadata into GFS/S3 under a unique key generated by the page content hash.
   Write to S3: { url, content, headers, crawled_at, content_hash } (Deduplication at storage level using content_hash key).
8. Step 8: Discovered URLs Ingestion (1 ms)
   Each extracted child URL is normalized, checked against the global seen-URLs Bloom filter, and added to the frontier with a calculated priority score if it is brand new.
   Trap Protection: Increments crawled:{domain} in Redis. If a domain spans more than 1 million pages, crawling for that domain is halted to avoid infinite folder traps.
9. Step 9: Release & Back Queue Cooling
   Sets `last_fetch_time = now()` for example.com, locking the back queue from worker dequeues for the duration of the crawl delay.

Timeline Summary: Total time per URL:

~220 ms (dominated by network I/O). A single thread achieves ~4.5 URLs/sec. To scale to 1 billion pages per day, we scale up to ~2,500 active worker processes.

Distributed Coordination: Domain-Sharded Architecture

In a large-scale system with 1,000+ crawler workers, coordinating which thread crawls which domain is critical to prevent politeness rate violations and high locking overheads.

The Shared Frontier Concurrency Problem:

• If multiple workers query a single centralized queue of URLs, they might fetch from the same domain at the exact same moment.
• This issues sudden spike loads to web hosts, violating politeness agreements and generating massive distributed lock contention across workers.

The Consistent Hashing Solution:

• We partition domains deterministically across workers using consistent hashing:
  domain_shard = hash(domain) % num_workers
• For instance:
  • Worker 0: assigned to [google.com, stackoverflow.com, ...]
  • Worker 1: assigned to [wikipedia.org, amazon.com, ...]
  • ...
  • Worker 999: assigned to domains hashing to 999
• Each worker maintains its own local URL frontier and Back Queues for its assigned subset of domains.
• Zero-Lock Coordination: Because a domain is only ever processed by a single writer node, no distributed locks or inter-process rate limiters are required to guarantee politeness!

Data Ingestion and Failover via Kafka:

• Ingestion Pipeline: Extracted child URLs are published to a Kafka topic discovered-urls, partitioned by domain hash. Kafka automatically routes URLs to the partition of the worker responsible for that domain.
• When any worker discovers new URLs, it publishes to Kafka with key = domain. Kafka routes to correct partition → correct worker consumes.
• The worker consumes URLs for its assigned domains, checks the shared seen-URLs Bloom filter (Redis-backed or local with periodic sync), and adds to the local frontier if it is brand new.
• Failover and Rebalancing: If a worker (e.g. Worker 42) crashes, the Kafka consumer group triggers a rebalance. Another worker inherits its partition, retrieves the last crawl state and timestamps from Redis, and resumes crawling that domain's queue within 30 seconds.
• Mitigating Hot Domains: If a massive site (like wikipedia.org) overloads a single worker, we split the domain into paths (e.g. wikipedia.org/wiki/A-M vs wikipedia.org/wiki/N-Z) and hash the path prefixes as separate domains.

Advantages over Centralized Frontier:

• ✓ No Single Point of Failure: Masterless architecture ensures there is no centralized coordinator/master node to fail.
• ✓ Linear Scalability: Adding more workers/machines dynamically scales the number of domains handled.
• ✓ Politeness by Design: Guaranteed by a single writer per domain.
• ✗ Load Imbalances (Hot Domains): Hot domains (e.g., google.com) are assigned to one worker creating uneven loads. Mitigated by path-based sub-crawler hashing.

BFS vs DFS vs Priority-Based Crawling

Selecting the path traversal model changes which pages are crawled first and impacts memory consumption:

• Breadth-First Search (BFS):
  • Crawls all root seeds, then all depth-1 pages, followed by depth-2 pages.
  • ✓ Pros: Discovers crucial landing pages early (homepage → navigation sections).
  • ✗ Cons: Tends to waste valuable network bandwidth on low-value pages at the same depth level, and cannot prioritize important content.
• Depth-First Search (DFS):
  • Follows links straight down a site structure before backtracking.
  • ✓ Pros: Low memory consumption since only the active page traversal path is stored.
  • ✗ Cons: Easily trapped in deep recursive page paths, and takes a long time to discover major sections of other domains.
• Priority-Based Crawling (⭐ Recommended):
  • Scores each URL based on relative importance and crawls the highest-scored URLs first.
  • Scoring Equation:
    Score = α × PageRank(domain) + β × depth_penalty + γ × freshness_need
  • ✓ Pros: Guarantees the highest-value internet pages are discovered and cached first.
  • ✓ Adaptive Recrawling: Can reprioritize dynamic schedulers based on real-time change discovery.
  • ✗ Cons: Requires managing complex distributed priority queues.

Practical Hybrid Implementation: Start with BFS from seeds to quickly map a website's core architecture, switch to a priority-based scheduler for daily operations (focusing on important pages), and use DFS locally to walk sitemap hierarchies efficiently.

URL Normalization: Why It Matters

Websites often serve the exact same page content across multiple distinct URL formats. Normalization prevents wasting network and storage bandwidth on redundant crawls.

The Redundancy Problem:

Without normalization, the following 7 URLs would be treated as completely different entities, causing the crawler to fetch the same page 7 separate times (wasted bandwidth):

• https://example.com/page (Canonical template)
• https://Example.COM/page  →  lowercase host
• https://example.com/page/  →  trailing slash removal
• https://example.com/page?a=1&b=2  →  query parameter sorting
• https://example.com/page?b=2&a=1  →  same params, different order
• http://example.com/page  →  scheme normalization
• https://example.com/./page/../page  →  relative path segment resolution

Normalization Rules (Applied before Seen Bloom Filter check):

1. Lowercase the scheme and host components.
2. Remove default protocol ports (e.g. :80 for HTTP and :443 for HTTPS).
3. Strip trailing slashes (except for root domains).
4. Sort all query parameters alphabetically.
5. Remove tracking parameters (e.g., utm_source, fbclid, gclid).
6. Resolve path references (e.g., strip /. and /..).
7. Decode unreserved percent-encoded hex codes (e.g. %41 → A).
8. Extract and honor canonical tags (<link rel="canonical" href="...">) where available.