4-外文文献译文.docx

外海或7家夫学毕业设计（论文）外文文献原文及译文毕业论文题目：常用博客和论坛数据自动抓取系统的设计与实现文献中文题目:UbiCrawIer:一种可扩展的全分布式网络爬虫文献英文题目：UbiCraWler:aSCaIabIefullydistributedWebCraWler专业软件工程学号学生姓名指导教师答辩日期2015-06-25哈尔滨工业高校外文文献译文UbiCrawIer：一种可扩展的全分布式网络爬虫1 .引言在本文中我们介绍UbiCraWIer的设计与实现，一种可扩展的，可容错的全分布式网络爬虫，并且我们从先验和后验两方面评估了它的性能。UbiCraWIer设计的整体结构在1,2和3进行了描述.这项工作是个项目的一部分，其目的是收集大量的数据集，探讨Web的结构。这是从统计分析特定的网络域4估计的分布经典参数，如页面排名5和重新设计阿里安娜发展的技术，最大的意大利搜寻引擎等。由于该顼目的第一阶段，我们发觉集中爬虫已不再是足够的在网络中抓取仃意义的部分。事实上，它已经相识到，”作为网络的大小成长，成为爬行的过程并行化势在必行，为了完成卜我页在一个合理的时间量6,7。很多商业和探讨机构运行他们的网络爬虫收集关于Web的数据。即使没有可用的代码，在一些状况下，基本的设计已被公开：这都是是案例，例如，整卡托8（AItaViSta爬虫），原来的谷欹爬虫9,和些在学术界的爬虫UO-12。尽管如此，几乎没有发表的作品事实上探讨了在他行过程中所涉及的不I可任务的并行化这个基本的问题。特殊是，我们知道的全部的方法都是运用某种集中管理，确定去访问哪些网址，并存储已经被抓取的网址。最好,这些组件可以被发制，他们的工作可以被划分为静态。相反，当设计Ubiera*ler,我们确定把每一项任务，具有明显的可扩展性和容错性方面的优势.Ubicrawler的基本特征： 平台独立性： 充分安排每一个任务（没有单一的故障点和没有集中协调）： 基于一样哈希的局部可计算的地址安挎： 容忍故障：永久性以及短留的优雅地处理故障：.可扩展性。正如我们将在2节中概述，这些特性是一个定义明确的设计目标的副产品：故障容钳和全分布（缺乏任何集中限制）是指导我们的建设性选择的假设.例如，虽然有几个合理的方式来划分将被抓取的域，假如我们假设存在个中心服务器,要找到项任务变得困难了，不同的网址是完全分布式的，不须要太多的协调,并允许我们应对失败。在2节中给出UbiCraWler总体设计，特殊是要求探讨什么指引着我们的选择。第3节给出了一个高层次的爬虫软件架构的描述，并且第4节介绍的安排功能，用于分发的网址被抓取，给出了其性质的般性结果。UbiCraWICr发展中面临的问题详见第5节，而第6节是特地的绩效评价，既从分析又从实证的角度看。最终，第7节对比我们的探讨结果与文献中的相关工作。2 .设计，需求和目标在这一节中我们将介绍最IIt要的具有指导Ubicruwler实施的设计选择.更精确地说，我们勾画了总体设计的目标和要求，以及应容忍的故障类型的假设。全分布。为了在编程，部署和调试方面取得显著的优势，一个平行的分布式爬虫应当由同一个程序代理组成，区分啡一的标识符。这有一个根本性的结果：每个任务必需在一个完全分布式的方式进行，即没有中心协调器可以存在。全分布是有助于获得个可扩展的，易于配置的系统，没有电-的故障点。我们也不希望依靠于任何假设有关的代理的位置，这意味若延迟可以成为一个问题，因此，我们应当尽垃削减通信，以削减它.平衡局部可计算安排。网址的分布是个重要的问题.关键是关系到分布式爬行过程的效率。我们确定了以下三个目标。 在任何时候，每个网址应当被安排到一个特定的代理，这是唯一一个负责它，以避开不想要的数据如制。 对于任何给定的网址，其负货的代理人的学问应当是本地可用。换句话说，每一个代理都应当有实力计算代理的标识符，负责一个网址，没有通信.此功能削减代理间的通信量：此外，假如代理检测到故障时试图安排一个IJR1.到另个代理,在没有进一步的沟通下它将可以选择新的负贵人代理。 网址的分布应当是平衡的，即，每个代理应当负货约相同数量:的网址。在异构代理的状况下，网址的数Fl应当是成正比的代理的可用资源（如内存，便盘容量:等）0可扩展性。每秒的页面数和代理应当是（几乎）独立的代理数51.换句话说，我们期望的吞吐量与代理的数量呈线性增长。文静性。一个平行的爬虫决不应当试图从一个给定的主机上获得一页以上的一页.此外，一个合适的延迟，应在随后的恳求之间引入相同的主机。容错性。一个分布式的爬虫应当能接着工作在崩溃故障卜，这是当一些代理突然死亡的时候。在这种崩溃的存在下，没有行为可以被假定，除了有缺陷的代理停止通信：特殊是，一个不能规定任何行动，一个崩溃的代理人,或史原其状态之后。当一个代理崩溃，剩余的代理应接着满意就地平衡计豫安排的要求：这意味着，在特定的UR1.,这架代理将被重新安排。这有2个全要的后果。 不行能假设网址是静态分布。 由于“就地平衡计算任务的要求必需满意在任何时间”，在崩溃之后依除分布式安排协议这是不合理的。事实上，在重新安排的要求将被破坏。3 .软件体系结构UbiCraWler由几个代理，自主协调它们的行为，在这样一种方式，每个人扫描其网络的共享。一个代理执行它的任务，通过运行多个线程，每一个单独的主机单独访问“更准确地说，每一个线程扫描一个主机运用广度优先访问。我们确保不同的线程访问不同的生机在同时间，因此，每个主机不超载太多的要求。这是不是本地主机的给定样本被派遣到代理权，使其在页面被访问队列。因此，整体的Web访问是广度优先，但尽快达到一个新的主机，它是完全访问（可能有界深度达到或总页数）,再次在广度优先的方式。更先进的方法（可以考虑适当的优先级相关的网址，如，他们的排名）可以很简洁地实现。然而，值得留意的是，有几个作者（见，例如，13）认为，广度优先访问倾向于在爬取的时候找到高质价的网页关F页面历址的个更深化的探讨,在第6节中绐出。一个重要的优势是，每个主机广度优先访问DNS恳求是罕见的。网络爬虫运用全球广度优先策略必需在DNS服务器的延迟：这通常是由一个多线程缓存缓冲恳求通过了.同样，没有缓存是由“机器人解除标准”M所需的robots.txt文件须要：事实上这样的文件可以下效，当主机访问起先。代理的主机安排考虑到在每个代理的质量存储资源和带宽。这是目前所做的一个单一的指标，称为实力，这是作为一个权重的安排功能安排主机运用。在某些状况下，每一个代理的主机比例的比例，其容忌的主机（见4节的一个精确的描述如何工作）。留意，即使每个主机的UR1.数量参差不齐，代理人之间的UR1.分布趋于匀称在大爬虫中。除此之外的阅历统计的缘由，也有其他的动机，如用右边界的最大数量的网页抓取的政策的运用和访问的最大深度。这样的政策是必要的，以避开（可能是恶意）网络陷阱。最终，对UbieraRler必不行少的组成部分，是一个牢靠的故障检测器15运用超时检测撞剂：牢靠性是指一个揄剂最终会被每一个活性剂（通常称为故障探测器的理论完备性较强的属性）。故障检测器是UbiCraWler唯同步组件（即运用定时功能的唯部件）；全部其他的组件在个完全异步的方式进行交用。4 .功能安排在木节中我们描述的UbiCraWler功能安排，和我们说明为什么这个功能可以实现每一个任务和实现容错的Fl标。让4表示我们的代理标识符（即潜在的代理的名字），1.U4是活若的代理设假：我们必需指定主机代理/.更准确地说，我们已经设置了功能B,每个非空集合1.活剂，和为每个主机H,代表的货任，取（UR1.S）H的代理61.（三）Z.下列属性是需求的功能安排.1.平衡,每个代理应当得到大约相同数星的生机：换句话说，假如m是主机（总数），我们想要-I1.（八）m1.!对于每一个a1.2.逆变：安排给一个代理主机的设巴应当就在失活和活剂激活设贪在逆变方式转变.更准确地说，假如1.U1.然后6-11.（八）N-11.（八）：也就是说，假如代理的数量增长，每个代理的网页抓取的部分必需收缩。逆变具有根本性的后果：假如增加一个新的代理，没有旧的代理将失去在另一剂有利于安排；更准确地说，假如4“并且540"4,那么AiofW="徐）;这保证了在任何时间，该组的代理可以扩大与当前主机安排的最小干扰.留意，满意部分上述要求并不难：例如，一个用于非容错分布式爬虫的典型方法是计算基模的主机名称的哈希函数。这有很好的平衡性能（每个代理得到约相同数盘的主机），当然，可以计算本地的每个代理知道只是一组活剂。然而，当一个代理崩溃发生了什么？可以计算出的赋值函数，给几乎全部的主机供应了一个不同的结果。对安排给每个代理1三机的集合的大小会增大或缩小反变，但这些桀合的内容会在一个完全混沌的方式变更.因此，在崩溃之后，大多数的页面都会被个不应当获得的代理存信，并I1.它们可以被错误地重新获得几次。明显，假如中心协调器是可用的或者代理人可以从事一种“同步”阶段可以收集其他信息和运用其他机制来重新安排主机爬取.然而，我们只会把容错问题在后者的同步相位,错误将是致命的，4.1 背景虽然不是特别明显,不难看出，逆变意味着每个可能的生机导致订单总额（即置换）4上：更精确地，逆变安排是等效函数安扑SA（对称群元素在4即a的桀全排列的元素，或等价地，每个主机的全部元素）总序集：然后，1.（三）的计算，在与H的排列，第一列，属于集合1.个简洁的方法来获得个平衡，逆变安排功能包括试图产生这样的排列，例如，运用一些从主机名称提取种子（伪）随机发生涔，然后随机置换可能代理设置,该解决方案具有在时间和空间上的运行时间和可能的代理（这是一个希望保持尽可能大的成比例的大的缺点.因此，我们须要一个更困难的方法。4. 2一样性哈希最近，一个新的散列技术称为一样性哈希16,17已经提出了实现系统的分布式Keb绫存（种不同的方法对同问题可以发觉在18）。样的散列的想法是特别简洁的，但深刻。正如我们留意到的，对于一个典型的散列函数，在哈希表中添加一个桶（即一个新的地方）是灾难性事务“在一样性哈希,相反，每个桶是发制的个固定数量K时代,每个副本（我们称之为副本）映射到单位圆上的随机。当我们要散列一个密钥时，我们从某个角度计鸵单位圆中的一个点，并找到它最近的副本：相应的桶是我们的哈希。读者被称为16为一个具体的报告，强大的功能一样的散列，这特殊是给我们自由.逆变也简洁瞪证。在我们的例子中,桶是代理,而密糊是主机，我们必需特别当心，但是，假如我们希望逆变（2）实行，因为随机副木映射到单位网每次启动代理时不工作：事实上，6不仅取决于1.,但也对副本的选择。因此，全部的代理应当计算同一套副本对应T一个给定的代理，这样，一旦主机变成单位恻上的点，全部代理将同意谁是负货生机。4.2标识符种子一样性哈希固定设置的副本相关代理，尽量保持良好的随机性属性的一样性哈希方法推导出一套副本从接种剂标识符的一个很好的随机数生成器：我们称这种方法为标识符种子一样的哈希.我们选择一个更好的19,一个特别长的周期，通过很强的统计测试快速随机发生器。然而，该解决方案时进一步的限制：由于复制不能重处，单位圆的任何离散化将产生的生日悖论，即使有特别大量的点，副本玳检的概率符成为不行忽视的.事实上，当一个新的代理起先，它的标识符是用来生成代理的副本。但是，假如在这个过程中,我们生成一个已安排给其他代理的副本，我们必需强制新代理选择另一个标识符。假如一个代理在一段时间下进行，并在重新启动时发觉冲突，这个解决方案可能是问题的根源.尽管如此，一些标准的概率参数，用64位表示单位四的元素有10'与IO-"冲突概率空间。引用1 BoldiP,CodenottiB,SantiniM1VignaS.Trovatore:Towardsahighlyscalabledistributedwebcrawler.PosterProceedingsoftheIOlhInternationalWorldWideWebConference,IlongKo11,China,2001.ACMPress:NewYork,2001：140-141.WinneroftheBestPosterAward.2 BoldiP,CodenottiB,SantiniM1VignaS.Ubicrawler:ScalabiIityandfaull-toleranceissues.PosterProceedingsoftheIlthInternationaWorldWideWebConference,Honolulu,HI,2002.ACMPress:NewYork,2002.3 BoldiP,CodenottiB,SantiniM,VignaS.Ubicrawler:AscalablefullydistributedWebcrawler.ProceedingsofAusWebO2.The8thAustralianWorldWideWebConference,2002.4 BoldiP,CodenottiB,SantiniM.VignaS.StructuralpropertiesoftheAfricanweb.PosterProceedingsoftheU"InternationalWorldWideWebConference,Honolulu,HI,2002.CMPress:NewYork,2002.5 Page1.,BrinS1MotwaniR.WinogradT.Thepagcrankcitationranking:Bringingordertotheweb.TechnicalReport,StanfordDigilaI1.ibraryTechnologiesProject,StanfordUniversity,Stanford,CA,1998.6 ChoJ,Garcia-MolinaH.Parallelcrawlers.ProceedingsoftheIlthInternationalWorldWideWebConference,2002.CMPress:NewYork,2002.7 ArasuA,ChoJ,Garcia-MolinaH,PaepckeA,RaghavanS.Searchingtheweb.ACMTransactionsonInternetTechnology2001;1(1):2-43.8 NajorkM,Ileydon.High-performanceWebcrawli11.HandbookofMassiveDataSets,AbolIoJ,PardalosP,RescndoM(eds.).Kluwer:Dordrccht,2001.9 BrinS,Page1.Theanatomyofalarge-scalehypertextualwebsearchengine.ComputerNetworks1998;30(1/7):107-117.10 YanH,WangJ,1.iX,Guo1.ArchitecturaldesignandevaluationofanefficientWeb-crawlingsystem.TheJournalofSystemsandSoftware2002;60(3):185-193.11 Zeinalipour-YaztiD,DikaiakosM.DesignandinplCiiientationofadistributedcrawlerandfilteringprocessor.ProceedingsofNGlTS2002(1.ectureNotesinComputerScience,vol.2382).Springer,2002：58-74.12 SbkapenyukV,SuelT.DesignandimplementationofHhighperformancedistributedwebcrawler.IEEEInternationalConferenceonDataEngineering(ICDE)12002.IEEEComputerSociety,2002.13 NajorkM,WienerJ1.Breadthfirstsearchcrawlingyieldshigh-qualitypages.ProCeedingSoftheIOthInternationalWorldWideWebConference,HongKong1China,2001.ACMPress:NewYork,2001.14 KosterM.TheRobotExclusionStandard.:/robotstxt.org200115 ChandraTD1ToucgS.Unreliablefailuredetectorsforreliabledistributedsystems.JournaloftheACM1996：43(2):225-267.16 KargerD,1.ehmanE11.eightonT,1.evineM,1.evinI),PanigrahyR.Consistenthashingandrandomtrees:DistributedcachingprotocolsforrelievinghotspotsontheWorldWideWeb.Proceedingsofthe29thAnnualCMSymposiumonTheoryofCOmPUling,ElPaso,TX,1997.CMPress:NewYork,1997;654-663.17 KargerD11.cightonT,1.ewinD,ShermanA.Webcachingwithconsistenthashing.Proceedingsofthe8thInternationalWorldWideWebConference,Toronto,Canada,1999.ACMPress:NewYork,1999.18 DevineR.DesignandimplementationofDDH:Adistributeddynamichashingalgorithm.ProceedingsoftheFoundationsofDataOrganizationandAlgorithms,4thInternationalConference,EODO'93,Chicago,Illinois.I1.,1993(1.ectureNotesinComputerScience,vol.730),1.ometDB(ed.).Springer:Berlin,1993;101-114.19 MatsumotoM1NishimuraT.Mersennetwister:A623-dimensionallyequidislributeduniformpseudo-randomnumbergenerator.ACMTMCS:ACMTransactionsonMode1ingandComputerSimulation1998;8:3-30.外文文献原文XXXXXXXXXXXXXXX（文献题目）（正文可以用复印、扫描、截图、PDF、文本均可）