[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/Code language: plaintext (plaintext)

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"Code language: plaintext (plaintext)

バージョン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
}

Code language: Go (go)

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

Code language: Go (go)

main関数を修正します。

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

Code language: Go (go)

実行してみると、クロール回数は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"Code language: plaintext (plaintext)

並列化の準備

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

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

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

Code language: Go (go)
func (f fakeFetcher) Fetch(url string) (string, []string, error) {
	time.Sleep(time.Second)

Code language: Go (go)

バージョン3: 並列化

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

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

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

Code language: Go (go)

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

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

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



Code language: Go (go)

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
	}


Code language: Go (go)

実行してみると、表示内容は同じですが、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"Code language: plaintext (plaintext)

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

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

２つめは、並列の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パッケージによる方法です。
blog.kaznishi.com
Goroutineの最大数を制御する方法 - Qiita
Goで複数の仕事があるとして、goroutineを新たに作成してそれに1つ1つの仕事を任せるのは普通のやり方だと思う。たとえばクライアントからの接続を待っているサーバをGoで書いているとして、クライ…
qiita.com

残念ながら、これらの方法は、バージョン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
}

Code language: Go (go)

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
}
Code language: Go (go)

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

Code language: Go (go)

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

Code language: Go (go)

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

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

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