Same-Hostname Web Crawler: Single-Threaded, Then Multithreaded

Implement a web crawler. You are given a start URL and an HTML parser that fetches a page and returns the links on it. Starting from the start URL, find every URL that can be reached by following links and whose hostname is exactly the start URL's hostname. Write a single-threaded version first; after discussing it, make the crawler multithreaded. ```python class HtmlParser: def get_urls(self, url: str) -> list[str]: """Fetch the page at url and return the URLs it links to (blocking network I/O).""" def crawl(start_url: str, html_parser: HtmlParser) -> list[str]: ... ``` ### Rules - Before comparing or recording any URL, including the start URL, remove its fragment: everything from the first `#` onward. `http://news.example.com/world#top` and `http://news.example.com/world` are the same page. - A URL is in scope only when its hostname is exactly the start URL's hostname. For a crawl that starts on `news.example.com`, both `http://blog.example.com/` and `http://example.com/` are out of scope. - Only in-scope pages are fetched. A link that appears only on out-of-scope pages is never discovered. - Links can form cycles, and one page can be linked from many others. No page may be fetched more than once. - Return every in-scope URL that was reached, once each and without its fragment, in any order. The start URL is part of the result. ### Example ```text Pages and the links on them (illustrative): http://news.example.com/ -> http://news.example.com/world#top http://blog.example.com/ http://news.example.com/sports http://news.example.com/world -> http://news.example.com/ http://news.example.com/sports#scores http://news.example.com/sports -> http://news.example.com/world http://blog.example.com/ -> http://news.example.com/tech start_url = "http://news.example.com/" Result (any order): http://news.example.com/ http://news.example.com/world http://news.example.com/sports ``` `/world#top` and `/sports#scores` collapse onto pages already found, the links among `/`, `/world` and `/sports` form cycles, and `http://news.example.com/tech` is absent because it is linked only from the out-of-scope blog page. ### Constraints and Clarifications - Assumed for this write-up: every URL is absolute and starts with `http://`, and the hostname is the text between `http://` and the next `/` (or the end of the URL). The report does not say how ports, letter case or other schemes are treated. - `get_urls` dominates the running time: it waits on the network, while the work done on each returned link is small. ### Clarifying Questions - Can URLs carry ports, uppercase hostnames or `https`, and if so, is `http://news.example.com:8080/` or `http://NEWS.example.com/` on the same hostname? - Is the query string part of a page's identity, so that `/search?q=a` and `/search?q=b` are different pages? - Can `get_urls` raise an error or hang, and what should the crawler return for a page that fails? - How many threads may the multithreaded version use, and is there a limit on concurrent requests to the site? ### Part 1 — Single-threaded crawler Implement `crawl` with no concurrency, applying every rule above. ```hint Normalize before you compare Pick the one place where a raw link becomes the key you deduplicate and filter on, and make sure the start URL goes through the same step. ``` #### What This Part Should Cover - A traversal of the link graph that fetches each in-scope page exactly once despite cycles - Fragment removal and exact hostname comparison applied consistently, including to the start URL - The cost in parser calls and in link processing ### Part 2 — Multithreaded crawler Each `get_urls` call mostly waits on the network, so fetch several pages at once using multiple threads. The result must match Part 1's, no page may be fetched twice, and `crawl` must return as soon as the crawl is complete: neither early nor never. ```hint Two threads, one new link Picture two threads finding the same new link at the same moment. Work out which steps must happen as one indivisible action so that only one of them fetches it. ``` ```hint When is the crawl over? An empty work queue can be a passing state while another thread is still parsing a page. Decide what else you must track to know that no more links can ever arrive. ``` #### What This Part Should Cover - Shared state that is safe under concurrent access, and what is (and is not) done while holding a lock - A completion condition that neither exits early nor deadlocks, and a clean shutdown of the worker threads - Why threads pay off for this workload, and what happens when a page fetch fails ### What a Strong Answer Covers - Clarifies URL identity (fragment, query string, case, ports) and the hostname rule before coding - A correct single-threaded traversal that the multithreaded version visibly builds on - Atomic deduplication so that no page is fetched twice, with the network call kept outside any lock - A completion condition based on outstanding work, not on a momentarily empty queue - Error handling that cannot leave the crawler hanging, and tests that exercise cycles, fragments and out-of-scope links ### Follow-up Questions - One page's fetch raises an exception and another never returns. How does your multithreaded crawler behave in each case, and what would you change? - How would you choose the number of threads, and how would you cap the request rate if the site starts rejecting requests? - The site is too large for one machine. How would you split the crawl across machines while still fetching each page only once? - How would you test the multithreaded version so that a race or a premature exit shows up reliably rather than once in a hundred runs?