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