前言

我们重点讨论网络爬虫的设计， 这也是一个有趣且经典的系统设计面试问题。

爬虫开发的复杂性取决于我们想要支持的爬虫规模。它可以是一个小的学校项目，只需要几小时就可以完成，也可以是一个需要专业开发团队持续优化的巨型项目。因此，下面我们会先确定我们需要支持的爬虫规模和特性。

第一步 理解问题并确定设计的边界

爬虫的基本算法很简单。

1. 给定一组URL，下载这些URL对应的所有网页。
2. 从这些网页中提取URL。
3. 将新的URL添加到需要下载的URL列表里。然后重复执行这3个步骤。

爬虫的工作真的像基本算法所述的这样简单吗？并不完全是。 设计大规模的可扩展爬虫是一个极度复杂的任务。在面试时间内，没有人能设计出一个巨型爬虫。在着手设计之前，我们必须通过提问来理解需求并确定设计的边界。

候选人： 爬虫的主要目的是什么？是用于搜索引擎索引、数据挖掘还是其他什么？
面试官： 搜索引擎索引。
候选人： 爬虫每个月收集多少网页？
面试官： 10亿个。
候选人： 包括哪些内容类型？是只有HTML页面， 还是也包括其他内容类型，比如PDF文件、 图片等？
面试官： 仅包括HTML页面。
候选人： 我们需要考虑新增的或者有更新的网页吗？
面试官： 是的，我们应该要考虑新增的或者有更新的网页。
候选人： 我们需要保存从网络上爬取的HTML页面吗？
面试官： 是的，最多要保存5年。
候选人： 我们如何处理有重复内容的网页？
面试官： 忽略有重复内容的网页。

除了要与面试官理清功能需求， 还要确定爬虫是否具备如下特性，它们都是一个好的爬虫应该具备的。

• 可扩展性：互联网很庞大，存在数十亿的网页。爬虫需要通过并行化来高效爬取信息。
• 健壮性：网络上充满了陷阱。糟糕的HTML页面、无响应的服务器、宕机、 恶意链接等都很常见。爬虫必须应对所有这些极端场景。
• 礼貌性：爬虫不应该在很短的时间间隔内对一个网站发送太多请求。
• 可扩展性：系统应该具有灵活性，只需要做最少的更改就能支持新的内容类型。举个例子，如果我们将来想要爬取图片， 应该不需要重新设计整个系统。

封底估算

下面的估算基于很多假设，与面试官交流并达成共识很重要。

• 假设每个月要下载10亿个网页。
• QPS：1,000,000,000÷30÷24÷3600≈400，即每秒约400个网页。
• 峰值QPS=2×QPS=800。
• 假设平均每个网页的大小是500KB。
• 每月需要存储1，000，000，000×500KB=500TB。存储单位计算见传送门。
• 假设数据要保存5年，则500TB×12×5=30PB，即需要30PB的存储空间来保存5年的内容。

第二步 提议高层级的设计并获得认同

一旦明确了需求，我们就可以考虑高层级设计了。受前人关于爬虫研究的启发，，我们提出如下图所示的高层级设计。
首先，我们探索每个组件以了解它们的功能，然后一步步分析这个爬虫的工作流程。

种子URL

爬虫使用种子URL作为爬行的起点。例如，要爬取一所大学网站上的所有网页，直观的方法是用该大学的域名作为种子URL。

URL前线(URL Frontier)

大部分现代爬虫把爬行状态分为两种：即将下载和已经下载。用来存储即将下载的URL的组件叫URL前线。你可以把它看作一个先进先出(FIFO)的队列。

HTML下载器

HTML下载器从互联网上下载网页。要下载的URL由URL前线来提供。

DNS解析器

要下载网页，必须将URL转换成IP地址。HTML下载器请求DNS解析器来获取URL对应的IP地址。举个例子，截至2019年5月3日，www.wikipedia.org会被转换成198.35.26.96这个IP地址。

已见过的内容？

有研究显示，29%的网页是重复内容，这可能导致同样的内容被多次存储。我们引入了“已见过的内容？”数据结构，来消除数据冗余和缩短处理时间。它帮助检测内容是否已存储在系统中。在比较两个HTML文件时，我们可以逐字符地比较。但是这个方法太慢且耗时，特别是有数十亿的网页要比较时。完成这个任务的一个高效方法是比较两个网页的哈希值。

内容存储

它是存储HTML内容的存储系统。选择什么样的存储系统，取决于数据的类型、大小、访问频率、生命周期等因素。硬盘和内存都被用到。

• 大部分内容存储在硬盘中，因为数据集太大，内存装不下。
• 热门内容被存储在内存中以降低延时。

URL提取器

URL提取器从HTML页面中解析和提取链接。下图展示了链接提取过程。通过添加前缀“https://en.wikipedia.org”，相对路径被转换成绝对URL。

URL过滤器

URL过滤器用于排除特定内容类型、文件扩展名、问题链接和“黑名单”网站的URL。

已见过的URL？

“已见过的URL？”是一种数据结构，可以用来追踪记录已访问过的或者已经在URL前线里的URL。“已见过的URL？”可以帮我们避免多次添加同一个URL，重复添加URL会增加服务器负载并导致潜在的无限循环。布隆过滤器和哈希表都是实现“已见过的URL？”组件的常见技术。

URL存储

URL存储用于保存已访问过的URL。
到目前为止，我们讨论了所有系统组件。接下来，我们把它们组合在一起来解释爬虫的工作流程。

爬虫工作流程

为了更好地分步骤解释爬虫工作流程，我们在设计图里加了序号，如下图所示。

第1步：将种子URL添加到URL前线中。
第2步：HTML下载器从URL前线中获取URL列表。
第3步：HTML下载器从DNS解析器中获取URL对应的IP地址并开始下载。
第4步：内容解析器解析HTML页面并检查页面是否有问题。
第5步：内容解析器将解析和验证后的内容传给“已见过的内容？”组件。
第6步：“已见过的内容？”组件检查这个HTML页面是否已经在数据库中。

• 如果页面已经在数据库中，意味着包含同样的内容的不同URL已经被处理过。在这种情况下，这个HTML页面会被丢弃。
• 如果页面不在数据库中，表示系统还没有处理过相同的内容。该页面将被传递给链接提取器。

第7步：链接提取器从HTML页面中提取链接。
第8步：提取出来的链接被传递给URL过滤器进行筛选。
第9步：经过筛选的链接被传递给“已见过的URL？”组件。
第10步：“已见过的URL？”组件检查这个URL是否已经在数据库中，如果是，则意味着它之前被处理过，无须再做处理。
第11步：如果这个URL之前没有被处理过，就将被添加到URL前线中。

第三步 设计继续深入

接下来，我们将深入讨论几个最重要的构建组件和技术。

• 深度优先搜索(DFS)与广度优先搜索(BFS)。
• URL前线。
• HTML下载器。
• 健壮性。
• 可扩展性。
• 检测和避免有问题的内容。

DFS vs BFS

因为DFS的深度可能非常深，所以它通常不是一个好的选择。
BFS是爬虫常用的方法，通过先进先出(FIFO)队列来实现。在一个FIFO队列中， URL按照它们入列的顺序出列。尽管如此， 这种实现方式还有以下两个问题。

• 同一个网页的大部分链接都指向同一个主机。
• 标准的BFS并没有考虑URL的优先级。

URL前线

URL前线是一个重要组件，它是一个存储待下载URL的数据结构，能确保爬虫礼貌地访问网页，确定URL优先级并保证内容新鲜度。

礼貌性

一般来说，爬虫应该避免在短时间内对同一个服务器发送太多的请求。 发送过多请求会被认为“不礼貌” ，甚至可能被视为拒绝服务攻击(DoS)。 举个例子，如果没有任何限制，爬虫可以对同一个网站每秒发送数千个请求。但这可能会让Web服务器不堪重负。

确保礼貌性的大致思路是，从同一个主机每次只下载一个网页。可以在两次下载任务之间加入一定的延时。礼貌性约束是通过维护网站主机名和下载线程(Worker)的映射来实现的。每个下载线程都有独立的FIFO队列且只下载这个队列里的URL。 下图展示了实现爬虫礼貌性的设计。

• 队列路由器：确保每个队列(b1， b2， …， bn)只包含来自同一个主机的URL。
• 映射表：把每个主机映射到队列中 。
  
• FIFO队列（从b1到bn）：每个队列只包含来自同一个主机的URL。• 队列选择器：每个Worker都被映射到一个FIFO队列，它只下载来自这个队列的URL。队列选择器实现队列选择的逻辑。
• 下载线程（Worker1到WorkerN）： Worker一个接一个地下载来源于同一个主机的网页。在两个下载任务之间可以加入延时。

优先级

我们对URL基于有用性来排优先级，可以通过PageRank、网站流量、更新频率等指标来度量。“优先级排序器” (Prioritizer)是处理URL优先级排序的组件。
下图展示了实现URL优先级排序的设计。

• 优先级排序器：它接收URL作为输入并计算其优先级。
• 队列f1到fn： 每个队列都有一个设定好的优先级。 优先级高的队列有更高的概率被选中。
• 队列选择器：从多个队列中随机选择一个，尽管优先级高的队列有更高的概率被选中，但这并不是绝对确定的，仍然存在一定的随机性。

下图展示了URL前线的设计，它包含两个模块。

• 前队列： 实现优先级管理。
• 后队列： 实现礼貌性管理。

新鲜度

由于互联网上不断有网页被添加、删除和修改，所以爬虫必须定期重新爬取下载过的网页，以确保数据是最新的。重新爬取所有的URL是非常消耗时间和资源的。下面是两个优化新鲜度的策略。

• 根据网页的更新历史来判断是否重新爬取。
• 对URL按优先级排序，并且优先频繁地重新爬取重要的网页。

URL前线的存储

在搜索引擎的实际爬取过程中，URL前线中的URL数量可能上亿。把所有内容放在内存中，既不可持续也不可扩展；而把所有内容放在硬盘中也不是理想的方案，因为硬盘的访问速度很慢，很容易成为爬虫爬取数据的瓶颈。
我们采用了一种混合方案。将大部分的URL存储在硬盘上，这样存储空间就不是问题。为了降低从硬盘读/写的开销，我们在内存中维护了缓冲区以进行入队/出队操作。缓冲区中的数据会被定期写入硬盘。

HTML下载器

HTML下载器通过HTTP协议从互联网下载网页。在讨论HTML下载器之前，我们先看看机器人排除协议(Robots Exclusion Protocol)——robots.txt。

robot.txt是网站和爬虫之间通信的标准。它标明了允许爬虫下载哪些网页。在尝试爬取一个网站之前，爬虫应该先检查对应的robots.txt并遵守其中的规则。

为了避免重复下载robots.txt文件，我们会缓存这个文件的结果。 这个文件会被定期下载并保存在缓存中。下面是从https://www.amazon.com/robots.txt中截取的一段robots.txt文件内容。其中规定了如creatorhub之类的目录是不允许谷歌机器人爬取的。

除了robots.txt，性能优化是HTML下载器中的另一个重要概念。
下面是HTML下载器的性能优化方法。

分布式爬取

为了实现高性能，爬取任务被分配给多个服务器，每个服务器中运行着多个线程。 URL空间被分成较小的部分， 这样每个下载器只负责处理一部分URL。下图展示了一个分布式爬取的例子。

缓存DNS解析器（奈斯）

因为很多DNS接口是同步的，所以DNS请求可能要花较长时间， 导致DNS解析器成为爬虫的一个性能瓶颈。 DNS响应时间在10ms到200ms之间。一旦爬虫的一个线程发出DNS请求，其他线程就会被阻塞，直到该DNS请求完成。 维护DNS缓存，避免频繁向DNS服务器发起请求，是一个提高爬虫爬行速度的有效技术。我们的DNS缓存保存了域名与IP地址之间的映射，并通过定时任务进行更新。

本地性

将爬虫服务器按地理位置分布。爬虫服务器离网站主机越近，爬虫的下载速度会越快。本地性设计可以应用到大部分系统组件上：爬虫服务器、 缓存、 队列、存储等。

短超时时间

一些Web服务器响应慢或者根本不响应。为了避免长时间等待，需要确定一个最长等待时间。如果一个主机在预定时间内没有响应，爬虫就会停止该任务转而爬取其他页面。

健壮性

除了性能优化，健壮性也是一个重要的考虑因素。以下是一些提升系统健壮性的方法。

• 一致性哈希：有助于负载在HTML下载器之间均匀分布。使用一致性哈希，可以添加或者移除新的下载器服务器。见传送门。
• 保存爬取状态和数据：为了应对故障，将爬取状态和数据写入存储系统。通过加载保存的爬取状态和数据，可以很容易地重启被中断的爬取过程。
• 异常处理：在大型系统中，错误是无法避免的，出错是很常见的事情。爬虫必须能“得体地”处理异常，避免系统崩溃。
• 数据校验：这是防止系统错误的重要措施。

可扩展性

因为几乎所有系统都在演进，所以系统的设计目标之一就是要足够灵活以支持新的内容类型。爬虫可以通过插入新的模块来进行扩展。下图展示了如何添加新模块。

• PNG下载器模块作为插件被添加进来，用于下载PNG文件。
• 网络监视器模块作为插件被添加进来，用于监控网络，以避免版权和商标侵权。

检查和避免有问题的内容

本节讨论检测及避免重复、无意义或者有害内容的方法。

重复内容

如前所述，接近30%的网页是重复的。哈希和校验和(Checksum)可以帮助我们检测出重复内容。

蜘蛛陷阱

蜘蛛陷阱是可以导致爬虫陷入无限循环的网页，例如，一个无限深的目录结构www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/…。可以通过设置最大URL长度来避免这样的蜘蛛陷阱。尽管如此，并不存在检测蜘蛛陷阱的通用解决方案。含有蜘蛛陷阱的网站是容易识别的，因为在这种网站上网页的数量异常多。但是很难开发出一个自动算法来躲避蜘蛛陷阱。不过，用户可以手动验证和识别蜘蛛陷阱，然后要么在爬取时排除这些网站，要么应用一些定制的URL过滤器。

数据噪声

有些内容只有很少的或者根本没有任何价值，比如广告、代码片段、垃圾邮件URL等。如果有可能，应该将其排除。

第四步 总结

我们先讨论了好爬虫的特点——它应该具有可扩展性、礼貌性和健壮性。接着，我
们给出了设计方案并讨论了关键组件。因为互联网异常庞大且充满陷阱，所以创建一个可扩展的爬虫并非易事。即使讨论了很多内容，但我们依然漏掉了很多相关的讨论点，比如：

• 服务端渲染。无数网站使用JavaScript、 AJAX等脚本来动态生成链接。如果直接下载和解析网页，我们并不能获取这些动态生成的链接。 为了解决这个问题，我们会在解析网页之前先进行服务器端渲染（也叫动态渲染）。
• 滤掉不想要的网页。因为存储容量和爬虫资源是有限的，使用反垃圾组件，有助于滤掉低质量的垃圾页面。
• 数据库复制和分片。复制和分片等技术可以增强数据层的可用性、可扩展性和可靠性。
• 横向扩展。 对于大范围的爬取，需要成百上千的服务器来执行下载任务。保持服务器无状态是关键。
• 可用性、一致性和可靠性。这些概念是任何大型系统成功的核心。
• 数据分析：收集和分析数据对任何系统来说都很重要，因为数据是优化系统的关键要素。

后记

恭喜你已经看到这里了。给自己一些鼓励。干得不错！