8.6. 示例: 併發的Web爬蟲

在5.6節中,我們做了一個簡單的web爬蟲,用bfs(廣度優先)算法來抓取整個網站。在本節中,我們會讓這個這個爬蟲併行化,這樣每一個彼此獨立的抓取命令可以併行進行IO,最大化利用網絡資源。crawl函數和gopl.io/ch5/findlinks3中的是一樣的。

gopl.io/ch8/crawl1 go func crawl(url string) []string { fmt.Println(url) list, err := links.Extract(url) if err != nil { log.Print(err) } return list }

主函數和5.6節中的breadthFirst(深度優先)類似。像之前一樣,一個worklist是一個記録了需要處理的元素的隊列,每一個元素都是一個需要抓取的URL列表,不過這一次我們用channel代替slice來做這個隊列。每一個對crawl的調用都會在他們自己的goroutine中進行併且會把他們抓到的鏈接發送迴worklist。

func main() {
    worklist := make(chan []string)

    // Start with the command-line arguments.
    go func() { worklist <- os.Args[1:] }()

    // Crawl the web concurrently.
    seen := make(map[string]bool)
    for list := range worklist {
        for _, link := range list {
            if !seen[link] {
                seen[link] = true
                go func(link string) {
                    worklist <- crawl(link)
                }(link)
            }
        }
    }
}

註意這里的crawl所在的goroutine會將link作爲一個顯式的參數傳入,來避免“循環變量快照”的問題(在5.6.1中有講解)。另外註意這里將命令行參數傳入worklist也是在一個另外的goroutine中進行的,這是爲了避免在main goroutine和crawler goroutine中同時向另一個goroutine通過channel發送內容時發生死鎖(因爲另一邊的接收操作還沒有準備好)。當然,這里我們也可以用buffered channel來解決問題,這里不再贅述。

現在爬蟲可以高併發地運行起來,併且可以産生一大坨的URL了,不過還是會有倆問題。一個問題是在運行一段時間後可能會出現在log的錯誤信息里的:

$ go build gopl.io/ch8/crawl1
$ ./crawl1 http://gopl.io/
http://gopl.io/
https://golang.org/help/
https://golang.org/doc/
https://golang.org/blog/
...
2015/07/15 18:22:12 Get ...: dial tcp: lookup blog.golang.org: no such host
2015/07/15 18:22:12 Get ...: dial tcp 23.21.222.120:443: socket: too many open files
...

最初的錯誤信息是一個讓人莫名的DNS査找失敗,卽使這個域名是完全可靠的。而隨後的錯誤信息揭示了原因:這個程序一次性創建了太多網絡連接,超過了每一個進程的打開文件數限製,旣而導致了在調用net.Dial像DNS査找失敗這樣的問題。

這個程序實在是太他媽併行了。無窮無盡地併行化併不是什麽好事情,因爲不管怎麽説,你的繫統總是會有一個些限製因素,比如CPU核心數會限製你的計算負載,比如你的硬盤轉軸和磁頭數限製了你的本地磁盤IO操作頻率,比如你的網絡帶寬限製了你的下載速度上限,或者是你的一個web服務的服務容量上限等等。爲了解決這個問題,我們可以限製併發程序所使用的資源來使之適應自己的運行環境。對於我們的例子來説,最簡單的方法就是限製對links.Extract在同一時間最多不會有超過n次調用,這里的n是fd的limit-20,一般情況下。這個一個夜店里限製客人數目是一個道理,隻有當有客人離開時,才會允許新的客人進入店內(譯註:作者你個老流氓)。

我們可以用一個有容量限製的buffered channel來控製併發,這類似於操作繫統里的計數信號量概念。從概念上講,channel里的n個空槽代表n個可以處理內容的token(通行證),從channel里接收一個值會釋放其中的一個token,併且生成一個新的空槽位。這樣保證了在沒有接收介入時最多有n個發送操作。(這里可能我們拿channel里填充的槽來做token更直觀一些,不過還是這樣吧~)。由於channel里的元素類型併不重要,我們用一個零值的struct{}來作爲其元素。

讓我們重寫crawl函數,將對links.Extract的調用操作用獲取、釋放token的操作包裹起來,來確保同一時間對其隻有20個調用。信號量數量和其能操作的IO資源數量應保持接近。

gopl.io/ch8/crawl2 ```go // tokens is a counting semaphore used to // enforce a limit of 20 concurrent requests. var tokens = make(chan struct{}, 20)

func crawl(url string) []string { fmt.Println(url) tokens <- struct{}{} // acquire a token list, err := links.Extract(url) <-tokens // release the token if err != nil { log.Print(err) } return list } ```

第二個問題是這個程序永遠都不會終止,卽使它已經爬到了所有初始鏈接衍生出的鏈接。(當然,除非你慎重地選擇了合適的初始化URL或者已經實現了練習8.6中的深度限製,你應該還沒有意識到這個問題)。爲了使這個程序能夠終止,我們需要在worklist爲空或者沒有crawl的goroutine在運行時退出主循環。

func main() {
    worklist := make(chan []string)
    var n int // number of pending sends to worklist

    // Start with the command-line arguments.
    n++
    go func() { worklist <- os.Args[1:] }()

    // Crawl the web concurrently.
    seen := make(map[string]bool)

    for ; n > 0; n-- {
        list := <-worklist
        for _, link := range list {
            if !seen[link] {
                seen[link] = true
                n++
                go func(link string) {
                    worklist <- crawl(link)
                }(link)
            }
        }
    }
}

這個版本中,計算器n對worklist的發送操作數量進行了限製。每一次我們發現有元素需要被發送到worklist時,我們都會對n進行++操作,在向worklist中發送初始的命令行參數之前,我們也進行過一次++操作。這里的操作++是在每啟動一個crawler的goroutine之前。主循環會在n減爲0時終止,這時候説明沒活可榦了。

現在這個併發爬蟲會比5.6節中的深度優先蒐索版快上20倍,而且不會出什麽錯,併且在其完成任務時也會正確地終止。

下面的程序是避免過度併發的另一種思路。這個版本使用了原來的crawl函數,但沒有使用計數信號量,取而代之用了20個長活的crawler goroutine,這樣來保證最多20個HTTP請求在併發。

func main() {
    worklist := make(chan []string)  // lists of URLs, may have duplicates
    unseenLinks := make(chan string) // de-duplicated URLs

    // Add command-line arguments to worklist.
    go func() { worklist <- os.Args[1:] }()

    // Create 20 crawler goroutines to fetch each unseen link.
    for i := 0; i < 20; i++ {
        go func() {
            for link := range unseenLinks {
                foundLinks := crawl(link)
                go func() { worklist <- foundLinks }()
            }
        }()
    }

    // The main goroutine de-duplicates worklist items
    // and sends the unseen ones to the crawlers.
    seen := make(map[string]bool)
    for list := range worklist {
        for _, link := range list {
            if !seen[link] {
                seen[link] = true
                unseenLinks <- link
            }
        }
    }
}

所有的爬蟲goroutine現在都是被同一個channel-unseenLinks餵飽的了。主goroutine負責拆分它從worklist里拿到的元素,然後把沒有抓過的經由unseenLinks channel發送給一個爬蟲的goroutine。

seen這個map被限定在main goroutine中;也就是説這個map隻能在main goroutine中進行訪問。類似於其它的信息隱藏方式,這樣的約束可以讓我們從一定程度上保證程序的正確性。例如,內部變量不能夠在函數外部被訪問到;變量(§2.3.4)在沒有被轉義的情況下是無法在函數外部訪問的;一個對象的封裝字段無法被該對象的方法以外的方法訪問到。在所有的情況下,信息隱藏都可以幫助我們約束我們的程序,使其不發生意料之外的情況。

crawl函數爬到的鏈接在一個專有的goroutine中被發送到worklist中來避免死鎖。爲了節省空間,這個例子的終止問題我們先不進行詳細闡述了。

練習 8.6: 爲併發爬蟲增加深度限製。也就是説,如果用戶設置了depth=3,那麽隻有從首頁跳轉三次以內能夠跳到的頁面才能被抓取到。

練習 8.7: 完成一個併發程序來創建一個線上網站的本地鏡像,把該站點的所有可達的頁面都抓取到本地硬盤。爲了省事,我們這里可以隻取出現在該域下的所有頁面(比如golang.org結尾,譯註:外鏈的應該就不算了。)當然了,出現在頁面里的鏈接你也需要進行一些處理,使其能夠在你的鏡像站點上進行跳轉,而不是指向原始的鏈接。

譯註: 拓展閲讀 Handling 1 Million Requests per Minute with Go