邵曉文

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130022）

0 引言

進(jìn)入21 世紀(jì)以來(lái)，互聯(lián)網(wǎng)技術(shù)進(jìn)入了飛速發(fā)展階段，互聯(lián)網(wǎng)上的信息量成爆炸式增長(zhǎng)，谷歌、百度、雅虎等搜索引擎，每天都會(huì)抓住數(shù)以?xún)|計(jì)的網(wǎng)頁(yè)，不同領(lǐng)域、不同背景的用戶(hù)，對(duì)于信息的需求不同，盡管這些搜索引擎幫助我們抓取了互聯(lián)網(wǎng)上的大部分信息，但是返回的結(jié)果包含大量用戶(hù)不關(guān)心的網(wǎng)頁(yè)。網(wǎng)絡(luò)爬蟲(chóng)[1]是搜索引擎的基礎(chǔ)，目的是為了對(duì)互聯(lián)網(wǎng)中的海量數(shù)據(jù)進(jìn)行抓取，當(dāng)需要對(duì)具體網(wǎng)站（如知乎）數(shù)據(jù)進(jìn)行抓取，通用搜索引擎無(wú)法完成這部分工作，需要設(shè)計(jì)專(zhuān)門(mén)的主題爬蟲(chóng)[3-4]程序，自動(dòng)抓取特定網(wǎng)頁(yè)中的信息。

知乎作為國(guó)內(nèi)知名的問(wèn)答社區(qū)，連接著各行各業(yè)的用戶(hù)。用戶(hù)分享著彼此的知識(shí)、經(jīng)驗(yàn)和見(jiàn)解，為中文互聯(lián)網(wǎng)源源不斷的提供多種多樣的信息。目前知乎的用戶(hù)已經(jīng)突破1 億，但是知乎官方并沒(méi)有提供相應(yīng)的數(shù)據(jù)接口，以供使用。Python 語(yǔ)言常被用于爬蟲(chóng)程序編寫(xiě)[2]，但相比于Java 而言Python 的執(zhí)行效率低，并且Java 語(yǔ)言對(duì)多線程的支持更加完善。因此本文設(shè)計(jì)了一款基于Java 語(yǔ)言的多線程并發(fā)網(wǎng)絡(luò)爬蟲(chóng)，爬取知乎用戶(hù)的相關(guān)信息。實(shí)驗(yàn)結(jié)果表明：多線程爬蟲(chóng)，具有較快的爬取效率，可以更快地爬取數(shù)據(jù)。

1 爬蟲(chóng)簡(jiǎn)介

整個(gè)互聯(lián)網(wǎng)可以看成一個(gè)無(wú)限大的有向圖，網(wǎng)絡(luò)爬蟲(chóng)的抓取流程是以一個(gè)URL 為初始點(diǎn)，根據(jù)URL 發(fā)送請(qǐng)求，獲取對(duì)應(yīng)的HTML 頁(yè)面，提取出需要采集的信息保存，同時(shí)解析出更多的URL 加入U(xiǎn)RL 隊(duì)列，從而實(shí)現(xiàn)從一個(gè)點(diǎn)擴(kuò)展到整個(gè)網(wǎng)絡(luò)的過(guò)程。直到符合爬蟲(chóng)的停止條件。爬蟲(chóng)的抓取流程如圖1 所示。

圖1 普通爬蟲(chóng)的抓取流程

2 爬蟲(chóng)結(jié)構(gòu)設(shè)計(jì)

2.1 抓取的策略

知乎的用戶(hù)之間的關(guān)系可以看做一個(gè)有向圖，如圖2 所示。

圖2 知乎用戶(hù)關(guān)系示意圖

對(duì)圖的搜索主要有兩種方式，深度優(yōu)先搜索和寬度優(yōu)先搜索。深度優(yōu)先遍歷測(cè)試是指網(wǎng)絡(luò)爬蟲(chóng)會(huì)從起始頁(yè)開(kāi)始，一個(gè)鏈接一個(gè)鏈接跟蹤下去，處理完這條線路的鏈接之后，再轉(zhuǎn)入下一個(gè)起始頁(yè)，繼續(xù)跟蹤鏈接。寬度優(yōu)先策略是按照樹(shù)的層次進(jìn)行搜索，如果此層沒(méi)有搜索完成，不會(huì)進(jìn)入下一層搜索。即首先完成一個(gè)層次的搜索，其次再進(jìn)行下一層次，也稱(chēng)之為分層處理。

本文采用的是寬度優(yōu)先搜索。因?yàn)殡x種子URL比較近的，往往是重要的網(wǎng)頁(yè)，隨著瀏覽的不斷深入，所看到的網(wǎng)頁(yè)重要性會(huì)越來(lái)越低。寬度優(yōu)先搜索也有利于多爬蟲(chóng)的合作抓取。

知乎中的每個(gè)用戶(hù)都有唯一的Urltoken 與之對(duì)應(yīng)，首先選取一名知乎活躍用戶(hù)作為起點(diǎn)，使用httpclient 工具發(fā)送請(qǐng)求，返回JSON 格式的數(shù)據(jù)，提取用戶(hù)的相關(guān)信息存入MySQL 數(shù)據(jù)庫(kù)，同時(shí)獲取該用戶(hù)關(guān)注的用戶(hù)列表，用戶(hù)列表中的數(shù)據(jù)以Urltoken 的方式給出，通過(guò)Urltoken 組成新的URL 加入隊(duì)列。

2.2 隊(duì)列的設(shè)計(jì)

爬蟲(chóng)隊(duì)列的設(shè)計(jì)是網(wǎng)絡(luò)爬蟲(chóng)的關(guān)鍵部分，小型爬蟲(chóng)可以直接使用鏈表實(shí)現(xiàn)，但是需要爬取的數(shù)據(jù)量很大時(shí)，僅僅靠Java 自身提供的數(shù)據(jù)結(jié)構(gòu)是遠(yuǎn)遠(yuǎn)不夠的，并且當(dāng)爬取時(shí)間很長(zhǎng)時(shí)，爬蟲(chóng)程序不一定能夠在一次的啟動(dòng)過(guò)程中就完成所有爬取工作，可能需要重復(fù)啟動(dòng)多次，這就需要將隊(duì)列中的數(shù)據(jù)固化到硬盤(pán)中，否則再次啟動(dòng)爬蟲(chóng)，將重新從開(kāi)始節(jié)點(diǎn)爬取。因此這里選用Redis 數(shù)據(jù)庫(kù)來(lái)實(shí)現(xiàn)爬蟲(chóng)隊(duì)列。

Redis 是一款高性能的key-value 數(shù)據(jù)庫(kù)，主要具有以下特點(diǎn)：

●Redis 支持?jǐn)?shù)據(jù)的持久化，可以將內(nèi)存中的數(shù)據(jù)保存在磁盤(pán)中，重啟的時(shí)候可以再次加載進(jìn)行使用，這一點(diǎn)對(duì)網(wǎng)絡(luò)爬蟲(chóng)來(lái)說(shuō)非常重要。

●Redis 不僅僅支持簡(jiǎn)單的key-value 類(lèi)型的數(shù)據(jù)，同時(shí)還提供list、set、hash 等數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)。

●Redis 性能極高，讀取速度高達(dá)110000 次/s，寫(xiě)入速度高達(dá)81000 次/s。

因此Redis 非常適合用來(lái)做網(wǎng)絡(luò)爬蟲(chóng)的隊(duì)列，本文使用Redis 的List 結(jié)構(gòu)，作為爬蟲(chóng)程序的URL 隊(duì)列。

2.3 布隆過(guò)濾器

在采用深度優(yōu)先的爬取策略時(shí)，需要對(duì)已經(jīng)爬取過(guò)的URL 進(jìn)行過(guò)濾，避免重復(fù)爬取，可以使用Java 提供的哈希表對(duì)已經(jīng)爬取過(guò)的URL 進(jìn)行記錄，從而達(dá)到避免重復(fù)的效果。對(duì)于小型爬蟲(chóng)而言，通過(guò)Java 提供的哈希表來(lái)實(shí)現(xiàn)過(guò)濾器，能滿(mǎn)足需求。但是知乎的用戶(hù)數(shù)量已經(jīng)超過(guò)一億，當(dāng)爬取的數(shù)據(jù)量很大時(shí)，需要非常大的內(nèi)存空間，一般服務(wù)器很難滿(mǎn)足這樣的存儲(chǔ)需求。因此本文采用了布隆過(guò)濾器[5-6]來(lái)過(guò)濾已爬取的URL。

布隆過(guò)濾器是由巴頓·布隆于1970 年提出，它是一種數(shù)學(xué)工具，只需要哈希表的1/8～1/4 的大小就能解決同樣的問(wèn)題。它主要是由一個(gè)二進(jìn)制的向量和一系列的hash 函數(shù)組成。本文通過(guò)下面的示例說(shuō)明其工作原理。

利用內(nèi)存中的一個(gè)長(zhǎng)度是m 的位數(shù)組B，對(duì)其中所有位都置為0，如圖3 所示。

圖3 位數(shù)組的初始狀態(tài)

對(duì)于每一個(gè)URL 地址，選取8 個(gè)不同的隨機(jī)質(zhì)數(shù)，根據(jù)這8 個(gè)質(zhì)數(shù)，計(jì)算出八個(gè)不同的hash 值，并將位數(shù)組中對(duì)應(yīng)hash 值的位置設(shè)為1，如圖4 所示。

圖4 布隆過(guò)濾器的實(shí)現(xiàn)

對(duì)于5000 萬(wàn)級(jí)別的URL，布隆過(guò)濾器值占用200M 左右的空間，大大節(jié)省了存儲(chǔ)空間。

正如上文所述，當(dāng)爬取數(shù)據(jù)量很大，爬取時(shí)間很長(zhǎng)的時(shí)候，當(dāng)遇到爬蟲(chóng)程序意外終止的情況，再次啟動(dòng)爬蟲(chóng)程序，就得重新開(kāi)始爬取，對(duì)于過(guò)濾器也一樣，如果使用HashMap 或者Set，再次啟動(dòng)爬蟲(chóng)時(shí)，過(guò)濾器中的數(shù)據(jù)丟失，因此，鑒于前面對(duì)Redis 的介紹，這里采用Redis 的List 結(jié)構(gòu)來(lái)實(shí)現(xiàn)。

2.4 多線程爬蟲(chóng)

爬蟲(chóng)主要消耗三種資源：網(wǎng)絡(luò)帶寬、中央處理器和磁盤(pán)。三者中的任何一個(gè)都可能成為會(huì)爬蟲(chóng)程序的瓶頸。在這三者都無(wú)法控制的前提下，單線程爬蟲(chóng)的效率低下，爬取速度很慢。為了增加爬蟲(chóng)的效率，最直接方便的辦法就是使用多線程技術(shù)[7]并行抓取，Java 語(yǔ)言對(duì)多線程提供了很好的支持。在爬蟲(chóng)系統(tǒng)中，要處理的URL 隊(duì)列是唯一的，多個(gè)線程依次從隊(duì)列中取出URL，各自對(duì)用戶(hù)信息進(jìn)行抓取，再將用戶(hù)關(guān)注者的URL 加入隊(duì)列，因此，線程既是生產(chǎn)者也是消費(fèi)者，這里使用線程池來(lái)管理線程。

使用多線程并發(fā)爬取數(shù)據(jù)時(shí)可以大大提升爬取的效率，但同時(shí)也帶來(lái)數(shù)據(jù)競(jìng)爭(zhēng)的問(wèn)題。即存在同一塊內(nèi)存上，存在兩個(gè)并發(fā)的操作，其中至少有一個(gè)為寫(xiě)操作。數(shù)據(jù)競(jìng)爭(zhēng)會(huì)導(dǎo)致讀取的數(shù)據(jù)和預(yù)期的不一致。本文通過(guò)Redis 實(shí)現(xiàn)了URL 隊(duì)列和布隆過(guò)濾器，Redis 的基本操作，在并發(fā)環(huán)境下是具有原子性的，因此不用考慮數(shù)據(jù)競(jìng)爭(zhēng)。

2.5 計(jì)數(shù)器

本文的爬蟲(chóng)程序結(jié)束邏輯是使用了一個(gè)共享變量count 作為計(jì)數(shù)器，記錄已爬取的URL 數(shù)量，當(dāng)達(dá)到指定數(shù)量，就不再向URL 隊(duì)列中加入新的URL，直至將URL 隊(duì)列中的數(shù)據(jù)爬取完畢，URL 隊(duì)列為空，爬蟲(chóng)程序終止，因此爬取頁(yè)面的時(shí)間遠(yuǎn)遠(yuǎn)長(zhǎng)于向隊(duì)列中加入U(xiǎn)RL 的時(shí)間，因此不會(huì)出現(xiàn)URL 隊(duì)列為空，而count 沒(méi)有達(dá)到指定數(shù)量的情況。由于多線程的執(zhí)行順序使無(wú)法確定的，且線程之間的操作是相互透明的，因此對(duì)count 的操作是存在線程安全問(wèn)題的，會(huì)產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)的問(wèn)題。對(duì)此，通常的解決方案是將操作count 的臨界區(qū)通過(guò)Java 提供的同步鎖進(jìn)行保護(hù)，保證每一次只有一個(gè)線程修改count 變量，但是當(dāng)線程數(shù)量很多是，鎖機(jī)制會(huì)大大降低爬蟲(chóng)的效率。因此采用樂(lè)觀鎖來(lái)解決count 的數(shù)據(jù)競(jìng)爭(zhēng)問(wèn)題，樂(lè)觀鎖的主要元素是通過(guò)CAS（Compare And Swap）操作實(shí)現(xiàn)，使用Java 提供的原子操作類(lèi)：AtomicInteger 原子更新整型類(lèi)，該類(lèi)保證更新的原子性，性能高效，線程安全。本文的爬蟲(chóng)程序結(jié)構(gòu)如圖5 所示。

圖5 本文的爬蟲(chóng)架構(gòu)

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

表1

3.2 使用的Jar包工具

表2

3.3 抓取過(guò)程

首先從種子URL 開(kāi)始，使用HttpClient，根據(jù)URL，向服務(wù)器發(fā)送請(qǐng)求，知乎服務(wù)器響應(yīng)一段HTML代碼，其中包含用戶(hù)相關(guān)信息的JSON 格式數(shù)據(jù)，使用Jsoup 解析HTML 網(wǎng)頁(yè)，獲取用戶(hù)的信息，通過(guò)JsonObject，解析出用戶(hù)的相關(guān)數(shù)據(jù)并存入MySQL 數(shù)據(jù)庫(kù)，根據(jù)用戶(hù)的token，發(fā)起新的請(qǐng)求，獲取用戶(hù)關(guān)注列表，得到JSON 格式數(shù)據(jù)，解析出關(guān)注列表的Urltoken，組成新的URL，存入隊(duì)列，最終完成隊(duì)列的初始化工作。

完成初始化工作后，開(kāi)啟線程開(kāi)始爬取工作，從隊(duì)列中取出URL，判斷URL 是否已經(jīng)被爬取，如果沒(méi)有，就執(zhí)行爬取工作，否則重新從隊(duì)列中取出新的URL，當(dāng)URL 計(jì)數(shù)器達(dá)到指定數(shù)量時(shí)，停止向隊(duì)列中加入新的URL，繼續(xù)爬取隊(duì)列中剩下的URL，最終URL 隊(duì)列為空，結(jié)束爬蟲(chóng)程序。

3.4 實(shí)驗(yàn)結(jié)果分析

表3

實(shí)驗(yàn)結(jié)果表明：相比單線程爬蟲(chóng)的抓取速度遠(yuǎn)遠(yuǎn)小于多線程爬蟲(chóng)，因此本文設(shè)計(jì)的爬蟲(chóng)，能夠有效提高了爬蟲(chóng)的效率。

4 結(jié)語(yǔ)

本文的爬蟲(chóng)采用Java 語(yǔ)言針對(duì)知乎的用戶(hù)數(shù)據(jù)進(jìn)行抓取，設(shè)計(jì)了多線程爬蟲(chóng)架構(gòu)，實(shí)現(xiàn)了多數(shù)據(jù)的并發(fā)抓起，加快了爬取的速度，并使用了Redis 實(shí)現(xiàn)了URL隊(duì)列，提升了存取的效率。本文實(shí)現(xiàn)了布隆過(guò)濾器，過(guò)濾已爬取的URL，大大減少了內(nèi)存的消耗，放棄使用同步鎖，使用Java 提供的原子操作類(lèi)AtomicInteger，保證了線程的安全，提升了爬蟲(chóng)的效率，最終達(dá)到預(yù)期的爬取效果。