我最早寫(xiě)爬蟲(chóng)的時(shí)候覺(jué)得這玩意兒和數(shù)學(xué)八竿子打不著。無(wú)非就是發(fā)HTTP請(qǐng)求、解析HTML、把數(shù)據(jù)塞進(jìn)數(shù)據(jù)庫(kù)頂多再處理一下并發(fā)、反爬策略哪兒用得上圖論這種聽(tīng)起來(lái)就很學(xué)院的玩意兒直到有一次我寫(xiě)的一個(gè)抓取程序在中型站點(diǎn)上莫名卡死排查了一下午最后發(fā)現(xiàn)是一個(gè)URL參數(shù)在無(wú)限生成新鏈接程序在一個(gè)永遠(yuǎn)走不完的循環(huán)里空轉(zhuǎn)。那天晚上翻著圖論的筆記我突然意識(shí)到爬蟲(chóng)做得越深圖論就越繞不開(kāi)。這篇文章想聊清楚一件事圖論和網(wǎng)絡(luò)爬蟲(chóng)到底是怎么綁定在一起的。從網(wǎng)頁(yè)關(guān)系的圖模型到抓取順序背后的遍歷策略再到蜘蛛陷阱里的環(huán)檢測(cè)最后是PageRank這類鏈接分析算法怎么反過(guò)來(lái)指導(dǎo)爬蟲(chóng)干活。無(wú)論你是剛寫(xiě)完第一個(gè)爬蟲(chóng)的初學(xué)者還是正在為抓取效率頭疼的工程師這篇文章都能幫你在只會(huì)調(diào)庫(kù)寫(xiě)循環(huán)和真正理解爬蟲(chóng)原理之間跨過(guò)那個(gè)坎。1. 整個(gè)互聯(lián)網(wǎng)本來(lái)就是一張巨圖爬蟲(chóng)的數(shù)學(xué)底色1.1 網(wǎng)頁(yè)、鏈接和圖爬蟲(chóng)早就跑在圖上了先做一個(gè)非常簡(jiǎn)單的抽象把每一個(gè)網(wǎng)頁(yè)當(dāng)做一個(gè)節(jié)點(diǎn)把網(wǎng)頁(yè)里的每一個(gè)超鏈接當(dāng)做一條從當(dāng)前頁(yè)面指向目標(biāo)頁(yè)面的邊那么整個(gè)互聯(lián)網(wǎng)就是一張巨大的有向圖。這里的方向很關(guān)鍵A頁(yè)面鏈向B頁(yè)面并不代表B頁(yè)面會(huì)鏈回A頁(yè)面所以這是一張有向圖不能拿無(wú)向圖的思維去理解它。爬蟲(chóng)做的事情本質(zhì)上就是在這張有向圖上做遍歷和采樣。我們選定一批種子URL作為起點(diǎn)抓取頁(yè)面、解析出邊超鏈接、再沿著邊走向新的節(jié)點(diǎn)不斷重復(fù)。這個(gè)過(guò)程和你在圖上做深度優(yōu)先搜索、廣度優(yōu)先搜索沒(méi)有任何本質(zhì)區(qū)別只是邊上附帶了一個(gè)額外的動(dòng)作——下載并解析HTML。這個(gè)視角一旦建立起來(lái)很多問(wèn)題會(huì)變得清晰得多。為什么爬蟲(chóng)需要去重因?yàn)閳D里天然存在大量指向同一節(jié)點(diǎn)的多條路徑不維護(hù)一個(gè)visited集合就會(huì)重復(fù)抓取。為什么爬蟲(chóng)最怕蜘蛛陷阱因?yàn)閹Лh(huán)的圖會(huì)讓遍歷永遠(yuǎn)無(wú)法結(jié)束。為什么搜索引擎的結(jié)果排序如此重要因?yàn)閳D里某些節(jié)點(diǎn)就是比另一些節(jié)點(diǎn)承載了更多的流量權(quán)重。圖論不會(huì)直接幫你寫(xiě)出一個(gè)能跑的爬蟲(chóng)但它給了你一張地圖。你手上的爬蟲(chóng)框架只是交通工具而圖論告訴你目的地在哪個(gè)方向、路況如何、什么時(shí)候該掉頭。1.2 動(dòng)態(tài)、不完整、超大爬蟲(chóng)面對(duì)的不是教科書(shū)里的圖你可能在教科書(shū)里見(jiàn)過(guò)那種規(guī)規(guī)矩矩的圖節(jié)點(diǎn)有限、邊固定、結(jié)構(gòu)清楚。但互聯(lián)網(wǎng)這張圖完全不是這樣它有幾個(gè)和教科書(shū)截然不同的特征。第一它在持續(xù)變化。頁(yè)面會(huì)新增、刪除、改版超鏈接會(huì)失效今天存在的節(jié)點(diǎn)明天可能就返回404。爬蟲(chóng)永遠(yuǎn)在追趕一張不斷變化的快照無(wú)法拿到完整的全量圖。第二它的規(guī)模極其龐大。哪怕只是一個(gè)中型垂直站點(diǎn)的子圖節(jié)點(diǎn)數(shù)量也可能輕松達(dá)到百萬(wàn)級(jí)。搜索引擎面對(duì)的圖是百億甚至千億級(jí)節(jié)點(diǎn)的動(dòng)態(tài)網(wǎng)絡(luò)任何O(n2)級(jí)別的算法在這種規(guī)模上都是災(zāi)難。第三我們永遠(yuǎn)只能觀察到局部。爬蟲(chóng)不是上帝視角它只能通過(guò)已經(jīng)抓到的頁(yè)面發(fā)現(xiàn)新的鏈接視野永遠(yuǎn)受限于已探索的部分。這和圖論里的在線算法、采樣算法所面對(duì)的局面非常像。理解這三點(diǎn)你就能明白為什么爬蟲(chóng)工程里沒(méi)有那么多完美算法更多的是在效率和資源之間的妥協(xié)。教科書(shū)上的圖論算法往往假設(shè)擁有完整信息而爬蟲(chóng)場(chǎng)景要求把算法改造成可以接受不完整輸入、允許小概率出錯(cuò)的版本。這一點(diǎn)在后面談布隆過(guò)濾器和環(huán)檢測(cè)工程落地時(shí)你會(huì)有更深的體會(huì)。2. 抓取順序就是圖的遍歷策略從BFS到有優(yōu)先級(jí)的搜索2.1 BFS和DFS不只是教科書(shū)概念爬蟲(chóng)從種子URL出發(fā)解析頁(yè)面里的鏈接放進(jìn)待抓取隊(duì)列然后循環(huán)處理。這一步最基礎(chǔ)的策略選擇其實(shí)就是圖遍歷里的BFS和DFS。BFS用先進(jìn)先出的隊(duì)列一層一層往外擴(kuò)先抓離種子頁(yè)面近的、深度淺的URL。DFS用后進(jìn)先出的棧一條道走到黑適合在一個(gè)網(wǎng)站里深挖某個(gè)特定方向的內(nèi)容。不少爬蟲(chóng)新手寫(xiě)代碼的時(shí)候根本沒(méi)有區(qū)分過(guò)這兩者反正都是解析鏈接塞列表再來(lái)個(gè)循環(huán)但實(shí)際表現(xiàn)出來(lái)的行為差異非常大。維度BFS廣度優(yōu)先DFS深度優(yōu)先數(shù)據(jù)結(jié)構(gòu)FIFO隊(duì)列LIFO棧爬取效果優(yōu)先覆蓋站點(diǎn)首頁(yè)、列表頁(yè)容易鉆進(jìn)某個(gè)欄目出不來(lái)對(duì)目標(biāo)站點(diǎn)的壓力分布均勻相對(duì)友好可能短時(shí)間集中請(qǐng)求同一路徑觸發(fā)風(fēng)控典型場(chǎng)景通用爬蟲(chóng)、搜索引擎爬蟲(chóng)定向采集某個(gè)專欄、回溯歷史頁(yè)面我自己早期寫(xiě)爬蟲(chóng)時(shí)習(xí)慣用列表的append和pop(0)模擬隊(duì)列純BFS。后來(lái)發(fā)現(xiàn)對(duì)某些站點(diǎn)來(lái)說(shuō)BFS會(huì)抓太多低價(jià)值的列表頁(yè)而DFS又容易在深鏈里迷路最后選擇的是折中方案先BFS鋪幾層再對(duì)高價(jià)值子樹(shù)做有限深度的DFS。這個(gè)套路在垂直采集場(chǎng)景里很實(shí)用。2.2 帶權(quán)重的待抓隊(duì)列工程版的最佳優(yōu)先搜索純粹的BFS有一個(gè)天生的問(wèn)題它把所有相鄰節(jié)點(diǎn)一視同仁但工程上我們明明知道有些鏈接更值得抓。舉個(gè)例子一個(gè)新聞?wù)军c(diǎn)的首頁(yè)和欄目頁(yè)重要性遠(yuǎn)高于某個(gè)隨機(jī)文章的標(biāo)簽聚合頁(yè)一個(gè)包含大量出鏈的導(dǎo)航頁(yè)比一個(gè)孤零零的圖片頁(yè)更有抓取價(jià)值。如果待抓隊(duì)列只按先進(jìn)先出的順序處理重要頁(yè)面可能會(huì)被大量低價(jià)值頁(yè)面擠到后面。所以真實(shí)爬蟲(chóng)的待抓隊(duì)列幾乎都不會(huì)是樸素的FIFO而是帶權(quán)重的優(yōu)先隊(duì)列。每個(gè)URL根據(jù)某種啟發(fā)式規(guī)則算出一個(gè)分?jǐn)?shù)分?jǐn)?shù)高的先抓。這不是什么高深的技巧Scrapy里也有內(nèi)置的優(yōu)先級(jí)參數(shù)但我見(jiàn)過(guò)不少團(tuán)隊(duì)把這個(gè)參數(shù)當(dāng)作擺設(shè)。我的經(jīng)驗(yàn)是優(yōu)先級(jí)函數(shù)里至少可以包含這幾個(gè)信號(hào)URL所在域名的歷史數(shù)據(jù)質(zhì)量該域名下內(nèi)容頁(yè)占比高不高URL在已抓頁(yè)面中出現(xiàn)的位置首頁(yè)、正文區(qū)域里出現(xiàn)的鏈接比評(píng)論區(qū)、底部推薦的鏈接更有價(jià)值URL模式的匹配度符合已知內(nèi)容頁(yè)模式的URL直接加分頁(yè)面深度離種子頁(yè)面越遠(yuǎn)新鮮感越低但某些特定路徑例外。這個(gè)思路和圖論里的最佳優(yōu)先搜索異曲同工——用代價(jià)函數(shù)或價(jià)值函數(shù)指導(dǎo)搜索方向而不是機(jī)械地按深度鋪開(kāi)。所謂智能爬蟲(chóng)很大一部分智能就體現(xiàn)在這個(gè)優(yōu)先級(jí)的計(jì)算上。2.3 URL去重圖遍歷里的visited集合還有布隆過(guò)濾器圖遍歷一定離不開(kāi)visited集合爬蟲(chóng)也一樣。稍有規(guī)模的爬蟲(chóng)待去重的URL數(shù)量很快就會(huì)突破千萬(wàn)級(jí)別這時(shí)候如果直接用Python的set或者Redis的Set存儲(chǔ)每一個(gè)完整URL內(nèi)存和存儲(chǔ)成本都相當(dāng)可觀。我算過(guò)一筆賬一個(gè)URL平均按200字節(jié)算一億個(gè)URL就是20GB。哪怕壓縮存儲(chǔ)對(duì)在線服務(wù)來(lái)說(shuō)也是一筆不小的開(kāi)銷。這時(shí)候就該布隆過(guò)濾器上場(chǎng)了。布隆過(guò)濾器的核心思想是用一個(gè)位數(shù)組配合多個(gè)哈希函數(shù)來(lái)表示一個(gè)集合。插入一個(gè)URL時(shí)用k個(gè)哈希函數(shù)把它映射到位數(shù)組的k個(gè)位置全部置為1查詢時(shí)只要發(fā)現(xiàn)任何一個(gè)位置是0就說(shuō)明這個(gè)URL肯定沒(méi)被訪問(wèn)過(guò)。如果所有位置都是1那只能說(shuō)很可能訪問(wèn)過(guò)存在一定誤判率。誤判率也不是拍腦袋定的它和位數(shù)組長(zhǎng)度m、哈希函數(shù)個(gè)數(shù)k、已插入元素?cái)?shù)量n有關(guān)大約等于(1 - e^(-kn/m))^k。工程上常見(jiàn)做法是讓m/n約等于10k約等于7誤判率能壓到1%左右。這個(gè)代價(jià)完全可控?fù)Q來(lái)的是內(nèi)存占用降一個(gè)數(shù)量級(jí)。import mmh3 import math class BloomFilter: def __init__(self, capacity, error_rate0.01): self.bit_size int(-capacity * math.log(error_rate) / (math.log(2) ** 2)) self.k max(1, int(self.bit_size / capacity * math.log(2))) self.bits bytearray(math.ceil(self.bit_size / 8)) def _hashes(self, url): return [mmh3.hash(url.encode(), i) % self.bit_size for i in range(self.k)] def add(self, url): for h in self._hashes(url): self.bits[h // 8] | 1 (h % 8) def contains(self, url): return all(self.bits[h // 8] (1 (h % 8)) for h in self._hashes(url))上面是最簡(jiǎn)實(shí)現(xiàn)真正的生產(chǎn)環(huán)境可以直接用pybloom_live或者Redis的布隆模塊。這里想強(qiáng)調(diào)一個(gè)坑標(biāo)準(zhǔn)布隆過(guò)濾器不支持刪除操作。如果你抓某個(gè)URL失敗了想把它重新放回待抓隊(duì)列標(biāo)準(zhǔn)的布隆過(guò)濾器里它已經(jīng)留下了已訪問(wèn)標(biāo)記你沒(méi)法撤銷。我當(dāng)時(shí)的解決辦法是成功的URL進(jìn)布隆過(guò)濾器失敗的URL單獨(dú)記在一個(gè)帶過(guò)期時(shí)間的Redis Set里允許重試N次超過(guò)N次才放棄。這套組合比較穩(wěn)。3. 蜘蛛陷阱與環(huán)路檢測(cè)被圖論救活的爬蟲(chóng)3.1 蜘蛛陷阱的圖論本質(zhì)無(wú)窮路徑和環(huán)蜘蛛陷阱是每個(gè)爬蟲(chóng)工程師早晚會(huì)遇到的問(wèn)題。表現(xiàn)形式千奇百怪但圖論視角下無(wú)非兩種無(wú)窮路徑或者環(huán)。無(wú)窮路徑很好理解。站點(diǎn)通過(guò)動(dòng)態(tài)參數(shù)、日歷翻頁(yè)、排序組合等機(jī)制可以無(wú)止境地生成新URL。比如一個(gè)商品篩選頁(yè)把品牌、價(jià)格、顏色、尺寸的參數(shù)排列組合一下就能變出幾百萬(wàn)個(gè)URL再比如日歷組件可以一年一年往下翻翻到2050年還有新頁(yè)面。每個(gè)頁(yè)面內(nèi)容都大同小異但URL各不相同如果只靠字符串去重根本防不住。環(huán)則更陰險(xiǎn)。A頁(yè)面鏈向BB鏈向CC又鏈回A。程序在A→B→C→A的循環(huán)里開(kāi)心地跑著每次都會(huì)抓到相同或相近的內(nèi)容但不會(huì)報(bào)錯(cuò)、不會(huì)有異常就是一直空轉(zhuǎn)浪費(fèi)帶寬和存儲(chǔ)。很多新手遇到蜘蛛陷阱的第一反應(yīng)是加去重但去重只能解決URL完全相同的情況。面對(duì)參數(shù)排列組合和動(dòng)態(tài)token字符串級(jí)別的去重完全無(wú)效。這時(shí)候需要的是真正的圖論思維判斷遍歷路徑上是否出現(xiàn)了環(huán)路或者對(duì)路徑深度做硬限制。3.2 三色標(biāo)記法DFS環(huán)檢測(cè)的標(biāo)準(zhǔn)解法圖論里檢測(cè)有向圖是否有環(huán)最經(jīng)典的做法是在DFS過(guò)程中維護(hù)三種顏色狀態(tài)白色該節(jié)點(diǎn)還沒(méi)被訪問(wèn)灰色該節(jié)點(diǎn)在當(dāng)前遞歸棧中即正在被探索黑色該節(jié)點(diǎn)已經(jīng)完成所有子節(jié)點(diǎn)的探索不可能再形成環(huán)。如果在DFS過(guò)程中遇到一條邊指向一個(gè)灰色節(jié)點(diǎn)說(shuō)明我們找到了一個(gè)環(huán)。WHITE, GRAY, BLACK 0, 1, 2 def has_cycle(graph): color {node: WHITE for node in graph} def dfs(node): color[node] GRAY for nxt in graph.get(node, []): if color[nxt] GRAY: return True if color[nxt] WHITE and dfs(nxt): return True color[node] BLACK return False return any(color[node] WHITE and dfs(node) for node in graph)這段代碼在教科書(shū)圖上是沒(méi)問(wèn)題的但放到真實(shí)爬蟲(chóng)里直接套用會(huì)碰到一個(gè)很現(xiàn)實(shí)的問(wèn)題真實(shí)爬蟲(chóng)是分布式的、多線程的、異步的沒(méi)有一個(gè)統(tǒng)一的遞歸?？梢跃S護(hù)顏色狀態(tài)。你沒(méi)法在分布式環(huán)境下維護(hù)一個(gè)完整的當(dāng)前調(diào)用路徑。所以工程上需要把環(huán)檢測(cè)轉(zhuǎn)化成更容易落地的等價(jià)策略。我常用的手段是給每個(gè)請(qǐng)求附帶一條路徑上下文記錄當(dāng)前URL是從哪個(gè)頁(yè)面跳過(guò)來(lái)的、已經(jīng)連續(xù)跳了幾層、這條路徑上的URL列表是什么。如果新解析出的URL出現(xiàn)在當(dāng)前路徑里就說(shuō)明已經(jīng)踩進(jìn)環(huán)了停止沿這條路徑繼續(xù)擴(kuò)展。3.3 從算法到工程環(huán)檢測(cè)的真正落地姿勢(shì)算法歸算法工程落地還得靠幾板斧。我在處理蜘蛛陷阱時(shí)靠的不是單一招數(shù)而是組合策略。第一是URL標(biāo)準(zhǔn)化。把統(tǒng)計(jì)參數(shù)utm_source、from等、排序參數(shù)、session參數(shù)全部剔除只保留真正決定頁(yè)面內(nèi)容的參數(shù)。很多看起來(lái)不同的URL標(biāo)準(zhǔn)化之后其實(shí)是同一個(gè)頁(yè)面。第二是單站點(diǎn)路徑深度限制。在爬蟲(chóng)配置里對(duì)每個(gè)域名單獨(dú)設(shè)定最大深度限制比如首頁(yè)算第0層最多允許往下鉆5層。就算站點(diǎn)有無(wú)限翻頁(yè)的日歷深度限制也能保證程序在有限步內(nèi)收斂。第三是內(nèi)容相似度去重。這是對(duì)付URL不同但內(nèi)容相同類陷阱的有力手段。抓下來(lái)的HTML算一個(gè)simhash指紋或者抽取正文后算MD5摘要如果和最近一段時(shí)間抓過(guò)的內(nèi)容重復(fù)率過(guò)高就判定為低價(jià)值頁(yè)面不入庫(kù)也不擴(kuò)展其鏈接。這個(gè)方法在抓動(dòng)態(tài)頁(yè)面時(shí)尤其好用。第四是單域頁(yè)面上限。無(wú)論一個(gè)站點(diǎn)多么龐大設(shè)定單次抓取任務(wù)內(nèi)的頁(yè)面數(shù)量上限。比如一個(gè)域名最多抓2萬(wàn)個(gè)頁(yè)面到了就停。這是最簡(jiǎn)單粗暴但永遠(yuǎn)有效的兜底策略。想起那個(gè)讓我排查了一下午的日歷bug最終修復(fù)用的就是URL標(biāo)準(zhǔn)化白名單加內(nèi)容摘要去重雙管齊下。日歷URL后面的隨機(jī)token每次都不一樣字符串層面完全防不住但頁(yè)面正文摘要幾乎一模一樣內(nèi)容去重一抓一個(gè)準(zhǔn)。4. 抓完之后的圖分析PageRank和鏈接結(jié)構(gòu)4.1 PageRank的數(shù)學(xué)直覺(jué)和計(jì)算過(guò)程如果說(shuō)遍歷和環(huán)檢測(cè)是爬蟲(chóng)過(guò)程中的圖論那PageRank就是爬蟲(chóng)之后的圖論。早期的通用搜索引擎面臨的問(wèn)題很簡(jiǎn)單網(wǎng)頁(yè)這么多用戶輸入一個(gè)查詢哪個(gè)結(jié)果應(yīng)該排在前面PageRank的想法非常優(yōu)雅把互聯(lián)網(wǎng)想象成一個(gè)用戶隨機(jī)點(diǎn)擊鏈接的模型。一個(gè)用戶在某個(gè)網(wǎng)頁(yè)上以概率d點(diǎn)擊頁(yè)面里的一個(gè)隨機(jī)鏈接跳轉(zhuǎn)到下一頁(yè)以概率1-d直接跳到互聯(lián)網(wǎng)上任意一個(gè)隨機(jī)頁(yè)面。長(zhǎng)時(shí)間下來(lái)用戶停留在每個(gè)頁(yè)面上的概率就反映了這個(gè)頁(yè)面的重要程度。用圖論的數(shù)學(xué)語(yǔ)言說(shuō)PageRank就是這個(gè)馬爾可夫鏈的平穩(wěn)分布是轉(zhuǎn)移矩陣的主導(dǎo)特征向量。公式表達(dá)是PR(A) (1-d) d × Σ(PR(Ti) / C(Ti))其中Ti是鏈向A的所有頁(yè)面C(Ti)是Ti的出鏈數(shù)量d是阻尼因子一般取0.85。用代碼算就簡(jiǎn)單多了。大多數(shù)時(shí)候我不手寫(xiě)迭代直接套NetworkXimport networkx as nx G nx.DiGraph() G.add_edges_from([ (a, b), (b, c), (c, a), (d, a), (a, d), ]) pr nx.pagerank(G, alpha0.85, max_iter100, tol1e-06) print(pr)注意一個(gè)細(xì)節(jié)阻尼因子取0.85是經(jīng)驗(yàn)值它的含義是用戶大概有85%的概率繼續(xù)沿著鏈接點(diǎn)擊15%的概率隨機(jī)跳到別的頁(yè)面。這個(gè)值調(diào)大PageRank會(huì)更傾向于被高權(quán)重頁(yè)面鏈接的節(jié)點(diǎn)調(diào)小則會(huì)更傾向于入鏈數(shù)量多的節(jié)點(diǎn)。具體場(chǎng)景下值得多試幾組參數(shù)。4.2 讓PageRank反過(guò)來(lái)指導(dǎo)爬蟲(chóng)調(diào)度大多數(shù)人把PageRank理解成搜索引擎排名算法和爬蟲(chóng)沒(méi)什么直接關(guān)系。但實(shí)際上這是一個(gè)很好的閉環(huán)爬蟲(chóng)抓下來(lái)的鏈接結(jié)構(gòu)可以用來(lái)計(jì)算頁(yè)面重要度反過(guò)來(lái)重要度高的頁(yè)面應(yīng)該被更頻繁地重新抓取。我當(dāng)時(shí)接手的一個(gè)垂直資訊爬蟲(chóng)就遇到過(guò)這個(gè)問(wèn)題所有頁(yè)面統(tǒng)一更新頻率導(dǎo)致高價(jià)值頁(yè)面的更新被低價(jià)值頁(yè)面的抓取任務(wù)拖累。后來(lái)按PageRank把已抓頁(yè)面分成三檔高權(quán)重頁(yè)每天重抓中權(quán)重頁(yè)每周重抓低權(quán)重頁(yè)只在有新鏈接指向它時(shí)才抓。同樣的帶寬核心內(nèi)容的新鮮度明顯提升。這個(gè)思路對(duì)未抓取的URL同樣有效。當(dāng)我們估算一個(gè)未知URL的重要度時(shí)雖然沒(méi)法直接算PageRank但可以根據(jù)它出現(xiàn)在哪些頁(yè)面里做個(gè)近似——一個(gè)鏈接如果同時(shí)出現(xiàn)在多個(gè)高權(quán)重頁(yè)面的正文區(qū)域那它極大概率是個(gè)值得抓的頁(yè)面給它提高優(yōu)先級(jí)就對(duì)了。4.3 入度、強(qiáng)連通分量、社區(qū)發(fā)現(xiàn)爬蟲(chóng)工具箱里的其他圖算法PageRank之外圖論還給爬蟲(chóng)工程師備了不少趁手工具。入度和出度分析最直觀。一個(gè)頁(yè)面入鏈多說(shuō)明它被廣泛引用是權(quán)威頁(yè)一個(gè)頁(yè)面出鏈多說(shuō)明它是導(dǎo)航頁(yè)、目錄頁(yè)是爬蟲(chóng)擴(kuò)展路徑的樞紐。我經(jīng)常在抓完一輪后統(tǒng)計(jì)一下出入度分布快速找出站點(diǎn)里的門(mén)戶頁(yè)和內(nèi)容頁(yè)再針對(duì)不同頁(yè)面類型設(shè)計(jì)不同的抓取頻率。強(qiáng)連通分量檢測(cè)也很實(shí)用。站點(diǎn)之間的互鏈經(jīng)常形成集團(tuán)比如幾個(gè)垂直社區(qū)互相引用、互相推薦構(gòu)成一個(gè)緊密的強(qiáng)連通分量。這意味著抓取A站時(shí)很可能會(huì)順著鏈接發(fā)現(xiàn)B站、C站而且它們內(nèi)容高度相關(guān)。如果平臺(tái)對(duì)同一集團(tuán)內(nèi)的站點(diǎn)統(tǒng)一調(diào)度可以有效控制對(duì)同一內(nèi)容源的多路冗余抓取。社區(qū)發(fā)現(xiàn)算法則適合做垂直采集的主題聚類。把URL按鏈接關(guān)系聚成社區(qū)每個(gè)社區(qū)代表一個(gè)話題或一類業(yè)務(wù)爬蟲(chóng)可以按社區(qū)分配資源而不是一個(gè)域名一個(gè)域名機(jī)械地抓。這些分析不必實(shí)時(shí)跑離線批處理就夠。把已抓數(shù)據(jù)導(dǎo)出成圖結(jié)構(gòu)跑一遍分析把結(jié)果同步到在線存儲(chǔ)供調(diào)度模塊讀取。這個(gè)離線圖分析在線調(diào)度的架構(gòu)是性價(jià)比非常高的做法。5. 一次真實(shí)重構(gòu)把爬蟲(chóng)從無(wú)腦抓取改成圖驅(qū)動(dòng)5.1 問(wèn)題的表象是入庫(kù)率低根子是鏈路缺失當(dāng)時(shí)的情況是這樣一個(gè)垂直資訊聚合爬蟲(chóng)覆蓋幾十個(gè)站點(diǎn)每天抓幾十萬(wàn)頁(yè)面但真正能進(jìn)內(nèi)容庫(kù)、能被搜索引擎收錄的不到三成。大量帶寬和存儲(chǔ)都浪費(fèi)在低質(zhì)量的列表頁(yè)、標(biāo)簽頁(yè)、翻頁(yè)副本和動(dòng)態(tài)生成的相似頁(yè)面上。團(tuán)隊(duì)一開(kāi)始討論的方案都是加大反爬力度提高并發(fā)數(shù)多掛代理這些都是在抓得更快上做文章但根本問(wèn)題其實(shí)是我們根本不知道哪些頁(yè)面值得抓、哪些頁(yè)面抓了純屬浪費(fèi)。用圖論的話說(shuō)我們手里有一堆節(jié)點(diǎn)但完全沒(méi)利用節(jié)點(diǎn)之間的關(guān)系信息。后來(lái)我們做的事情本質(zhì)上就是把抓取從無(wú)腦BFS升級(jí)成圖驅(qū)動(dòng)的最優(yōu)搜索。5.2 圖建模和優(yōu)先隊(duì)列的改造路徑改造分四步走。第一步把已抓頁(yè)面建立成有向圖。節(jié)點(diǎn)是URL的標(biāo)準(zhǔn)化形式邊是頁(yè)面間的鏈接關(guān)系圖的存儲(chǔ)用的是離線導(dǎo)出的CSV加NetworkX分析。第二步離線跑圖分析。用PageRank給所有已抓頁(yè)面打分同時(shí)統(tǒng)計(jì)每個(gè)頁(yè)面的入度、出度、所在強(qiáng)連通分量等基礎(chǔ)指標(biāo)。分析結(jié)果寫(xiě)回Rediskey就是頁(yè)面URLvalue是JSON包含各種圖指標(biāo)。第三步改造待抓隊(duì)列的優(yōu)先級(jí)函數(shù)。對(duì)新URL做估算如果它出現(xiàn)在多個(gè)高權(quán)重頁(yè)面的正文區(qū)直接給高分如果它的URL模式和歷史低質(zhì)量頁(yè)面相似就給低分甚至直接過(guò)濾如果它所在的域名整體圖指標(biāo)很差那就延遲抓取。第四步動(dòng)態(tài)更新抓取計(jì)劃。每輪抓取結(jié)束后把新抓到的頁(yè)面加入圖模型增量更新相關(guān)頁(yè)面的權(quán)重讓調(diào)度策略可以跟著網(wǎng)絡(luò)結(jié)構(gòu)的變化走。改造上線后入庫(kù)率從不到三成提到了接近六成由于少抓了大量低價(jià)值頁(yè)面整體請(qǐng)求量下降被站點(diǎn)屏蔽的次數(shù)反而少了。更重要的是團(tuán)隊(duì)后續(xù)做內(nèi)容推薦、頁(yè)面更新調(diào)度時(shí)手里有了一套基于圖結(jié)構(gòu)的數(shù)據(jù)資產(chǎn)很多決策都變得有據(jù)可依。5.3 關(guān)于圖計(jì)算選型和工程落地的幾點(diǎn)經(jīng)驗(yàn)關(guān)于選型我的建議是先想清楚數(shù)據(jù)量級(jí)再?zèng)Q定上不上圖數(shù)據(jù)庫(kù)。百萬(wàn)節(jié)點(diǎn)以下NetworkX完全夠用離線算完導(dǎo)結(jié)果就行沒(méi)必要為了用了圖數(shù)據(jù)庫(kù)而上圖數(shù)據(jù)庫(kù)。千萬(wàn)級(jí)以上再考慮Neo4j或JanusGraph這類分布式圖數(shù)據(jù)庫(kù)。還有幾個(gè)實(shí)際踩過(guò)的坑可以分享。PageRank迭代次數(shù)不足會(huì)導(dǎo)致結(jié)果偏向初始值max_iter至少給100收斂容差tol給到1e-06不然排名會(huì)出現(xiàn)上輪結(jié)果慣性。強(qiáng)連通分量檢測(cè)在大圖上很吃內(nèi)存。我曾在千萬(wàn)級(jí)圖上跑tarjan算法直接把內(nèi)存打滿了。正確姿勢(shì)是先做抽樣驗(yàn)證確認(rèn)連通性預(yù)估沒(méi)問(wèn)題再在核心子圖上跑分析避免在異常圖上浪費(fèi)資源。不要把圖分析和在線抓取耦合在一起。離線分析和在線調(diào)度必須解耦圖分析跑掛了不能影響抓取服務(wù)繼續(xù)運(yùn)行。我們當(dāng)時(shí)的做法是圖分析結(jié)果寫(xiě)Redis抓取服務(wù)只讀Redis里的結(jié)果如果分析結(jié)果過(guò)期抓取服務(wù)自動(dòng)退化成BFS模式保證整體可用性。最后再分享一個(gè)小技巧寫(xiě)爬蟲(chóng)之前先別急著寫(xiě)代碼?；ò胄r(shí)把目標(biāo)網(wǎng)絡(luò)的圖結(jié)構(gòu)在腦子里過(guò)一遍甚至手畫(huà)一張草圖種子頁(yè)面有哪些、哪些頁(yè)面是樞紐頁(yè)、哪些頁(yè)面可能形成環(huán)、哪些頁(yè)面才有真實(shí)價(jià)值。這個(gè)過(guò)程就像打仗前看地圖畫(huà)完之后你寫(xiě)代碼的思路會(huì)完全不一樣。另外遇到爬蟲(chóng)難題時(shí)可以多問(wèn)自己一句這個(gè)問(wèn)題能不能建模成圖問(wèn)題URL無(wú)限生成就是無(wú)窮路徑抓取卡死就是環(huán)抓取質(zhì)量差就是節(jié)點(diǎn)權(quán)重沒(méi)算對(duì)抓取浪費(fèi)資源就是沒(méi)做社區(qū)聚類。把問(wèn)題翻譯成圖論語(yǔ)言能用的成熟算法和工具就多出來(lái)了。這大概就是數(shù)學(xué)之美在工程里最實(shí)在的體現(xiàn)——它不直接給你答案但幫你把問(wèn)題看清楚。