Concurrent Web Crawlers and Work Queues

What's being tested

Candidates are evaluated on designing a concurrent web crawler that is correct, efficient, and robust: concurrency control for fetching, URL normalization and deduplication, polite per-host rate-limiting, frontier organization, and failure / retry behavior. Interviewers want to see the candidate ask the right scope questions (scale, single vs multi-domain, freshness), decompose into clear subsystems, and trade off practical choices (async vs threads, Bloom filters vs exact sets, centralized vs sharded frontier).

Core knowledge

• URL normalization / canonicalization: normalize scheme/host (lowercase), remove default ports, resolve relative paths, drop fragments, and canonicalize query params (sort or whitelist) to avoid combinatorial explosion from session IDs and tracking parameters.

• Same-domain / same-origin differences: same-domain may include subdomains; same-origin requires identical scheme+host+port. Clarify which constraint governs link acceptance and cookie/robot behavior.

• Frontier design: the URL frontier is a prioritized work queue; implement per-host queues with a global scheduler to enforce politeness and fairness (round-robin or weighted). For N up to ~10M, a single-machine in-memory frontier is OK; beyond that, shard by host to multiple machines.

• Duplicate detection: Bloom filter for large-scale membership with tunable false-positive p. Use $m = -n \ln p /(\ln 2)^2$ bits and $k = (m/n) \ln 2$ hashes; e.g., $n=100M$, $p=1e-6 \to m \approx 2.87e9$ bits (∼360MB).

• Concurrency models: choose between thread pool, async/await (aiohttp), or event-loop + worker processes. Async scales better for high I/O; thread pools are simpler when CPU-bound parsing dominates.

• Per-host politeness / rate-limiting: implement token-bucket or leaky-bucket per host and a global max_outstanding_per_host semaphore to avoid DOSing sites and respect robots.txt Crawl-delay.

• Retry / failure semantics: use lease/visibility timeouts (like SQS), exponential backoff for 5xx, idempotent storage for successful fetches, and a retry limit with a dead-letter queue for permanent errors.

• Cycle safety & depth control: maintain a visited set (or Bloom filter) and enforce max depth and per-domain URL caps to avoid infinite calendar or calendar-like traps.

• Politeness sources: parse robots.txt, honor crawl-delay, and respect Sitemap hints; cache DNS results and respect HTTP Retry-After.

• Storage & dedupe at content level: use content hashing (e.g., SHA-256) or canonical HTML signatures to detect duplicate pages with different URLs; store (url, content-hash, last-fetched) for freshness checks.

• Metrics & SLAs: track pages/sec, p99 fetch latency, queue depth, successes/failures, and per-host rate metrics; surface slow hosts and crawled-domain coverage.

• Scaling & sharding: shard by host hash to keep politeness local; coordinate frontier assignment via consistent hashing or a small master to avoid multi-master races.

Worked example — Design a Concurrent Domain Crawler

First 30s framing: clarify whether “domain” means exact hostname or includes subdomains, expected scale (pages/day), freshness requirements, and allowed content types (HTML only?). State assumptions: single logical domain, target 10M URLs, need politeness and breadth-first behavior. Organize the answer around four pillars: (1) frontier with per-host queue and global scheduler, (2) fetchers as async workers with per-host semaphores and token buckets, (3) deduplication using a Bloom filter for visited URLs plus content-hash dedupe, and (4) storage & retry with visibility leases and DLQ. Flag tradeoff: using Bloom filter saves memory but yields false positives (lost crawls); choose p based on acceptable misses and keep a small exact secondary store for recent URLs. Close by noting follow-ups: shard the frontier for higher scale, add politeness heuristics per subdomain, and instrument p95/p99 latency and coverage metrics for tuning.

A second angle — Crawl Same-Domain Links

This problem narrows to graph traversal inside one domain, emphasizing URL normalization, cycle-safe traversal, and depth constraints. The same core systems apply, but scale is smaller so you can use an exact Postgres visited table rather than probabilistic structures. Decide traversal strategy: BFS gives even coverage for site-mapping and search-indexing, while DFS uses less memory but risks deep traps. Here emphasize canonicalization (drop tracking params) and per-path heuristics to avoid calendaring traps (detect repeating numeric patterns). Rate-limiting and politeness are simpler (single host), so more budget can go to parsing and link extraction accuracy.

Common pitfalls

Pitfall: Underestimating duplicate-address space — assuming exact-string dedupe is sufficient will explode when query parameters or session IDs vary widely; always canonicalize and whitelist query parameters.

Pitfall: Not asking scope questions — failing to clarify single-domain vs multi-domain, scale, or freshness misses critical design constraints and leads to wrong architecture choices.

Pitfall: Overengineering concurrency — prematurely designing a distributed sharded system for a small crawl wastes time; start with async workers and per-host semaphores, then shard when throughput or memory demands justify it.

Connections

Interviewers often pivot to adjacent topics: designing a distributed task-queue with leasing semantics (visibility timeout, idempotent retries), or discussing content extraction/parsing performance and storage schema for crawled content. They may also shift into rate-limiting and backpressure strategies used broadly in distributed systems.

Further reading

• The Anatomy of a Large-Scale Hypertextual Web Search Engine (Brin & Page) — classic crawler/indexer architecture and tradeoffs.

• [Bloom Filters — Wikipedia / original references] — concise formulas and tradeoffs for probabilistic membership testing.

• Heritrix (Internet Archive crawler) docs — practical production crawler design and politeness implementation.