Web Crawler Multithreaded
Web Crawler Multithreaded is a medium graphs problem solved with the bfs / dfs basics pattern.
The best approach, optimal (thread pool + concurrent seen set), runs in O(N · L / T) time and O(N) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (single-threaded bfs) up.
Problem
You are given a starting address startUrl and an HtmlParser object whose method getUrls(url) returns the links found on the page at url. Return every URL reachable from startUrl that has the same hostname as startUrl (including startUrl), in any order, crawling each URL only once.
The hostname is the text between http:// and the next / (or the end of the URL), so http://news.site.org/a has hostname news.site.org, which differs from site.org.
The twist: getUrls is a slow, blocking call, and a single-threaded crawl is too slow. Your solution must use multiple threads to fetch pages concurrently, while keeping shared state (which URLs were already claimed, when the crawl is finished) correct under concurrency.
Examples
Example 1
- Input
pages: http://shop.io -> [http://shop.io/cart, http://blog.shop.io], http://shop.io/cart -> [http://shop.io/help], http://shop.io/help -> [http://shop.io], startUrl = "http://shop.io"- Output
["http://shop.io", "http://shop.io/cart", "http://shop.io/help"]- Why
blog.shop.iois a different hostname and is skipped; the link from/helpback to the start page is not fetched again.
Example 2
- Input
pages: http://lab.dev/a -> [http://lab.dev/b, http://lab.dev/c], http://lab.dev/b -> [http://lab.dev/c], http://lab.dev/c -> [], startUrl = "http://lab.dev/a"- Output
["http://lab.dev/a", "http://lab.dev/b", "http://lab.dev/c"]- Why
/band/ccan be fetched at the same time by different threads, but/cmust still be fetched only once even though two pages link to it.
Constraints
1 <= number of pages <= 1000,0 <= number of links <= 5000- Every URL starts with
http://, has no port, and is at most300characters long. getUrlsis slow (it blocks for a while), so fetching pages one after another is too slow; it is safe to call from several threads at once.startUrlis one of the pages.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (single-threaded BFS) | O(N · L) | O(N) |
| Optimal (thread pool + concurrent seen set) | O(N · L / T) | O(N) |
1Brute force (single-threaded BFS)
O(N · L)N sequential fetches, each costing the fetch latency L (plus the work per link).O(N)The seen set and the queue.Ignore concurrency: run a normal BFS from startUrl, following only same-host links and marking URLs as seen when queued. It returns the right answer but calls getUrls one page at a time, so total time is the sum of all fetch delays.
- host = hostname of startUrl; seen = {startUrl}; queue = [startUrl].
- Pop a URL, call getUrls; for each new same-host link, add to seen and queue.
- Return seen when the queue is empty.
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String host = hostOf(startUrl);
Set<String> seen = new HashSet<>();
Deque<String> queue = new ArrayDeque<>();
seen.add(startUrl);
queue.add(startUrl);
while (!queue.isEmpty()) {
String url = queue.poll();
for (String next : htmlParser.getUrls(url)) {
if (hostOf(next).equals(host) && seen.add(next)) queue.add(next);
}
}
return new ArrayList<>(seen);
}
private String hostOf(String url) {
int end = url.indexOf('/', 7);
return end == -1 ? url.substring(7) : url.substring(7, end);
}
}class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
host = self.hostOf(startUrl)
seen = {startUrl}
queue = deque([startUrl])
while queue:
url = queue.popleft()
for nxt in htmlParser.getUrls(url):
if self.hostOf(nxt) == host and nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return list(seen)
def hostOf(self, url: str) -> str:
end = url.find('/', 7)
return url[7:] if end == -1 else url[7:end]class Solution {
public:
vector<string> crawl(string startUrl, HtmlParser htmlParser) {
string host = hostOf(startUrl);
unordered_set<string> seen{startUrl};
queue<string> q;
q.push(startUrl);
while (!q.empty()) {
string url = q.front();
q.pop();
for (const string& next : htmlParser.getUrls(url)) {
if (hostOf(next) == host && seen.insert(next).second) q.push(next);
}
}
return vector<string>(seen.begin(), seen.end());
}
private:
static string hostOf(const string& url) {
size_t end = url.find('/', 7);
return end == string::npos ? url.substr(7) : url.substr(7, end - 7);
}
};function crawl(startUrl, htmlParser) {
const host = hostOf(startUrl);
const seen = new Set([startUrl]);
const queue = [startUrl];
for (let head = 0; head < queue.length; head++) {
for (const next of htmlParser.getUrls(queue[head])) {
if (hostOf(next) === host && !seen.has(next)) {
seen.add(next);
queue.push(next);
}
}
}
return [...seen];
}
function hostOf(url) {
const end = url.indexOf('/', 7);
return end === -1 ? url.substring(7) : url.substring(7, end);
}2Optimal (thread pool + concurrent seen set)
O(N · L / T)With T worker threads, up to T fetches of latency L run at the same time (bounded by how wide the link graph is).O(N)The seen set plus queued tasks.Run the same graph walk, but hand every fetch to a thread pool so many slow getUrls calls overlap. A thread-safe set decides ownership: a URL is crawled only by the thread whose insert into the set succeeded. A counter of pending tasks tells the main thread when every fetch, including ones that spawned more work, has finished.
- seen = concurrent set containing startUrl; pending = 1; submit a task for startUrl.
- Task(url): for each link from getUrls(url), if same host and seen.add(link) succeeds, increment pending and submit Task(link). Finally decrement pending and wake the main thread when it reaches 0.
- Main thread waits until pending == 0, shuts the pool down and returns seen.
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String host = hostOf(startUrl);
Set<String> seen = ConcurrentHashMap.newKeySet();
ExecutorService pool = Executors.newFixedThreadPool(8);
AtomicInteger pending = new AtomicInteger(1);
Object done = new Object();
seen.add(startUrl);
submit(pool, startUrl, host, htmlParser, seen, pending, done);
synchronized (done) {
while (pending.get() > 0) {
try { done.wait(); } catch (InterruptedException e) { Thread.currentThread().interrupt(); break; }
}
}
pool.shutdown();
return new ArrayList<>(seen);
}
private void submit(ExecutorService pool, String url, String host, HtmlParser parser,
Set<String> seen, AtomicInteger pending, Object done) {
pool.execute(() -> {
try {
for (String next : parser.getUrls(url)) {
if (hostOf(next).equals(host) && seen.add(next)) {
pending.incrementAndGet();
submit(pool, next, host, parser, seen, pending, done);
}
}
} finally {
if (pending.decrementAndGet() == 0) {
synchronized (done) { done.notifyAll(); }
}
}
});
}
private String hostOf(String url) {
int end = url.indexOf('/', 7);
return end == -1 ? url.substring(7) : url.substring(7, end);
}
}import threading
from concurrent.futures import ThreadPoolExecutor
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
host = self.hostOf(startUrl)
seen = {startUrl}
lock = threading.Lock()
done = threading.Condition(lock)
pending = [1]
pool = ThreadPoolExecutor(max_workers=8)
def task(url: str) -> None:
try:
for nxt in htmlParser.getUrls(url):
if self.hostOf(nxt) != host:
continue
with lock:
if nxt in seen:
continue
seen.add(nxt)
pending[0] += 1
pool.submit(task, nxt)
finally:
with lock:
pending[0] -= 1
if pending[0] == 0:
done.notify_all()
pool.submit(task, startUrl)
with lock:
while pending[0] > 0:
done.wait()
pool.shutdown()
return list(seen)
def hostOf(self, url: str) -> str:
end = url.find('/', 7)
return url[7:] if end == -1 else url[7:end]class Solution {
public:
vector<string> crawl(string startUrl, HtmlParser htmlParser) {
host = hostOf(startUrl);
parser = &htmlParser;
seen.insert(startUrl);
pending = 1;
work.push(startUrl);
vector<thread> workers;
for (int t = 0; t < 8; t++) workers.emplace_back([this] { run(); });
for (auto& w : workers) w.join();
return vector<string>(seen.begin(), seen.end());
}
private:
string host;
HtmlParser* parser = nullptr;
unordered_set<string> seen;
queue<string> work;
int pending = 0;
mutex mu;
condition_variable cv;
void run() {
while (true) {
string url;
{
unique_lock<mutex> lock(mu);
cv.wait(lock, [this] { return !work.empty() || pending == 0; });
if (work.empty()) return; // pending == 0: everything is done
url = work.front();
work.pop();
}
vector<string> links = parser->getUrls(url); // slow call, no lock held
{
lock_guard<mutex> lock(mu);
for (const string& next : links) {
if (hostOf(next) == host && seen.insert(next).second) {
pending++;
work.push(next);
}
}
pending--;
}
cv.notify_all();
}
}
static string hostOf(const string& url) {
size_t end = url.find('/', 7);
return end == string::npos ? url.substr(7) : url.substr(7, end - 7);
}
};// JavaScript has no shared-memory threads here: the same pool idea is expressed
// with async workers on the event loop, assuming getUrls returns a Promise.
async function crawl(startUrl, htmlParser) {
const host = hostOf(startUrl);
const seen = new Set([startUrl]);
const work = [startUrl];
let active = 0;
async function worker() {
while (work.length > 0 || active > 0) {
if (work.length === 0) {
await new Promise((r) => setTimeout(r, 0));
continue;
}
const url = work.pop();
active++;
const links = await htmlParser.getUrls(url);
for (const next of links) {
if (hostOf(next) === host && !seen.has(next)) {
seen.add(next);
work.push(next);
}
}
active--;
}
}
await Promise.all(Array.from({ length: 8 }, () => worker()));
return [...seen];
}
function hostOf(url) {
const end = url.indexOf('/', 7);
return end === -1 ? url.substring(7) : url.substring(7, end);
}Edge cases to test
- Two threads discover the same new URL at the same moment (it must be claimed exactly once)
- Cycles of links back to pages already crawled
- Hostnames that only share a suffix or prefix (
shop.iovsblog.shop.io) - Knowing when to stop: the queue can be empty while other threads are still fetching and about to add more work
Hints
Hint 1
Start from the single-threaded BFS. Which part is slow, and which parts touch shared state?
Hint 2
Only the getUrls calls need to run in parallel. Claim a URL by inserting it into a thread-safe set; whoever succeeds is the only one who fetches it.
Hint 3
Submit each claimed URL as a task to a thread pool and track how many tasks are still running; the crawl is finished when that count reaches zero.
FAQ
What is the best time complexity for Web Crawler Multithreaded?
Optimal (thread pool + concurrent seen set) runs in O(N · L / T) time and O(N) extra space. With T worker threads, up to T fetches of latency L run at the same time (bounded by how wide the link graph is).
Which pattern does Web Crawler Multithreaded use?
It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: BFS - Normal + Level by Level, DFS - Recursive + Iterative, Clone Graph.
Is there a brute force solution for Web Crawler Multithreaded?
Yes. Brute force (single-threaded BFS) takes O(N · L) time and O(N) space. Ignore concurrency: run a normal BFS from startUrl, following only same-host links and marking URLs as seen when queued.
Which edge cases should I test for Web Crawler Multithreaded?
Two threads discover the same new URL at the same moment (it must be claimed exactly once); Cycles of links back to pages already crawled; Hostnames that only share a suffix or prefix (shop.io vs blog.shop.io); Knowing when to stop: the queue can be empty while other threads are still fetching and about to add more work.