系统设计：网络爬虫设计（09）

Published: at 13:18:50

本章重点介绍网络爬虫设计：一道有趣且经典的系统设计面试题。

网络爬虫被称为机器人或蜘蛛。搜索引擎广泛使用它来发现 Web 上的新内容或更新内容。内容可以是网页、图像、视频、PDF 文件等。网络爬虫首先收集一些网页，然后按照这些页面上的链接收集新内容。图 9-1 显示了抓取过程的可视化示例。

爬虫有多种用途：

开发网络爬虫的复杂性取决于我们打算支持的规模。它可以是一个只需要几个小时即可完成的小型学校项目，也可以是一个需要专门的工程团队不断改进的大型项目。因此，我们将在下面探讨支持的规模和功能。

第1步：了解问题并确定设计范围

网络爬虫的基本算法很简单：

网络爬虫真的像这个基本算法一样简单吗？不完全是。设计一个高度可扩展的网络爬虫是一项极其复杂的任务。任何人都不太可能在面试时间内设计出一个庞大的网络爬虫。在进入设计之前，我们必须提出问题以了解需求并建立设计范围：

候选人：爬虫的主要目的是什么？它用于搜索引擎索引、数据挖掘或其他用途吗？

面试官：搜索引擎索引。

候选人：网络爬虫每个月收集多少网页？

采访者：10 亿页。

候选人：包括哪些内容类型？仅 HTML 还是其他内容类型（如 PDF 和图像）？

面试官：只有 HTML。

候选人：我们是否考虑新增或编辑的网页？

面试官：是的，我们应该考虑新添加或编辑的网页。

候选人：我们需要存储从网络上爬取的 HTML 页面吗？

面试官：是的，最多5年

应聘者：我们如何处理内容重复的网页？

面试官：重复内容的页面应该忽略。

以上是您可以向面试官提出的一些示例问题。了解需求并澄清歧义很重要。即使你被要求设计一个简单的产品，比如网络爬虫，你和你的面试官可能不会有相同的假设。

除了要向面试官澄清的功能之外，记下优秀网络爬虫的以下特征也很重要：

粗略估算

以下估算基于许多假设，与面试官沟通以达成共识很重要。

第2步：提出高层次的设计方案并获得认同

一旦需求明确了，我们就开始进行高层设计。受以前关于网络抓取的研究[4][5]的启发，我们提出了一个高层设计，如图9-2所示。

首先，我们探索每个设计组件以了解它们的功能。然后，我们逐步检查爬虫工作流程。

Seed URLs

网络爬虫使用种子 URL 作为爬网过程的起点。例如，要抓取大学网站的所有网页，选择种子 URL 的一种直观方法是使用大学的域名。

要抓取整个网络，我们需要创造性地选择种子 URL。一个好的种子 URL 是一个很好的起点，爬虫可以利用它来遍历尽可能多的链接。一般的策略是将整个 URL 空间分成更小的空间。第一个提议的方法是基于位置的，因为不同的国家可能有不同的流行网站.

另一种方法是根据主题选择种子网址；例如，我们可以将 URL 空间划分为购物、体育、医疗保健等。种子 URL 选择是一个开放式问题，您不应该给出完美的答案，先大胆想想。

URL Frontier

大多数现代网络爬虫将爬行状态分为两种：待下载和已下载。存储待下载的URL的组件被称为URL Frontier。你可以把它称为先进先出（FIFO）队列。关于URL Frontier的详细信息，请参考深入研究的内容。

HTML Downloader

HTML Downloader 从互联网上下载网页。这些URL是由URL Frontier提供的。

DNS Resolver

要下载网页，必须将 URL 转换为 IP 地址。 HTML Downloader 调用 DNS Resolver 为 URL 获取相应的 IP 地址。例如，截至 2019 年 3 月 5 日，URL www.wikipedia.org 已转换为 IP 地址 198.35.26.96。

Content Parser

下载网页后，必须对其进行解析和验证，因为格式错误的网页可能会引发问题并浪费存储空间。在爬网服务器中实现内容解析器会减慢爬网过程。因此，Content Parser（内容解析器）是一个单独的组件。

Content Seen?

在线研究[6]显示，29%的网页是重复的内容，这可能导致同一内容被多次存储。我们引入了 “Content Seen? “数据结构，以消除数据的冗余，缩短处理时间。它有助于检测以前存储在系统中的新内容。为了比较两个HTML文档，我们可以逐个字符进行比较。然而，这种方法既慢又费时，特别是当涉及到数十亿的网页时。完成这项任务的一个有效方法是比较两个网页的哈希值[7]。

Content Storage

它是一个用于存储HTML内容的存储系统。存储系统的选择取决于诸如数据类型、数据大小、访问频率、寿命等因素，磁盘和内存都被使用。

URL Extractor

URL Extractor（网址提取器） 从 HTML 页面解析和提取链接。图 9-3 显示了链接提取过程的示例。通过添加“https://en.wikipedia.org”前缀将相对路径转换为绝对 URL。

URL Filter

URL Filter 排除某些内容类型、文件扩展名、错误链接和“黑名单”站点中的 URL。

URL Seen？

“URL Seen? “是一个数据结构，用于跟踪之前被访问过的或已经在Frontier中的URL。“URL Seen? “有助于避免多次添加相同的URL，因为这可能会增加服务器负载并导致潜在的无限循环。

布隆过滤器和哈希表是实现 “URL Seen? “组件的常用技术。我们不会在这里介绍布隆过滤器和哈希表的详细实现。欲了解更多信息，请参考参考资料[4][8]。

URL Storage

URL Storage 存储已经访问过的 URL。到目前为止，我们已经讨论了每个系统组件。接下来，我们将它们放在一起来解释工作流程。

网络爬虫工作流程

为了更好地逐步解释工作流程，在设计图中添加了序列号，如图 9-4 所示。

第 1 步：将种子 URL 添加到 URL Frontier

第 2 步：HTML 下载器从 URL Frontier 获取 URL 列表。

第 3 步：HTML 下载器从 DNS 解析器获取 URL 的 IP 地址并开始下载。

第 4 步：Content Parser 解析 HTML 页面并检查页面是否格式错误。

第 5 步：内容经过解析和验证后，传递给“Content Seen?”组件。

第 6 步：“Content Seen”组件检查 HTML 页面是否已在存储中。

第 7 步：网址提取器从 HTML 页面中提取网址。

第 8 步：将提取的网址传递给 URL 过滤器。

第 9 步：网址过滤后，传递给“URL Seen?”组件。

第 10 步：“URL Seen”组件检查一个URL是否已经在存储中，如果是，则之前处理过，不需要做任何事情。

第 11 步：如果一个 URL 以前没有被处理过，它被添加到 URL Frontier。

第3步：深入设计

到目前为止，我们已经讨论了高层设计。接下来，我们将深入讨论最重要的构建组件和技术：

DFS vs BFS

你可以把网络想象成一个有向图，其中网页作为节点，超链接（URL）作为边。抓取过程可以被视为从一个网页到其他网页的有向图的遍历。两种常见的图形遍历算法是DFS和BFS。然而，DFS通常不是一个好的选择，因为DFS的深度可能很深。

BFS 通常被网络爬虫使用，并通过先进先出 (FIFO) 队列实现。在 FIFO 队列中，URL 按照它们入队的顺序出队。但是，这种实现有两个问题：

  1. 来自同一网页的大多数链接都链接回同一主机。在图 9-5 中，wikipedia.com 中的所有链接都是内部链接，使得爬虫忙于处理来自同一主机（wikipedia.com）的 URL。当爬虫试图并行下载网页时，维基百科服务器将被请求淹没。这被认为是“不礼貌的”

  2. 标准的BFS没有考虑到一个URL的优先级。网络很大，不是每个页面都有相同的质量和重要性。因此，我们可能希望根据页面排名、网络流量、更新频率等来确定URL的优先级。

URL Frontier

URL Frontier 有助于解决这些问题。 URL Frontier 是一种存储要下载的 URL 的数据结构。 URL Frontier 是确保礼貌、URL 优先级和新鲜度的重要组成部分。参考资料 [5] [9] 中提到了一些关于 URL Frontier 的值得注意的论文。这些论文的研究结果如下：

HTML 下载器

HTML下载器使用HTTP协议从互联网上下载网页。在讨论HTML下载器之前，我们先看一下Robots排除协议。

Robots.txt**

Robots.txt，称为Robots排除协议，是网站用来与爬虫沟通的标准。它规定了爬虫可以下载哪些页面。在尝试爬行一个网站之前，爬虫应首先检查其相应的robots.txt，并遵守其规则。为了避免重复下载 robots.txt 文件，我们对该文件的结果进行了缓存。该文件会定期下载并保存到缓存中。下面是取自https://www.amazon.com/robots.txt 的robots.txt文件的一个片段。一些目录，如creatorhub，是不允许谷歌机器人访问的。

User-agent: Googlebot
Disallow: /creatorhub/*
Disallow: /rss/people/*/reviews
Disallow: /gp/pdp/rss/*/reviews
Disallow: /gp/cdp/member-reviews/
Disallow: /gp/aw/cr/

除了 robots.txt，性能优化是我们将为HTML下载器介绍的另一个重要概念。

性能优化

以下是HTML下载器的性能优化列表.

  1. 分布式抓取

    为了实现高性能，抓取工作被分配到多个服务器，每个服务器运行多个线程。URL空间被分割成更小的部分；因此，每个下载器负责URL的一个子集。图9-9显示了一个分布式抓取的例子。

  2. 缓存DNS解析器

    DNS解析器是爬虫的一个瓶颈，因为由于许多DNS接口的同步性，DNS请求可能需要时间。DNS响应时间从10ms到200ms不等。一旦爬虫线程对DNS进行了请求，其他线程就会被阻断，直到第一个请求完成。维护我们的DNS缓存以避免频繁调用DNS是一种有效的速度优化技术。我们的DNS缓存保持域名到IP地址的映射，并通过cron作业定期更新。

  3. 位置

    按地理分布抓取服务器。当爬行服务器离网站主机较近时，爬行者会体验到更快的下载时间。设计定位适用于大多数系统组件：抓取服务器、缓存、队列、存储等。

  4. 短暂的超时

    有些网络服务器响应缓慢，或者根本不响应。为了避免漫长的等待时间，指定了一个最大的等待时间。如果一个主机在预定的时间内没有反应，爬虫将停止工作并抓取一些其他的网页。

鲁棒性

除了性能优化，鲁棒性也是一个重要的考虑因素。我们提出了一些提高系统鲁棒性的方法。

可扩展性（Extensibility）

差不多每个系统都在不断发展，设计目标之一是使系统足够灵活，以支持新的内容类型。抓取器可以通过插入新的模块来扩展。图9-10显示了如何添加新模块。

检测并避免有问题的内容

本节讨论冗余、无意义或有害内容的检测和预防。

  1. 冗余内容

    如前所述，近30%的网页是重复的。哈希值或校验和有助于检测重复[11]。

  2. 搜索引擎蜘蛛陷阱

    搜索引擎蜘蛛陷阱是导致爬虫陷入无限循环的网页。 例如，一个无限深的目录结构如下： www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/… 可以通过设置 URL 的最大长度来避免此类蜘蛛陷阱。但是，不存在检测蜘蛛陷阱的万能解决方案。 包含蜘蛛陷阱的网站很容易识别，因为在此类网站上发现的网页数量异常多。 很难开发自动算法来避免蜘蛛陷阱； 但是，用户可以手动验证和识别蜘蛛陷阱，并从爬虫中排除这些网站或应用一些自定义的 URL 过滤器。

  3. 垃圾数据

    有些内容价值很小或没有价值，例如广告、代码片段、垃圾邮件 URL 等。这些内容对爬虫没有用，应尽可能排除。

第4步：总结

在本章中，我们首先讨论了一个好的爬虫的特征：可伸缩性、礼貌性、可扩展性和健壮性。 然后，我们提出了设计方案并讨论了关键组件。 构建可扩展的网络爬虫并不是一项简单的任务，因为网络非常庞大且充满陷阱。 即使我们涵盖了所有主题，我们仍然遗漏了许多相关的讨论要点：

恭喜你走到了这一步！现在给自己一个鼓励，干得漂亮！

参考资料