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.

Preferred design: atomic claim + inFlight termination

Do not treat busy-wait-on-empty as the production solution. Two upgrades close the real hazards:

1. Atomic claim: ConcurrentHashMap.putIfAbsent(url, Boolean.TRUE) == null (or seen.add(url)) as a single op so claim and mark cannot split across locks.
2. inFlight counter: increment when a URL is accepted into the frontier; decrement when processing finishes. Exit only when queue.isEmpty() && inFlight == 0, waiting on a condition instead of spinning.

// Production-shaped Java sketch (preferred over busy-wait)
BlockingQueue<String> q = new LinkedBlockingQueue<>(10_000);
Set<String> seen = ConcurrentHashMap.newKeySet();
AtomicInteger inFlight = new AtomicInteger(0);

void seed(String u) {
  if (seen.add(u)) { inFlight.incrementAndGet(); q.offer(u); }
}

// worker body:
while (true) {
  String url = q.poll(100, TimeUnit.MILLISECONDS);
  if (url == null) {
    if (q.isEmpty() && inFlight.get() == 0) break;
    continue; // or condition.await until signal on inFlight-- / enqueue
  }
  try {
    for (String link : fetch(url)) {
      if (seen.add(link)) { // atomic claim
        inFlight.incrementAndGet();
        q.put(link);
      }
    }
  } finally {
    inFlight.decrementAndGet();
  }
}

Go's channel + WaitGroup (below) is the preferred dual: close(q) ends range only after true quiescence.

Legacy illustration: two independent locks + busy-wait (anti-pattern to study)

The historical Java version uses a plain LinkedList queue and a ConcurrentHashMap.newKeySet() for the visited set, each guarded by its own ReentrantLock. There are exactly three separate critical sections per loop iteration — useful as a race-window teaching artifact, not as the pattern to ship:

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. Prefer putIfAbsent instead.)
3. Push children — under queueLock only: for each link not already visited, add() to the queue. Release.

Termination by busy-wait on empty is incorrect/poor as a primary solution: it burns CPU, and without an in-flight counter an agent can exit while another is mid-fetch about to push children. Study the race in the trace below, then use the preferred design above.

import java.util.concurrent.ConcurrentHashMap;
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 = ConcurrentHashMap.newKeySet();

  // 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. Because visitedRecord is a ConcurrentHashMap-backed set, that read is thread-safe, but it is still a racy filter — it can let an already-visited or duplicate link slip into the queue. Section 2 re-checks and drops it on the next claim under visitedLock, 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

When NOT a single-process shared queue

The interview crawler is a concurrency teaching device. Real web-scale crawl design is dominated by other constraints:

• Per-domain politeness queues and rate limits (robots.txt, crawl-delay) — one global queue thrashes hosts.
• Persistent frontier (disk/DB) so a process crash does not lose the work queue.
• Retries / backoff / dead-letter for 429/5xx; at-least-once fetch with idempotent claim.
• Distributed workers via a message bus (Kafka/SQS) rather than one JVM heap queue.

Use the in-process pattern for job runners, scrapers of modest size, and interview solutions. At internet scale, the bottleneck is policy and storage, not ReentrantLock craft.

Drill ladder

• L1: Why is empty queue ≠ done?
• L2: What race does split claim/mark open? How does putIfAbsent close it?
• L3: State the exit predicate with inFlight.

Answers: L1 — workers may still be fetching and will enqueue children. L2 — two agents can both pass "not visited" before either marks; atomic add/putIfAbsent. L3 — empty && inFlight==0.

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). Prefer the inFlight / putIfAbsent design over busy-wait for production judgment.