Problem 16 Scenario Multithreaded Web Crawler

The scenario

A web crawler walks the web: starting from a seed URL, it fetches a page, extracts the links on it, and repeats for every link it has not already seen. Going multithreaded is the obvious win — network fetches dominate the cost, and many can run in parallel. But the moment several crawler agents share a to-visit queue and a visited set, two hazards appear:

• Duplicate work / races. Two agents must never pop the same URL, and must never both decide a fresh URL is "unvisited" and process it twice.
• Termination. An empty queue does not mean the crawl is done — an agent may be mid-fetch and about to push three new links. Shutting down on a momentarily-empty queue truncates the crawl.

The first hazard is solved with mutual exclusion over the shared state. The second is the subtle one, and it is where the Java (lock + queue) and Go (channel + WaitGroup) solutions diverge in mechanism while sharing the same invariant.

The shared state and the invariant

• toVisitList — URLs discovered but not yet claimed.
• visitedRecord — URLs already claimed by some agent (the claim happens before processing, so it doubles as a "do not touch" marker).
• Invariant: each distinct URL is processed exactly once, and the program exits only after the transitive closure of reachable URLs has been processed — not merely when the queue is briefly empty.

Java: two independent locks, one busy-wait loop

The Java version uses a plain LinkedList queue and a HashSet, each guarded by its own ReentrantLock. There are exactly three separate critical sections per loop iteration, and it is worth being precise about them because the lock granularity is what the trace below must reflect:

1. Claim a URL — under queueLock only: check empty, then poll(). Release.
2. Mark visited — under visitedLock only: if already in visitedRecord continue; else add(). Release. (Note: claim and mark are not one atomic step — a URL can be polled, then found already-visited, and dropped.)
3. Push children — under queueLock only: for each link not already visited, add() to the queue. Release.

Termination here is by busy-wait: every agent loops while(true), and an agent breaks only when it acquires queueLock and finds the queue empty. Because each agent runs until it personally sees an empty queue, an agent that is mid-sleep keeps the others alive implicitly — they keep looping and re-checking rather than exiting. This is correct but wasteful (spinning agents repeatedly lock/unlock an empty queue), and it relies on the children being pushed before the pushing agent's next empty-check.

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Solution {

  private static final int NUM_AGENTS = 5;
  private final Queue<String> toVisitList = new LinkedList<>();
  private final Set<String> visitedRecord = new HashSet<>();

  // Each shared structure has its OWN lock — three separate critical sections.
  private final Lock queueLock = new ReentrantLock();
  private final Lock visitedLock = new ReentrantLock();

  public static void main(String[] args) {
    new Solution().startCrawling("http://example.com");
  }

  public void startCrawling(String initialUrl) {
    toVisitList.add(initialUrl);
    Thread[] agents = new Thread[NUM_AGENTS];
    for (int i = 0; i < NUM_AGENTS; i++) {
      agents[i] = new Thread(this::crawlerAgent);
      agents[i].start();
    }
    for (Thread agent : agents) {
      try { agent.join(); } catch (InterruptedException e) { e.printStackTrace(); }
    }
    System.out.println("Crawling finished.");
  }

  public void crawlerAgent() {
    while (true) {
      String url;

      // CRITICAL SECTION 1 — queueLock only: claim a URL (or exit).
      queueLock.lock();
      try {
        if (toVisitList.isEmpty()) break;   // sole termination condition
        url = toVisitList.poll();
      } finally {
        queueLock.unlock();
      }

      // CRITICAL SECTION 2 — visitedLock only: mark visited (or skip).
      visitedLock.lock();
      try {
        if (visitedRecord.contains(url)) continue;
        visitedRecord.add(url);
      } finally {
        visitedLock.unlock();
      }

      // No lock held while doing the slow work.
      System.out.println("Processing: " + url);
      try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); }
      String[] links = getLinksFromPage(url);

      // CRITICAL SECTION 3 — queueLock only: push unvisited children.
      queueLock.lock();
      try {
        for (String link : links) {
          if (!visitedRecord.contains(link)) {
            toVisitList.add(link);
          }
        }
      } finally {
        queueLock.unlock();
      }
    }
  }

  public String[] getLinksFromPage(String url) {
    return new String[] { "link1", "link2", "link3" };
  }
}

One honest caveat on this code: in critical section 3 it reads visitedRecord while holding only queueLock, not visitedLock. That is a benign-but-imprecise filter — it can let an already-visited or duplicate link slip into the queue, but section 2 re-checks and drops it on the next claim, so the exactly-once invariant still holds. The duplicate just costs one wasted poll.

Worked trace (true lock granularity)

Two agents, A and B, seed = S. The table keeps each lock acquisition on its own row, so you can see exactly where each lock is taken and released — the three critical sections never collapse into one atomic step.

Step 4 exposes the real risk of the busy-wait design: B exits while work is still pending because it observed a momentarily-empty queue between A's claim (step 1) and A's push (step 5). The crawl is still correct only because the remaining agents (here, A) keep looping and drain L1..L3 themselves; the surviving agents carry the work. With all 5 agents idle at the same instant on a truly-empty queue, every one breaks and the crawl genuinely ends. The lesson the trace teaches: "queue empty right now" is a weak termination signal, and correctness leans on at least one agent still being in its loop. The Go version replaces this implicit reasoning with an explicit count.

Go: count the URLs, not the goroutines

Go would tempt you to spin one goroutine per URL and wg.Add(1) per goroutine. With a fixed worker pool reading from a channel, that does not work — the goroutines are long-lived, so counting them tells you nothing about whether work remains. The fix is to make the WaitGroup count in-flight URLs, with three rules that together guarantee the counter only reaches zero at true quiescence:

1. Add before the send. Every toVisit <- url — the seed and every child — is preceded by pending.Add(1). The increment happens-before the URL becomes visible to a worker, so the count can never drop to zero while a URL is sitting in the channel or about to be sent.
2. Done after the children are enqueued. A worker calls pending.Done() (via defer) only after it has finished pushing this URL's children. Because each child did its own Add before this URL's Done, the counter never momentarily dips to zero between a parent finishing and its children being counted.
3. A separate goroutine closes the channel. pending.Wait() blocks until in-flight count hits zero — the genuine end of the crawl — and only then close(toVisit). The close is what makes every worker's for range loop terminate. A second WaitGroup over the workers lets main join them.

This is the direct answer to the central claim: you cannot close() the channel the moment it momentarily drains. A drained channel is the Go equivalent of Java's "empty queue right now" — a worker may be mid-sleep, about to Add three children. Closing then would panic any in-flight send on a closed channel and truncate the crawl. The WaitGroup-over-URLs replaces the implicit "some agent is still looping" reasoning of the Java version with an explicit, checkable count of outstanding work.

package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	var (
		mu      sync.Mutex          // guards visited
		visited = map[string]bool{} // URLs already claimed
		pending sync.WaitGroup      // counts URLs IN FLIGHT, not goroutines
		workers sync.WaitGroup      // counts the worker goroutines
	)

	// Buffered so the seeding send never blocks the main goroutine.
	toVisit := make(chan string, 10000)

	getLinks := func(url string) []string {
		return []string{"link1", "link2", "link3"}
	}

	process := func(url string) {
		defer pending.Done() // RULE 2: exactly one Done per Add, after children enqueued

		// Claim the URL under the mutex (Go's equivalent of Java CS2).
		mu.Lock()
		if visited[url] {
			mu.Unlock()
			return
		}
		visited[url] = true
		mu.Unlock()

		fmt.Println("Processing:", url)
		time.Sleep(1 * time.Second) // simulate fetch; no lock held

		for _, link := range getLinks(url) {
			mu.Lock()
			seen := visited[link]
			mu.Unlock()
			if seen {
				continue
			}
			pending.Add(1) // RULE 1: Add BEFORE the send
			toVisit <- link
		}
	}

	const numWorkers = 5 // fixed pool, mirroring the 5 Java agents
	for i := 0; i < numWorkers; i++ {
		workers.Add(1)
		go func() {
			defer workers.Done()
			for url := range toVisit { // ends only when toVisit is closed
				process(url)
			}
		}()
	}

	pending.Add(1) // RULE 1 applies to the seed too
	toVisit <- "http://example.com"

	// RULE 3: a SEPARATE goroutine waits for true quiescence, then closes.
	// Closing the channel the instant it drains would be the same early-exit bug.
	go func() {
		pending.Wait()  // unblocks only when no URL is in flight
		close(toVisit)  // the close is what ends the worker range loops
	}()

	workers.Wait() // returns after every worker's range loop has exited
	fmt.Println("Crawling finished.")
}

Verification

The Go program above was compiled and run under the race detector (go vet clean, go run -race). With getLinks returning link1/link2/link3 for every page, the reachable set is exactly {seed, link1, link2, link3}, so each must be processed exactly once and the program must terminate.

$ go vet ./...        # no findings
$ go run -race main.go
Processing: http://example.com
Processing: link1
Processing: link2
Processing: link3
Crawling finished.
# (ordering of the three links varies run to run; counts do not)

Repeated under -race five times: every run exits cleanly (status 0), reports no data race, processes each of the four distinct URLs exactly once, and prints Crawling finished. exactly once. This is the executable counterpart to the Java join()-based shutdown: it confirms the WaitGroup-of-URLs reaches zero only at true quiescence, so the channel close — and therefore termination — happens after the full reachable set is processed, never on a momentary drain.

Side-by-side

Source & verification

Java reference implementation adapted from the original lesson "Problem 16 Scenario Multithreaded Web Crawler" (Concurrency › Concurrency Problems) in this guide. Go implementation authored for this rewrite and verified locally with Go 1.25.5 (darwin/arm64): go vet reports no findings, and go run -race main.go across repeated runs shows no data race, each reachable URL processed exactly once, and clean termination. The "count in-flight URLs, not goroutines" and "separate goroutine closes the channel after WaitGroup.Wait()" patterns follow the standard Go concurrency idiom for fan-out work whose size is discovered dynamically (cf. the Go Blog, "Go Concurrency Patterns: Pipelines and cancellation", and the sync.WaitGroup documentation).