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