Web Crawler Exercise

[Kevin Simonson]

I just completed the Web Crawler exercise (at "127.0.0.1:3999/concurrency/10") and therefore the whole Go Tour. But I'm just kind of wondering. The exercise was to create a web crawler that explored every URL on a page, and for each such URL every URL on the page that URL referred to, and so on and on forever recursively. (Well, not quite forever; there was a depth limit built into it.) My code that accomplished it was:

package main

import (
	"fmt"
	"sync"
	"time"
)

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

type SafeMap struct {
    mp  map[string]int
	mux sync.Mutex
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl ( sm SafeMap, url string, depth int, fetcher Fetcher) {
    sm.mux.Lock()
    sm.mp[url]++
	if 1 < sm.mp[url] {
	    sm.mux.Unlock()
        return
    }
	sm.mux.Unlock()
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
	if depth <= 0 {
		return
	}
	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 {
		go Crawl(sm, u, depth-1, fetcher)
	}
	return
}

func main() {
	Crawl( SafeMap{mp: make(map[string]int)}, "http://golang.org/", 4, fetcher)
	time.Sleep( time.Second)
}

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

But note that in order to get it to work I had to put in a call to "time.Sleep( time.Second)" in my main function. Without that line in, the main function would end up returning, and terminating the program, before very many calls to "Crawl()" had gotten executed. Is there some way in Go to tell the main function to wait and stay alive until all currently executing lightweight threads have completed executing?

I was thinking one way I could implement that would be to add an integer "Count" field to my "SafeMap" struct, increment it before each call to "go Crawl(sm, u, depth-1, fetcher)", and only decrement it at the end of the "Crawl()" function, and then have my main function loop on that "Count" variable until it was zero again. That seems kind of drastic though. Anybody have any better ideas?

[Junilu Lacar]

Kevin, the code tag doesn't currently recognize "go" as a language that it can prettify so don't set that attribute for now. I'll see what I can do to add "go" as a language that the code tags recognize.

[Junilu Lacar]

I don't think you should be changing the function signature(s) to include your SafeMap as a parameter. Since goroutines run in the same address space, the SafeMap would be shared by functions in your program. It's the methods in your SafeMap that would use mutex.Lock() and mutex.Unlock() to serialize access to the encapsulated Map. Your implementation "reaches into" the object and manipulates the mutex. That breaks encapsulation.

That is, your implementation should have something like this:

func (s *SafeMap) whatever(...) ... {
    s.mux.Lock()
    defer s.mux.Unlock()

    ... do whatever
}

[Junilu Lacar]

Also, the map they refer to is supposed to act as a cache, so you can avoid going to the Fetcher more than 1 time for each URL. A cache usually holds the same kind of thing you get from the original source. Your SafeMap holds a map[string]int which is not the same thing you get from the original source. I would look to the Fetch function parameters to see what kind of map the SafeMap should hold. As an object, I think the SafeMap should have Fetch() and Put() methods.

[Junilu Lacar]

You might also want to look at the example under the "Parallel digestion" section on this page: https://blog.golang.org/pipelines

[Junilu Lacar]

Instead of sleeping, you can wait on a channel that gets closed when no more new URLs are found, i.e., all URLs are retrieved from the cache.

[Pat Farrell]

Sorry to jump in with a negative comment, but the code posted looks like Java code that is accidentally written in GO. Its a long way from idomatic GO

For example, GO code doesn't use sleep, it uses channel. And the mutex usage looks straight out of Henry Wong's Java Threads book.

Don't feel bad, most folks write in their old language when learning a new one. But to see GO's strengths, you have to write idiomatic GO.