# Design a Distributed Web Crawler ## Scenario Design a distributed crawler for an encyclopedia-style site. Starting from seed URLs, it should fetch allowed pages, store page snapshots and metadata, extract links, and schedule newly discovered pages. Clarify whether crawling is limited to approved hosts, how current the stored copy must be, and the expected scale before selecting components. ### 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 canonicalization versions are 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, partitioning scheme, and 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. - Leases, acknowledgements, idempotency, and recovery when a worker disappears. - Priority rules for seeds, new pages, retries, and recrawls. ```hint Align ownership with throttling The partition key should make the politeness rule enforceable without forcing every worker through one global lock. ``` ### Part 3: 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 page URL before normalization and deduplication. - Duplicate content, parser failures, crawl traps, and poison URLs. - 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 4: 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. ``` ### 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 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?