Design a Distributed Web Crawler

##### Question Design a distributed web crawler. Starting from one or more seed URLs, it fetches the pages it is permitted to fetch, stores a snapshot and metadata for every fetch, extracts links, and schedules newly discovered pages. The fetch tier runs on roughly **1,000 heterogeneous worker devices** with very different bandwidth, CPU, and reliability characteristics. Before choosing components, clarify the crawl scope (open web, or an approved host list such as an encyclopedia-style site), how current the stored copy must be, and the expected scale. Work through the following parts: 1. **URL identity and crawl scope** — how the system decides that two URLs are the same crawl target and whether a discovered link is eligible. 2. **Durable frontier, partitioning, and deduplication** — the frontier's states, its partitioning scheme, and atomic dedupe when many pages discover the same link. 3. **Coordination across 1,000 heterogeneous workers** — work assignment, leases, backpressure, and at-least-once vs. exactly-once fetch semantics. 4. **Fetch, parse, and store** — the path of one URL through the network, validation, snapshot storage, link extraction, and completion, plus the retry strategy. 5. **Storage schemas** — concrete data models for the frontier, fetched pages, page metadata, and the link graph. 6. **Recrawl, backpressure, and operations** — freshness policy, and the metrics, alerts, and procedures operators need. 7. **Capacity estimation** — throughput, bandwidth, and storage for the stated scale. 8. **Safety and legal controls** — politeness enforcement, kill switches, and avoiding overload or legal exposure. 9. **APIs and data models** — enqueueing work, checking status, and reading results. --- ### Part 1: Define URL identity and crawl scope Explain how the system decides whether two URLs represent the same crawl target and whether a discovered link is eligible. #### What This Part Should Cover - URL parsing and canonicalization rules for scheme, host, path, fragments, and query parameters. - Allowed hosts, protocols, content types, and redirect behavior. - Robots directives, crawl permissions, and per-host politeness requirements. - A stable URL identifier and where the canonicalization version is recorded. ```hint Preserve identity evidence Canonicalization that is too aggressive can merge distinct pages, while weak canonicalization can create an infinite duplicate frontier. ``` ### Part 2: Distribute the frontier and deduplicate work Design the durable frontier, its partitioning scheme, and the worker-claim protocol. #### What This Part Should Cover - Separate states for discovered, scheduled, leased, completed, and retryable URLs. - Partitioning that permits horizontal scale while respecting host-level rate limits. - Atomic deduplication when many pages discover the same link concurrently. - Priority rules for seeds, newly discovered pages, retries, and recrawls. - Host fairness: how the frontier avoids head-of-line blocking behind one slow host. ```hint Align ownership with throttling The partition key should make the politeness rule enforceable without forcing every worker through one global lock. ``` ### Part 3: Coordinate 1,000 heterogeneous workers Explain how work reaches a fleet of unequal, unreliable devices and what delivery guarantees the system actually offers. #### What This Part Should Cover - Work assignment: consistent hashing, queues, pull vs. push, and capability-weighted allocation for fast and slow devices. - Leases, acknowledgements, and recovery when a worker disappears mid-fetch. - Idempotency of every downstream write when a job is delivered more than once. - Backpressure from storage and parsing back into lease issuance. - Whether "exactly-once fetch" is achievable, and what you can guarantee instead. ```hint Say what is actually once Delivery and side effects are different problems. Be precise about which one you can make exactly-once. ``` ### Part 4: Fetch, parse, and store pages Trace a URL through network fetching, validation, snapshot storage, link extraction, and completion. #### What This Part Should Cover - Timeouts, redirects, status codes, size limits, and safe content-type handling. - Snapshot bytes, fetch metadata, content hashes, and conditional requests. - Link resolution against the final page URL, before normalization and deduplication. - Exact and near-duplicate content detection across different URLs. - Retry classification: which failures are transient, which are terminal, and what goes to a dead-letter queue. - Crawl traps, poison URLs, parser failures, and idempotent writes when a lease is retried. ```hint Separate evidence from workflow state Keep the immutable fetched artifact separate from mutable scheduling metadata so retries cannot silently rewrite history. ``` ### Part 5: Storage schemas Give concrete schemas for the state the crawler keeps. #### What This Part Should Cover - Frontier and scheduling state, including the queue key that produces the right pop order. - The fetched-page (snapshot) store and how objects are addressed. - Per-URL metadata with multiple fetch versions over time. - The link graph (outlinks, and optionally inlinks) and the robots cache. - Which store each item belongs in, and why. ### Part 6: Recrawl, backpressure, and operations Explain how the crawler keeps useful pages fresh without overwhelming a host or its own storage and parsing systems. #### What This Part Should Cover - Recrawl priority based on observed change rate, importance, and freshness targets. - Conditional requests and behavior for unchanged, removed, or redirected pages. - Backpressure across fetching, parsing, storage, and frontier insertion. - Metrics and alerts for frontier age, host throttling, fetch failures, duplicates, parser lag, and storage errors. - Procedures for changing canonicalization rules or rebuilding frontier state. ```hint Measure useful progress A growing frontier is not automatically success; compare discovery rate with sustainable downstream throughput and freshness goals. ``` ### Part 7: Estimate throughput, bandwidth, and storage State your assumptions and do the arithmetic for a fleet of about 1,000 workers. #### What This Part Should Cover - Pages per second as a function of concurrency and fetch latency. - Egress bandwidth, and whether it fits a plausible budget. - Daily and steady-state storage, raw and compressed. - Headroom for retries, bursts, and the link graph and index built on top. ### Part 8: Safety and legal controls Describe the controls that stop the crawler from harming a site or the company. #### What This Part Should Cover - Identifying user-agent with contact information, and honoring robots and site-specific limits. - Global and per-host hard ceilings on QPS, bandwidth, and concurrent connections. - Allowlists, blocklists, regional and data-residency restrictions, and takedown handling. - Kill switches at global, campaign, and per-domain scope. - Content the crawler must never touch: authenticated areas, checkout flows, forms. ### Part 9: APIs and data models Define the external surface for operating the crawler. #### What This Part Should Cover - Enqueueing a URL or a campaign, including priority, depth, and scheduling options. - Querying the status of a URL or the aggregate progress of a campaign. - Reading results: page metadata, snapshot pointers, and the outlink feed. - Inspecting and replaying the dead-letter queue. - Idempotent request semantics so a retried enqueue does not duplicate work. ### What a Strong Answer Covers A strong design gives URL identity, permissions, politeness, deduplication, and retry semantics first-class treatment. It has a durable recoverable frontier, idempotent workers, immutable snapshot evidence, bounded resource use, and an explicit recrawl policy. It puts scheduling and politeness on a shard that owns each host so rate limits are enforceable without a global lock, and it sizes the fleet with real arithmetic rather than adjectives. It also explains how operators detect crawler traps, lag, and unintended load on a host. ### Follow-up Questions - How would you prevent one large host from starving all other hosts? - What changes if pages require JavaScript rendering? - How would you migrate to a new canonicalization rule without losing provenance? - How would you prove that two workers cannot create two logical records for the same discovered URL? - Half your 1,000 devices are on residential links that disappear for hours at a time. What breaks, and what do you change? - Your crawl must finish a 1-billion-page pass in 30 days. Which of your numbers has to move?