【正文】 版 ) 2021 概要： 要在網(wǎng)絡(luò)上爬行非常簡(jiǎn)單：基本的算法是：（ a）取得一個(gè)網(wǎng)頁(yè)（ b）解析它提取所有的鏈接 URLs（ c）對(duì)于所有沒有見過(guò)的 URLs 重復(fù)執(zhí)行（ a） （ c）。但是，網(wǎng)絡(luò)的大?。ü烙?jì)有超過(guò) 40 億的網(wǎng)頁(yè)）和他們變化的頻率（估計(jì)每周有7%的變化）使這個(gè)計(jì)劃由一個(gè)微不足道的設(shè)計(jì)習(xí)題變成一個(gè)非常嚴(yán)峻的算法和系統(tǒng)設(shè)計(jì)挑戰(zhàn)。實(shí)際上，光是這兩個(gè)要素就意味著如果要進(jìn)行及時(shí)地，完全地爬行網(wǎng)絡(luò)，步驟（ a）必須每秒鐘執(zhí)行大約 1000 次，因此，成員檢測(cè)（ c）必須每秒鐘執(zhí)行超過(guò) 10000次，并有非常大的數(shù)據(jù)儲(chǔ)存到主內(nèi)存中。這個(gè)要求有一個(gè)分布式構(gòu)造，使得成員檢測(cè)更加復(fù)雜。 一個(gè)非常重要的方法加速這個(gè)檢測(cè)就是用 cache（高速緩存），這個(gè)是把見過(guò)的 URLs 存入主內(nèi)存中的一個(gè)（動(dòng)態(tài)）子集中。這個(gè)論文最主要的成果就是仔細(xì)的研究了幾種關(guān)于網(wǎng)絡(luò)爬蟲的 URL緩存技術(shù)。 我們考慮所有實(shí)際的算法：隨機(jī)置換，靜態(tài) cache， LRU，和 CLOCK，和理論極限：透視 cache和極大的 cache。我們執(zhí)行了大約 1800次模擬，用不同的 cache 大小執(zhí)行這些算法，用真實(shí)的 log日志數(shù)據(jù)，獲取自一個(gè)非常大的 33 天的網(wǎng)絡(luò)爬行，大約執(zhí)行了超過(guò) 10 億次的請(qǐng)求。 我們的主要的結(jié)論是 cache 是非常高效的 在我們的機(jī)制里，一個(gè)有大約50000 個(gè)入口的 cache 可以完成 80%的速率。有趣的是，這 cache 的大小下降到一個(gè)臨界點(diǎn)：一個(gè)足夠的小一點(diǎn)的 cache 更有效當(dāng)一個(gè)足夠的大一點(diǎn)的 cache只能帶來(lái)很小的額外好處。我們推測(cè)這個(gè)臨界點(diǎn)是固有的并且冒昧的解釋一下這個(gè)現(xiàn)象。 皮尤 基金會(huì)最新的研究指出：“搜索引擎已經(jīng)成為互聯(lián)網(wǎng)用戶不可或缺的工具”，估計(jì)在 2021 年中期，初略有超過(guò) 1 半的美國(guó)人用網(wǎng)絡(luò)搜索獲取信息。因此，一個(gè)強(qiáng)大的搜索引擎技術(shù)有巨大的實(shí)際利益，在這個(gè)論文中，我們集中于一方面的搜索技術(shù)，也就是搜集網(wǎng)頁(yè)的過(guò)程，最終組成一個(gè)搜索引擎的文集。 搜索引擎搜集網(wǎng)頁(yè)通過(guò)很多途徑，他們中，直接提交 URL，回饋內(nèi)含物，然后從非 web源文件中提取 URL，但是大量的文集包含一個(gè)進(jìn)程叫 crawling 或者 SPIDERing，他們遞歸的探索互聯(lián)網(wǎng)?；镜乃惴ㄊ牵? Fetch a page Parse it to extract all linked URLs For all the URLs not seen before， repeat（ a） (c) 網(wǎng)絡(luò)怕從一般開始于一些 種子 URLs。有些時(shí)候網(wǎng)絡(luò)爬蟲開始于一個(gè)正確連接的頁(yè)面，或者一個(gè)目錄就像： ，但是因?yàn)檫@個(gè)原因相關(guān)的巨大的部分網(wǎng)絡(luò)資源無(wú)法被訪問到。（估計(jì)有超過(guò) 20%） 如果把網(wǎng)頁(yè)看作圖中的節(jié)點(diǎn)，把超鏈接看作定向 的移動(dòng)在這些節(jié)點(diǎn)之間，那么網(wǎng)絡(luò)爬蟲就變成了一個(gè)進(jìn)程就像數(shù)學(xué)中的圖的遍歷一樣。不同的遍歷策略決定著先不訪問哪個(gè)節(jié)點(diǎn)，下一個(gè)訪問哪個(gè)節(jié)點(diǎn)。 2種標(biāo)準(zhǔn)的策略是深度優(yōu)先算法和廣度優(yōu)先算法 他們?nèi)菀妆粚?shí)現(xiàn)所以在很多入門的算法課中都有教。 但是，在網(wǎng)絡(luò)上爬行并不是一個(gè)微不足道的設(shè)計(jì)習(xí)題，而是一個(gè)非常嚴(yán)峻的算法和系統(tǒng)設(shè)計(jì)挑戰(zhàn)因?yàn)橐韵?2點(diǎn)原因： 網(wǎng)絡(luò)非常的龐大。現(xiàn)在， Google 需要索引超過(guò) 30 億的網(wǎng)頁(yè)。很多研究都指出，在歷史上，網(wǎng)絡(luò)每 912個(gè)月都會(huì)增長(zhǎng)一倍。 網(wǎng)絡(luò)的頁(yè)面改變很頻繁。如果這個(gè)改變指的是任何改變，那么有 40%的網(wǎng)頁(yè)每周會(huì)改變。如果我們認(rèn)為頁(yè)面改變?nèi)种换蛘吒啵敲从写蠹s 7%的頁(yè)面每周會(huì)變。 這 2個(gè)要素意味著，要獲得及時(shí)的，完全的網(wǎng)頁(yè)快照，一個(gè)搜索引擎必須訪問 1億個(gè)網(wǎng)頁(yè)每天。因此，步驟（ a）必須執(zhí)行大約每秒 1000次，成員檢測(cè)的步驟（ c）必須每秒執(zhí)行超過(guò) 10000次，并有非常大的數(shù)據(jù)儲(chǔ)存到主內(nèi)存中。另外，網(wǎng)絡(luò)爬蟲一般使用一個(gè)分布式的構(gòu)造來(lái)平行地爬行更多的網(wǎng)頁(yè)，這使成員檢測(cè)更為復(fù)雜：這是可能的成員問題只能回答了一個(gè)同行節(jié)點(diǎn)，而不是當(dāng)?shù)亍? 一個(gè)非常重要的方法加速這個(gè)檢測(cè)就是用 cache（高速緩存），這個(gè)是 把見過(guò)的 URLs 存入主內(nèi)存中的一個(gè)（動(dòng)態(tài)）子集中。這個(gè)論文最主要的成果就是仔細(xì)的研究了幾種關(guān)于網(wǎng)絡(luò)爬蟲的 URL緩存技術(shù)。我們考慮所有實(shí)際的算法：隨機(jī)置換，靜態(tài) cache， LRU，和 CLOCK，和理論極限：透視 cache和極大的 cache。我們執(zhí)行了大約 1800次模擬，用不同的 cache 大小執(zhí)行這些算法，用真實(shí)的 log日志數(shù)據(jù)，獲取自一個(gè)非常大的 33 天的網(wǎng)絡(luò)爬行，大約執(zhí)行了超過(guò) 10 億次的請(qǐng)求。 這個(gè)論文像這樣組織的：第 2 部分討論在文學(xué)著作中幾種不同的爬行解決方案和什么樣的 cache 最適合他們 。第 3部分介紹關(guān)于一些 cache的技術(shù)和介紹了關(guān)于 cache幾種理論和實(shí)際算法。第 4部分我們實(shí)現(xiàn)這些算法，在實(shí)驗(yàn)機(jī)制中。第 5部分描述和討論模擬的結(jié)果。第 6部分是我們推薦的實(shí)際算法和數(shù)據(jù)結(jié)構(gòu)關(guān)于 URLcache。第 7部分是結(jié)論和指導(dǎo)關(guān)于促進(jìn)研究。 網(wǎng)絡(luò)爬蟲的出現(xiàn)幾乎和網(wǎng)絡(luò)同期，而且有很多的文獻(xiàn)描述了網(wǎng)絡(luò)爬蟲。在這個(gè)部分，我們呈現(xiàn)一個(gè)摘要關(guān)于這些爬蟲程序，并討論問什么大多數(shù)的網(wǎng)絡(luò)爬蟲會(huì)受益于 URL cache。 網(wǎng)絡(luò)爬蟲用網(wǎng)絡(luò)存檔雇員多個(gè)爬行進(jìn)程，每個(gè)一次性完成一個(gè)徹底 的爬行對(duì)于 64 個(gè) hosts 。爬蟲進(jìn)程儲(chǔ)存非本地的 URLs 到磁盤；在爬行的最后，一批工作將這些 URLs 加入到下個(gè)爬蟲的每個(gè) host的種子 sets 中。 最初的 google 爬蟲，實(shí)現(xiàn)不同的爬蟲組件通過(guò)不同的進(jìn)程。一個(gè)單獨(dú)的 URL服務(wù)器進(jìn)行維護(hù)需要下載的 URL的集合；爬蟲程序獲取的網(wǎng)頁(yè)；索引進(jìn)程提取關(guān)鍵字和超鏈接； URL 解決進(jìn)程將相對(duì)路徑轉(zhuǎn)換給絕對(duì)路徑。這些不同的進(jìn)程通過(guò)文件系統(tǒng)通信。 這個(gè)論文的中實(shí)驗(yàn)我們使用的 meractor 網(wǎng)絡(luò)爬蟲。 Mercator 使用了一個(gè)獨(dú)立的集合，通信網(wǎng)絡(luò)爬蟲進(jìn)程。每個(gè)爬蟲進(jìn)程都是一個(gè)有效的 web 服務(wù)器子集；URLs 的分配基于 URLs 主機(jī)組件。沒有責(zé)任通過(guò) TCP 傳送這個(gè) URL給網(wǎng)絡(luò)爬蟲，有責(zé)任把這些 URLs 綁在一起減少 TCP 開銷。我們描述 mercator 很多的細(xì)節(jié)在第 4部分。 任何網(wǎng)絡(luò)爬蟲必須維護(hù)一個(gè)集合，裝那些需要被下載的 URLs。此外，不能重復(fù)地下載同一個(gè) URL，必須要個(gè)方法避免加入 URLs 到集合中超過(guò)一次。一般的，達(dá)到避免可以用維護(hù)一個(gè)發(fā)現(xiàn) URLs 的集合。如果數(shù)據(jù)太多，可以存入磁盤，或者儲(chǔ)存經(jīng)常被訪問的 URLs。 在大多數(shù)的計(jì)算機(jī)系統(tǒng)里面，內(nèi)存是分等級(jí)的，意思是，存在 2級(jí)或更多級(jí)的內(nèi)存，表現(xiàn)出不同的空間和速度。舉個(gè)例，在一個(gè)典型的工作站里，有一個(gè)非常小但是非?？斓膬?nèi)存，一個(gè)大，但是比較慢的 RAM內(nèi)存，一個(gè)非常大膽是很慢的 disk內(nèi)存。在一個(gè)網(wǎng)絡(luò)環(huán)境中，也是分層的。 Caching就是一種想法儲(chǔ)存經(jīng)常用到的項(xiàng)目從慢速內(nèi)存到快速內(nèi)存。 Caching術(shù)語(yǔ)就像下面： cache是內(nèi)存用來(lái)儲(chǔ)存同等大小的元素。一個(gè) cache有 k的大小，那么可以儲(chǔ)存 k個(gè)項(xiàng)目 .在每個(gè)時(shí)間段 ,cache接受到來(lái)自一個(gè)項(xiàng)目的請(qǐng)求 .如果這個(gè)請(qǐng)求項(xiàng)目在這個(gè) cache 中，這種情況將會(huì)引發(fā)一個(gè)碰撞并且不需要進(jìn)一步的動(dòng)作。另一方面，這種情況叫做 丟失或者失敗。如果 cache 沒有 k 個(gè)項(xiàng)目，那個(gè)丟失的項(xiàng)目被加入 cache。另一方面，算法必須選擇驅(qū)逐一個(gè)項(xiàng)目來(lái)空出空間來(lái)存放那個(gè)丟失的項(xiàng)目，或者不加入那個(gè)丟失的項(xiàng)目。 Caching算法的目標(biāo)是最小化丟失的個(gè)數(shù)。 清楚的， cache 越大，越容易避免丟失。因此，一個(gè) caching 算法的性能要在看在一個(gè)給定大小的 cache中的丟失率。 一般的， caching成功有 2個(gè)原因： 不一致的請(qǐng)求。一些請(qǐng)求比其他一些請(qǐng)求多。 時(shí)間相關(guān)性或地方的職權(quán)范圍。