Concurrently crawl URLs (the Tour of Go web crawler) with depth limits, deduplication and bounded parallelism.
Question 525HardGo 1.22 to 1.25
There are three concerns:
- Dedup: a mutex-guarded
seenmap. You must check and mark it in one critical section, before fetching. Otherwise two goroutines both see "not seen" and fetch the same URL. - Bounded parallelism: a buffered-channel semaphore held only around
Fetch. - Completion: a
WaitGroupwhereAddis called before eachgo.
type Fetcher interface {
Fetch(ctx context.Context, url string) (body string, urls []string, err error)
}
func Crawl(ctx context.Context, root string, depth, parallel int, f Fetcher) map[string]error {
var (
mu sync.Mutex
seen = make(map[string]error)
wg sync.WaitGroup
sem = make(chan struct{}, parallel)
)
var visit func(url string, depth int)
visit = func(url string, depth int) {
defer wg.Done()
if depth <= 0 {
return
}
mu.Lock()
if _, ok := seen[url]; ok {
mu.Unlock()
return
}
seen[url] = nil // claim before fetching
mu.Unlock()
select {
case sem <- struct{}{}:
case <-ctx.Done():
mu.Lock()
seen[url] = ctx.Err()
mu.Unlock()
return
}
_, urls, err := f.Fetch(ctx, url)
<-sem // release BEFORE spawning children
mu.Lock()
seen[url] = err
mu.Unlock()
if err != nil {
return
}
for _, u := range urls {
wg.Add(1)
go visit(u, depth-1)
}
}
wg.Add(1)
go visit(root, depth)
wg.Wait()
return seen
}
Gotchas:
- If a goroutine held the semaphore while waiting on its children, the crawl would deadlock once the depth exceeds
parallel. wg.Addinside the child goroutine is a race, becauseWaitmight see zero first.- The semaphore bounds fetches, not goroutines. A page with 10k links creates 10k parked goroutines, which is cheap (a few KB each) but unbounded.
For strict bounds, use a fixed worker pool that reads from a frontier queue and counts outstanding work, so it can close the queue when the count reaches zero. Another option is errgroup.SetLimit, but its Go blocks when the limit is full. Calling it from inside a worker can deadlock, so use TryGo or a separate dispatcher.
More on Classic Concurrency Coding Problems
- Q523Implement a Future/Promise type in Go with Get(ctx) and error propagation using generics.
- Q524Implement a concurrent prime sieve with a daisy chain of goroutines. How many goroutines does it create, and how do you stop it without leaks?
- Q526Count word frequencies in a large set of files concurrently and return the top K words. How do you merge per-worker maps efficiently?
- Q527Implement a debouncer and a throttler for a stream of events using time.Timer and channels.
- Q528Implement a sharded concurrent map (N shards with separate mutexes). When does it beat sync.Map and a single RWMutex?
- Q529Implement a readers-writer lock that prefers writers using only channels or sync.Mutex. Why is it hard to get right?