Web Crawler Multithreaded

Medium Graphs BFS / DFS Basics Original on LeetCode

Reported atSnowflakeRubrik

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.io is a different hostname and is skipped; the link from /help back 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
/b and /c can be fetched at the same time by different threads, but /c must 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 most 300 characters long.
  • getUrls is 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.
  • startUrl is 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.

ApproachTimeSpace
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)

TimeO(N · L)N sequential fetches, each costing the fetch latency L (plus the work per link).
SpaceO(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.

  1. host = hostname of startUrl; seen = {startUrl}; queue = [startUrl].
  2. Pop a URL, call getUrls; for each new same-host link, add to seen and queue.
  3. 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);
    }
}

2Optimal (thread pool + concurrent seen set)

TimeO(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).
SpaceO(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.

  1. seen = concurrent set containing startUrl; pending = 1; submit a task for startUrl.
  2. 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.
  3. 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);
    }
}

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.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

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.