在本章，我们重点讨论网络爬虫的设计，这也是一个有趣且经典的系统设计面试问题。
网络爬虫（Web Crawler，下文简称为“爬虫”）也称为机器人(Bot)或者蜘蛛(Spider)，被搜索引擎广泛地用于发现网络上的新内容或者更新的内容。这些内容可以是网页、图片、视频、PDF文件等。爬虫从收集网页开始，然后顺着这些网页上的链接收集新的内容。图-1展示了爬虫爬取页面的示例。爬虫有很多用途。
•搜索引擎索引：这是最常见的使用场景。爬虫收集网页并为搜索引擎创建本地索引。例如，Googlebot就是谷歌搜索引擎背后的爬虫。
•网页存档：这是指从网上收集信息并保存起来以备未来使用的过程。很多国家图书馆运行爬虫来存档网站，比如美国国会图书馆和欧盟网页存档。
•网络挖掘：互联网的迅猛发展为数据挖掘提供了前所未有的机会。网络挖掘帮助我们从互联网上发现有用的信息。比如，顶级金融公司使用爬虫来获取关键公司的股东会议信息和年报，从而了解它们的动向。
•网络监控：爬虫可以帮助监控互联网上的版权和商标侵权行为。例如，Digimarc公司[插图]利用爬虫发现盗版作品并上报。
爬虫开发的复杂性取决于我们想要支持的爬虫规模。它可以是一个小的学校项目，只需要几小时就可以完成，也可以是一个需要专业开发团队持续优化的巨型项目。因此，下面我们会先确定我们需要支持的爬虫规模和特性。
图-1
9.1 场景界定
爬虫的基本算法很简单。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年的内容。
9.2 顶层设计
一旦明确了需求，我们就可以考虑高层级设计了。受前人关于爬虫研究的启发，，我们提出如图-2所示的高层级设计。首先，我们探索每个组件以了解它们的功能，然后一步步分析这个爬虫的工作流程。
图-2
种子URL
爬虫使用种子URL作为爬行的起点。例如，要爬取一所大学网站上的所有网页，直观的方法是用该大学的域名作为种子URL。为了爬整个网络，我们需要有创意地选择种子URL。好的种子URL让我们有一个好的起点，爬虫可以利用它来遍历尽可能多的链接。一般的策略是把整个URL空间分成若干小块。因为不同国家可能有不同的热门网站，所以我们提议的第一个方法是基于物理位置来划分。另一个方法是基于话题来选择种子URL，比如我们可以把URL空间分为购物、体育、健康等部分。种子URL的选择是一个开放式问题。你不必给出完美的答案。只要边想边说出来就好。
URL前线(URL Frontier)
大部分现代爬虫把爬行状态分为两种：即将下载和已经下载。用来存储即将下载的URL的组件叫URL前线。你可以把它看作一个先进先出(FIFO)的队列。关于URL前线的详细信息，将在3.2节讲解。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页面中解析和提取链接。图-3展示了链接提取过程。通过添加前缀“[https://en.wikipedia.org](https://en.wikipedia.org)”，相对路径被转换成绝对URL。
图-3
URL过滤器
URL过滤器用于排除特定内容类型、文件扩展名、问题链接和“黑名单”网站的URL。已见过的URL？
“已见过的URL？”是一种数据结构，可以用来追踪记录已访问过的或者已经在URL前线里的URL。“已见过的URL？”可以帮我们避免多次添加同一个URL，重复添加URL会增加服务器负载并导致潜在的无限循环。布隆过滤器和哈希表都是实现“已见过的URL？”组件的常见技术。URL存储
URL存储用于保存已访问过的URL。到目前为止，我们讨论了所有系统组件。接下来，我们把它们组合在一起来解释爬虫的工作流程。
爬虫工作流程
为了更好地分步骤解释爬虫工作流程，我们在设计图里加了序号，如图-4所示。
图-4
第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前线中。
3.深入设计
到目前为止，我们已经讨论过高层级的设计。接下来，我们将深入讨论几个最重要的构建组件和技术。•深度优先搜索(DFS)与广度优先搜索(BFS)。
•URL前线。
•HTML下载器。
•健壮性。
•可扩展性。
•检测和避免有问题的内容。
3.1 DFS vs.BFS
你可以把网络想成一个有向图，其中网页就是节点，超链接(URL)是边。爬虫在网络上爬行的过程可以看作是从一个网页到其他网页的有向图遍历。常见的两种图遍历算法是DFS和BFS。但是，因为DFS的深度可能非常深，所以它通常不是一个好的选择。BFS是爬虫常用的方法，通过先进先出(FIFO)队列来实现。在一个FIFO队列中，URL按照它们入列的顺序出列。尽管如此，这种实现方式还有以下两个问题。
•同一个网页的大部分链接都指向同一个主机。如图-5所示，wikipedia.com中的所有链接都是内部链接，这使得爬虫忙于处理来自同一个主机(wikipedia.com)的URL。当爬虫尝试并行下载网页时，维基百科的服务器会被大量请求“淹没”。这样做被认为是“不礼貌”的。
图-5
•标准的BFS并没有考虑URL的优先级。互联网很大，不是每个网页都有同样水平的质量和同等重要性。因此，我们可能想要基于网页的排名、网络流量、更新频率等对URL进行排序，以便优先处理某些网页。
3.2 URL前线
URL前线帮我们解决了这些问题。URL前线是一个重要组件，它是一个存储待下载URL的数据结构，能确保爬虫礼貌地访问网页，确定URL优先级并保证内容新鲜度。礼貌性
一般来说，爬虫应该避免在短时间内对同一个服务器发送太多的请求。发送过多请求会被认为“不礼貌”，甚至可能被视为拒绝服务攻击(DoS)。举个例子，如果没有任何限制，爬虫可以对同一个网站每秒发送数千个请求。但这可能会让Web服务器不堪重负。确保礼貌性的大致思路是，从同一个主机每次只下载一个网页。可以在两次下载任务之间加入一定的延时。礼貌性约束是通过维护网站主机名和下载线程(Worker)的映射来实现的。每个下载线程都有独立的FIFO队列且只下载这个队列里的URL。图-6展示了实现爬虫礼貌性的设计。
图-6
•队列路由器：确保每个队列(b1，b2，…，bn)只包含来自同一个主机的URL。
•映射表：把每个主机映射到队列中（见表-1）。
•FIFO队列（从b1到bn）：每个队列只包含来自同一个主机的URL。
•队列选择器：每个Worker都被映射到一个FIFO队列，它只下载来自这个队列的URL。队列选择器实现队列选择的逻辑。
•下载线程（Worker1到WorkerN）：Worker一个接一个地下载来源于同一个主机的网页。在两个下载任务之间可以加入延时。
优先级
某论坛上的一篇关于苹果产品的随机帖子与苹果官网上的文章相比，权重的差异很大。尽管它们都含有“苹果”这个关键字，但是对爬虫而言，先爬取苹果官网的网页肯定是更明智的选择。我们对URL基于有用性来排优先级，可以通过PageRank、网站流量、更新频率等指标来度量。“优先级排序器”(Prioritizer)是处理URL优先级排序的组件。请参阅相关文章来了解关于这个组件的更多信息。
图-7展示了实现URL优先级排序的设计。
图-7
•优先级排序器：它接收URL作为输入并计算其优先级。
•队列f1到fn：每个队列都有一个设定好的优先级。优先级高的队列有更高的概率被选中。
•队列选择器：从多个队列中随机选择一个，尽管优先级高的队列有更高的概率被选中，但这并不是绝对确定的，仍然存在一定的随机性。
图-8展示了URL前线的设计，它包含两个模块。
•前队列：实现优先级管理。
•后队列：实现礼貌性管理。
新鲜度
由于互联网上不断有网页被添加、删除和修改，所以爬虫必须定期重新爬取下载过的网页，以确保数据是最新的。重新爬取所有的URL是非常消耗时间和资源的。下面是两个优化新鲜度的策略。•根据网页的更新历史来判断是否重新爬取。
•对URL按优先级排序，并且优先频繁地重新爬取重要的网页。
URL前线的存储
在搜索引擎的实际爬取过程中，URL前线中的URL数量可能上亿。把所有内容放在内存中，既不可持续也不可扩展；而把所有内容放在硬盘中也不是理想的方案，因为硬盘的访问速度很慢，很容易成为爬虫爬取数据的瓶颈。我们采用了一种混合方案。将大部分的URL存储在硬盘上，这样存储空间就不是问题。为了降低从硬盘读/写的开销，我们在内存中维护了缓冲区以进行入队/出队操作。缓冲区中的数据会被定期写入硬盘。
图-8
3.3 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。图-9展示了一个分布式爬取的例子。缓存DNS解析器
因为很多DNS接口是同步的，所以DNS请求可能要花较长时间，导致DNS解析器成为爬虫的一个性能瓶颈。DNS响应时间在10ms到200ms之间。一旦爬虫的一个线程发出DNS请求，其他线程就会被阻塞，直到该DNS请求完成。维护DNS缓存，避免频繁向DNS服务器发起请求，是一个提高爬虫爬行速度的有效技术。我们的DNS缓存保存了域名与IP地址之间的映射，并通过定时任务进行更新。
图-9
本地性
将爬虫服务器按地理位置分布。爬虫服务器离网站主机越近，爬虫的下载速度会越快。本地性设计可以应用到大部分系统组件上：爬虫服务器、缓存、队列、存储等。短超时时间
一些Web服务器响应慢或者根本不响应。为了避免长时间等待，需要确定一个最长等待时间。如果一个主机在预定时间内没有响应，爬虫就会停止该任务转而爬取其他页面。3.4 健壮性
除了性能优化，健壮性也是一个重要的考虑因素。以下是一些提升系统健壮性的方法。•一致性哈希：有助于负载在HTML下载器之间均匀分布。使用一致性哈希，可以添加或者移除新的下载器服务器。
•保存爬取状态和数据：为了应对故障，将爬取状态和数据写入存储系统。通过加载保存的爬取状态和数据，可以很容易地重启被中断的爬取过程。
•异常处理：在大型系统中，错误是无法避免的，出错是很常见的事情。爬虫必须能“得体地”处理异常，避免系统崩溃。
•数据校验：这是防止系统错误的重要措施。
3.5 可扩展性
因为几乎所有系统都在演进，所以系统的设计目标之一就是要足够灵活以支持新的内容类型。爬虫可以通过插入新的模块来进行扩展。图-10展示了如何添加新模块。•PNG下载器模块作为插件被添加进来，用于下载PNG文件。
•网络监视器模块作为插件被添加进来，用于监控网络，以避免版权和商标侵权。
图-10
3.6 检测和避免有问题的内容
本节讨论检测及避免重复、无意义或者有害内容的方法。重复内容如前所述，接近30%的网页是重复的。哈希和校验和(Checksum)可以帮助我们检测出重复内容。
蜘蛛陷阱
蜘蛛陷阱是可以导致爬虫陷入无限循环的网页，例如，一个无限深的目录结构www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/…。可以通过设置最大URL长度来避免这样的蜘蛛陷阱。尽管如此，并不存在检测蜘蛛陷阱的通用解决方案。含有蜘蛛陷阱的网站是容易识别的，因为在这种网站上网页的数量异常多。但是很难开发出一个自动算法来躲避蜘蛛陷阱。不过，用户可以手动验证和识别蜘蛛陷阱，然后要么在爬取时排除这些网站，要么应用一些定制的URL过滤器。数据噪声
有些内容只有很少的或者根本没有任何价值，比如广告、代码片段、垃圾邮件URL等。这些内容对于爬虫来说没有用，如果有可能，应该将其排除。4 总结
在本章中，我们先讨论了好爬虫的特点——它应该具有可扩展性、礼貌性和健壮性。接着，我们给出了设计方案并讨论了关键组件。因为互联网异常庞大且充满陷阱，所以创建一个可扩展的爬虫并非易事。即使讨论了很多内容，但我们依然漏掉了很多相关的讨论点，比如：•服务端渲染。无数网站使用JavaScript、AJAX等脚本来动态生成链接。如果直接下载和解析网页，我们并不能获取这些动态生成的链接。为了解决这个问题，我们会在解析网页之前先进行服务器端渲染（也叫动态渲染）。
•滤掉不想要的网页。因为存储容量和爬虫资源是有限的，使用反垃圾组件[插图]，[插图]有助于滤掉低质量的垃圾页面。
•数据库复制和分片。复制和分片等技术可以增强数据层的可用性、可扩展性和可靠性。
•横向扩展。对于大范围的爬取，需要成百上千的服务器来执行下载任务。保持服务器无状态是关键。
•可用性、一致性和可靠性。这些概念是任何大型系统成功的核心。我们在第1章中详细讨论了这些概念。复习一下这些内容。
•数据分析。收集和分析数据对任何系统来说都很重要，因为数据是优化系统的关键要素。