《这就是搜索引擎》爬虫部分摘抄总结

《这就是搜索引擎》这本书的第二章是关于爬虫的,干货很多(文章几乎没有废话,所以复制居多),可以参考搜索引擎是如何构建爬虫系统的。

1 通用爬虫框架

首先从互联网页面中精心选择一部分网页,以这些网页的链接地址作为种子URL,将这些种子URL放入待抓取URL队列中,爬虫从待抓取URL队列依次读取,并将URL通过DNS解析,把链接地址转换为网站服务器对应的IP地址。然后将其和网页相对路径名称交给网页下载器,网页下载器负责页面内容的下载。对于下载到本地的网页,一方面将其存储到页面库中,等待建立索引等后续处理;另一方面将下载网页的URL放入已抓取URL队列中,这个队列记载了爬虫系统已经下载过的网页URL,以避免网页的重复抓取。对于刚下载的网页,从中抽取出所包含的所有链接信息,并在已抓取URL队列中检查,如果发现链接还没有被抓取过,则将这个URL放入待抓取URL队列末尾,在之后的抓取调度中会下载这个URL对应的网页。如此这般,形成循环,直到待抓取URL队列为空,这代表着爬虫系统已将能够抓取的网页尽数抓完,此时完成了一轮完整的抓取过程。

如果从更加宏观的角度考虑,处于动态抓取过程中的爬虫和互联网所有网页之间的关系,可以大致如下图所示,将互联网页面划分为5个部分:

  • 已下载网页集合:爬虫已经从互联网下载到本地进行索引的网页集合。
  • 已过期网页集合:由于网页数量巨大,爬虫完整抓取一轮需要较长时间,在抓取过程中,很多已经下载的网页可能过期。之所以如此,是因为互联网网页处于不断的动态变化过程中,所以易产生本地网页内容和真实互联网网页不一致的情况。
  • 待下载网页集合:即处于图2-1中待抓取URL队列中的网页,这些网页即将被爬虫下载。
  • 可知网页集合:这些网页还没有被爬虫下载,也没有出现在待抓取URL队列中,不过通过已经抓取的网页或者在待抓取URL队列中的网页,总是能够通过链接关系发现它们,稍晚时候会被爬虫抓取并索引。
  • 不可知网页集合:有些网页对于爬虫来说是无法抓取到的,这部分网页构成了不可知网页集合。事实上,这部分网页所占的比例很高。

根据具体应用的不同,爬虫系统在许多方面存在差异,大体而言,可以将爬虫划分为如下3种类型:

  • 批量型爬虫(Batch Crawler):批量型爬虫有比较明确的抓取范围和目标,当爬虫达到这个设定的目标后,即停止抓取过程。至于具体目标可能各异,也许是设定抓取一定数量的网页即可,也许是设定抓取消耗的时间等,不一而足。
  • 增量型爬虫(Incremental Crawler):增量型爬虫与批量型爬虫不同,会保持持续不断的抓取,对于抓取到的网页,要定期更新,因为互联网网页处于不断变化中,新增网页、网页被删除或者网页内容更改都很常见,而增量型爬虫需要及时反映这种变化,所以处于持续不断的抓取过程中,不是在抓取新网页,就是在更新已有网页。通用的商业搜索引擎爬虫基本都属此类。
  • 垂直型爬虫(Focused Crawler):垂直型爬虫关注特定主题内容或者属于特定行业的网页,比如对于健康网站来说,只需要从互联网页面里找到与健康相关的页面内容即可,其他行业的内容不在考虑范围。垂直型爬虫一个最大的特点和难点就是:如何识别网页内容是否属于指定行业或者主题。从节省系统资源的角度来说,不太可能把所有互联网页面下载下来之后再去筛选,这样浪费资源就太过分了,往往需要爬虫在抓取阶段就能够动态识别某个网址是否与主题相关,并尽量不去抓取无关页面,以达到节省资源的目的。垂直搜索网站或者垂直行业网站往往需要此种类型的爬虫。

2 优秀爬虫的特点

高性能

互联网的网页数量庞大如海,所以爬虫的性能至关重要,这里的性能主要是指爬虫下载网页的抓取速度,常见的评价方式是以爬虫每秒能够下载的网页数量作为性能指标,单位时间能够下载的网页数量越多,则爬虫的性能越高。

要提高爬虫的性能,在设计时程序访问磁盘的操作方法及具体实现时数据结构的选择很关键。比如对于待抓取URL队列和已抓取URL队列,因为URL数量非常大,不同实现方式性能表现迥异,所以高效的数据结构对于爬虫性能影响很大。

可扩展性

如上所述,爬虫需要抓取的网页数量巨大,即使单个爬虫的性能很高,要将所有网页都下载到本地,仍然需要相当长的时间周期,为了能够尽可能缩短抓取周期,爬虫系统应该有很好的可扩展性,即很容易通过增加抓取服务器和爬虫数量来达到此目的。

目前实用的大型网络爬虫一定是分布式运行的,即多台服务器专做抓取,每台服务器部署多个爬虫,每个爬虫多线程运行,通过多种方式增加并发性。对于巨型的搜索引擎服务商来说,可能还要在全球范围、不同地域分别部署数据中心,爬虫也被分配到不同的数据中心,这样对于提高爬虫系统的整体性能是很有帮助的。

健壮性

爬虫要访问各种类型的网站服务器,可能会遇到很多种非正常情况,比如网页HTML编码不规范,被抓取服务器突然死机,甚至是爬虫陷阱等。爬虫对各种异常情况能够正确处理非常重要,否则可能会不定期停止工作,这是无法忍受的。

从另外一个角度来讲,假设爬虫程序在抓取过程中死掉,或者爬虫所在的服务器宕机,健壮的爬虫系统应该能够做到:再次启动爬虫时,能够恢复之前抓取的内容和数据结构,而不是每次都需要把所有工作完全从头做起,这也是爬虫健壮性的一种体现。

友好性

爬虫的友好性包含两方面的含义:一是保护网站的部分私密性,另一是减少被抓取网站的网络负载。

爬虫抓取的对象是各种类型的网站,对于网站拥有者来说,有些内容并不希望被所有人搜索到,所以需要设定协议,来告知爬虫哪些内容是不允许抓取的。目前有两种主流的方法可达此目的:爬虫禁抓协议和网页禁抓标记。

爬虫禁抓协议(Robot Exclusion Protocol)指的是由网站所有者生成一个指定的文件robot.txt,并放在网站服务器的根目录下,这个文件指明了网站中哪些目录下的网页是不允许爬虫抓取的。具有友好性的爬虫在抓取该网站的网页前,首先要读取robot.txt文件,对于禁止抓取的网页一般不进行下载。

遵循以上协议的爬虫可以被认为是友好的,这是从保护私密性的角度考虑的。另外一种友好性则是,希望爬虫对某网站的访问造成的网络负载较低。爬虫一般会根据网页的链接连续获取某网站的网页,如果爬虫访问网站频率过高,会给网站服务器造成很大的访问压力,有时候甚至会影响网站的正常访问,造成类似DOS攻击的效果,所以为了减少网站的网络负载,友好性的爬虫应该在抓取策略部署时考虑每个被抓取网站的负载,在尽可能不影响爬虫性能的情况下,减少对单一站点短期内的高频访问。

3 爬虫质量的评价标准

如果从搜索引擎用户体验的角度考虑,对爬虫的工作效果有不同的评价标准,其中最主要的3个标准是:抓取网页覆盖率、抓取网页时新性及抓取网页重要性。如果这3个方面做得好,则搜索引擎用户体验必佳。

通盘考虑以上3个因素,可以将目前爬虫研发的目标简单描述如下:在资源有限的情况下,既然搜索引擎只能抓取互联网现存网页的一部分,那么就尽可能选择比较重要的那部分页面来索引;对于已经抓取到的网页,尽可能快地更新其内容,使得索引网页和互联网对应页面内容同步更新;在此基础上,尽可能扩大抓取范围,抓取到更多以前无法发现的网页。3个“尽可能”基本说清楚了爬虫系统为增强用户体验而奋斗的目标。

以Google为例,其至少包含两套不同目的的爬虫系统,一套被称为Fresh Bot,主要考虑网页的时新性,对于内容更新频繁的网页,目前可以达到以秒计的更新周期;而另外一套被称之为Deep Crawl Bot,主要针对其他更新不是那么频繁的网页抓取,以天为更新周期。

4 抓取策略

爬虫的不同抓取策略,就是利用不同的方法来确定待抓取URL队列中URL优先顺序的。

爬虫的抓取策略有很多种,但不论方法如何,其基本目标一致:优先选择重要网页进行抓取。

宽度优先遍历策略(Breath First)

“将新下载网页包含的链接直接追加到待抓取URL队列末尾”,这就是宽度优先遍历的思想。也就是说,这种方法并没有明确提出和使用网页重要性衡量标准,只是机械地将新下载的网页抽取链接,并追加到待抓取URL队列中,以此安排URL的下载顺序。图2-7是这种策略的示意图:假设队列头的网页是1号网页,从1号网页中抽取出3个链接指向2号、3号和4号网页,于是按照编号顺序依次放入待抓取URL队列,图中网页的编号就是这个网页在待抓取URL队列中的顺序编号,之后爬虫以此顺序进行下载。

非完全PageRank策略(Partial PageRank)

PageRank是一种著名的链接分析算法,可以用来衡量网页的重要性。但是PageRank是个全局性算法,也就是说当所有网页都下载完成后,其计算结果才是可靠的,而爬虫的目的就是去下载网页,在运行过程中只能看到一部分页面,所以在抓取阶段的网页是无法获得可靠PageRank得分的。

非完全PageRank策略的基本思路:对于已经下载的网页,加上待抓取URL队列中的URL一起,形成网页集合,在此集合内进行PageRank计算,计算完成后,将待抓取URL队列里的网页按照PageRank得分由高到低排序,形成的序列就是爬虫接下来应该依次抓取的URL列表。

如果每次新抓取到一个网页,就将所有已经下载的网页重新计算新的非完全PageRank值,明显效率太低,在现实中是不可行的。一个折中的办法是:每当新下载的网页攒够K个,然后将所有下载页面重新计算一遍新的非完全PageRank。

在展开下一轮PageRank计算之前,从新下载的网页抽取出包含的链接,很有可能这些链接的重要性非常高,理应优先下载,这种情况该如何解决?非完全PageRank赋予这些新抽取出来但是又没有PageRank值的网页一个临时PageRank值,将这个网页的所有入链传导的PageRank值汇总,作为临时PageRank值,如果这个值比待抓取URL队列中已经计算出来PageRank值的网页高,那么优先下载这个URL。

下图是非完全PageRank策略的一个简略示意图。我们设定每下载3个网页即进行新的PageRank计算,此时已经有{P1,P2,P3}3个网页下载到本地,这3个网页包含的链接指向{P4,P5,P6},形成了待抓取URL队列,如何决定其下载顺序?将这6个网页形成新的集合,对这个集合计算PageRank值,这样P4、P5和P6就获得自己对应的PageRank值,由大到小排序,即可得出其下载顺序。这里可以假设顺序为:P5、P4、P6,当下载P5页面后抽取出链接,指向页面P8,此时赋予P8临时PageRank值,如果这个值大于P4和P6的PageRank,则接下来优先下载P8。如此不断循环,即形成了非完全PageRank策略的计算思路。

非完全PageRank看上去相对复杂,那么是否效果一定优于简单的宽度优先遍历策略呢?不同的实验结果存在争议,有些表明非完全PageRank结果略优,有些实验结果结论则恰恰相反。更有研究人员指出:非完全PageRank计算得出的重要性与完整的PageRank计算结果差异很大,不应作为衡量抓取过程中URL重要性计算的依据。

OCIP策略(Online Page Importance Computation,在线页面重要性计算)

可以将其看做是一种改进的PageRank算法。在算法开始之前,每个互联网页面都给予相同的“现金”(cash),每当下载了某个页面P后,P将自己拥有的“现金”平均分配给页面中包含的链接页面,把自己的“现金”清空。而对于待抓取URL队列中的网页,则根据其手头拥有的现金金额多少排序,优先下载现金最充裕的网页。OCIP从大的框架上与PageRank思路基本一致,区别在于:PageRank每次需要迭代计算,而OCIP策略不需要迭代过程,所以计算速度远远快于PageRank,适合实时计算使用。同时,PageRank在计算时,存在向无链接关系网页的远程跳转过程,而OCIP没有这一计算因子。实验结果表明,OCIP是种较好的重要性衡量策略,效果略优于宽度优先遍历策略。

大站优先策略(Larger Sites First)

大站优先策略思路很直接:以网站为单位来衡量网页重要性,对于待抓取URL队列中的网页,根据所属网站归类,如果哪个网站等待下载的页面最多,则优先下载这些链接。其本质思想倾向于优先下载大型网站,因为大型网站往往包含更多的页面。鉴于大型网站往往是著名企业的内容,其网页质量一般较高,所以这个思路虽然简单,但是有一定依据。实验表明这个算法效果也要略优于宽度优先遍历策略。

网页更新策略

常用的网页更新策略有3种:历史参考策略、用户体验策略和聚类抽样策略。

历史参考策略

历史参考策略是最直观的一种更新策略,它建立于如下假设之上:过去频繁更新的网页,那么将来也会频繁更新。所以,为了预估某个网页何时进行更新,可以通过参考其历史更新情况来做出决定。

这种方法往往利用泊松过程来对网页的变化进行建模,根据每个网页过去的变动情况,利用模型预测将来何时内容会再次发生变化,以此来指导爬虫的抓取过程。但是不同方法侧重不尽相同,比如有的研究将一个网页划分成不同的区域,抓取策略应该忽略掉广告栏或者导航栏这种不重要区域的频繁变化,而集中在主题内容的变化探测和建模上。

用户体验策略

一般来说,搜索引擎用户提交查询后,相关的搜索结果可能成千上万,而用户没有耐心查看排在后面的搜索结果,往往只查看前3页搜索内容。用户体验策略就是利用搜索引擎用户的这个特点来设计更新策略的。

这种更新策略以用户体验为核心,即使本地索引的网页内容是过时的,但是如果不影响用户体验,那么晚些更新这些过时网页也未尝不可。所以判断一个网页何时更新为好,取决于这个网页的内容变化所带来搜索质量的变化(往往采用搜索结果排名的变化来衡量),影响越大的网页,则应该越快更新。

用户体验策略保存网页的多个历史版本,并根据过去每次内容变化对搜索质量的影响,得出一个平均值,以此作为判断爬虫重抓该网页时机的参考依据,对于影响越厉害的网页,则越优先调度重新抓取。

聚类抽样策略

上面介绍的两种网页更新策略严重依赖网页的历史更新信息,因为这是能够进行后续计算的基础。但是在现实中,为每个网页保存其历史信息,搜索系统会大量增加额外负担。从另外一个角度考虑,如果是首次抓取到的网页,因为没有历史信息,所以也就无法按照这两种思路去预估其更新周期。聚类抽样策略即是为了解决上述缺点而提出的。

聚类抽样策略认为:网页具有一些属性,根据这些属性可以预测其更新周期,具有相似属性的网页,其更新周期也是类似的。于是,可以根据这些属性将网页归类,同一类别内的网页具有相同的更新频率。为了计算某个类别的更新周期,只需对类别内网页进行采样,以这些被采样网页的更新周期作为类别内所有其他网页的更新周期。与之前叙述的两种方法相比较,这种策略一方面无须为每个网页保存历史信息;另一方面,对于新网页,即使没有历史信息,也可以根据其所属类别来对其进行更新。

聚类抽样策略基本流程如下图所示,首先根据网页所表现出的特征,将其聚类成不同的类别,每个类别内的网页具有相似的更新周期。从类别中抽取一部分最有代表性的网页(一般抽取最靠近类中心的那些网页),对这些网页计算其更新周期,那么这个更新周期适用于类别内的所有网页,之后即可根据网页所属类别来决定其更新频率。

在Tan等人的研究中,将能够体现网页更新周期的属性特征划分为两大类:静态特征和动态特征。静态特征包括:页面的内容、图片数量、页面大小、链接深度、PageRank值等十几种;而动态特征则体现了静态特征随着时间的变化情况,比如图片数量的变化情况、入链出链的变化情况等。根据这两类特征,即可对网页进行聚类。

上图所示为一个较为通用的流程,不同算法在细节处有差异。比如有些研究直接省略聚类这个步骤,而是以网站作为聚类单位,即假设属于同一个网站的网页具有相同的更新周期,对网站内页面进行抽样,计算其更新频率,之后网站内所有网页以这个更新周期为准。这个假设虽显粗糙,因为很明显同一网站内网页更新频率差异很大,但是可以省掉聚类这个步骤,在计算效率方面会更可行些。

相关实验表明,聚类抽样策略效果好于前述两种更新策略,但是对以亿计的网页进行聚类,其难度也是非常巨大的。

暗网抓取(Deep Web Crawling)

所谓暗网,是指目前搜索引擎爬虫按照常规方式很难抓取到的互联网页面。如前所述,搜索引擎爬虫依赖页面中的链接关系发现新的页面,但是很多网站的内容是以数据库方式存储的,典型的例子是一些垂直领域网站,比如携程旅行网的机票数据,很难有显式链接指向数据库内的记录,往往是服务网站提供组合查询界面,只有用户按照需求输入查询之后,才可能获得相关数据。所以,常规的爬虫无法索引这些数据内容,这是暗网的命名由来。

为了能够对暗网数据进行索引,需要研发与常规爬虫机制不同的系统,这类爬虫被称做暗网爬虫。暗网爬虫的目的是将暗网数据从数据库中挖掘出来,并将其加入搜索引擎的索引,这样用户在搜索时便可利用这些数据,增加信息覆盖程度。

垂直网站提供的搜索界面,往往需要人工选择或者填写内容,比如机票搜索需要选择出发地、到达地和日期,图书搜索需要指出书名或者作者。而暗网爬虫为了能够挖掘数据库的记录,必须模拟人的行为,填写内容并提交表单。对于暗网爬虫来说,其技术挑战有两点:一是查询组合太多,如果一一组合遍历,那么会给被访问网站造成太大压力,所以如何精心组合查询选项是个难点;第二点在于:有的查询是文本框,比如图书搜索中需要输入书名,爬虫怎样才能够填入合适的内容?这个也颇具挑战性。

分布式爬虫

分布式爬虫可以分为若干个分布式层级,不同的应用可能由其中部分层级构成,下图是一个大型分布式爬虫的3个层级:分布式数据中心、分布式抓取服务器及分布式爬虫程序。整个爬虫系统由全球多个分布式数据中心共同构成,每个数据中心负责抓取本地域周边的互联网网页。

每个数据中心又由多台高速网络连接的抓取服务器构成,而每台服务器又可以部署多个爬虫程序。通过多层级的分布式爬虫体系,才可能保证抓取数据的及时性和全面性。

对于同一数据中心的多台抓取服务器,不同机器之间的分工协同方式会有差异,常见的分布式架构有两种:主从式分布爬虫和对等式分布爬虫。

主从式分布爬虫(Master-Slave)

对于主从式分布爬虫,不同的服务器承担不同的角色分工,其中有一台专门负责对其他服务器提供URL分发服务,其他机器则进行实际的网页下载。URL服务器维护待抓取URL队列,并从中获得待抓取网页的URL,分配给不同的抓取服务器,另外还要对抓取服务器之间的工作进行负载均衡,使得各个服务器承担的工作量大致相等,不至于出现忙的过忙、闲的过闲的情形。抓取服务器之间没有通信联系,每个抓取服务器只和URL服务器进行消息传递。

对等式分布爬虫(Peer to Peer)

在对等式分布爬虫体系中,服务器之间不存在分工差异,每台服务器承担相同的功能,各自负担一部分URL的抓取工作。

由服务器自己来判断某个URL是否应该由自己来抓取,或者将这个URL传递给相应的服务器。至于采取的判断方法,则是对网址的主域名进行哈希计算,之后取模(即hash[域名]%m,这里的m对应服务器个数),如果计算所得的值和抓取服务器编号匹配,则自己下载该网页,否则将该网址转发给对应编号的抓取服务器。

为了解决哈希取模的对等式分布爬虫存在的问题,UbiCrawler爬虫提出了改进方案,即放弃哈希取模方式,转而采用一致性哈希方法(Consisting Hash)来确定服务器的任务分工。

对等式分布爬虫(一致性哈希)

一致性哈希将网站的主域名进行哈希,映射为一个范围在0到232之间的某个数值,大量的网站主域名会被均匀地哈希到这个数值区间。将哈希值范围首尾相接,即认为数值0和最大值重合,这样可以将其看做有序的环状序列,从数值0开始,沿着环的顺时针方向,哈希值逐渐增大,直到环的结尾。而某个抓取服务器则负责这个环状序列的一个片段,即落在某个哈希取值范围内的URL都由该服务器负责下载。这样即可确定每台服务器的职责范围。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

选择一个异步应用程序服务器还是多阻塞服务器?

Jonathan Willis,白天是软件开发者,晚上是超级英雄,有人通过Twitter在StackOverflow上向他提了一个有趣的问题: 许多Rails应...

2218
来自专栏小白课代表

Autodesk Navisworks 2016 安装教程。

Autodesk Navisworks软件能够将AutoCAD和Revit®系列等应用创建的设计数据,与来自其它设计工具的几何图形和信息相结合,将其作为整体的三...

1253
来自专栏小白课代表

Autodesk Navisworks 2019 安装教程。

Autodesk Navisworks软件能够将AutoCAD和Revit®系列等应用创建的设计数据,与来自其它设计工具的几何图形和信息相结合,将其作为整体的三...

902
来自专栏北京马哥教育

正确评估SQL数据库性能,你必须知道的原理和方法!

作者:阿特 来源: http://blog.csdn.net/capsicum29/article/details/71480799 数据库是一个很重要的模块...

49211
来自专栏小白课代表

matlab 2014b

MATLAB是matrix&laboratory两个词的组合,意为矩阵工厂(矩阵实验室)。是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式...

1363
来自专栏一个小程序员的成长笔记

Bug 级别定义标准

1412
来自专栏跨界架构师

分布式系统关注点——仅需这一篇,吃透「负载均衡」妥妥的

  上一篇《分布式系统关注点——初识「高可用」》我们对「高可用」有了一个初步认识,其中认为「负载均衡」是「高可用」的核心工作。那么,本篇将通过图文并茂的方式,来...

1452
来自专栏FreeBuf

利用开源工具TempestSDR实现屏显内容远程窃取

你可能还不了解“TEMPEST”,它是用来窃取远程视频信息的一种基于软件定义的无线电平台技术,可被当做间谍工具包使用,用来针对某些目标电子设备的射频信号(声音和...

2435
来自专栏小白课代表

Autodesk Navisworks 2015 安装教程。

Autodesk Navisworks软件能够将AutoCAD和Revit®系列等应用创建的设计数据,与来自其它设计工具的几何图形和信息相结合,将其作为整体的三...

832
来自专栏章鱼的慢慢技术路

Unity导入3D模型的过程与方法

3744

扫码关注云+社区

领取腾讯云代金券