搜索引擎原理（一）网络爬虫

开通“搜索引擎原理”专栏，以后每周整理一篇关于通用搜索引擎原理的文章，先从网络爬虫开始。

搜索引擎的技术架构复杂，Google为了存储海量数据，研发了一整套云存储与云计算平台，比如著名的GFS和Map/Reduce。

通用搜索引擎的架构大概由以下几部分组成（图1）：

（图1）

当然上面只是一个简易的模型，每一个模块都可以独立成一个完整的系统，本专栏会依次讲解。

在通用搜索引擎中，其处理对象是互联网网页。基本的做法是递归下载网页（当然这里面可能涉及到一些禁止爬虫爬取的协议），形成互联网网页的镜像备份，然后由其它程序处理这些网页。

网络爬虫是搜索引擎中最基础的组件。

本文主要介绍以下内容：

• 基本架构
• 内容抓取策略
• 内容更新策略
• 暗网抓取
• 分布式爬虫

基本架构

以下是搜索引擎爬虫的基本架构：

（图2）

爬虫首先从互联网页面中选取一部分“种子URL”，然后将这些URL放入“待抓取URL列表”，爬虫从待抓取列表中依次访问URL，然后将网页路径名称交给“网页下载器”（一般是独立的服务器或服务器集群）进行下载。对于下载到的网页，一般有两个处理步骤，第一步是将其存储到页面库中，等待建立索引；二是将该URL放倒已读取URL队列中，以避免网页重复抓取。

对于通用爬虫，往往还需要网页去重和网页反作弊，以后会讲到。

基本上来说，网页爬虫可以分为5个部分：

1. 已下载网页集合；
2. 已过期网页集合：互联网在不停变化，网页也会变化；
3. 待下载网页集合；
4. 可知网页集合：可以通过Web的URL进行发现的网页；
5. 不可知网页集合：有些网页对爬虫来说无法抓取，这就成了不可知网页集合。

大多数爬虫遵循（图2）的处理流程，但根据业务的不同，爬虫可以分为以下三种类型：

1. 批量型爬虫：有目的的有范围的抓取；
2. 增量型爬虫：无目的无范围的抓取，通用的商用搜索引擎都属于这种；
3. 垂直型爬虫：特定主题、行业等的爬虫；

爬虫特性

优秀的爬虫应该具备以下特性：

1. 高性能，面对互联网海量数据，常见的爬虫性能评价标准是，每秒能够下载的网页数量。单位时间下载的网页数量越多，性能越高；
2. 可拓展性，可以动态扩展服务器和哦啊虫数量，并且能够不同地域的部署数据中心，即分布式运行；
3. 健壮性，在遇到一些特殊情况时系统不会宕调；
4. 友好性，此条非常重要。有两层含义：
   1. 保护网站的部分私密性，即遵守爬虫禁抓协议；
      1. 爬虫禁抓协议介绍：
         1. 由网站所有者指定的一个文件：robot.txt，这个文件指明了哪些目录下的网页是不允许爬虫抓取的。具备友好性的爬虫，在抓取网站之前应该读取其robot.txt文件。
   2. 减少被抓取网站的网络负载，即需要在每次抓取之间加延迟处理。

内容抓取策略

互联网数据量非常大，所以待抓取URL列表也是一个非常庞大的存储库，如何高效抓取便成了需要解决的问题。

目前代表性的方案主要有四个：

1. 宽度优先遍历
2. 非完全PageRank
3. OPIC策略
4. 大站优先策略

宽度优先遍历

宽度优先遍历是一种古老简单而又有效的方法，在爬虫建立之初就在使用，看下示意图就好了：

宽度优先遍历的本质就是将下载网页所包含的链接直接追加到待抓取URL末尾。这种方法的缺点就是完全无目的，不管网页重要性排名，这会造成质量高的网站可能被滞后下载。所以产生了网页重要性评价标准：PageRank。

非完全PageRank策略

PageRank是一项著名的网页重要性分析算法，以后的文章会详细讲解这个算法。利用PageRank可以对网页链接进行优先级排序。但这里有个问题，PageRank是个全局性算法，他需要在网页下载完成后全局计算，而爬虫的目的是下载网页，它只能边下载边分析，所以叫“非完全PageRank”。

OPIC策略

OPIC的英文全称是：Online Page Importance Computation，中文含义是“在线页面重要性计算”，其实就是改进的PageRank算法。其基本原理如下：

1. 初始化每个互联网页面的“现金”，现金数量相同；
2. 下载某网页P后，P将自己拥有的“现金”平均分配给页面中包含的链接页面，并把自己的现金清空；
3. 对于待抓取URL队列中的网页，根据手头现金拥有的多少进行排序，优先下载现金最充裕的网页；

OPIC的效果优于宽度优先搜索策略。

大站优先策略

原理非常简单，整理好著名网站，然后优先下载即可。

内容更新策略

互联网最显著的特征是其动态性，页面的内容随时都会被更改或删除，因此更新网页内容也是爬虫的一项重要工作。

历史参考策略

历史参考是基于一个假设：过去频繁更新的网页将来也会频繁更新。

比较主观，需要参考之前的历史更新情况。

用户体验策略

如果内容不影响用户使用，那么晚些更新网页也行。判断一个网页何时更新为好取决于网页内容的变化带来的网页质量的变化。

聚类抽样策略

聚类抽样策略认为网页具有一些属性，这些属性将会影响网页的更新周期。

聚类抽样策略基本流程如（图3）所示：

（图3）

首先根据网页表现出的特征聚类成不同的类别，每个类别内的网页具有相似的更新周期。从类别中选取具有代表性的网页，对这些网页计算其更新周期，那么这个更新周期适用于类别内的所有网页。

实践表明，聚类抽样优于前两种，但是对亿计的网页计算难度也非常巨大。

暗网抓取

暗网指搜索引擎难以抓到的网页，比如需要用户登录才能看到的网页或其它一些违法网站。

对于暗网来说，搜索引擎提供商会和其联系合作，寻求API或表单填写的方式完成数据的抓取。

分布式爬虫

对于商用搜索引擎，分布式爬虫是必须采取的技术。

分布式爬虫可以由若干个层级组成，一般分为三层：

1. 分布式数据中心
2. 分布式抓取服务器
3. 分布式爬虫程序

每个数据中心可以分布在全球各地，地缘更近，抓取速度更快。

主要的分布式架构主要有两种：

1. 主从分布式爬虫
2. 对等分布式爬虫

主从分布式爬虫

对于主从式爬虫，不同的服务器承担不同的分工，但是有一台服务器专门提供URL分发服务，对整个系统进行复杂均衡。

（图4）

Google早期使用这种爬虫。

对等分布式爬虫

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

由于没有URL分发服务器，所以分工就成了问题。为了解决这个问题，工业界普遍采用“一致性哈希算法”来确定服务器的任务分工。

一致性哈希算法将网站的主域名进行哈希，映射为一个范围在0到2^32之间的某个数值，大量的网站主域名会被均匀哈希到这个数值区间。将哈希值范围首尾相连，即认为数值0和最大值重合，这样可以将其看作有序的环状序列，从数值0开始，沿着环的顺时针方向，哈希值逐渐增大，直到环的结尾。而某个抓取服务器则负责这个环状序列的一个片段，即落在某个哈希取值范围的URL都由这台服务器下载，这样每台服务器的责任便得到了清晰划分，参考（图5）。

（图5）

现在假设2号服务器接收到了域名http://www.weibo.com，经过哈希计算后，2号服务器知道在自己的管辖范围内，于是自己下载这个URL。在此之后，3号服务器收到了http://www.baidu.com，经过哈希计算，3号服务器确认是2号的管辖范围，于是将URL转发到2号服务器。如果2号服务器司机，那么3号得不到回应，则会暂时按照环的大小顺序查找，将URL转达给第一个碰到的服务器，即1号服务器。此后2号服务器的下载任务会暂时交给1号服务器接管，直到3号服务器重新启动。

对等式爬虫是比较优秀的分布式爬虫方案。

到这里，关于搜索引擎爬虫的一切就讲完了。

下一篇文章将会讲解搜索引擎索引相关内容。