【正文】 e to data recently needed. In our context, temporal correlation occurs first because links tend to be repeated on the same page – we found that on average about 30% are duplicates, cf. Section , and second, because pages on a given host tend to be explored sequentially and they tend to share many links. For example, many pages on a Computer Science department server are likely to share links to other Computer Science departments in the world, notorious papers, etc. Because of these two factors, a cache that contains popular requests and recent 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 漢語(yǔ)翻譯 基于網(wǎng)絡(luò)爬蟲的有效 URL緩存 馬克 BMJ (國(guó)際版 ) 2021 概要： 要在網(wǎng)絡(luò)上爬行非常簡(jiǎn)單：基本的算法是：（ a）取得一個(gè)網(wǎng)頁(yè)（ b）解析它提取所有的鏈接 URLs（ c）對(duì)于所有沒有見過的 URLs 重復(fù)執(zhí)行（ a） （ c）。 一個(gè)非常重要的方法加速這個(gè)檢測(cè)就是用 cache（高速緩存），這個(gè)是把見過的 URLs 存入主內(nèi)存中的一個(gè)（動(dòng)態(tài)）子集中。 我們的主要的結(jié)論是 cache 是非常高效的 在我們的機(jī)制里，一個(gè)有大約50000 個(gè)入口的 cache 可以完成 80%的速率。因此，一個(gè)強(qiáng)大的搜索引擎技術(shù)有巨大的實(shí)際利益，在這個(gè)論文中，我們集中于一方面的搜索技術(shù)，也就是搜集網(wǎng)頁(yè)的過程，最終組成一個(gè)搜索引擎的文集。（估計(jì)有超過 20%） 如果把網(wǎng)頁(yè)看作圖中的節(jié)點(diǎn)，把超鏈接看作定向 的移動(dòng)在這些節(jié)點(diǎn)之間，那么網(wǎng)絡(luò)爬蟲就變成了一個(gè)進(jìn)程就像數(shù)學(xué)中的圖的遍歷一樣?，F(xiàn)在， Google 需要索引超過 30 億的網(wǎng)頁(yè)。如果我們認(rèn)為頁(yè)面改變?nèi)种换蛘吒?，那么有大約 7%的頁(yè)面每周會(huì)變。 一個(gè)非常重要的方法加速這個(gè)檢測(cè)就是用 cache（高速緩存），這個(gè)是 把見過的 URLs 存入主內(nèi)存中的一個(gè)（動(dòng)態(tài)）子集中。 這個(gè)論文像這樣組織的：第 2 部分討論在文學(xué)著作中幾種不同的爬行解決方案和什么樣的 cache 最適合他們 。第 6部分是我們推薦的實(shí)際算法和數(shù)據(jù)結(jié)構(gòu)關(guān)于 URLcache。 網(wǎng)絡(luò)爬蟲用網(wǎng)絡(luò)存檔雇員多個(gè)爬行進(jìn)程，每個(gè)一次性完成一個(gè)徹底 的爬行對(duì)于 64 個(gè) hosts 。這些不同的進(jìn)程通過文件系統(tǒng)通信。沒有責(zé)任通過 TCP 傳送這個(gè) URL給網(wǎng)絡(luò)爬蟲，有責(zé)任把這些 URLs 綁在一起減少 TCP 開銷。一般的，達(dá)到避免可以用維護(hù)一個(gè)發(fā)現(xiàn) URLs 的集合。在一個(gè)網(wǎng)絡(luò)環(huán)境中，也是分層的。另一方面，這種情況叫做 丟失或者失敗。 清楚的， cache 越大，越容易避免丟失。 時(shí)間相關(guān)性或地方的職權(quán)范圍。 一般的， caching成功有 2個(gè)原因： 不一致的請(qǐng)求。另一方面，算法必須選擇驅(qū)逐一個(gè)項(xiàng)目來(lái)空出空間來(lái)存放那個(gè)丟失的項(xiàng)目，或者不加入那個(gè)丟失的項(xiàng)目。 Caching術(shù)語(yǔ)就像下面： cache是內(nèi)存用來(lái)儲(chǔ)存同等大小的元素。 在大多數(shù)的計(jì)算機(jī)系統(tǒng)里面，內(nèi)存是分等級(jí)的，意思是，存在 2級(jí)或更多級(jí)的內(nèi)存，表現(xiàn)出不同的空間和速度。 任何網(wǎng)絡(luò)爬蟲必須維護(hù)一個(gè)集合，裝那些需要被下載的 URLs。 Mercator 使用了一個(gè)獨(dú)立的集合，通信網(wǎng)絡(luò)爬蟲進(jìn)程。 最初的 google 爬蟲，實(shí)現(xiàn)不同的爬蟲組件通過不同的進(jìn)程。 網(wǎng)絡(luò)爬蟲的出現(xiàn)幾乎和網(wǎng)絡(luò)同期，而且有很多的文獻(xiàn)描述了網(wǎng)絡(luò)爬蟲。第 4部分我們實(shí)現(xiàn)這些算法，在實(shí)驗(yàn)機(jī)制中。我們考慮所有實(shí)際的算法：隨機(jī)置換，靜態(tài) cache， LRU，和 CLOCK，和理論極限：透視 cache和極大的 cache。因此，步驟（ a）必須執(zhí)行大約每秒 1000次，成員檢測(cè)的步驟（ c）必須每秒執(zhí)行超過 10000次，并有非常大的數(shù)據(jù)儲(chǔ)存到主內(nèi)存中。 網(wǎng)絡(luò)的頁(yè)面改變很頻繁。 2種標(biāo)準(zhǔn)的策略是深度優(yōu)先算法和廣度優(yōu)先算法 他們?nèi)菀妆粚?shí)現(xiàn)所以在很多入門的算法課中都有教?；镜乃惴ㄊ牵? Fetch a page Parse it to extract all linked URLs For all the URLs not seen before， repeat（ a） (c) 網(wǎng)絡(luò)怕從一般開始于一些 種子 URLs。我們推測(cè)這個(gè)臨界點(diǎn)是固有的并且冒昧的解釋一下這個(gè)現(xiàn)象。 我們考慮所有實(shí)際的算法：隨機(jī)置換，靜態(tài) cache， LRU，和 CLOCK，和理論極限：透視 cache和極大的 cache。實(shí)際上，光是這兩個(gè)要素就意味著如果要進(jìn)行及時(shí)地，完全地爬行網(wǎng)絡(luò)，步驟（ a）必須每秒鐘執(zhí)行大約 1000 次，因此，成員檢測(cè)（ c）必須每秒鐘執(zhí)行超過 10000次，并有非常大的數(shù)據(jù)儲(chǔ)存到主內(nèi)存中。 and URL resolver processes convert relative into absolute URLs, which are then fed to the URL Server. The various processes municate via the file system. For the experiments described in this paper, we used the Mercator web crawler [22, 29]. Mercator uses a set of independent, municating web crawler processes. Each crawler process is responsible for a subset of all web servers。外文資料原文 Efficient URL Caching for World Wide Web Crawling Marc Najork BMJ (International Edition) 2021 Crawling the web is deceptively simple: the basic algorithm is (a)Fetch a page (b) Parse it to extract all linked URLs (c) For all the URLs not seen before, repeat (a)–(c). However, the size of the web (estimated at over 4 billion pages) and its rate of change (estimated at 7% per week) move this plan from a trivial programmi ng exercise to a serious algorithmic and system design challenge. Indeed, these two factors alone