讲义集外文原文

1、外文资料原文Efficient URL Caching for World Wide Web CrawlingMarc NajorkBMJ (ernational Edition)2009Crawling 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 (esti

2、mated at over 4 billion pages) and its rate of change (estimated at 7% perk) move this plan from a trivial programming exercise to a serious algorithmic and systemdesign challenge., these two factors alone implyt for a reasonably fresh and completecrawl of the web, step (a) must be executed abouhous

3、and times per second, and thus themembership test (c) must be dell over ten thousand times per second against a set toolarge to store in main memory. This requires a distributed architecture, which furthercomplicates the membership test.A crul way to speed up the test is to cache,t is, to storeaemor

4、y a(dynamic) subset of the “seen” URLs. The main goal of this pr is to carefully investigateseveral URL caching techniques for web crawling. We consider both practical algorithms:random replacement, sic cache, LRU, and CLOCK, and theoretical limits: clairvoyantcaching and infinite cache.erformed abo

5、ut 1,800 simulations using these algorithms withvarious cache sizes, using actual log data extracted from a massive 33 day web crawlt iedover one billion HTTP requests. Our mainist caching is very effective in oursetup, a cache of roughly 50,000 entries can achieve a hit rate of almost 80%.erestingl

6、y, thiscache size fallsritical po: a substantially smaller cache is much less effective while asubstantially larger cache brings little additional benefit. We conjecturet such critical posare inherent to our problem and venture an explanation for this phenome.1.RODUCTIONA recent Pew Foundation study

7、 31 sest “Search engines havee anindispensable utility forernet users” and estimatest as of mid-2002, slightly over 50% ofall Americans have used web search to find information. Hence, the technologytersweb search is of enormous practical search technology, namely the prosearch engine corpus.erest.h

8、is pr, we concentrate oe aspect of thes of collecting wgest eventually constitute theSearch engines collect pages, and URL extraction fromany ways, among them direct URL submis, paidincluweb sour, but the bulk of the corpus is obtained byrecursively exploring the web, a proiss known as crawling or S

9、ERing. The basic algorithm(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.So

10、metimes crawls are started from a single well connected page, or a directory such as, buthis case a relatively large portion of the web (estimated at over 20%) isnever reached. See 9 for a discusof the graph structure of the webt leads to thisphenome.If we view wthese nodes, then crawlingges as node

11、s in a graph, and hyperlinks as directed edges amonges a pros knownathematical circles as graph traversal.Various strategies fraph traversal differheir choice of which node among the nodes notyet explored to explore next. Two standard strategies fraph traversal are DepthSearch(DFS) and BreadthSearch

12、 (BFS) they are easy to implement and taught in manyroductory algorithms classes. (See for instance 34).However, crawling the web is not a trivial programming exercise but a seriousalgorithmic and system design challenge because of the followino factors.1. The web is very large. Currently, pages. Va

13、rious studies 3, 27, 28 have indicated9-12 months.20 claims to have indexed over 3 billiont, historically, the web has doubled every2. Wges are changing raly. If “change” means “any change”, then about 40%of all wges changekly 12. Even if we consider only pagest change by a third ormore, about 7% of

14、 all wges changekly 17.These two factors implyt to obtain a reasonably fresh and 679 complete snapshotof the web, a search engine must crawleast 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 bedmaell over ten tho

15、usand times per second, against a set of URLst is too large to store inemory. In addition, crawlers typically use a distributed architecture to crawl more pagesin parallel, which further complicates the membership test: it issiblet the membershipquestion caly be answered byer node, not locally.A cru

16、“seen” URLsl way to speed up the membershipto cache a (dynamic) subset of ther is to investigate in depth severalaemory. The main goal of this pURL caching techniques for web crawling.xamined four practical techniques: randomreplacement, sic cache, LRU, and CLOCK, and compared them against two theor

17、etical limits:clairvoyant caching and infinite cache when run againsrace of a web crawlt ied overone billion HTTP requests. We foundeven at relatively small cache size implemented very efficiently.t simple caching techniques are extremely effectivech as 50,000 entries and show how these caches can b

18、eThe pr isanized as follows: Section 2 discusses the various crawling solutionsproedhe literature and how caching fitsheir m. Section 3 presents anroductionto caching techniques and describes several theoretical and practical algorithms for caching.We implemented these algorithms under the experimen

19、tal setup described in Section 4. Theresults of our simulations are dcted and discussed in Section 5, and ourmendationsfor practical algorithms and data structures for URL caching are presented in Section 6. Section7 contains ours and directions for further research.2. CRAWLINGWeb crawlers are almos

20、t as old as the web itself, and numerous crawling systems havebeen describedhe literature.his section,resent a brief survey of these crawlers (inhistorical order) and then discuss why most of these crawlers could benefit from URL caching.The crawler used by theernet Archive 10 employs multiple crawl

21、ing proses,each of which performs an exhaustive crawl of 64 hosts aime. The crawling proses save-local URLs to disk; atsets of the next crawl.of a crawl, a batch job adds these URLs to the per-host seedThe originalcomponents as different procrawler, described in 7, implements the different crawlerse

22、s. A single URL servros maains the set of URLs todownload; crawling proses fetch pages; indexing proses extract words and links; andURL resolvroses convert relativeo absolute URLs, which are then fed to the URLServer. The various proses communicate via the file system.For the experiments describedhi

23、s pr, we used the Mercator web crawler 22,29. Mercator uses a set of independent, communicating web crawlroses. Each crawlerpropros is responsible for a subset of all web servers; the assignment of URLs to crawlerses is based on a hash of the URLs host component. A crawlert discovers an URLfor which

24、 it is not responsible sends this URL via TCP to the crawlert is responsible for it,batching URLs together to minimize TCP overhead. We describe MercatorSection 4.ore detail inCho and Gar-Molinas crawler 13 is similar to Mercator. The system is comedof multiple independent, communicating web crawlro

25、ses (called “C-procs”). Cho andGar-Molina consider different schemes for partitioning the URL space, including URL-based (assigning an URL to a C-proc based on a hash of the entire URL), site-based (assigningan URL to a C-proc based on a hash of the URLs host part), and hierarchical (assigning anURL

26、 to a C-proc based on some property of the URL, such as its top-level).The WebFountain crawler 16 is also comed of a set of independent,communicating crawling proses (the “ants”). An antt discovers an URL for which it isnot responsible, sends this URL to a dedicated proURL to the appropriate ant.s (

27、the “controller”), which forwards theUbiCrawler (formerly known as Trovatore) 4, 5 is again comed of multipleindependent, communicating web crawlroses. It also employs a controllros whichoversees thecrawling procrawling proses.ses, detects pros failures, and initiates fail-over to otherShknyuk and S

28、uels crawler 35 is similar tos; the different crawlercomponents are implemented as different proses. A “crawling application” maains the setof URLs to be downloaded, and schedules the order in which to download them. It sendsdownload requests to a “crawl manager”, which forwards them to a pool of “d

29、ownloader”proses. The downloadroses fetch the pages and save them to an NFS-mounted filesystem. The crawling application reads those saved pages, extracts any links contained withinthem, and adds them to the set of URLs to be downloaded.Any web crawler must maain a collection of URLst are to be down

30、loaded.Moreover, since it would be unacceptable to download the same URL over and over, it musthave a way to avoid adding URLs to the collection morece. Typically, avoidance isachieved by maaining a set of discovered URLs, covering the URLshe frontier as wellemory (which itas thoseoften is, givenve

31、already been downloaded. If this set is too large to fitt there are billions of valid URLs), it is stored on disk and caching popularURLsemory is a win: Caching allows the crawler to discard a large fraction of the URLswithouving to consult the disk-based set.Many of the distributed web crawlers des

32、cribedWebFountain 16, UbiCrawler4, and Cho and Molinasabove, namely Mercator 29,crawler 13, are comprised of ges, extracts their links, andcooperating crawling proses, each of which downloads wsends these links to the peer crawling pros responsible for it. However, there iseed tosend a URL toer craw

33、ling pros morece. Maaining a cache of URLs andconsultingt cache before sending a URL toer crawler goes a long way toward reducingtransmiss to peer crawlers, as we showhe remainder of this pr.3. CACHINGost computer systems, memory is hierarchical,t is, there exist two or more levelsof memory, represe

34、nting different tradeoffs betn size and speed. For instance, in a typicalworksion there is a very small but very fast on-chip memory, a larger but slower RAMmemory, and a very large and much slower disk memory. In a network environment, thehierarchy continues with network acsible storage and so on.

35、Caching is the idea of storingfrequently used items from a slower memory in a faster memory.he right circumstan,caching grey improves the performance of the overall system and hence it is a fundamentaltechniquehe design of operating systems, discussedength in any standard textbook 21,37.he web conte

36、xt, caching is often mentionedhe context of a web proxy caching wcontext, since the number of visited URLsges 26, Chapter 11. In our web crawleres too large to storeaemory, we storethe collection of visited URLs on disk, and cache a small portionaemory.Caching terminology is as follows: the cache is

37、 memory used to store equal sizedatomic items. A cache has size k if it can store at most k items.1 At eacit of time, the cachereceives a request for an item. If the requested item ishe cache, the situation is called a hitand no further action is needed. Otherwise, the situation is called a miss or

38、a fault. If the cachehas fewern k items, the missed item is added to the cache. Otherwise, the algorithm mustchoose either to evict an item from the cache to make room for the missed item, or not to add the missed item. The caching policy or caching algorithm decides which item to evict. The goalof

39、the caching algorithm is to minimize the number of misses.Clearly, the larger the cache, the easier it is to avoid misses. Therefore, the performanceof a caching algorithm is characterized by the miss ratio for a given size cache. In general,caching icsful for two reasons:_-uniformity of requests. S

40、ome requests are muore popularn others. Inour context, for instance, a link toto the authors home pages.is a muore common occurrencen a link_ Temporal correlation or locality of reference. Current requests are more likely toduplicate requests madehe recent pastn requests made long ago. The latter te

41、rminologycomes from the computer memory m data needed now is likely to be closehe addressbecause linksspace to data recently needed. In our context, temporal correlation occurstend to be repeated on the same page we foundt oage about 30% are duplicates, cf.Section 4.2, and second, because pages on a

42、 given host tend to be explored sequentially andthey tend to share many links. For exle, many pages on a Computer Science departmentserver are likely to share links to other Computer Science departmentsprs, etc.he world, notoriousBecause of these two factors, a cachet contains popular requests and r

43、ecent requestsis likely to perform betteruition in various ways.n an arbitrary cache. Caching algorithms try to capture thisWe now describe some standard caching algorithms, whose performancein Section 5.valuate附录B汉语翻译基于网络爬虫的有效 URL 缓存BMJ (国际版)2009概要：要在网络上爬行非常简单：基本的算法是：（a）取得一个网页（b）它提取所有的URLs（c）对于所有没有

44、见过的 URLs 重复执行（a）-（c）。但是，网络的大小（估计有超过 40 亿的网页）和他们变化的频率（估计每周有 7%的变化）使这个计划由一个微道的设计习题变成一个非常严峻的算法和系统设计。实际上，光是这两个要素就意味着如果要进行及时地，完全地爬行网络，步骤（a）必须每秒钟执行大约 1000 次，因此，成员检测（c）必须每秒钟执行超过 10000 次，并有非常大的数据到主内存中。这个要求有一个分布式构造，使得成员检测更加复杂。一个非常重要的方法加速这个检测就是用 cache（高速缓存），这个是把见过的 URLs 存入主内存中的一个（动态）子集中。这个最主要的成果就是仔细的研究了几种关于网络

45、爬虫的 URL 缓存技术LRU，和 CLOCK，和理论极限：考虑所有实际的算法：随机置换，静态 cache，cache 和极大的 cache。执行了大约 1800 次模拟，用不同的 cache 大小执行这些算法，用真实的 log 日志数据，获取自一个非常大的 33 天的网络爬行，大约执行了超过 10 亿次的http 请求。的主要的结论是 cache 是非常高效的-在的机制里，一个有大约 50000个的 cache 可以完成 80%的速率。有趣的是，这 cache 的大小下降到一个临界点：一个足够的小一点的 cache 更有效当一个足够的大一点的 cache 只能带来很小的额外好处。推测这个临界

46、点是固有的并且冒昧的解释一下这个现象。1.介绍皮尤的研究：“搜索引擎已经成为互联网用户不可或缺的工具”，估计在 2002 年中期，初略有超过 1 半的人用网络搜索获取信息。因此，一个强大的搜索引擎技术有巨大的实际利益，在这个中，集中于一方面的搜索技术，也就是搜集网页的过程，最终组成一个搜索引擎的。搜索引擎搜集网页通过很多途径，他们中，直接提交 URL，回馈内含物，然后从非 web 源文件中提取 URL ， 但是大量的包含一个进程叫 crawling 或者SERing，他们递归的探索互联网。基本的算法是：Fetch a pageParse it to extract all linked URL

47、sFor all the URLs not seen before，repeat（a）-(c)URLs。有些时候网络爬虫开始于一个正确连接的页，但是因为这个原因相关的巨大的部分网络资源无法网络怕从一般开始于一些面，或者一个目录就像：被到。（估计有超过 20%）如果把网页看作图中的节点，把超看作定向的移动在这些节点之间，那么网络爬虫就变成了一个进程就像数学中的图的遍历一样。不同的遍历策略决定着先不哪个节点，下一个哪个节点。2 种标准的策略是深度优先算法和广度优先算法-他们容易被实现所以在很多入门的算法课中都有教。但是，在网络上爬行并不是一个微道的设计习题，而是一个非常严峻的算法和系统设计因为以下 2 点原因：需要索引超过 30 亿的网页。很多研究都网络非常的庞大。现在，在历史上，网络每 9-12 个月都会增长一倍。网络的页面改变很频繁。如果这个改变指的是任何改变，那么有 40%的网页每周会改变。如果认为页面改变三分之一或者，那么有大约 7%的页面每周会变。这 2 个要素意味着，要获得及时的，完全的网页快照，一个搜索引擎必须1 亿个网页每天。因此，步骤（a）必须执行大约每秒 1000 次，成员检测的步骤（c）必须每秒执行超过 10000 次，并有非常大的数据到主内存中。另络爬虫一般使用一个分布式的构造来