去旅游#10 : Lost in concurrency

Question

我一直在努力完成所有的 go 教程之旅，但我被困在了 the web crawler exercise 上。 .

我以为我完成了，但是输出不一致，我没有足够的并发经验来弄清楚为什么。

Here's我的代码:

package main

import (
    "fmt"
    "sync"
)

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)
}
var cache = struct {
    fetched map[string]bool
    sync.Mutex
}{fetched: make(map[string]bool)}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher, c chan []string, quit chan int) {
    if depth <= 0 {
        return
    }
    go safeVisit(url, c, quit, fetcher)
    for {
        select {
        case <- quit:
            return
        case u:= <-c:
            for _, v:= range u {
                go Crawl(v, depth -1, fetcher, c, quit)
            }
        }
    }
}
func main() {
    c := make(chan []string)
    quit := make(chan int)
    Crawl("http://golang.org/", 4, fetcher, c, quit)
}

func safeVisit(url string, c chan []string, quit chan int, fetcher Fetcher) {
    cache.Lock()
    defer cache.Unlock()
    if _, ok := cache.fetched[url] ; ok {
        quit <- 0
        return
    }
    body, urls, err := fetcher.Fetch(url)
    cache.fetched[url] = true
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("Visited : %s, %q \n", url, body)
    c <- urls

}

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

这是一些示例输出

Visited : http://golang.org/, "The Go Programming Language" 
not found: http://golang.org/cmd/
Visited : http://golang.org/pkg/, "Packages" 
Visited : http://golang.org/pkg/os/, "Package os" 
**Visited : http://golang.org/pkg/fmt/, "Package fmt"** 

Process finished with exit code 0

与第一个不同，最后一个包丢失(故意在上面的星号中)

Visited : http://golang.org/, "The Go Programming Language" 
not found: http://golang.org/cmd/
Visited : http://golang.org/pkg/, "Packages" 
Visited : http://golang.org/pkg/os/, "Package os"

最后，甚至在某些运行中出现死锁:

Visited : http://golang.org/, "The Go Programming Language" 
not found: http://golang.org/cmd/
Visited : http://golang.org/pkg/, "Packages" 
Visited : http://golang.org/pkg/os/, "Package os" 
Visited : http://golang.org/pkg/fmt/, "Package fmt" 
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [select]:
main.Crawl(0x4bfdf9, 0x12, 0x4, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
main.main()
    /home/kostas/development/challenges/go/helloWorld.go:39 +0xab

goroutine 23 [select]:
main.Crawl(0x4bfdf9, 0x12, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

goroutine 24 [select]:
main.Crawl(0x4c09f9, 0x16, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

goroutine 5 [select]:
main.Crawl(0x4bfdf9, 0x12, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

goroutine 6 [select]:
main.Crawl(0x4c0a0f, 0x16, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

我假设它与并发和递归有关。我在 github 中看到了其他使用 WaitGroups 等的解决方案，但到目前为止还没有在 go 之旅中使用它，所以我宁愿不使用它。

更新

我弄清楚了正在发生的事情并正在解决这个问题。基本上有时 select 语句会陷入无限循环，因为 channel 退出和 c 并不总是按预期顺序执行。我添加了一个打印(“无事可做”)的默认情况，程序有时会永远循环，有时会以正确的方式幸运地执行。我的退出条件不对

Answer 1

我认为情况很清楚。你的 channel 一团糟。多个 goroutines 从同一个 channel 接收，golang 只是随机选择一个。

当你通过 quit 发送一个零时，你永远不知道哪个 goroutine 退出了:它是由 go sheduler 随机选择的。新生成的 Crawl 有可能在从 c 接收到之前从 quit 接收到(即使两个 channel 都已准备好)。

因此，depth 是一团糟，它使调用 safeVisit 的次数不稳定，导致 quit 发出不同的(随机的) ) 信号。有时仅仅退出所有生成的 goroutine 是不够的，这是一个死锁。

编辑:

首先你应该明白你的任务是什么。 Crawl 函数接收一个 url、一个 dep 和一个 fetcher，它:

1. 获取网址
2. 打印获取的正文
3. 使用 dep-1 从获取的 url 生成新的 Crawl 队列

虽然tour要求你并行“fetch”url，但是很明显step 2和step 3必须在step 1之后发生，也就是说单次Crawl等待fetch是正常的。这意味着，不需要新的 goroutine 来调用 Fetch。

并且在第 3 步，每个新的 Crawl 调用都无需等待前一个完成，因此这些调用应该是并行的。

通过这些分析，可以得到这些代码:

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 {
        go Crawl(u, depth-1, fetcher)
    }
    return
}

还有一个问题:处理访问过的 url。你做的很好，不是发送一个quit，而是让它成为func(string) bool并直接调用它:if Visited(Url) { return } 完成。

旁注:游览真的不擅长教授并发性。您可能想查看 go 博客文章，例如 golang 并发模式或通过通信共享内存。