Go 語(yǔ)言 示例: 并發(fā)的Web爬蟲(chóng)

原文鏈接：https://gopl-zh.github.io/ch8/ch8-06.html

8.6. 示例: 并發(fā)的Web爬蟲(chóng)

在5.6節(jié)中，我們做了一個(gè)簡(jiǎn)單的web爬蟲(chóng)，用bfs(廣度優(yōu)先)算法來(lái)抓取整個(gè)網(wǎng)站。在本節(jié)中，我們會(huì)讓這個(gè)爬蟲(chóng)并行化，這樣每一個(gè)彼此獨(dú)立的抓取命令可以并行進(jìn)行IO，最大化利用網(wǎng)絡(luò)資源。crawl函數(shù)和gopl.io/ch5/findlinks3中的是一樣的。

gopl.io/ch8/crawl1

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

主函數(shù)和5.6節(jié)中的breadthFirst(廣度優(yōu)先)類似。像之前一樣，一個(gè)worklist是一個(gè)記錄了需要處理的元素的隊(duì)列，每一個(gè)元素都是一個(gè)需要抓取的URL列表，不過(guò)這一次我們用channel代替slice來(lái)做這個(gè)隊(duì)列。每一個(gè)對(duì)crawl的調(diào)用都會(huì)在他們自己的goroutine中進(jìn)行并且會(huì)把他們抓到的鏈接發(fā)送回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會(huì)將link作為一個(gè)顯式的參數(shù)傳入，來(lái)避免“循環(huán)變量快照”的問(wèn)題（在5.6.1中有講解）。另外注意這里將命令行參數(shù)傳入worklist也是在一個(gè)另外的goroutine中進(jìn)行的，這是為了避免channel兩端的main goroutine與crawler goroutine都嘗試向?qū)Ψ桨l(fā)送內(nèi)容，卻沒(méi)有一端接收內(nèi)容時(shí)發(fā)生死鎖。當(dāng)然，這里我們也可以用buffered channel來(lái)解決問(wèn)題，這里不再贅述。

現(xiàn)在爬蟲(chóng)可以高并發(fā)地運(yùn)行起來(lái)，并且可以產(chǎn)生一大坨的URL了，不過(guò)還是會(huì)有倆問(wèn)題。一個(gè)問(wèn)題是在運(yùn)行一段時(shí)間后可能會(huì)出現(xiàn)在log的錯(cuò)誤信息里的：

$ 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
...

最初的錯(cuò)誤信息是一個(gè)讓人莫名的DNS查找失敗，即使這個(gè)域名是完全可靠的。而隨后的錯(cuò)誤信息揭示了原因：這個(gè)程序一次性創(chuàng)建了太多網(wǎng)絡(luò)連接，超過(guò)了每一個(gè)進(jìn)程的打開(kāi)文件數(shù)限制，既而導(dǎo)致了在調(diào)用net.Dial像DNS查找失敗這樣的問(wèn)題。

這個(gè)程序?qū)嵲谑翘麐尣⑿辛?。無(wú)窮無(wú)盡地并行化并不是什么好事情，因?yàn)椴还茉趺凑f(shuō)，你的系統(tǒng)總是會(huì)有一些個(gè)限制因素，比如CPU核心數(shù)會(huì)限制你的計(jì)算負(fù)載，比如你的硬盤(pán)轉(zhuǎn)軸和磁頭數(shù)限制了你的本地磁盤(pán)IO操作頻率，比如你的網(wǎng)絡(luò)帶寬限制了你的下載速度上限，或者是你的一個(gè)web服務(wù)的服務(wù)容量上限等等。為了解決這個(gè)問(wèn)題，我們可以限制并發(fā)程序所使用的資源來(lái)使之適應(yīng)自己的運(yùn)行環(huán)境。對(duì)于我們的例子來(lái)說(shuō)，最簡(jiǎn)單的方法就是限制對(duì)links.Extract在同一時(shí)間最多不會(huì)有超過(guò)n次調(diào)用，這里的n一般小于文件描述符的上限值，比如20。這和一個(gè)夜店里限制客人數(shù)目是一個(gè)道理，只有當(dāng)有客人離開(kāi)時(shí)，才會(huì)允許新的客人進(jìn)入店內(nèi)。

我們可以用一個(gè)有容量限制的buffered channel來(lái)控制并發(fā)，這類似于操作系統(tǒng)里的計(jì)數(shù)信號(hào)量概念。從概念上講，channel里的n個(gè)空槽代表n個(gè)可以處理內(nèi)容的token（通行證），從channel里接收一個(gè)值會(huì)釋放其中的一個(gè)token，并且生成一個(gè)新的空槽位。這樣保證了在沒(méi)有接收介入時(shí)最多有n個(gè)發(fā)送操作。（這里可能我們拿channel里填充的槽來(lái)做token更直觀一些，不過(guò)還是這樣吧。）由于channel里的元素類型并不重要，我們用一個(gè)零值的struct{}來(lái)作為其元素。

讓我們重寫(xiě)crawl函數(shù)，將對(duì)links.Extract的調(diào)用操作用獲取、釋放token的操作包裹起來(lái)，來(lái)確保同一時(shí)間對(duì)其只有20個(gè)調(diào)用。信號(hào)量數(shù)量和其能操作的IO資源數(shù)量應(yīng)保持接近。

gopl.io/ch8/crawl2

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

第二個(gè)問(wèn)題是這個(gè)程序永遠(yuǎn)都不會(huì)終止，即使它已經(jīng)爬到了所有初始鏈接衍生出的鏈接。（當(dāng)然，除非你慎重地選擇了合適的初始化URL或者已經(jīng)實(shí)現(xiàn)了練習(xí)8.6中的深度限制，你應(yīng)該還沒(méi)有意識(shí)到這個(gè)問(wèn)題。）為了使這個(gè)程序能夠終止，我們需要在worklist為空或者沒(méi)有crawl的goroutine在運(yùn)行時(shí)退出主循環(huán)。

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

這個(gè)版本中，計(jì)數(shù)器n對(duì)worklist的發(fā)送操作數(shù)量進(jìn)行了限制。每一次我們發(fā)現(xiàn)有元素需要被發(fā)送到worklist時(shí)，我們都會(huì)對(duì)n進(jìn)行++操作，在向worklist中發(fā)送初始的命令行參數(shù)之前，我們也進(jìn)行過(guò)一次++操作。這里的操作++是在每啟動(dòng)一個(gè)crawler的goroutine之前。主循環(huán)會(huì)在n減為0時(shí)終止，這時(shí)候說(shuō)明沒(méi)活可干了。

現(xiàn)在這個(gè)并發(fā)爬蟲(chóng)會(huì)比5.6節(jié)中的深度優(yōu)先搜索版快上20倍，而且不會(huì)出什么錯(cuò)，并且在其完成任務(wù)時(shí)也會(huì)正確地終止。

下面的程序是避免過(guò)度并發(fā)的另一種思路。這個(gè)版本使用了原來(lái)的crawl函數(shù)，但沒(méi)有使用計(jì)數(shù)信號(hào)量，取而代之用了20個(gè)常駐的crawler goroutine，這樣來(lái)保證最多20個(gè)HTTP請(qǐng)求在并發(fā)。

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

所有的爬蟲(chóng)goroutine現(xiàn)在都是被同一個(gè)channel - unseenLinks喂飽的了。主goroutine負(fù)責(zé)拆分它從worklist里拿到的元素，然后把沒(méi)有抓過(guò)的經(jīng)由unseenLinks channel發(fā)送給一個(gè)爬蟲(chóng)的goroutine。

seen這個(gè)map被限定在main goroutine中；也就是說(shuō)這個(gè)map只能在main goroutine中進(jìn)行訪問(wèn)。類似于其它的信息隱藏方式，這樣的約束可以讓我們從一定程度上保證程序的正確性。例如，內(nèi)部變量不能夠在函數(shù)外部被訪問(wèn)到；變量（§2.3.4）在沒(méi)有發(fā)生變量逃逸（譯注：局部變量被全局變量引用地址導(dǎo)致變量被分配在堆上）的情況下是無(wú)法在函數(shù)外部訪問(wèn)的；一個(gè)對(duì)象的封裝字段無(wú)法被該對(duì)象的方法以外的方法訪問(wèn)到。在所有的情況下，信息隱藏都可以幫助我們約束我們的程序，使其不發(fā)生意料之外的情況。

crawl函數(shù)爬到的鏈接在一個(gè)專有的goroutine中被發(fā)送到worklist中來(lái)避免死鎖。為了節(jié)省篇幅，這個(gè)例子的終止問(wèn)題我們先不進(jìn)行詳細(xì)闡述了。

練習(xí) 8.6： 為并發(fā)爬蟲(chóng)增加深度限制。也就是說(shuō)，如果用戶設(shè)置了depth=3，那么只有從首頁(yè)跳轉(zhuǎn)三次以內(nèi)能夠跳到的頁(yè)面才能被抓取到。

練習(xí) 8.7： 完成一個(gè)并發(fā)程序來(lái)創(chuàng)建一個(gè)線上網(wǎng)站的本地鏡像，把該站點(diǎn)的所有可達(dá)的頁(yè)面都抓取到本地硬盤(pán)。為了省事，我們這里可以只取出現(xiàn)在該域下的所有頁(yè)面（比如golang.org開(kāi)頭，譯注：外鏈的應(yīng)該就不算了。）當(dāng)然了，出現(xiàn)在頁(yè)面里的鏈接你也需要進(jìn)行一些處理，使其能夠在你的鏡像站點(diǎn)上進(jìn)行跳轉(zhuǎn)，而不是指向原始的鏈接。

譯注： 拓展閱讀 Handling 1 Million Requests per Minute with Go。