ゼロから学ぶGo言語プログラミング(16) A Tour of Go 71~72

f:id:belbo:20140616112930j:plain

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らしい書き方というのが身についているのか不安で、取り組んだ後には解答例が欲しくなりました。

ツアーの中で触れられていない基本的な要素も多数ありそうなので、次も何かチュートリアルを見てみようと思います。