Efficient URL Caching for World Wide Web Crawling
Andrei Z. Broder
IBM TJ Watson Research Center
19 Skyline Dr
Hawthorne, NY 10532
abroder@us.ibm.com
Marc Najork
Microsoft Research
1065 La Avenida
Mountain View, CA 94043
najork@microsoft.com
Janet L. Wiener
Hewlett Packard Labs
1501 Page Mill Road
Palo Alto, CA 94304
janet.wiener@hp.com
ABSTRACT
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 programming exercise to a serious algorithmic and system design challenge. Indeed, these two factors alone imply that for a reasonably fresh and complete crawl of the web, step (a) must be executed about a thousand times per second, and thus the membership test (c) must be done well over ten thousand times per second against a set too large to store in main memory. This requires a distributed architecture, which further complicates the membership test.
A crucial way to speed up the test is to cache, that is, to store in main memory a (dynamic) subset of the “seen” URLs. The main goal of this paper is to carefully investigate several URL caching techniques for web crawling. We consider both practical algorithms: random replacement, static cache, LRU, and CLOCK, and theoretical limits: clairvoyant caching and infinite cache. We performed about 1,800 simulations using these algorithms with various cache sizes, using actual log data extracted from a massive 33 day web crawl that issued over one billion HTTP requests. Our main conclusion is that caching is very effective – in our setup, a cache of roughly 50,000 entries can achieve a hit rate of almost 80%. Interestingly, this cache size falls at a critical point: a substantially smaller cache is much less effective while a substantially larger cache brings little additional benefit. We conjecture that such critical points are inherent to our problem and venture an explanation for this phenomenon.
1. INTRODUCTION
A recent Pew Foundation study [31] states that “Search engines have become an indispensable utility for Internet users” and estimates that as of mid-2002, slightly over 50% of all Americans have used web search to find information. Hence, the technology that powers web search is of enormous practical interest. In this paper, we concentrate on one aspect of the search technology, namely the process of collecting web pages that eventually constitute the search engine corpus.
Search engines collect pages in many ways, among them direct URL submission, paid inclusion, and URL extraction from nonweb sources, but the bulk of the corpus is obtained by recursively exploring the web, a process known as crawling or SPIDERing. 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)
Crawling typically starts from a set of seed URLs, made up of URLs obtained by other means as described above and/or made up of URLs collected during previous crawls. Sometimes crawls are started from a single well connected page, or a directory such as yahoo.com, but in this case a relatively large portion of the web (estimated at over 20%) is never reached. See [9] for a discussion of the graph structure of the web that leads to this phenomenon.
If we view web pages as nodes in a graph, and hyperlinks as directed edges among these nodes, then crawling becomes a process known in mathematical circles as graph traversal. Various strategies for graph traversal differ in their choice of which node among the nodes not yet explored to explore next. Two standard strategies for graph traversal are Depth First Search (DFS) and Breadth First Search (BFS) – they are easy to implement and taught in many introductory algorithms classes. (See for instance [34]).
However, crawling the web is not a trivial programming exercise but a serious algorithmic and system design challenge because of the following two factors.
1. The web is very large. Currently, Google [20] claims to have indexed over 3 billion pages. Various studies [3, 27, 28] have indicated that, historically, the web has doubled every 9-12 months.
2. Web pages are changing rapidly. If “change” means “any change”, then about 40% of all web pages change weekly [12]. Even if we consider only pages that change by a third or more, about 7% of all web pages change weekly [17].
These two factors imply that to obtain a reasonably fresh and 679 complete snapshot of the web, a search engine must crawl at least 100 million pages per day. Therefore, step (a) must be executed about 1,000 times per second, and the membership test in step (c) must be done well over ten thousand times per second, against a set of URLs that is too large to store in main memory. In addition, crawlers typically use a distributed architecture to crawl more pages in parallel, which further complicates the membership test: it is possible that the membership question can only be answered by a peer node, not locally.
A crucial way to speed up the membership test is to cache a (dynamic) subset of the “seen” URLs in main memory. The main goal of this paper is to investigate in depth several URL caching techniques for web crawling. We examined four practical techniques: random replacement, static cache, LRU, and CLOCK, and compared them against two theoretical limits: clairvoyant caching and infinite cache when run against a trace of a web crawl that issued over one billion HTTP requests. We found that simple caching techniques are extremely effective even at relatively small cache sizes such as 50,000 entries and show how thes
全文共32945字，剩余内容已隐藏，支付完成后下载完整资料
用于万维网抓取的高效URL缓存
Andrei Z.Broder
IBM TJ 华盛顿研究中心
19天际线博士
Marc Najork
微软研究院
1065 La Avenida
Mountainc View,CA 94043
Janet L.Wiener
Hewlett Packard Labs
1501 Page Mill Road
Palo Alto,CA 94304
Janet.wiener@hp.com
摘要：
抓取网页的过程看似简单，它的基本算法是：（a）获取网页（b）解析网页以提取所有的URL(c)对于之前从未出现的URL，重复（a）-（c）。然而，网页的数量（估计超过40亿页）及其变化率（估计每周7%）将本来简单的编程过程变成了一项复杂的算法和系统设计的挑战。实际上，这两个因素本身就意味着对于爬取完整的网页，步骤（a）必须每秒执行大约1000次，在此基础上步骤（c）必须每次执行超过1万次，但这会导致数据的集合太大以至于难以在主存中存储。这需要分布式结构，但会使得上述步骤更加复杂。
加速的一个关键方法是使用缓存，即在主存中存储已经获取的URL的（动态）子集。本文的主要目标是详细研究几种用于Web爬虫的URL缓存技术。我们兼具考虑了实用的算法：随机替换和静态缓存，LRU和CLOCK，以及理论限制：透视缓存和无限缓存。我们使用各种缓存大小不同的算法和实际记录的数据大约进行了1800次模拟，这些大量的数据是我们在33天中发出超过10亿次的http请求得到的。我们的主要结论是使用缓存非常有效。在我们的设置中，一个大约有50000个记录的缓存可以达到接近80％的命中率。有趣的是，这个缓存大小处于一个关键点：一个比它小的缓存效率要低得多，而一个比它大的缓存也几乎带来不了什么额外收益。我们推测这个关键点是我们的问题所固有的并大胆地解释这一现象。
1.介绍
皮尤基金会最近的一项研究[31]指出,“搜索引擎已成为互联网用户不可或缺的实用工具”，并估计截至2002年中期，略超过50％的美国人使用网络搜索来查找信息。因此，支持网络搜索的技术具有巨大的实际意义。在本文中，我们专注于搜索技术的一个方面，也就是收集最终组成了搜索引擎数据库的网页。
搜索引擎以多种方式收集页面，其中包括直接URL提交，付费包含和从非网页资源提取URL，但是大部分数据库的内容是通过递归浏览网络获得的，这一过程称为爬虫或SPIDER。 基本算法是
- 抓取一个网页
- 解析它链接的所有URL
- 对于之前所有没有出现的URL,重复（a）-（c）步骤
爬虫通常从一组种子URL开始，这些URL由通过上述其他方式获得的URL和先前爬行时收集的URL组成。有时，爬虫是从单个连接良好的页面或yahoo.com等目录开始的，但在这种情况下，Web页面中相当大的一部分（估计超过20%）是无法爬行到的。有关导致此现象的网页图形结构的讨论，请参见[9]。
如果我们将网页视为图形中的节点，并将超链接视为这些节点之间的有向边，则爬行可以视为数学循环中已知的图遍历的过程。用于图遍历的各种策略在它们对尚未探索的节点中的哪个节点的选择方面存在差异。图遍历的两个标准方法是深度优先搜索（DFS）和广度优先搜索（BFS），它们容易在许多算法入门课中实现和教授。（参见例如[34]）。
但是，爬虫的编程过程并不简单，它需要复杂的算法和系统设计，因为有以下两个因素：
- 网页数量非常大。目前，谷歌[20]声称索引超过30亿页。各种研究[3,27,28]表明，从历史上看，网页的数量每9-12个月翻一番。
- 网页正在迅速变化。 如果“改变”是指“任何改变”，那么大约40％的网页每周都会改变[12]。 即使我们考虑那些只改变三分之一或更多的页面，还有大约7％的网页每周都会改变[17]。
这两个因素意味着要获得一个相当新鲜且完整的网页，搜索引擎必须每天抓取至少1亿页。因此，前面所提的步骤（a）必须每秒执行大约1,000次，并且步骤（c）中的过程必须每秒完成超过一万次，但这会导致URL的集合太大而不能存储在主存中。此外，爬虫通常使用分布式体系结构来并行抓取更多页面，这进一步使步骤变得复杂：步骤中出现的问题可能只能由对等的节点应答，而不能在本地应答。
加速步骤的一个关键方法是在主内存中缓存已经发现的URL的（动态）子集。 本文的主要目的是深入研究几种用于Web爬虫的URL缓存技术。我们考察了四种实用的技术：随机替换，静态缓存，LRU和CLOCK，并将它们与两个理论限制：透视缓存和无限缓存对照，当针对发出超过10亿个HTTP请求的Web爬网的痕迹运行时。 我们发现简单的缓存技术尤其对相对较小的缓存（如50,000条记录）非常有效，并展示了这些缓存怎么被有效地使用。
本文的结构如下：第2节讨论了文献中提出的各种爬虫解决方案以及在这些方案中缓存怎么适配。第3节介绍了缓存技术，并涉及了几种用于缓存的理论和实用算法。我们在第4节中描述的实验设置中实现了这些算法。我们在第5节描述和讨论了模拟爬虫的结果，我们对URL缓存的实用算法和数据结构的建议见第6节。第7节包含了我们的结论和进一步研究的方向。
2.抓取
Web爬虫几乎与Web本身一样古老，并且文献中描述了许多爬虫系统。 在本节中，我们将对这些抓取工具进行简要考查（按历史顺序），然后讨论为什么大多数抓取工具都可以从URL缓存中受益。
Internet Archive [10]使用了多个爬虫进程，每个进程一次对64个主机进行详细的爬行。爬过程将非本地URL保存到磁盘;在爬虫结束时，批处理作业会将这些URL添加到下一次爬行的每个主机的种子集中。
[7]中描述的原始Google抓取工具将不同的抓取工具组件实现为不同的进程。 单个URL服务器进程维护要下载的URL集;抓取进程获取页面;索引过程提取单词和链接;和URL解析程序进程将相对转换为绝对URL，然后将其提供给URL Server。各种进程通过文件系统进行通信。
对于本文中描述的实验，我们使用了Mercator网络爬虫[22,29]。 Mercator使用一组独立的，通信的Web爬虫程序。每个爬虫程序进程负责所有Web服务器的子集;为爬虫程序进程分配基于URL主机组件的哈希表。发现其中没有意义的URL通过TCP将此URL发送给负责它的爬虫部分，将URL按批处理以最小化TCP开销。我们在第4节中更详细地描述了Mercator。
Cho和Garcia-Molina的爬虫[13]与Mercator相似。该系统由多个独立，通信的Web爬虫程序（称为“C-procs”）组成。 Cho和Garcia-Molina考虑用于划分URL空间的不同方案，包括基于URL（基于整个URL的散列将URL分配给C-proc），基于站点（将URL分配给基于C-proc的URL）， 在URL的主机部分的散列上和分层（根据URL的某些属性（例如其顶级域）将URL分配给C-proc）。
WebFountain爬虫[16]也由一组独立的，通信的爬虫程序（“蚂蚁”）组成。没有意义的URL会被发送到专用进程（“控制器”），该进程将URL转发到相应的蚂蚁。
UbiCrawler（以前称为Trovatore）[4,5]也由多个独立，通信的网络爬虫程序组成。它还使用一个控制器进程来监视爬虫进程，检测进程故障，并将故障交给指定程序处理。。
Shkapenyuk和Suel的爬虫[35]类似于Google的;不同的爬虫组件实现为不同的进程。“爬虫应用程序”维护要下载的URL集，并安排下载它们的顺序。它将下载请求发送到“爬虫管理器”，后者将它们转发到“下载程序”进程池。下载程序进程获取页面并将其保存到NFS挂载的文件系统。爬虫应用程序读取这些已保存的页面，提取其中包含的所有链接，并将它们添加到要下载的URL集中。
任何Web爬虫程序都必须维护要下载的URL集合。此外，由于一遍又一遍地下载相同的URL是不可接受的，因此必须有一种方法可以避免多次向集合中添加URL。通常，通过维护一组发现的URL来实现避免，这些URL覆盖边界中的URL以及已经下载的URL。
如果这个集合太大而无法容纳在内存中（考虑到有数十亿个有效的URL，它经常是这样），它存储在磁盘上并在内存中缓存流行的URL是一个胜利：缓存允许爬虫丢弃大部分 的URL而不必查阅基于磁盘的集。
上面描述的许多分布式网络爬虫，即Mercator [29]，WebFountain [16]，UbiCrawler [4]以及Cho和Molina的爬虫[13]，都包含协作爬行过程，每个过程都下载网页，提取它们的链接，并将这些链接发送到负责它的对等爬网过程。 但是，不需要多次向对等爬网进程发送URL。在将URL发送到对等爬虫之前维护URL的缓存并咨询缓存对于减少向对等爬虫的传输大有帮助，正如我们在本文的其余部分中所示。
3.缓存
在大多数计算机系统中，存储是分层的，即存在两个或更多级别的存储器，他们在大小和速度方面有不同的权重。例如，在典型的工作站中，存在非常小但非常快的片上存储器，更大但更慢的RAM存储器，以及非常大且更慢的磁盘存储器。 在网络环境中，层次结构继续使用网络可访问存储，依此类推。 缓存是将较慢的内存中的常用项目存储在更快的内存中的想法。在适当的情况下，缓存大大提高了整个系统的性能，因此它是操作系统设计的基本技术，在任何标准教科书中都会详细讨论[21,37]。 在Web上下文中，经常提到缓存。在Web代理缓存网页的上下文中[26，第11章]。在我们的网络爬虫上下文中，由于访问过的URL数量太大而无法存储在主内存中，因此我们将访问过的URL集合存储在磁盘上，并将一小部分缓存在主内存中。
缓存术语如下：缓存是用于存储大小相等的原子项的内存。如果缓存最多可以存储k个项目，则缓存的大小为k.1。在每个单位时间，缓存接收对项目的请求。如果请求的项目在缓存中，则该情况称为命中，不需要进一步的操作。否则，这种情况称为未命中或故障。如果缓存少于k个项目，则将错过的项目添加到缓存中。否则，算法必须选择从缓存中逐出项目以为错过的项目腾出空间，或者不添加错过的项目。缓存策略或缓存算法决定逐出哪个项目。缓存算法的目标是最小化未命中数。
显然，缓存越大，越容易避免未命中。因此，高速缓存算法的性能的特征在于给定大小高速缓存的未命中率。通常，缓存成功有两个原因：
-请求的不一致性。有些请求比其他请求更受欢迎。例如，在我们的上下文中，指向yahoo.com的链接比作者主页的链接更常见。
-时间相关性或参考位置。当前请求更有可能重复最近发出的请求，而不是很久以前提出的请求。 后一术语来自计算机存储器模型-现在所需的数据可能在地址空间中接近最近需要的数据。在我们的上下文中，时间关联首先发生，因为链接往往在同一页面上重复-我们发现平均约30％是重复的，参见 第4.2节和第二节，因为给定主机上的页面倾向于按顺序进行探索，并且它们倾向于共享许多链接。例如，计算机科学部门服务器上的许多页面可能与世界上其他计算机科学部门共享链接，臭名昭着的论文等。
由于这两个因素，包含常用请求和最近请求的缓存可能比任意缓存执行得更好。 缓存算法试图以各种方式捕获这种直觉。
我们现在描述一些标准的缓存算法，我们在第5节中评估它们的性能。
3.1无限缓存（INFINITE）
这是一种理论算法，假设缓存的大小大于不同请求的数量。
3.2透视缓存（MIN）
35年前，L#39;aszl#39;o Belady [2]表明，如果提前知道整个请求序列（换句话说，算法是透视的），那么最好的策略是逐出下一个请求的项目 是最远的时间。 该理论算法表示为MIN，因为它在任何序列上实现了最小数量的未命中，因此它提供了对性能的严格限制。
3.3最近最少使用（LRU）
LRU算法驱逐缓存中未被请求最长时间的项目。LRU的直觉是，过去很长一段时间内不需要的物品很可能在将来很长一段时间内不需要，因此Belady算法的精神将最小化未命中的数量。
尽管有“过去表现不能保证未来结果”的警告，但令人遗憾的是，目前的股票市场已经证实，在实践中，LRU通常非常有效。但是，它需要维护请求的优先级队列。该队列具有处理时间成本和存储器成本。后者通常在项目很大的缓存情况下被忽略。
3.4时钟
CLOCK是一种流行的近似LRU，发明于60年代后期[15]。标记位M0;M1;Mk对应于当前在大小为k的缓存中的项目。该数组被视为一个圆，即第一个位置跟在最后一个位置。时钟句柄指向缓存中的一个项目。当请求X到达时，如果项目X在高速缓存中，则其标记位被打开。否则，手柄顺序移动通过阵列，关闭标记位，直到找到未标记的位置。对应于未标记位置的高速缓存项被驱逐并由X代替。
3.5随机替换（RANDOM）
随机替换（RANDOM）完全忽略了过去。如果请求的项目不在缓存中，则从缓存中驱逐并替换随机项。
在大多数实际情况中，随机替换比CLOCK表现更差但不会更糟。我们的结果表现出类似的模式，如第5节所示.RANDOM可以在没有任何额外空间成本的情况下实现; 见第6节。
3.6静态缓存（STATIC）
如果我们假设每个项目具有一定的
全文共10771字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[862]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
