Web Crawler gehen Tour verschiedene Ausgabe gleichen Code

Question

Ich habe versucht, die ganze Tour von Go-Tutorials zu tun, und ich bin bei der Web-Crawler stecken. Ich dachte, ich hätte es beendet, aber die Ausgabe ist inkonsistent und ich habe nicht genügend Nebenläufigkeitserfahrung, um herauszufinden, warum.

Hier ist mein Code:

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

Hier einige Beispielausgabe

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 

anders als die erste der letzten Paket wird (absichtlich in Sternchen oben)

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" 

fehlt Und schließlich , sogar ein Deadlock in einigen Läufen:

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 

Ich nehme an, es hat etwas mit Gleichzeitigkeit und Rekursion zu tun. Ich habe andere Lösungen in git Hub gesehen, die eine Warteliste und ähnliches verwenden, aber es wird nicht in den Tutorials verwendet - Tour of Go so weit, dass ich es lieber noch nicht benutzen würde.

UPDATE

ich herausgefunden, was los ist und die Arbeit am Thema. Im Allgemeinen bleibt die select-Anweisung in einer Endlosschleife hängen, da die Kanäle beendet werden und c nicht immer in der erwarteten Reihenfolge ausgeführt wird. Ich fügte einen Standardfall hinzu, der druckt ("nichts zu tun") und das Programm manchmal für immer geloopt, manchmal durch Glück auf eine korrekte Art und Weise ausgeführt. Meine Ausgangsbedingung ist nicht richtig

Answer 1

Ich denke, der Fall ist ziemlich klar. Deine Kanäle sind unordentlich. Mehrere goroutines erhalten von einem gleichen Kanal, und Golang wählt nur zufällig einen aus.

Wie Sie eine Null durch quit senden, wissen Sie nie, welche Goroutine beendet: Es wird zufällig von der Go-Sheduler ausgewählt. Es ist möglich, dass ein neu generiertes Crawl von quit empfangen wurde, bevor es von c empfangen wurde (auch wenn beide Kanäle bereit sind).

Und aufgrund dessen ist die depth ein Durcheinander und es macht Nummern von safeVisit wird instabil genannt, was zu quit Ausgabe von verschiedenen (zufällig) Signal. Manchmal ist es einfach nicht genug, um alle generierten Ganoutinen zu beenden, und es ist ein Deadlock.

Edit:

Zuerst sollten Sie verstehen, was Ihre Aufgabe ist. Die Crawl Funktion nimmt in einer URL, einem dep und einem Abholer, und es:

1. Fetch die URL
2. Drucken der abgerufene Körper
3. neue Crawl Warteschlange aus der abgerufenen URL generiert Stellen mit dep-1

Obwohl die Tour Sie fragt, URL in Parellel "holen", ist klar, dass Schritt 2 und Schritt 3 nach Schritt 1 passieren müssen, was bedeutet, dass es normal ist, dass ein einzelnes Crawling auf den Abruf wartet. Das bedeutet, dass keine neue Goroutine benötigt wird, um Fetch aufzurufen.

Und auf Schritt 3 muss jeder neue Crawl Anruf nicht warten, die vorherige zu beenden, so dass diese Anrufe parallel sein sollten.

Mit dieser Analyse kann man zu diesem Code kommen:

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 
} 

Es ein weiteres Problem ist: mit einer besuchten URL handelt. Sie haben es gut gemacht, anstatt eine quit zu senden, machen Sie es einfach func(string) bool und nennen Sie es direkt: if Visited(Url) { return } und es ist fertig.

Eine Randnotiz: Die Tour ist wirklich nicht gut im Unterrichten der Übereinstimmung. Vielleicht möchten Sie schauen, Blog-Artikel, wie Golang Courcency Muster oder Speicher teilen durch Kommunikation.