Web Crawler Multithreaded
Core idea: Run a breadth-first graph traversal where every edge is a slow network call, fan the work out across many threads to hide that latency, and protect just two things — an atomic visited check and a correct we're done signal.
The problem, rephrased
You run a tiny in-house wiki at http://wiki.acme.io. Every page lists the URLs it links to, but the only way to read those links is to call fetch(page) — a function that makes a real HTTP request and takes ~15 ms to come back. Some links point at other Acme wiki pages; some point off to http://blog.acme.com or out to the public internet.
You want a list of every Acme wiki page reachable from the homepage, where "Acme wiki" means the exact same hostname as the page you started on. You must not fetch the same page twice (pages link to each other in cycles), and you only have one tool: fetch(url).
The catch: if you fetch pages one at a time, you spend 15 ms blocked on the network for each page and the wall clock crawls. The whole point is to have many fetches in flight at once.
A page graph is given as an edge list — page -> [links it contains]. You're handed only the startUrl; the graph is hidden behind fetch().
startUrl |
edges (page → links) | hostname rule | Expected crawled set |
|---|---|---|---|
http://a.com/home |
a.com/home → [a.com/x, b.com/y], a.com/x → [a.com/home] |
same host = a.com |
{a.com/home, a.com/x} |
http://a.com/p |
a.com/p → [] |
— | {a.com/p} |
http://b.com/start |
b.com/start → [a.com/1, a.com/2] |
same host = b.com |
{b.com/start} |
Note in the first row that b.com/y is reachable but excluded (different host), and a.com/x links back to home (a cycle) — we must not loop forever.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson