[Go] A Tour of Go, Exercise: Web Crawler

Go言語のチュートリアル「A Tour of Go」の最後のExercise: Web Crawlerの解答例です。

バージョン1: 例題について

Web Crawlerといっても、実際にはクロールしません。ソースコードを下に見ていくと、fakeFetcherにリテラル定義してあります。

ソースコードが下に長いことに気づかなくて、自分でFetcherも実装するのかと勘違いしちゃったよ

問題文には「同じURLを2度取ってくることなく並列してURLを取ってくるように、 Crawl 関数を修正してみてください」とあります。

mapを使った重複防止、goroutineを使った並列処理、の2点を実装するんですね。

まず、提示されているソースコードを実行しました。

$ go run exercise-web-crawler_v1.go found: https://golang.org/ "The Go Programming Language" found: https://golang.org/pkg/ "Packages" found: https://golang.org/ "The Go Programming Language" found: https://golang.org/pkg/ "Packages" not found: https://golang.org/cmd/ not found: https://golang.org/cmd/ found: https://golang.org/pkg/fmt/ "Package fmt" found: https://golang.org/ "The Go Programming Language" found: https://golang.org/pkg/ "Packages" found: https://golang.org/pkg/os/ "Package os" found: https://golang.org/ "The Go Programming Language" found: https://golang.org/pkg/ "Packages" not found: https://golang.org/cmd/

found、not found合わせて、13回クロールしていました。

重複防止していれば、foundが4回、not foundが1回、合わせて5回になるはずです。

found: https://golang.org/ "The Go Programming Language" found: https://golang.org/pkg/ "Packages" not found: https://golang.org/cmd/ found: https://golang.org/pkg/fmt/ "Package fmt" found: https://golang.org/pkg/os/ "Package os"

バージョン2: mapを使った重複防止

まず、mapを使った重複防止を実装します。

mapは、map[string]boolとし、url文字列をキー、値がtrueならクロール済み、にしました。

まだ、sync.Mutex.Lock()、sync.Mutex.unlock()は必要ありませんが、いずれ必要になるので、実装しました。

import ( "fmt" "sync" ) type UrlMap struct { mu sync.Mutex crawledMap map[string]bool } func (urlMap *UrlMap) isCrawled(url string) bool { defer urlMap.mu.Unlock() urlMap.mu.Lock() f := urlMap.crawledMap[url] if !f { urlMap.crawledMap[url] = true } return f }

Crawl関数の引数にurlMapを追加します。すでにmapに登録済みなら、returnします。再帰呼出しの引数にもurlMapを追加します。

func Crawl(url string, depth int, fetcher Fetcher, urlMap *UrlMap) { if urlMap.isCrawled(url) { return } // 省略 for _, u := range urls { Crawl(u, depth-1, fetcher, urlMap) }

main関数を修正します。

func main() { urlMap := &UrlMap{crawledMap: make(map[string]bool)} Crawl("https://golang.org/", 4, fetcher, urlMap) }

実行してみると、クロール回数は5回になりました。

$ go run exercise-web-crawler_v3.go found: https://golang.org/ "The Go Programming Language" not found: https://golang.org/cmd/ found: https://golang.org/pkg/ "Packages" found: https://golang.org/pkg/fmt/ "Package fmt" found: https://golang.org/pkg/os/ "Package os"

並列化の準備

並列化の効果がわかりやすいように、Fetch関数で1秒スリープをいれます。

1秒おきに1行づつ、クロール結果が表示されます。

import ( "fmt" "sync" "time" )
func (f fakeFetcher) Fetch(url string) (string, []string, error) { time.Sleep(time.Second)

バージョン3: 並列化

Crawl関数で、forループで再帰呼び出しをしている箇所があります。

for _, u := range urls { Crawl(u, depth-1, fetcher, urlMap) }

2つのURLが見つかったら、
Crawl("https://golang.org/pkg/")

Crawl("https://golang.org/cmd/")
の順で、Crawl関数が呼ばれるわけですね。

まず、ここを並列化します。

main関数のCrawl呼び出しをgoroutine化します。

func main() { urlMap := &UrlMap{crawledMap: make(map[string]bool)} ch := make(chan int) go Crawl("https://golang.org/", 4, fetcher, urlMap, ch) <-ch

Crawl関数の引数に、チャネルを追加します。

また、deferを使って、Crawl関数の終了時に、チャネルに通知するようにします。

func Crawl(url string, depth int, fetcher Fetcher, urlMap *UrlMap, ch0 chan int) { defer func() { ch0 <- 0 }()

for文の再帰呼び出しの箇所をgoroutein化します。

ch1 := make(chan int) for _, u := range urls { go Crawl(u, depth-1, fetcher, urlMap, ch1) } for i := 0; i < len(urls); i++ { <-ch1 }

実行してみると、表示内容は同じですが、3秒しかかかっていません。2行3行目がほぼ同時に、4行目5行目がほぼ同時に表示されました。

found: https://golang.org/ "The Go Programming Language" found: https://golang.org/pkg/ "Packages" not found: https://golang.org/cmd/ found: https://golang.org/pkg/fmt/ "Package fmt" found: https://golang.org/pkg/os/ "Package os"

この方法は、少々ムズムズするというか、座りが悪いというか、リファクタしたい部分があります。

1つめは、Crawl関数にチャネル制御が入り込んでしまいました。テストケースを作るとき、チャネルも準備しなくてはなりません。テストケースを作るのが難しくなりそうです。

2つめは、並列のgoroutine数(スレッド数)の上限を制御できていないことです。

Go言語のGroutineは軽量スレッドと呼ばれていて、Javaのスレッドよりはるかに多くのスレッドを作れるそうです。

なぜ Go では何百万もの Goroutine を作れるのに Java は数千のスレッドしか作れないのか?

https://mahata.gitlab.io/post/2018-10-15-goroutines-vs-java-threads/

この記事のノートPCでは、Javaスレッドは11500個、Groutineは7000万個、作れたそうです。

ところが、実際にはどこかでメモリ不足になるようです。先輩たちによると、Goroutineの同時実行数を制限する方法は、次のとおりです。

goroutineの同時実行数に制限をかける - kaznishi I/O
goroutineの同時実行数に制限をかける方法を2つ紹介しています。1つはchannelによる方法。もう一つはgolang.org/x/sync/semaphoreパッケージによる方法です。
Goroutineの最大数を制御する方法 - Qiita
Goで複数の仕事があるとして、goroutineを新たに作成してそれに1つ1つの仕事を任せるのは普通のやり方だと思う。たとえばクライアントからの接続を待っているサーバをGoで書いているとして、クライアントからのリクエストごとにgoro...

残念ながら、これらの方法は、バージョン3には使えませんでした。

バージョン3は、再帰的にGoroutine(Crawl関数)を呼び出しています。再帰呼出ししたGoroutineが終わるまで、呼出し元のGoroutine関数は終わりません。呼び出し先でGoroutine数に達して、空き待ちになってしまったとき、他のGoroutineは呼び出し元ばかりで終わりません、deadlockになってしまいました。

バージョン4: スレッドプール風の並列化

URLマップの値を0=未登録、1=未クロール、2=クロール済みにします。

URLマップの未クロール数が0なら、全てのCrawlが完了したと判断して、all_crawl_complete_chに通知します。

main関数で、全てのCrawlが送るまで待つときに、このall_crawl_complete_chを待ちます。

type CrawlParam struct { url string depth int } const CRAWL_STATUS_UNREGISTERED = 0 const CRAWL_STATUS_NOT_CRAWLED = 1 const CRAWL_STATUS_CRAWLED = 2 type UrlData struct { mu sync.Mutex urlCrawlstatusMap map[string]int queue chan CrawlParam all_crawl_completed_ch chan int } func (urlMap *UrlData) add(url string, depth int) { defer urlMap.mu.Unlock() urlMap.mu.Lock() f := urlMap.urlCrawlstatusMap[url] if f == CRAWL_STATUS_UNREGISTERED { urlMap.urlCrawlstatusMap[url] = CRAWL_STATUS_NOT_CRAWLED urlMap.queue <- CrawlParam{url: url, depth: depth} } } func (urlMap *UrlData) done(url string) { defer urlMap.mu.Unlock() urlMap.mu.Lock() urlMap.urlCrawlstatusMap[url] = CRAWL_STATUS_CRAWLED if urlMap.notCrawledCount() == 0 { urlMap.all_crawl_completed_ch <- 0 } } func (urlMap *UrlData) notCrawledCount() int { n := 0 for _, v := range urlMap.urlCrawlstatusMap { if v == 1 { n++ } } return n }

Crawl関数です。チャネル制御をなくしました。再帰呼出しはやめて、クロール結果をurlMapに登録するようにしました。

func Crawl(url string, depth int, fetcher Fetcher, urlMap *UrlData) { defer urlMap.done(url) 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 { urlMap.add(u, depth - 1) } return }

Crawl関数を呼び出すGoroutineです。urlMap.queueを待ち、Crawl関数を呼びます。

func CrawlThread(fetcher Fetcher, urlMap *UrlData, quit chan int) { for { select { case crawlParam := <-urlMap.queue: Crawl(crawlParam.url, crawlParam.depth, fetcher, urlMap) case <-quit: return; } } }

main関数で、スレッドプールを作ります。

func main() { urlMap := &UrlData{ urlCrawlstatusMap: make(map[string]int), queue: make(chan CrawlParam, 10), all_crawl_completed_ch: make(chan int), } quit := make(chan int) N_THREADS := 4 for i := 0; i < N_THREADS; i++ { go CrawlThread(fetcher, urlMap, quit) } urlMap.add("https://golang.org/", 4) <-urlMap.all_crawl_completed_ch for i := 0; i < N_THREADS; i++ { quit <- 0; } }

Crawl関数はきれいになったけど、チャネル制御がUrlMapとCrawlThread関数に移動しただけじゃない?

そのとおりね。チャネルを使わないCrawlとUrlMapを作ってから、Goroutine版を作ればよかったかもね。

タイトルとURLをコピーしました