Golang Tour Web Crawler Exercise

Question

In the last few days I've played around with Go a little and took the language tour. The last exercise (text here) requires you to crawl a graph that simulates a set of Web pages with links, using goroutines, channels and locking primitives to do it in a concurrent fashion without ever going to the same page twice. I added a random latency to the fetch procedure to simulate the time to actually fetch a page.

My solution involves a timeout, which I'm not very fond of. In a real Web crawler I could expect some action to be taken when a timeout is hit, but in this very limited case perhaps I can use some more robust solution. Any idea? I tried using a counter to keep track of enqueued items and then closing the results channel when there were no more items to explore but the goroutine fetching the page which feeds the results channel has no awareness of other page fetching going on, so I ended up closing the channel to early (now that I'm writing this down I realize perhaps I can use some sort of "control" channel to sync the goroutines in some way).

This is my solution (available in the Go Playground here — I've written code from the Fetch struct to the Crawl function, the rest was already provided by the exercise):

package main

import (
    "fmt"
    "sync"
    "time"
    "math/rand"
)

type Fetcher interface {
    Fetch(url string) (body string, urls []string, err error)
}

type Links struct {
    urls  []string
    depth int
}

type ConcurrentStringSet struct {
    set map[string]bool
    mux     sync.Mutex
}

func (cache *ConcurrentStringSet) onMissDoAsync(s string, f func()) {
    cache.mux.Lock()
    defer cache.mux.Unlock()
    if !cache.set[s] {
        cache.set[s] = true
        go f()
    }
}

func NewAsyncCrawler(fetcher Fetcher, timeout time.Duration) (crawl func(string, int)) {
    links := make(chan Links)
    cache := ConcurrentStringSet{set:make(map[string]bool)}
    crawl = func(url string, depth int) {
        cache.onMissDoAsync(url, func() {
            body, urls, err := fetcher.Fetch(url)
            if err != nil {
                fmt.Println(err)
            } else {
                fmt.Printf("found: %s %q\n", url, body)
                if depth > 1 {
                    links <- Links{urls, depth - 1}
                }
            }
        })
        for {
            select {
            case link := <-links:
                for _, url := range link.urls {
                    go crawl(url, link.depth)
                }
            case <-time.After(timeout):
                return
            }
        }
    }
    return
}

func Crawl(url string, depth int, fetcher Fetcher) {
    if (depth > 0) {
        crawl := NewAsyncCrawler(fetcher, 500 * time.Millisecond)
        crawl(url, depth)
    }
}

func main() {
    Crawl("http://golang.org/", 4, fetcher)
}

type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
    rand.Seed(time.Now().UnixNano())
    time.Sleep(time.Duration(rand.Intn(500)) * time.Millisecond)
    if res, ok := f[url]; ok {
        return res.body, res.urls, nil
    }
    return "", nil, fmt.Errorf("not found: %s", url)
}

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/",
        },
    },
}

Answer 1

Hello there again my dear myself from 7 years ago. Your solution was nice, but probably a bit overcomplicated. You will probably be happy to know you have been able to come back to it a few years later in the process of re-learning Go and came up with something simpler. It keeps track of outstanding goroutines using sync.WaitGroup. I know in a sense it feels a bit like cheating, since sync.WaitGroup is not covered by the tour, but it looks like a simple, clean and idiomatic solution, so why not?

package main

import (
    "fmt"
    "sync"
)

type Visited struct {
    m sync.Mutex
    s map[string]bool
}

func New() Visited {
    return Visited{s:make(map[string]bool)}
}

func (v *Visited) Add(key string) {
    v.m.Lock()
    v.s[key] = true
    v.m.Unlock()
}

func (v *Visited) Has(key string) bool {
    v.m.Lock()
    defer v.m.Unlock()
    return v.s[key]
}

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

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher, visited *Visited, wg *sync.WaitGroup) {
    defer wg.Done()
    if visited.Has(url) || depth <= 0 {
        return
    }
    visited.Add(url)
    body, urls, err := fetcher.Fetch(url)
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("found: %s %q\n", url, body)
    for _, u := range urls {
        wg.Add(1)
        go Crawl(u, depth-1, fetcher, visited, wg)
    }
    return
}

func main() {
    var wg sync.WaitGroup
    visited := New()
    wg.Add(1)
    go Crawl("https://golang.org/", 4, fetcher, &visited, &wg)
    wg.Wait()
}

// 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{
    "https://golang.org/": &fakeResult{
        "The Go Programming Language",
        []string{
            "https://golang.org/pkg/",
            "https://golang.org/cmd/",
        },
    },
    "https://golang.org/pkg/": &fakeResult{
        "Packages",
        []string{
            "https://golang.org/",
            "https://golang.org/cmd/",
            "https://golang.org/pkg/fmt/",
            "https://golang.org/pkg/os/",
        },
    },
    "https://golang.org/pkg/fmt/": &fakeResult{
        "Package fmt",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
    "https://golang.org/pkg/os/": &fakeResult{
        "Package os",
        []string{
            "https://golang.org/",
            "https://golang.org/pkg/",
        },
    },
}

Now onto more interesting stuff!