（计算机软件与理论专业论文）并行爬行器的架构与优化策略.pdf

摘要 摘要 搜索引擎是从互联网上快速而有效地获取信息资源的捷径。爬行器是搜索引 擎的重要组成部分，它在搜索引擎中负责网络信息采集，是搜索引擎数据库中原 始信息唯一来源。本文围绕着网络搜索这一前沿技术，深入研究了爬行器的工作 原理和相关技术，并在这些研究工作的基础之上设计实现了一个高性能并行爬行 器c h a o c r a w l e r 。 本文的研究内容主要包括： 分析并行爬行器现有的实现技术，包括系统框架，任务分配算法，系统内部 通信方式和协作方式。以主从结构为基本模型，阐述了基于n f s 的并行爬行器 系统架构，协作机制，以及在此机制下并行爬行器的数据处理流程和数据并发访 问的处理方法。 针对并行爬行器所遇到的实际问题，实现了三种优化策略：冲突规避，u r l 索引和d n s 缓冲。冲突规避算法将u r l 散列和站点名散列相结合，应用多线程 技术，在实现了负载平衡同时，又避免了并行爬行器的并发冲突。u r l 索引采 用了索引散列值的方法，基于b e r k e l e yd b 实现了h a s h 和b + 树两种u i 也索引 库，满足了爬行器快速查找u r l 的需要，为其正常运行提供了保障。d n s 缓冲 通过客户机缓冲的方式，采用全缓冲策略，解决了域名解析的瓶颈，提高了并行 爬行器的运行效率。 最后，设计实现了实验原型系统c h a o c r a w l e r 。通过在互联网上进行实验， 检验了并行爬行器c h a o c r a w l c r 的运行效果，并由此验证了其系统架构和三种优 化策略的有效性。 关键词搜索引擎；信息采集；爬行器；并行；检索 a b s n l c t a b s t r a c t as e a r c he n g i n ei sas h o r t c u tt of i n dm i o m a t l o nf b mi n t e m e t ac r a w l e r1 sa n i i n p o n a n tc o m p o n e n to fas e a r c he n 百n e i ti sr e s p o n s i b l ef o rw e bi n f o 珊a t i o n g a m e r i n g i ti sm eo n l ys o u r c eo ft h er a wd a t ai ns e a r c he n g i n ed a t a b a s e 1 1 1 i sp a p e r a i m e sa tw e bs e a r c h i n g ，ac u t t i i l ge d g et e c h n o l o g y ，a n di n v e s t i g a t e st l l er e l a t e dm e o r y a n dt e c h n o l o g yi nd e t a i l ah i 曲p e r f o m l a n c ep a r a l l e lc r a w l e ri sd e s i 印e da n d i m p l e m e m e db a s e do nt h i sk n o w l e d g e t h er e s e a r c hw o r km a i n l yi n c l u d e sf o l l o w i n go u t l i n e s f i r s t l y ，t h i sd i s s e r t a t i o np r o p o s e sb a s i ca r c h i t e c t u r e sf o rap a r a l l e lc r a w l e ra n d i d e n t 讯e ss o m ef 曲d a i n e n t a li s s u e sr e l a t e dt o p a r a l l e lc r a w l i n g ，i n c l u d i n gt h e a l g o r i m mo ft a s ka s s i g 啪e n t ，s y s t e mi n t e m a lc o m m u i l i c a t i o na n dc o l l a ：b o r a t i o n b a s e do nt h e s e u n d e r s t a n d i i l g s ， ac e n 删i z e da r c l l i t e c t l l r ei s p r o p o s e d f o r c h a o c r a w l e r ac o l l a b o m t i o nm e c h a n i s mb a s e do nn f sa 1 1 di t sc o n c u r r e n td a t a p r o c e s s i n gs o l u t i o ni sa l s oi n 廿o d u c e dm t h i sd i s s e r t a t i o n 加m 协ga tt h ep r a c t i c a lp r o b l e m sap a r a l l e lc r a w l e rw i l lf k et o ，m i sp 印e r a d v a i l c e st h r e et y p e so fo p t i r n i z a t i o np o l i c yf o rc h a o c r a w l e r ，i n c l u d i n gc o l l i s i o n a v o i d a i l c e ，u i 也i n d e x i n ga 1 1 dd n sc a c l l i n g t h ec o l l i s i o n a v o i d a l l c ea l g o r i t h m c o m b i n e su r lh a s h i n ga n ds i t e n a m eh a s h i n g 1 tr c a l i z e sw o r k1 0 a db a l 柚c i n ga n d a l s oa v o i d st h ec o l l i s i o n 、h e np a r a l l e lf c t c m n g u r li n d e x i n gi si m p l e m e n t e db y i n d e x i n gt h eu r lc h e c k s u m s au i ui i l d e xd a t a b a s e ，w h i c hh a s 押oi n d e x i n g a l g o 疗吐1 i n ，h a s ha n db + 仃e e ，i sb u i l tb a s e do nb e r k e l e yd b ns a t i s f i e sm en e e d so f m ep a r a l l e lc r a w l e r td n s c a c h i n gi sac l i e n tc a c h em e t l l o d i ta d o p t s 向1 1 一c a c h ep o l i c y t h ed n sb o t u e n e c ki ss 0 1 v e dw i t hi t sh e l pa 1 1 dt l l ep e r f o m l a l l c eo fm ep a r a l l e l c r a w l e ri sg r e a n yi m p m v e d f i n a l l y ，ap a r a l l e lc r a w l e rn 锄e dc h a o c r a w l e ri sd e s i 印e da n di m p l e m e n t e d b a s e d0 nm e s em e m o d s e x p 嘶m e n t sa r ea j s ot a k e nt oe x 锄j n et h ep e 1 0 n 1 1 a 1 1 c eo f c h a o c r a w l e rt h ee f r e c to fm et 1 1 r e eo p t i m i z a t i o nm e t h o di sv a l i d a t e db ym e e x d e r i m e n t s k e y w o r d ss e a r c he n g i n e ；i n f o m a t i o nr e t r i e v a l ；c r a w l e r ；p a r a l l e l ；i n d e x i i j 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：堇垒丝日期：壅：! ：! ：! = ) 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 趣钦 导师签 ，泸电s 6t o 鹅1 章绪论 第1 章绪论 近十几年以来，互联网技术迅速发展，使互联嘲逐渐成为人们不可或缺的巨 大信息源。准确而快速的从嘲上找到信息己成为人们迫切的需求。搜索引擎的出 现和发展在定程度上满足人们需要的同时，也面临着更多的挑战。网络搜索技 术主要包括信息采集和信息处理两方面，爬行器( c r a w l 。r ) 是搜索引擎用于信 息采集的程序，是搜索引擎的重要组成部分。 本章首先介绍了劂络搜索技术的研究背景，然后分析搜索引擎结构和爬行 器，最后介绍了本文的内容组织。 1 1 背景 1 1 1 互联网与搜索引擎 上世纪九十年代以来，互联网的迅猛发展，w e b 信息爆炸式增长。用户要在 互联网的信息海洋罩查找信息，就像大海捞针一样。搜索引擎的出现恰好解决了 这个难题。搜索引擎可以为用户提供互联网信息检索服务，目前，它正成为计算 机工业界和学术界争相研究的对象。搜索引擎最早出现于1 9 9 4 年。mm a u l d i n 将j l c a v m 的爬行器接入到其索引程序中，创建了i 妒o s o 。同，干，斯妇福大学 的两名博l 生d f i l o 和杨致远( g e n y y a l l g ) 共同创办了超级目录索引耻i l l 0 0 ， 使搜索引擎的概念深入人心。从此搜索引擎进入了高速的发展阶段。g o o g l e 是斯坦福大学存1 9 9 8 年的实验型搜索引擎基础上发展而成的，它多年被，l j 户评 为最受欢迎的搜索引擎，究其原因一是它的网页索引数量达到3 0 亿之多。g o o g l e 的响应速度和结果的质量方面强于其它搜索引擎。该搜索引擎的关健技术有 p a g c r a n k 【1 技术和超文本匹配分析技术( h y p e n e x t - m a 自c h i n ga n a l y s i s ) h m a 。 p a g e r a n k 技术基丁链接分析理论，通过对所有爬行网页做超链分析，计算出刚 页的重要性。这种重要性是由其它刚页来确定的，不像其它搜索引擎是基于网站 自身的文字内容，这使得网站本身很难操纵自己的排名，使排名更加客观和准确。 检索系统采用h m a 技术来计算查询词与网页之l 碰的相关度。当用户提交查询的 时候，系统就能将最相关的最重要的网页返回给用户。 目前的搜索引擎大致可以分为三类，目录搜索引擎。机器人搜索引擎和元搜 索引擎。 目录搜索引擎主要依靠人工维护网站索引，它虽然有搜索功能，但在严格意 目录搜索引擎主要依靠人工维护网站索引，它虽然有搜索功能，但在严格意 北京工业大学工学硕士学位论文 义上算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完 全可以不用进行关键词查询，仅靠分类目录也可找到需要的信息。国外比较著名 的目录索引搜索引擎有y 曲o o ，o p e nd i r e c t o r ) ，p r o j e c t ，l o o k s m a n 等；国内的搜 狐，新浪，网易搜索也都具有这一类功能。目录式搜索引擎通过人工浏览各站点 的信息，按照一定的分类规则或分类体系，对网站进行分类。它的优势在于内容 比较好的站点更容易被编辑所认同，更容易被索引，所以它的索引质量比较高。 目录式搜索引擎分类结构清晰、错误较少，比较符合人们的阅读习惯。缺点是工 作人员多、整理周期长、速度慢、人工干预成份多，不能适应w 曲资源的规模 发展。 机器人搜索引擎是名副其实的搜索引擎，国外代表性的有g o 0 9 1 e ，y 址o o s e 埘l ，m s ns e a r c h ；国内著名的有百度，中搜。它们都是通过从互联网上提取 的各个网站的信息而建立的数据库，检索与用户查询条件匹配的相关记录，然后 按一定的排列顺序将结果返回给用户，也是目前常规意义上的搜索引擎。机器人 搜索引擎的全部工作基本上由程序自动完成，人工参与成份很少。它通过爬行器 在网上采集信息，将搜索到的网页自动地加入到本地索引数据库中，用户可以很 快从索引数据库查到更新后的信息。如果某个网站的网页内容更新了，搜索引擎 会自动发现这些变化，并很快更新本地索引数据库，及时反映到用户的检索结果 中。它的优势在于自动化程度高、维护费用低，更强调技术上的创新和提高，也 更适合于开展研究工作，因而成为当前研究的热点。 机器人搜索引擎通常有三大模块：信息采集模块、信息处理模块、信息查询 模块。图1 1 以g o o d e 为例，描述了一个典型的搜索引擎系统架构。 图1 1g o 0 9 1 e 的系统结构图 f i g u r el la r c h i t e c n j r eo f g 0 0 羽e 搜索引擎的各组成部分相互交错相互依赖。机器人搜索引擎的实现原理，可 第l 荦绪论 以归结为四个步骤： l 、从互联网上抓取网页。利用能够从互联网上自动收集网页的网络爬行器 程序，自动访问互联网，并沿着任何网页中的所有u r l 爬到其它网页，起初的 u r l 并不多，随着信息采集量的增加，也就是分析到网页有新的链接，就会把 新的u r l 添加到u 也列表，以便继续采集网页，重复这过程，并把爬过的所有 网页收集到服务器中。 2 、建立索引数据库。由索引系统程序对收集回来的网页进行分析，提取相 关网页信息( 包括网页所在u r l 、编码类型、页面内容包含的关键词、关键词 位置、生成时间、大小、与其它网页的链接关系等) ，根据一定的相关度算法进 行大量复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关 性( 或重要性) ，然后用这些相关信息建立网页索引数据库。 3 、在索引数据库中搜索。当用户输入关键词搜索后，分解搜索请求，由搜 索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。 4 、对搜索结果进行处理排序。所有相关网页针对该关键词的相关信息在索 引库中都有记录，只需综合相关信息和网页级别形成相关度数值，然后进行排序， 相关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内 容摘要等内容组织起来返回给用户。 元搜索引擎是指在统一的用户查询界面与信息反馈形式下，共享多个搜索引 擎的资源库为用户提供检索服务的系统。著名的元搜索引擎有d o g p i l e ，v i s i m o 等；国内的元搜索引擎中具代表性的有搜星搜索引擎，优客搜索。在搜索结果排 列方面，有的直接按来源引擎排列搜索结果，如d o g p i l e ，有的则按自定的规则 将结果重新排列组合，如v i v i s i m o 。元搜索引擎的最大特点是没有自己的索引数 据库，只提供一个统一的检索界面。当用户向元搜索引擎提交查询式时，它将该 查询表达式翻译成相对应的搜索引擎查询表达式并分别发送出去，接受各搜索引 擎的检索结果，按照一定的规则，将结果返回给最终用户。元搜索引擎的优势在 于用户不需要记忆不同搜索引擎的地址和查询语法就能查询多个索引数据库，可 以大大提高查询结果的覆盖度，不用维护庞大的索引数据库，而将工作重心放在 检索结果的整合上，提高查询的准确度。但是元搜索引擎的网络资源丌销比较大， 从多个搜索引擎返回的结果中常常有很多重复信息，相关度排序十分困难。 这三种搜索引擎各有优缺点，在不同的领域有不同的应用。目录式搜索引擎 和全文检索搜索引擎现在己经紧密结合在一起，如g o 0 9 1 e 、北大天网等等，它 们在机器人搜索引擎的基础上，提供目录服务。没有全文检索搜索引擎也就没有 元搜索引擎。这些搜索引擎技术可以互为补充，不会出现一种搜索引擎完全取代 另一种的可能。 北京工业人学工学硕士学位论文 1 1 2 爬行器 爬行器主要用于机器人搜索引擎。爬行器是指可以在w e b 上漫游并按照一 定规则自动从w 曲上采集网页的计算机程序。它也经常被称为“蜘蛛”( s p i d e r ) ， “机器人”( r o b o t ) 或者“漫游者”( w a n d e r e r ) 等。本文统一采用“爬行器” 来代表该类计算机程序。通俗的讲，爬行器就是一种下载网页的程序。通常，一 个爬行器从一个初始的u r l 集合开始，首先把这些u r l 放进队列。爬行器在运 行时从队列中取出u r l ，下载其指向的页面，从下载的页面中提取出新的u r l ， 然后把新的u 也放进队列。这个过程被爬行器反复执行，直到其停止运行。可 以清晰地看到，爬行器所执行的这个过程实际上就是对互联网遍历的过程。爬行 器下载的页面被保存在磁盘上，并建立索引，以供日后分析其内容。 爬行器的应用领域十分广泛。目前主要的搜索引擎，如g o o g l e ，a l t a v i s t a ， e x c i t e ，m s n 等，都各自拥有自己实现的爬行器。这些综合性的搜索引擎要下载 大量的w e b 页面，并建立索引，为用户搜索信息提供资源。近年来兴起的主题 搜索中也利用的爬行器技术。在主题搜索中，爬行器也访问大量的w e b 页面， 但是只下载特定内容的信息( 例如邮件地址) 。爬行器也可以用于桌面应用。爬 行器可以为特定用户检索感兴趣的页面，并建立页面缓冲，为用户快速浏览信息 提供便利。 对于搜索引擎来说，要采集到互联网上所有的网页几乎是不可能的，从目前 公布的数据来看，容量最大的搜索引擎也不过只采集了整个网页数量的百分之四 十左右【2 】。这其中的原因一方面是爬行器技术的瓶颈，无法遍历所有的网页，有 许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的问 题，如果按照每个页面的平均大小为2 0 k 计算，l o o 亿网页的容量是1 0 0 + 2 0 0 0 g 字节。即使能够存储，下载也存在问题，按照一台机器平均每秒下载2 0 k 计算， 需要3 4 0 台机器不停的下载一年时间，才能把所有网页下载完毕。而互联网上的 页面数量又是在迅速增大的，因此穷尽下载互联网的内容几乎不可能。同时，如 果数据量太大，搜索引擎在提供搜索时也会有效率方面的影响。因此，用于搜索 引擎的爬行器只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据 可以是某个网页的链接深度。 1 2 相关工作 对于爬行器的研究始于互联网兴起的时期。r b s e 和w 曲c r a w l e r 是最早基 于自动爬行技术的公用搜索引擎扪。随着互联网发展，对爬行器的研究也日益深 第l 覃绪论 入，爬行器技术也随之不断进步。在上世纪9 0 年代末，互联网技术进入高潮的 时期，爬行器的研究也进入了一个高峰，这一时期，国外很多科研机构和高等院 校在爬行器的研究方面取得了一些成果，出现了一些比较完善的爬行器系统，比 如斯坦福大学的g o o g l e ，康柏系统研究中心的m e r c a t o r 【，卡耐基梅隆大学的 s p h 矾x 【5 】等等。这一时期对于页面排序算法的研究比较深入，出现了多种多样 的页面排序算法，例如：p a g e r a l l l 【，b e s t b i r s t 【6 j ，s h a r p s e a r c l 等等。 斯坦福大学的s e r g e yb n n 和l a 删c ep a g e 设计了用于搜索引擎g o o g i e 的 爬行器。他们所设计的爬行器采用了多机并行运行的方案，并且使用p a g c r a l l k 算法计算页面的重要性。系统使用p 圳h o n 和c + + 实现，每秒可以下载大约l o o 个页面。 康柏系统研究中心的a 1 l a nh e y d o n 和m a r cn a i o r k 设计了名叫m e r c a t o r 的爬 行器。系统采用j a v a 的线程方式实现并行处理，并加入了很多优化策略以提升 爬行器运行效率，如d n s 缓冲，延迟存储等。他们通过实验发现广度优先的爬 行策略是种发现高质量页面的有效方法【7 】。 分布式和a g e l l t 技术也被应用于爬行器的设计中，例如u b i c r a w l e r 【”， 口m i c r a 9 1 和基于分布式哈希表( d h t ) 的爬行器1 1 0 】。 国内搜索引擎的发展较国外相对滞后，因此有关爬行器的研究也同样滞后。 搜狐等早期的搜索引擎属于人工索引类型，没有自动采集的过程。近年来，随着 天网，百度等新一代搜索引擎的兴起，有关爬行器的研究逐渐丰富了起来，但是 大多数的研究工作都建立在单机爬行的基础上，专门研究并行爬行技术的人并不 多。北京大学网络与分布式实验室的天网搜索拥有一个比较成熟的并行爬行器， 并且成功的应用；上海交通大学计算机科学与工程系在并行爬行器方面也作了很 多有益的研究。 1 3 论文的组织结构 本文的结构安排如下： 第1 章，绪论，介绍互联网和搜索引擎的概况，搜索引擎的原理和爬行器。 第2 章，爬行器技术概述，介绍了爬行器所涉及的各种技术和规范。 第3 章，并行爬行器的协作与同步，介绍并行爬行器c h a o c r a w l e r 的系统架 构，任务分配和协作方式，包括协作算法，通信方式，数据共享和并发访问。 第4 章，并行爬行器的优化策略，介绍了实现并行爬行器的几个技术难题， 提出了c h a o c r a w 】c r 的解决方案，包括冲突规避，u u 索引，d n s 缓冲三种优 化策略，并通过实验验证了这些优化策略的有效性。 第5 章，系统设计与实现，详细介绍并行爬行器c h a o c r a w l c r 的实现细节。 第2 章爬行器技术概述 第2 章爬行器技术概述 通俗的讲，爬行器是一种下载网页的程序，主要用于搜索引擎。爬行器是 一种综合性的应用程序，涉及的技术面较广。本章介绍了爬行器的相关技术，包 括通用爬行器模型，爬行器的启发策略，并行爬行，页面存储和更新等方面的技 术。 2 1 通用爬行器模型 一般来说，爬行器需要一定数量的u r l 作为种子。在开始运行的时候将作 为种子的u r l 进队，然后按照某种策略从队列中取出u r l ，下载对应网页，分 析网页中的u r l ，再将网页内的u r l 进队。不断重复上述过程，直到u r l 队 列为空或满足其他结束条件为止。爬行器所执行的这个过程实际上就是对互联网 遍历的过程。爬行器下载的页面被保存在磁盘上，并建立索引，以供日后分析其 内容。图2 l 以伪代码的形式描述了基本的爬行器算法。 图2 1 基本的爬行器算法 f i g i l r e2 1b a s i cc r a w l m ga l g o i t l l m 通用爬行器可以采取的爬行策略有广度优先、深度优先、站内优先或有限深 度的广度优先等几种，不同的策略决定了对网页不同的访问次序。图2 2 中所示 的实例说明了它们的访问次序。假设有种子页面是a ，下面给出3 个策略的爬行 次序。 1 、广度优先访问次序是：a ，b ，c ，d ，e ，f 2 、深度优先访问次序是：a ，c ，e ，f ，d ，b 3 、站内优先的广度优先访问次序：a ，b ，d ，c ，e ，f 北京工业大学工学硕士学位论文 4 、有限深度的广度优先访问次序是( 假设最大深度为3 ) ：a ，b ，c ，d ， e 图2 - 2 爬行次序 f i g u r e2 - 2c r a w l i n gs e q u e n c e 在图2 2 给出的例子中，无论采用什么样的访问策略，网页g 都没有被访问 到，这是由于从种子页面a 出发，不存在到页面g 的通路。假设选取的种子站 点是页面g ，按照广度或深度的访问策略，就能够访问到图中的所有页面。这个 例子从一个侧面说明，爬行器下载网页的数量和范围，十分依赖于给定的种子站 点的数量和质量。即使在没有时间限制、w 曲的规模不够大的情况下，从给定的 种子沾点出发，爬行器也不一定能遍历整个互联网。因此图2 2 中的网页g 作为 种子的质量要高于网页a 作为种予的质量。如何选取高质量的种子页面，是爬 行器必须认真考虑的问题。一般情况下可以选取目录搜索引擎的网站目录作为爬 行器的种子。 2 2 爬行器的种类 为了解决w 曲采集的关键问题，研究者们经过不断地研究与实践，将爬行 器由最早期单纯的基于整个w e b 的爬行器发展到可满足不同需要的多种采集技 术的爬行器。归纳起来，大致可以分为以下几种类型： 第一种是基于整个w 曲的爬行器。主要是指目标为从一些种子u 也扩充到 整个w 曲的爬行器，这种爬行器通常是作为门户站点搜索引擎和大型的w 曲服 务提供商的数据采集部分。这类信息采集由于目标是采集整个w 曲，因此对内存 和硬盘等硬件的要求比较高，对采集页面的顺序要求相对较低。 第二种是增量式的爬行器【1 ”。传统的爬行器根据自己的需要采集足量的信息 后停止采集，当过一段时间这些数据过时后，它会重新采集一遍来代替先前的信 息，称为周期性w e b 采集器。而增量式的爬行器对待就的页面采用增量式更新， 即采集器在需要的时候采集新产生的或己经发生了变化的页面，而对没有变化的 第2 蕈爬仃器技术概述 页面不进行采集。和周期性信息采集相比，增量式信息采集能极大地减小数据采 集量，从而极大地减少了采集的时间与空间开销。但是与此同时，增量式信息采 集也增加了算法的复杂性和技术难度。 第三种是基于主题的爬行器【1 瓦”j ”，是指选择性地搜寻那些与预先定义好的 主题相关的页面的爬行器。和基于整个w 曲的爬行器相比，它并不采集那些与 主题无关的页面，所以大大地节省了硬件和网络资源，保存的页面也由于数量少 而更新快。加之它可以很好地满足一些特定人群对特定领域信息的需求，成为时 下研究的热门重点。但它的问题也是显而易见的，例如如何定义有实际意义的主 题，如何在采集时判定页面与主题的相关性以及如何提高系统的搜索精度和完全 度等。 第四种是基于用户个性化的爬行器。不同的用户对一个搜索引擎提交同一个 检索词，他们期待的结果是不尽相同的。而通用的搜索引擎却只能返回相同的检 索结果，这显然不完全符合用户的需要。而基于用户个性化的爬行器是一种轻量 级的采集系统，它的目标就是通过用户兴趣制导或与用户交互等手段来采集信 息，给用户提供个性化服务。 第五种是移动的爬行器【m l 。这种爬行器并不像其他爬行器一样在本地客户机 向w 曲站点服务器发送页面请求，而是将自己上载到它所要采集的服务器中， 在当地进行采集，并将采集结果压缩后，再回传到本地。这样做大量地节省了 w 曲资源，大量的剪裁工作将在被采集对象的服务器上完成。 第六种是基于元搜索的爬行器。它对用户的提交的查询请求通过多个领域或 门户搜索引擎搜索，并将结果整合后返回给用户。一般元搜索引擎并不保存w 曲 页面的索引文件，但是有一些元搜索引擎会保存为它服务的每个搜索引擎的信息 特征，以后根据用户请求做出选择。作为搜索引擎首要部件的爬行器在元搜索引 擎中功能有所退化，但依然是w 曲采集的一个研究方向，被称作基于元搜索的 信息采集。 2 3 设计爬行器需要考虑的问题 爬行器是搜索引擎的关键部分，它的性能好坏直接影响着搜索引擎整体性 能。设计一个性能良好的爬行器，通常应该考虑以下四个问题： 第一，页面选择。 爬行器不可能下载所有的网页，只能是一部分，随着w 曲网页数量的急剧 增长，下载的比例愈发变小了，优先下载高质量网页就显得更加重要。如何评价 一个爬行网页的质量是爬行器需要解决的一个问题。w 曲上的信息量如此巨大， 爬行器不可能采集到所有的页面，而且搜索引擎的数据库也没有那么大的容量。 北京_ t 业大学工学歌十学位论文 所以，必须尽可能改进爬行器的采集效果，即通过访问较少的不相关页面来获得 较多的相关页面。特别是对于基于主题的信息采集，需要采取较优的搜索策略， 对待采集页面评分，以此选择高质量的页面优先采集。目前，有五种常用的评价 页面质量高低的方法： 1 、相似度，包括己采集页面和链接与采集主题之间的相似度。 2 、p a g e r a l l l 【，一个页面的p a g e r a l l k 值为它所有链入页面所传递给它的 p a g e r a n k 值之和，而每个链入页面传递的p a g e r a i l l 【值为此页面的p a g e r a i l k 值 除以它的链出页面数，即这页的出度。 3 、l o c a t i o n ，页面在网站中所处的局部位置。 4 、b a c k l i l l k ，页面的入度大小。 5 、f o 刑a d l i l l k ，页面的出度大小。 第二，并行爬行。 爬行器需要在多个机器上运行，并行下载网页。并行化可以在合理的时间内 下载大量的网页。这些爬行器必须准确地协同工作，保证爬行器不重复访问相同 站点。但这种协同能力为爬行器带来通信负担，所以有必要限制并行工作的爬行 器个数。页面的采集速度一直是影响采集性能的主要因素。因为w 曲页面数量 巨大，加之网络硬件资源有限所导致的网络速度的缓慢，采集系统需要采取并行 工作的方式来提高采集效率。然而，这带来了许多新的问题： 1 、重复性。多个爬行器在同一时间采集增加了页面重复的可能性。并行化 可以在合理的时间内下载大量的网页。这些爬行器必须准确地协同工作，保证不 重复访问相同站点。 2 、质量问题。单个爬行器能够根据获得的全局信息调整搜索策略从而采集 到全局最优的页面。而若采取并行，每个爬行器只能采集到局部最优的页面，必 定影响到全局的采集质量。 3 、通信代价。为了实现并行爬行，各爬行器之间必不可少地需要信息交互， 这样就必然会增加网络通信的开销。所以通常情况下有必要根据系统和网络的具 体情况限制并行工作的爬行器个数，这样可以在一定程度上减轻这种协同能力为 爬行器带来通信负担。 第三，合理利用带宽。 爬行器运行时需要占用w 曲服务器的计算机资源。如c p u ，磁盘空间等， 同时也占用了网络带宽，增加了网络的负担。爬行器应该降低这些消耗，否则网 站w 曲管理员会屏蔽掉爬行器。遵循r o b o te x c l u s i o n 规则是其中一种方法，但 是更重要的是爬行器要自觉地避免大规模并发访问同一个网站，做到“礼貌”的 爬行【4 】。文献”1 介绍了限制爬行器占用网络带宽的方法。 第2 章爬行器技术概述 第四，页面更新。 一旦爬行器下载了大量的网页，就得重新访问，探测它们是否改变，更新下 载过的网页。因为w 曲上网页变化迅速，爬行器就得仔细决定哪些网页重新访 问哪些网页跳过，这决定了网页文档库的新鲜度。为了保持采集到的页面是最新 的，采集器必须对己采集页面进行周期性的更新。但由于w 曲上的信息量巨大 且更新速度快，经统计，1 4 的搜索引擎提供的页面是过期无效的。有研究对比 了三种页面刷新策略：固定顺序的刷新，随机刷新和纯随机刷新策略。直觉上， 更多的刷新应该分配给那些更新快的页面。但研究表明，对各种页面采取相同的 刷新周期效果反而更好，这是因为用过高频率刷新更新快的页面，使得其它页面 有较少的刷新机会，反而造成总体刷新质量的下降【l ”。 2 4 爬行器相关技术 2 4 1 启发策略 通用爬行器运行的过程中，并不会考虑网页的质量。由于w e b 的发展规模 任何爬行器都不可能下载和索引所有的网页，只能是尽可能多地下载高质量网 页，尽可能少地下载低质量网页。在通用爬行器的设计上，为了尽可能爬行高质 量的网页，很多研究者采用了各种各样的启发策略，以期提高爬行器的整体性能。 这些启发式策略可以利用以下信息： l 、域：不同的域，给予不同的优先级别。例如，如果以收录中文为主，那 么“c n ”的级别就最高；如果以收录学术性资源为主，“c o m ”和“g o v ”等的 级别就低些。 2 、目录深度：u r l 字符串中的路径部分表示的是页面在网站上的虚拟路径， 如果目录越深，优先级就越低。 3 、链接流行度( l i n kp o p u l 撕t y ) ：流行度是指网页本身被其它网页所指向 的次数，流行度的大小也影响到该网页的优先级。 4 、优先级的继承：如果一个网页的u r l 优先级高，则这个网页所包含的 u 也的优先级别也相对高些。 5 、页面相关度：主题爬行器通常采用这种方法，通常使用t f 一1 d f 或其他算 法计算页面与主题的相似程度，优先下载相似程度较高的页面所包含的链接。 6 、w 曲图：通过网页之间的超链接而形成的w 曲图有很多可以挖掘的信息， 文献【1 8 】利用了w 曲链接图实现了启发式爬行。 7 、还有研究发现，广度优先爬行策略是发现高质量页面的好方法【7 】，而深 北京工业大学工学硕士学位论文 度优先爬行策略更适合手动采集，因为它可以快速完成一个主题1 9 】。深度优先爬 行策略的这种特性通常被利用于用户驱动爬行器f 2 0 1 。 8 、另外一些爬行器需要w 曲服务器的协助来确定爬行策略，这也被称为“合 作爬行”【2 ”。 2 4 2 并行爬行 最初的爬行器模型没有明确的提出并行爬行的问题。1 9 9 8 年s e r g e y b 血和 l a 咖e p a g e 的关于g o 0 9 1 e 的论文中明确的提出了并行爬行的问题，但是并没有 提及细节信息。同时期的m e r c a t o r 和s p h d 还仅仅是单机运行的爬行器。爬行 器需要从互联网上下载页面，而下载页面相对来说是一个比较缓慢的过程，由于 目前互联网信息量已经是十分巨大，单机运行的爬行器无法满足要求，需要多机 并发运行的爬行器才能完成信息采集的任务。目的大部分商业搜索引擎内部都在 使用并行爬行器，但是其实现方式都没有对外透露。 2 4 3 网页存储 网页数据库被用来管理超大规模的w 曲网页，它应该是一个具有可扩展能 力的存储系统。网页数据库有两个基本功能：一个是为爬行器提供存储接口，另 一个是为索引器和文档分析模块提供易于访问的a p i 。在存储与管理功能上，网 页存储系统与文件管理系统和数据库管理系统有点相似，但是它更关注存储与管 理的效率，不提供日志、交易、目录结构等功能。 网页数据库需要解决如下问题： 1 、可扩展性：为了适应w 曲的大小，网页数据库需要无缝地将网页库分布 在计算机群和磁盘簇上，从而具备可扩展性。 2 、双重访问模式：网页数据库需要提供两种访问模式，即随机访问模式和 顺序访问模式。随机访问模式能够快速检出特定的网页，主要供查询引擎使用； 顺序访问模式用来接受整个文档集合或子集，供索引器和文档分析模块成批处理 网页使用。 3 、大规模数据更新：w e b 上的数据变化极快，存储系统需要能够处理高频 率的修改、更新操作。 4 、链接管理：需要提供一种机制来探测和删除陈旧无用的网页和链接。 第2 章爬行器技术概述 2 4 4 页面更新 许多用户经常抱怨，搜索引擎返回的页面链接无效，找不到链接指向的网页。 这一般是因为搜索引擎保存的页面索引已经过期了，网站信息已经发生变化，但 是搜索引擎的保存的数据还是以前采集来的数据，没有进行更新。在互联网信息 更新频率越来越快的形势之下，为了保存本地存储的页面的“新鲜度”，爬行器 必须阶段性的更新页面。 网页库的更新模式一般分为两种：备份式更新和即时更新【2 ”。备份式更新是 指页面存储器将爬行器传送过来的网页存入网页库之前先存入更新节点，每隔固 定时间，或一轮爬行结束后，将更新节点与当前使用的网页库合并，然后索引器 将整个库进行索引，形成新的索引库。这种方法容易实现，而且可以减少更新与 读取的冲突。即时更新指页面存储器收到爬行器传送的网页，直接存入当前使用 的网页库中，并马上提交给索引器进行索引，索引结果直接提交给索引库，即时 更新。 上世纪末，一个新的网页被主流的搜索引擎索引需要耗费6 个月的时间【2 3 】。 由于互联网规模的不断增长，搜索引擎索引更新的速度也不断加快。2 0 0 2 年底 的数据显示，g o o g l e 每月对其索引库进行一次更新，对级别较高和更新较快的 网站提供更快的更新速度。一些新的搜索引擎产品更新频率更高，例如i i l l ( t o m i 的w 曲s e a r c h9 每隔1 0 至1 4 天对整个索引库进行更新。随着互联网信息更新速 度的加快，搜索引擎数据更新速度也必须不断提高。 2 4 5 爬行陷阱 爬行陷阱是指一个能够引起爬行器无限地爬行的站点，它拖住了爬行器的工 作进程、无限消耗计算机的计算资源。有些爬行陷阱是无意中生成的，例如超链 接所形成的环路。有些爬行陷阱是人为设置的，例如使用c g i ( c o m m o ng a t e w a y i n t e r 丘l c e ) 动态生成网页诱导爬行器下载，网页内容略有不同，相应的u 也也不 同。故意设置爬行陷阱的动机是多种多样的。例如a 皿t i s p 锄陷阱就是用来逮住 i n t e m e tm a r k e t e r s 所用的爬行器，该爬行器四处查找e m a 儿地址，然后四处兜 售；有的是为了提高本网站在搜索引擎中的排名，使用一些欺诈手段；有的是担 心网络上大量搜索引擎对自己的正常服务产生影响，占用了自己过多的服务器资 源，从而将爬行器引入到另外的一台服务器。尽管有的服务器设置了r o b o t e x c l u s i o n ，但不是所有的爬行器都遵循该规则，所以有些网站就不得不采用爬行 陷阱来保证自己服务器正常工作。 北京工业大学工学硕士学位论文 在编写爬行器的时候，我们一方面要避开网站设置的爬行陷阱，同时也应该 不影响它们的正常工作，尽量避免对一个网站的持续大量地访问。 2 4 6 深度爬行 深度爬行是近年来兴起的一个关于爬行器的研究热点。随着互联网技术的不 断发展，动态页面大量增加。在客户机的页面发出请求之后，服务器端的程序生 成了动态页面并发送给客户机，这些页面里面往往包含有用的信息。但是，很少 有动态页面被爬行和索引【2 “。传统的爬行器不能处理多种多样的动态网页，因此 这些动态网页中信息无法被挖掘出来。这些隐藏的动态信息被称为“d e c pw e b ”。 爬行d e 印w 曲信息是一个非常有挑战性的问题，这有两个原因：第一，这些隐 藏信息的规模十分巨大，有研究表明，d e e pw 曲的信息总量超过7 5 0 0 t b ，而普 通w 曲信息总量仅有1 9 t b ，相差4 0 0 多倍 ”】；第二，获取这些隐藏信息需要 通过严格限制的访问界面，这些访问界面是为人而不是机器设计的，而训练爬行 器去适应这些访问界面绝不是一件轻而易举的事情。如今，如何挖掘d e c pw 曲 信息已经成为了各大搜索引擎厂商竞争的焦点。 2 6 小结 本章介绍了爬行器的相关技术。爬行器的启发策略有助于爬行器下载高质量 的网页：并行爬行技术可以大大提高爬行器的运行效率；有效的网页存储和更新 方法是搜索引擎为用户提供优质检索服务的保障；爬行器运行时需要注意避开爬 行陷阱的干扰；深度爬行是爬行器未来发展过程中需要着重解决的问题。 第3 章并行爬行器的西作与呲步 第3 章并行爬行器的协作与同步 并行爬行器一般由多个爬虫组成，每个爬虫和单个的爬行器类似，多个爬虫 需要共同完成采集网页的任务。在提高了采集效率的同时，也会带来页面重复或 者采集质量下降等问题，这就需要并行爬行器提供一种台理的机制，让所有的爬 虫能够相互协作，以保证并行爬行器的正常运行。 本章介绍了并行爬行器c h a o c r a w l e r 的架构和爬虫的协作方式，具体包括任 务分配，协作算法，系统内部通信方式，以及数据的共享和并发访阔。 3 1 并行爬行器的架构 并行爬行器一般包含多个爬虫，每个爬虫需要完成的任务和单个的爬行器类 似，它们从互联网上下载网页，并把网页保存在本地的磁盘，从中抽耿u r l 并沿 着这些u r l 的指向继续爬行。由于并行爬行器需要分割下载任务，可能爬虫会将 自己抽耿的u i 也发送给其他爬虫。这些爬虫可能分布在同一个同域网之中，或者 分散在不同的地理位置。图3 1 描述了并行爬行器的一般架构。 日c 弧c 矧p g c i 目q s 。f u 心t 图3 1 并行爬行器的一股架构”i j f 1 9 i l r e3 10 e n e r “盯曲i k c t u r eo fap 眦l l e lc r a w l 盯 根据爬虫的分散程度不同，可以把并行爬行器分成以下两大类： 1 、站内并行爬行器：这种并行爬行器的所有爬虫在同一个局域阱里运行， 通过高速的网络连接相互通信。这些爬虫通过同一个网络去访问外部互联网，下 载网页，所有的网络负载都集中在他们所在的那个局域网的出口上。由于局域网 的带宽较高，爬虫之间的通信的效率能够得到保证；但是网络出口的总带宽l 限 是同定的，爬虫的数量会受到局域网出口带宽的限制。 2 、分布武爬行器：当并行爬行器的爬