ゼロから学ぶGo言語プログラミング(16) A Tour of Go 71~72
A Tour of Goの続き。 ツアーもこれで最後。
71.Exercise: Web Crawler
最後の課題らしく、コードは多め、解説は少なめ。
まず、初期のコード。 今までのサンプルコードよりボリュームがあるので、まずはしっかり読んでみる。
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) } // 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: 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 { Crawl(u, depth-1, fetcher) } return } 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/", }, }, }
課題はシンプルなクローラの改良です。
まずmain()は以下の関数実行のみ。
func main() { Crawl("http://golang.org/", 4, fetcher) }
実行されるCrawl()。
// 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: 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 { Crawl(u, depth-1, fetcher) } return }
クロールの開始点となるURL、そこから何階層辿るかの指定depth、そしてFetcher型を受け取ります。
階層depthが0以下ならそこで終了。 そうでなければ、Fetcherのインターフェースに定義されているFetch()を、引数のURLで実行。 複数の戻り値をbody, urls, errで受けています。 これは実際のクローラーであれば、レスポンスのbodyと、headやbodyに含まれていたURLを切り出したslice、そしてステータスコードなどに基づくエラーを返すんでしょう。 エラーがnilでなければ、標準出力にエラーを記録して終了。 実際にはログでしょうか。
Fetch()が問題なければ、取得したURLとbodyを出力し、URLの詰まったsliceであるurlsをforとrangeで回す。 ここでdepthをひとつ減らしてCrawl()を再帰。 Crawl()はここまでです。
次に、Fetcherインターフェースの実装部分。
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) }
実装であるfakeFetcher型は、stringがキーで値がfakeResult型のポインタになったmapを指定しています。 そしてfakeResult型はFetcher()の戻り値と同じbodyとurls。 これは名前の通り、課題用のダミーのフェッチ結果を返すための実装ですね。 fakeFetcher型のFetch()実装は、自身のmapにURLをキーとする項目があるばそれを返し、無ければ"not found"を出力。
そして、ダミーデータを渡してfakeFetcherを取得。 ダミーデータは、URLをキーにして、bodyと次階層のurlsを持ったfakeResultを持つ。
// 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/", }, }, }
これで課題用クローラの初期コードは読み終わりました。 この初期コードを実行すると、ダミーデータから該当したURLとbodyが出力されます。
で、課題の改良は、クロールの並列化と重複の防止。 当然goroutineを使いますが、どこにどう入れるべきか。 悩んだりこねくり回した結果、こうなりました。
package main import ( "fmt" "sync" "time" ) var fetched = make(map[string]bool) 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 crawlResult struct { 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) { ch := make(chan crawlResult, 1) var wg sync.WaitGroup wg.Add(1) go func(){ wg.Wait() close(ch) }() go crawlWorker(url, depth, fetcher, ch, &wg) for r := range ch { if r.err == nil { fmt.Printf("found: %s %q\n", r.url, r.body) } else { fmt.Printf("not found: %s\n", r.url) } } } func crawlWorker(url string, depth int, fetcher Fetcher, ch chan crawlResult, wg *sync.WaitGroup) { // TODO: Fetch URLs in parallel. // TODO: Don't fetch the same URL twice. // This implementation doesn't do either: // fmt.Printf("%s", wg) defer wg.Done() if depth <= 0 { return } if fetched[url] { return } fetched[url] = true body, urls, err := fetcher.Fetch(url) r := crawlResult{url, body, urls, err} ch <- r if err != nil { return } for _, u := range urls { wg.Add(1) go crawlWorker(u, depth-1, fetcher, ch, wg) } return } 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) { time.Sleep(300 * time.Millisecond) 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/", }, }, }
これまで学んできた範囲で解決できなかったのは、channelによるクロール結果待ちが、goroutineのデッドロックを伴う点。 クロールを行う各goroutineからのメッセージは、無限ループでchannelを待って受け取りますが、全てのクロールが完了した時点でchannelを閉じる必要があります。 閉じなければ、channelが発生させるロックが宙に浮き、デッドロックとなってしまいます。 しかし、goroutine側ではどの時点でchannelを閉じるべきか判断できません。
あれこれ調べて、下記の記事に行き着きました。
悩んでいたそのものへの言及があり、syncパッケージを使うことで解決できそうだと判断しました。 syncのAdd(),Done(),Wait()を使って、wait用のgoroutineを無名関数で走らせて上手くいくはずが、なぜか変わらずデッドロックが発生。 しばらく考えてプリントデバグした結果、クロールのgoroutine側でwg.Add()したはずが、カウンタが増えていない。 WaitGroupをクローラの各goroutineに渡す際、値渡しになっていたのが原因でした。 結局ここをポインタによる参照渡しに変え、デッドロックは回避。
チュートリアルの課題で出てきていないパッケージであり、そんなもので解決するのは間違っている気もしますが、薄くとはいえgoroutineのイメージが少し深まったので良しとします。
重複するURLの取得回避にグローバルに置いたmapを使うとか、なんか色々問題はありそうですが、ひとまずこれで課題クリア。
72.Where to Go from here...
これでツアーは終了です。長かったような短かったような。
ツアー中ずっとgopherくんが見ていてくれたのは楽しかった。
課題はありがたいけど、goらしい書き方というのが身についているのか不安で、取り組んだ後には解答例が欲しくなりました。
ツアーの中で触れられていない基本的な要素も多数ありそうなので、次も何かチュートリアルを見てみようと思います。