[prog] Мое решение упражнения Web Crawler из A Tour of Go

Поскольку перспективы поиска следующего места работы пока туманны даже для меня, решил воспользоваться имеющимся временем для реализации идей, которые когда-то у меня были, но до которых не доходили руки. Заодно захотелось узнать, могу ли я еще, как разработчик, или уже все... :) В качестве старта захотел сделать небольшую утилиту, но чтобы сделать задачу поинтереснее, выбрал в качестве языка реализации Go. Просто чтобы попробовать его самостоятельно в чем-то более-менее реальном. Причем на Go я до этого ничего не писал, да и не смотрел на него уже очень давно (со времен вот этой заметки).

Прежде чем что-то писать, язык Go нужно сначала выучить. Начал изучение с A Tour of Go. Вещь прикольная, но в процессе накапливаются некоторые вопросы и недопонимание. Надеюсь, что ответы найдутся по ходу чтения более серьезных материалов.

Вчера добрался до упражнения Web Crawler. Его смысл в том, чтобы модифицировать некую функцию Crawl так, чтобы:

• один и тот же URL дважды не обрабатывался;
• обработка URL велась в параллель.

Собственно, вот полное условие задачи:

In this exercise you'll use Go's concurrency features to parallelize a web crawler. Modify the Crawl function to fetch URLs in parallel without fetching the same URL twice.

И все описание. А вот исходный код этой функции:

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

Честно признаюсь, впал в ступор. Поскольку для меня было очевидно, что если сохранять рекурсивную природу Crawl, да еще допускать ее запуск в разных потоках (goroutine-ах), то нельзя обойтись без общей структуры данных (вроде map-а), доступ к которой нужно синхронизировать. А из примитивов синхронизации в Tour of Go описывались только каналы. Еще одна загвоздка была в том, чтобы контролировать моменты завершения параллельных вызовов Crawl. Ведь об этом в Tour of Go ничего не говорилось, а простейший эксперимент показал, что функция main спокойно себе завершается не дожидаясь работы запущенных потоков.

В общем, с одной стороны было понятно, что при решении задачи нужно ограничится только теми средствами языка, которые были описаны в Tour of Go. С другой стороны, совершенно непонятно было, как сохранить рекурсивный принцип работы Crawl. В итоге, решил сделать паузу до сегодняшнего дня.

Сегодня, на свежую голову, решил отказаться от сохранения рекурсии в Crawl. Crawl превращается в менеджера, который запускает обход конкретных URL в параллель посредством простой нерекурсивной функции fetchUrl. Для обмена результатами работы используются Go-щные каналы. Более того, если вчера мне казалось, что потребуется несколько информационных каналов, то сегодня стало очевидно, что достаточно только одного, через который fetchUrl будут сообщать Crawl-у о результате обработки URL-а. В общем, где-то за час-полтора удалось переписать пример, скомпилировать его и убедится, что полученное решение вроде бы работает.

После чего погуглил аналогичные решения. С ходу нашлось три: #1, #2, #3 (наверняка их больше). Мне кажется, что мое не хуже :)

Полный код моего варианта под катом. Пока же небольшое резюме. Да, мозги уже не программерские, соображается туго :( Но руки, вроде бы, еще помнят ;) Так что если никому не нужен будет менеджер с опытом работы в экстремальных условиях, то буду зарабатывать быдлокодингом :)))

Свои же впечатления от языка Go пока описывать не стану, еще рано, нужно поднабраться опыта.

Небольшое примечание. Код мог бы быть компактнее, если бы я убрал из него лишние отладочные печати. Оно зато они позволяют убедится, что работа действительно идет параллельно и уже обработанные URL повторно не обрабатываются.

И таки да, это моя первая программа на Go :)

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) } func Crawl(url string, depth int, fetcher Fetcher) {    results := make(chan fetchResult)    processedUrls := map[string]bool {url: true}    fetcherCount := 1    go fetchUrl(url, depth, fetcher, results)    for fetcherCount != 0 {       r := <-results       fetcherCount--       fmt.Println("Handling fetch results...")       for _, nextUrl := range r.Urls {          if processedUrls[nextUrl] {             fmt.Printf("URL already processed: %s\n", nextUrl)          } else {             processedUrls[nextUrl] = true             fetcherCount++             go fetchUrl(nextUrl, r.Depth - 1, fetcher, results)          }       }    } } func main() {     Crawl("http://golang.org/", 4, fetcher) } type fetchResult struct {    Urls []string    Depth int } func fetchUrl(       url string,       depth int,       fecther Fetcher,       resultChannel chan fetchResult) {    fmt.Printf("Processing '%s'(%d)...\n", url, depth)    result := fetchResult{Depth: depth}     if depth > 0 {        body, urls, err := fetcher.Fetch(url)        if err != nil {            fmt.Println(err)        } else {           fmt.Printf("found: %s %q\n", url, body)           result.Urls = urls        }     }     resultChannel <- result } // 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/",         },     }, }