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]: Tracks the last fetch timestamp and active crawl_delay (such as 2 seconds) so that the next crawl window is calculated dynamically.
  • Queue [wikipedia.org]: With a longer crawl delay (such as 5 seconds), the next fetch is scheduled 5 seconds 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 (such as resolving example.com to 93.184.216.34). On a cache miss, queries recursive DNS resolvers and updates the cache with a standard TTL (such as 300 seconds).
   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 an HTTP 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 64-bit SimHash on the downloaded body. Queries the LSH candidate index using 16-bit sub-bands to retrieve candidate fingerprints sharing at least one band, then calculates the exact bitwise Hamming distance against each candidate. If the Hamming distance is ≤ 3, the page is confirmed as a near-duplicate and skipped. Otherwise, the fingerprint is written to the index 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 & Index Handoff (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).
   Once successfully written to object storage, emits a page-crawled event to Kafka containing the URL metadata and the content_hash storage reference, allowing downstream Search Engine indexers to ingest the document asynchronously without blocking the crawler.
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. Employs layered thresholds: requires a verified sitemap after 100,000 URLs, triggers an operational alert and quarantine throttling at 500,000 URLs, and halts crawl operations for that domain at 1 million pages to prevent infinite crawler 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: The total time per URL is approximately 220 ms (dominated by network I/O). A single thread achieves roughly 4.5 URLs per second. To scale to 1 billion pages per day, the crawler scales up to ~2,500 active worker processes deployed across a fleet of 100 worker nodes (averaging ~25 concurrent fetch processes per node, with each node handling ~115 pages/sec).

Distributed Coordination: Domain-Sharded Architecture

In a large-scale system with ~2,500 concurrent fetch workers across 100 nodes, coordinating which worker 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 a Consistent Hashing ring with virtual nodes:
  node = ring.find_successor(hash(domain))
• How the ring assigns and distributes domains:
  • Hash Ring Mapping: A 64-bit cryptographic hash ring places both worker nodes (with 100 to 200 virtual node tokens per physical machine) and target domain names on the same keyspace.
  • Deterministic Ownership: For any domain, the worker node located first clockwise from the domain's hash coordinates crawl operations for that domain.
  • Smooth Rebalancing: When a worker node crashes or scales out, only a fraction (1/N = ~1%) of domains migrate to adjacent nodes, avoiding the catastrophic global reshuffling of naive modulo hashing.
• Each worker node maintains its own local URL frontier and Back Queues for its assigned subset of domains.
• Zero-Lock Politeness for Normal Domains: Because each standard domain is owned by a single worker node at any given moment, the node manages politeness using an in-memory local token bucket with zero distributed lock overhead on the hot fetch path.

Data Ingestion, Failover, and Hot-Domain Politeness via Kafka:

• Ingestion Pipeline: Extracted child URLs are published to the Kafka topic discovered-urls, configured with 1,024 partitions and keyed by domain hash (key = domain). Kafka provides durable, ordered buffering and decouples URL ingestion from crawl execution. Keying by domain guarantees that all URLs for a single domain arrive on the same partition in FIFO order.
• Ingestion Routing and Hash Ring Decoupling: Worker nodes participate in a unified Kafka consumer group (frontier-ingest). While Kafka's consumer group protocol dynamically balances the 1,024 partitions across consumer nodes (~10 partitions per node) for ingestion I/O, Kafka consumer assignment does not determine domain crawl ownership. Instead, the consumer node reads newly discovered URLs, verifies them against the seen-URLs Bloom filter, and then consults the consistent-hashing ring (ring.find_successor(hash(domain))) to route deduplicated URLs to the authoritative worker node managing that domain's local frontier.
• Local Frontier Management: The authoritative worker node receives candidate URLs for its assigned domains and enqueues them into its local frontier back queues, enforcing rate limits with zero distributed lock overhead.
• Failover and Rebalancing: If a worker node crashes, the consistent-hashing ring smoothly shifts ownership of its domains to the next clockwise node in the ring. The new owner node retrieves crawl checkpoints and timestamps from Redis, resuming frontier execution without duplicate fetches or lost state. Separately, the Kafka consumer group detects heartbeat loss within 10 to 30 seconds and automatically rebalances partition ingestion across surviving nodes.
• Hot-Domain Sharding with Shared Host Politeness: If an exceptionally massive domain (such as wikipedia.org) overloads a single node's queue memory or network bandwidth, the crawler splits the domain across multiple worker nodes by path prefix (e.g. wikipedia.org/wiki/A-M vs wikipedia.org/wiki/N-Z). Crucially, to prevent overloading the target server, all worker nodes crawling that host coordinate against a shared host-level rate-limit budget (persisted in Redis as a token-leasing bucket). Path sharding scales queue throughput while preserving domain-level politeness.

Advantages over Centralized Frontier:

• ✓ No Single Point of Failure: Masterless ring architecture ensures there is no centralized coordinator or master node bottleneck to fail.
• ✓ Linear Scalability: Adding more worker nodes dynamically expands queue memory and domain capacity across the fleet.
• ✓ Zero-Lock Politeness for Normal Domains: Single-owner worker nodes enforce rate limits via local in-memory token buckets without distributed lock contention.
• ✗ Hot-Domain Coordination Overhead: When massive domains are split across nodes by path prefix, workers must coordinate against a shared Redis rate-limit lease pool to protect target hosts.

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, traversing from root homepages into major 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 = α x PageRank(domain) + β x depth_penalty + γ x freshness_need
  • ✓ Pros: Helps prioritize high-value pages for earlier discovery and caching.
  • ✓ 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 (normalizes host casing to lowercase)
• https://example.com/page/ (strips trailing slash)
• https://example.com/page?a=1&b=2 (sorts query parameters alphabetically)
• https://example.com/page?b=2&a=1 (normalizes query parameters to canonical ordering)
• http://example.com/page (normalizes protocol scheme)
• https://example.com/./page/../page (resolves relative path segments)

Normalization Hierarchy: Safe Rules vs Configurable Heuristics:

The normalization pipeline distinguishes universally semantics-preserving rules from policy-dependent canonicalization heuristics:

• 1. Universally Safe Normalizations (Strict Semantics Preservation):
  • Scheme and Host Lowercasing: Protocol schemes and DNS hostnames are strictly case-insensitive per RFC 3986 (e.g. HTTP://Example.COM becomes http://example.com).
  • Default Port Removal: Eliminate standard protocol ports (e.g. :80 for HTTP and :443 for HTTPS).
  • Fragment Identifier Removal: Strip URI fragments (#section) because fragments reference client-side DOM anchors and are never transmitted in HTTP requests.
  • Path Segment Resolution: Resolve dot-segments by resolving and removing inline /. and /.. path references.
  • Unreserved Percent-Encoding Decoding: Decode percent-encoded uppercase hex sequences for unreserved characters (such as converting %41 to A).
• 2. Configurable Canonicalization Heuristics (Policy-Dependent):
  • Trailing Slash Handling: Stripping trailing slashes is safe on root hosts (e.g. example.com/), but must be configured per site on path hierarchies where servers differentiate directory indexes from file resources.
  • Query Parameter Sorting: Reordering query parameters alphabetically helps match identical parameter sets, but is policy-dependent because dynamic applications and APIs may treat parameter order as semantically significant.
  • Tracking Parameter Removal: Strip recognized marketing and analytics query keys (e.g. utm_source, utm_campaign, fbclid, gclid, ref), but preserve functional parameters required for page rendering.
  • Canonical Tag Adherence: Extract and honor HTML canonical link tags (<link rel="canonical" href="...">) when verified by the downstream parser to collapse duplicate parameter variants into a single canonical target.