A Tour of Go 69
Exercise: Web Crawler
In this exercise you'll use Go's concurrency features to parallelize a web crawler.
Modify the Crawl function to fetch URLs in parallel without fetching the same URL twice.
Example
package main import ( "fmt" ) type Fetcher interface { // Fetch returns the body of URL and // a slice of URLs found on that page. Fetch(url string) (body string, urls []string, err error) } func crawlConcurr(url string, depth int, fetcher Fetcher, ch chan func()([]string,int), quit chan int) { if depth <= 0 { quit <- 0 return } body, urls, err := fetcher.Fetch(url) if err != nil { fmt.Println(err) quit <- 0 return } else { fmt.Printf("found: %s %q\n", url, body) f := func()([]string,int) { return urls, depth } ch <- f } } var history = make(map[string]bool) // Crawl uses fetcher to recursively crawl // pages starting with url, to a maximum of depth. func Crawl(url string, depth int, fetcher Fetcher) { // TODO: Fetch URLs in parallel. // TODO: Don't fetch the same URL twice. // This implementation doesn't do either: history[url] = true ch := make(chan func()([]string,int)) quit := make(chan int) routinsNum := 1 go crawlConcurr(url, depth, fetcher, ch, quit) for routinsNum > 0 { select { case f := <- ch: routinsNum -- us, d := f() for _, u := range us { if history[u] != true { history[u] = true; routinsNum ++ go crawlConcurr(u, d - 1, fetcher, ch, quit) } } case <- quit: routinsNum -- } } } func main() { Crawl("http://golang.org/", 4, fetcher) } // fakeFetcher is Fetcher that returns canned results. type fakeFetcher map[string]*fakeResult type fakeResult struct { body string urls []string } func (f *fakeFetcher) Fetch(url string) (string, []string, error) { if res, ok := (*f)[url]; ok { return res.body, res.urls, nil } return "", nil, fmt.Errorf("not found: %s", url) } // fetcher is a populated fakeFetcher. var fetcher = &fakeFetcher{ "http://golang.org/": &fakeResult{ "The Go Programming Language", []string{ "http://golang.org/pkg/", "http://golang.org/cmd/", }, }, "http://golang.org/pkg/": &fakeResult{ "Packages", []string{ "http://golang.org/", "http://golang.org/cmd/", "http://golang.org/pkg/fmt/", "http://golang.org/pkg/os/", }, }, "http://golang.org/pkg/fmt/": &fakeResult{ "Package fmt", []string{ "http://golang.org/", "http://golang.org/pkg/", }, }, "http://golang.org/pkg/os/": &fakeResult{ "Package os", []string{ "http://golang.org/", "http://golang.org/pkg/", }, }, }