3
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.