什么是DFS与BFS？如何设计一个网络爬虫？
成为架构师系列这个系列很难，但是它是程序员走向架构师所必备的知识，既能助你在面试中脱颖而出，也能让你在日常工作中游刃有余。从基础到深入，从理论到实践，一切你所需的都在这里。收藏本文，点击关注
在本篇中，我们来设计一个网络爬虫：这是一个有趣且经典的系统设计面试题。
网络爬虫也被称为机器人或蜘蛛，它被搜索引擎用于发现网络上的新内容或更新内容。内容可以是网页、图片、视频、PDF文件等。网络爬虫开始时会收集一些网页，然后跟随这些网页上的链接收集新的内容。图9-1展示了爬取过程的可视化示例。
爬虫的作用：
• 搜索引擎索引：这是最常见的用例。爬虫收集网页以为搜索引擎创建本地索引。例如，Googlebot就是Google搜索引擎背后的网络爬虫。
• 网络归档：这是从网络收集信息以保存数据供未来使用的过程。例如，许多国家的图书馆运行爬虫来归档网站。比如美国国会图书馆 [1] 和欧盟网站归档 [2]。
• 网络挖掘：网络的爆炸性增长为数据挖掘提供了前所未有的机会。网络挖掘有助于从互联网中发现有用的知识。例如，顶级金融公司使用爬虫下载股东会议和年度报告，以了解公司的关键倡议。
• 网络监控：爬虫有助于在互联网上监控版权和商标侵权。例如，Digimarc [3] 使用爬虫来发现盗版作品并进行报告。
开发网络爬虫的复杂度取决于我们打算支持的规模。它可能是一个只需几个小时就能完成的小项目，或者是需要一个专业工程团队不断改进的巨大项目。因此，我们将在下面探讨需要支持的规模和特性。
第一步 - 理解问题并确定设计范围
网络爬虫的基本算法很简单：
1. 给定一组URL，下载由这些URL指向的所有网页。
2. 从这些网页中提取URL。
3. 将新的URL添加到待下载的URL列表中。重复这三个步骤。
网络爬虫真的像这个基本算法那样简单吗？并非如此。设计一个可扩展的可大规模网络爬虫是一项极其复杂的任务。在面试时间内设计一个大规模的网络爬虫对任何人来说都不太可能。在开始设计之前，我们必须提问以理解需求并确定设计范围：
候选人：爬虫的主要目的是什么？它是用于搜索引擎索引、数据挖掘，还是其他什么？
面试官：搜索引擎索引。
候选人：网络爬虫每月收集多少网页？
面试官：10亿个网页。
候选人：包括哪些内容类型？仅HTML，还是也包括PDF和图片等其他内容类型？
面试官：仅HTML。
候选人：我们应该考虑新添加或编辑过的网页吗？
面试官：是的，我们应该考虑新添加或编辑过的网页。
候选人：我们需要存储从网络爬取的HTML页面吗？
面试官：是的，存储时间长达5年。
候选人：我们如何处理具有重复内容的网页？
面试官：应忽略具有重复内容的页面。
以上是我们向面试官提问的一些样本问题。理解需求和澄清歧义非常重要。即使你被要求设计一个像网络爬虫这样的需求清晰的产品，你和你的面试官可能也会有不同的侧重。
除了需要与面试官澄清的功能，还要注意记录下一个好的网络爬虫的以下特点：
• 可扩展性：网络非常庞大。那里有数十亿的网页。网络爬取应该并行化并且极其高效。
• 稳健性：网络充满了陷阱。糟糕的HTML、无响应的服务器、崩溃、恶意链接等都很常见。爬虫必须处理所有的边缘情况。
• 礼貌性：爬虫在短时间内不应向网站发送太多请求。
• 可扩展性：系统应该足够灵活，以便在支持新的内容类型时只需要最小的改变。例如，如果我们将来想要爬取图像文件，我们应该不需要重新设计整个系统。
粗略估计
以下估计基于许多假设，与面试官沟通以达成共识非常重要。
• 假设每个月下载10亿个网页。
• QPS：1,000,000,000 / 30天 / 24小时 / 3600秒 = 每秒大约400个网页。
• 峰值QPS = 2 * QPS = 800
• 假设平均网页大小为500k。
• 10亿页面 x 500k = 每月需要500TB存储。如果你对数字存储单位不清楚，请回去复习“2的力量”那一篇。
• 假设数据存储五年，500TB * 12个月 * 5年 = 30PB。存储五年的内容需要30PB的存储空间。
第二步 - 提出高级设计并获得认同
一旦需求明确，我们就可以进行高级设计。受到以往关于网络爬虫的研究[4] [5]的启发，我们提出了如图9-2所示的高级设计。
首先，我们探索每个设计组件以理解他们的功能。然后，我们逐步检查爬虫的工作流程。
种子URL
网络爬虫使用种子URL作为爬行过程的起点。例如，要从大学的网站上爬取所有网页，选择种子URL的直观方式是使用大学的域名。
要爬取整个网络，我们需要在选择种子URL时富有创造性。一个好的种子URL作为一个好的起点，爬虫可以利用它遍历尽可能多的链接。通常的策略是将整个URL空间分割成更小的部分。首先提出的方法是基于区域性，因为不同的国家可能有不同的热门网站。另一种方式是根据主题选择种子URL；例如，我们可以将URL空间划分为购物、体育、健康保健等。种子URL的选择是一个开放性问题。你不需要给出完美的答案。只需给面试官给出你的思考即可。
URL集合
大多数现代网络爬虫将爬行状态分为两种：待下载和已下载。存储待下载URL的组件称为URL集合。你可以将其视为先进先出（FIFO）队列。要获取关于URL集合的详细信息，请参考深入了解部分。
HTML下载器
HTML下载器从互联网上下载网页。这些URL由URL集合提供。
DNS解析器
要下载一个网页，必须将URL转换为IP地址。HTML下载器调用DNS解析器，获取URL对应的IP地址。例如，URL http://www.wikipedia.org 被转换为IP地址198.35.26.96。
内容解析器
下载一个网页后，必须对其进行解析和验证，因为格式不正确的网页可能会引发问题并浪费存储空间。在爬虫服务器中实现内容解析器会减慢爬行过程。因此，内容解析器最好是一个独立的组件。
内容爬过了吗？
在线研究[6]显示，29%的网页是重复内容，这可能导致相同的内容被多次存储。我们引入“内容爬过了吗？”数据结构来消除数据冗余并缩短处理时间。它有助于检测以前存储在系统中的新内容。比较两个HTML文档，我们可以逐字符地比较它们。然而，这种方法慢且耗时，特别是当涉及到数十亿个网页时。一种有效的方法是比较两个网页的哈希值[7]。
内容存储
这是一个用于存储HTML内容的存储系统。存储系统的选择取决于诸如数据类型、数据大小、访问频率、寿命等因素。使用的存储介质包括磁盘和内存。
• 因为数据集过大，无法全部放入内存，所以大部分内容存储在磁盘上。
• 受欢迎的内容保留在内存中以减少延迟。
URL提取器
URL提取器从HTML页面中解析并提取链接。图9-3显示了一个链接提取过程。通过添加“https://en.wikipedia.org”前缀，将相对路径转换为绝对URL。
URL过滤器
URL过滤器排除某些内容类型，文件扩展名，错误链接和“黑名单”网站中的URL。
URL爬过了吗？
“URL爬过了吗？”是一个跟踪之前访问过的URL或已经在前沿的URL的数据结构。“URL爬过了吗？”有助于避免多次添加同一URL，因为这可能会增加服务器负载并可能导致潜在的无限循环。
布隆过滤器和哈希表是实现“URL爬过了吗？”组件的常见技术。我们在这里不会详细介绍布隆过滤器和哈希表的实现。如需更多信息，请参考参考资料[4] [8]。
URL存储
URL存储存放已经访问过的URL。
到目前为止，我们已经讨论了每个系统组件。接下来，我们将它们组合在一起，以解释工作流程。
网络爬虫工作流程
为了更好地逐步解释工作流程，我们在设计图中添加了序列号，如图9-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集合。
第三步 - 深入设计
到现在为止，我们已经讨论了高层设计。接下来，我们将深入讨论最重要的构建组件和技术：
• 深度优先搜索（DFS）与广度优先搜索（BFS）
• URL集合
• HTML下载器
• 健壮性
• 可扩展性
• 检测并避免问题内容
DFS与BFS
你可以将网络视为一个有向图，其中网页作为节点，超链接（URL）作为边。爬取过程可以被看作是从一个网页到其他网页的有向图遍历。两种常见的图遍历算法是DFS和BFS。然而，DFS通常不是一个好的选择，因为在网络爬虫的场景下DFS的深度可能非常深。
网络爬虫常用的是BFS，它通过一个先进先出（FIFO）队列来实现。在一个FIFO队列中，URL按照他们入队的顺序出队。然而，这种实现有两个问题：
• 大多数来自同一网页的链接都链接回同一host。在图9-5中，wikipedia.com中的所有链接都是内部链接，使得爬虫忙于处理来自同一主机（wikipedia.com）的URL。当爬虫试图并行下载网页时，维基百科的服务器将被请求淹没。这被认为是“不礼貌的”。
• 标准的BFS并没有考虑到URL的优先级。网络很大，不是每个页面的质量和重要性都一样。因此，我们可能希望根据他们的页面排名，网页流量，更新频率等来对URL进行优先排序。
URL集合
URL集合有助于解决这些问题。URL集合是一个存储待下载URL的数据结构。URL集合是确保礼貌、URL优先级和新鲜度的重要组件。参考资料[5] [9]中提到了几篇值得关注的关于URL集合的论文。这些论文的发现如下：
礼貌
通常，网络爬虫应避免在短时间内向同一主机服务器发送过多的请求。发送过多的请求被视为“不礼貌的”，甚至被视为拒绝服务（DOS）攻击。例如，如果没有任何限制，爬虫可以每秒向同一网站发送数千个请求。这可能会压垮网络服务器。
实施礼貌的一般思想是一次从同一主机下载一个页面。并且在两个下载任务之间添加延迟。礼貌约束是通过维护从网站主机名到下载（工作线程）的映射来实现的。每个下载线程都有一个独立的FIFO队列，并且只从该队列下载URL。图9-6显示了管理礼貌的设计。
• 队列路由器：确保每个队列（b1，b2，... bn）只包含来自同一主机的URL。
• 映射表：将每个主机映射到一个队列。
• FIFO队列b1，b2至bn：每个队列包含来自同一主机的URL。
• 队列选择器：每个工作线程映射到一个FIFO队列，它只从该队列下载URL。队列选择逻辑由队列选择器完成。
• 工作线程1到N。工作线程一次从同一主机下载一个网页。可以在两个下载任务之间添加延迟。
优先级
论坛上的随机帖子与首页上的帖子具有不同的权重。尽管它们都包含“Apple”关键字，但爬虫优先爬取Apple首页是更成熟的做法。
我们根据有用性对URL进行优先级排序，这可以通过PageRank [10]，网站流量，更新频率等来衡量。"优先级处理器"是处理URL优先级的组件。有关这个概念的深入信息，请参考参考资料[5] [10]。
图9-7显示了管理URL优先级的设计。
• 优先级处理器：它接受URL作为输入并计算优先级。
• 队列f1至fn：每个队列都有一个分配的优先级。具有高优先级的队列具有更高的被选择概率。
• 队列选择器：随机选择一个队列，偏向于具有较高优先级的队列。
图9-8展示了URL集合设计，它包含两个模块：
• 前队列：管理优先级
• 后队列：管理礼貌性
新鲜度
网页一直处于不断地添加、删除和编辑的状态。网络爬虫必须定期重新爬取已下载的页面，以保持我们的数据集新鲜。重新爬取所有的URL既耗时又资源密集。以下列出了一些优化新鲜度的策略：
• 基于网页的更新历史进行重新爬取。
• 对URL进行优先级排序，并更频繁地重新爬取重要的页面。
URL Frontier的存储
在现实世界中为搜索引擎进行爬取时，集合中的URL数量可能达到几亿[4]。把所有东西都放在内存中既不持久也不可扩展。但是磁盘速度慢，我们也不希望把所有东西都存储在磁盘中；并且它很容易成为爬取的瓶颈。
我们采取了一种混合方法。大部分URL存储在磁盘上，因此存储空间不是问题。为了减少从磁盘读取和写入磁盘的成本，我们在内存中维护用于入队/出队操作的缓冲区。缓冲区中的数据会定期写入磁盘。
HTML下载器
HTML下载器使用HTTP协议从互联网下载网页。在讨论HTML下载器之前，我们先看一下机器人排除协议。
Robots.txt
Robots.txt，也被称为机器人排除协议，是网站用来与爬虫交流的一种标准。它指定了爬虫允许下载的页面。在尝试爬取一个网站之前，爬虫应该先检查其对应的robots.txt文件，并遵循其规则。
为了避免重复下载robots.txt文件，我们将文件的结果缓存在内存中。该文件会定期下载并保存到缓存中。这是从https://www.amazon.com/robots.txt获取的一部分robots.txt文件。像creatorhub这样的目录对于Google bot来说是禁止访问的。
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地址的映射，并由定时任务定期更新。
3. 区域性
地理分布爬取服务器。当爬取服务器更接近网站主机时，可以缩短下载时间。区域性设计适用于大多数系统组件：爬取服务器、缓存、队列、存储等。
4. 短超时
一些网页服务器响应慢或者可能根本不响应。为了避免长时间等待，我们设定了最大等待时间。如果一个主机在预定的时间内没有响应，爬虫将停止该任务并爬取其他页面。
鲁棒性
除了性能优化外，鲁棒性也是一个重要的考虑因素。我们提出了几种提高系统鲁棒性的方法：
• 一致性哈希：这有助于在下载器之间分配负载。新的下载服务器可以通过一致性哈希被添加或删除。详细信息请参前面的文章：设计一致性哈希。
• 保存爬取状态和数据：为了防止故障，爬取状态和数据被写入到存储系统。通过加载保存的状态和数据，可以轻松地重新启动中断的爬取。
• 异常处理：在大规模系统中，错误是不可避免且常见的。爬虫必须优雅地处理异常，而不是让系统崩溃。
• 数据验证：这是防止系统错误的重要手段。
可扩展性
几乎每个系统都会发展，所以我们的一个设计目标是使系统足够灵活，以支持新的内容类型。爬虫可以通过插入新的模块来扩展。图9-10显示了如何添加新的模块。
• PNG下载器模块被插入以下载PNG文件。
• 添加了网页监视模块，以监控网络并防止侵犯版权和商标。
检测并避免问题内容
本节讨论了冗余、无意义或有害内容的检测和防止。
1. 冗余内容
如前所述，近30%的网页是重复的。哈希或校验和有助于检测重复内容[11]。
2. 蜘蛛陷阱
蜘蛛陷阱是一个会导致爬虫陷入无限循环的网页。例如，一个无限深的目录结构如下所示： http://www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/...
通过设置URL的最大长度，可以避免这样的蜘蛛陷阱。然而，没有一种万全之策可以检测蜘蛛陷阱。包含蜘蛛陷阱的网站很容易识别，因为在这些网站上发现的网页数量异常大。开发自动避免蜘蛛陷阱的算法很难；但是，用户可以手动验证并识别蜘蛛陷阱，并将这些网站从爬虫中排除或应用一些自定义的URL过滤器。
3. 数据噪声
有些内容的价值很小或者没有价值，如广告、代码片段、垃圾URL等。这些内容对爬虫无用，如果可能，应该被排除。
步骤4 - 总结
在本章中，我们首先讨论了好的爬虫的特点：可扩展性、礼貌性、可扩展性和鲁棒性。然后，我们提出了一个设计并讨论了关键组件。构建一个可扩展的网页爬虫并非易事，因为网页数量庞大且充满陷阱。尽管我们已经涵盖了许多话题，但我们仍然遗漏了许多相关的讨论点：
• 服务器端渲染：许多网站使用如JavaScript、AJAX等脚本在加载中生成链接。如果我们直接下载和解析网页，我们将无法获取动态生成的链接。为了解决这个问题，我们在解析页面之前首先进行服务器端渲染（也称为动态渲染）[12]。
• 过滤掉不需要的页面：由于存储容量和爬取资源有限，反垃圾组件在过滤低质量和垃圾页面方面是很有用也是很有必有得[13] [14]。
• 数据库复制和分片：使用复制和分片等技术来提高数据层的可用性、可扩展性和可靠性。
• 水平扩展：对于大规模爬取，需要数百甚至数千台服务器来执行下载任务。关键是保持服务器无状态。
• 可用性、一致性和可靠性：这些概念是任何大型系统成功的核心。我们在第前面的文章细讨论了这些概念。忘了的话可以翻回去看看。
• 分析：收集和分析数据是任何系统的重要部分。
参考资料
[1] 美国国会图书馆：https://www.loc.gov/websites/
[2] 欧盟网站归档：http://data.europa.eu/webarchive
[3] Digimarc：https://www.digimarc.com/products/digimarc-services/piracy-intelligence
[4] Heydon A., Najork M. Mercator: A scalable, extensible web crawler World Wide Web, 2(4) (1999), pp. 219-229
[5] Christopher Olston, Marc Najork著：Web Crawling. http://infolab.stanford.edu/~olston/publications/crawling_survey.pdf
[6] 29%的网站面临重复内容问题：https://tinyurl.com/y6tmh55y
[7] Rabin M.O., et al. Fingerprinting by random polynomials Center for Research in Computing Techn., Aiken Computation Laboratory, Univ. (1981)
[8] B. H. Bloom，“Space/time trade-offs in hash coding with allowable errors,” Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970.
[9] Donald J. Patterson, Web Crawling: https://www.ics.uci.edu/~lopes/teaching/cs221W12/slides/Lecture05.pdf
[10] L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank citation ranking: Bringing order to the web,” Technical Report, Stanford University,
[11] Burton Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), pages 422--426, July 1970.
[12] Google 动态渲染：https://developers.google.com/search/docs/guides/dynamic-rendering
[13] T. Urvoy, T. Lavergne, and P. Filoche，“Tracking web spam with hidden style similarity,” in Proceedings of the 2nd International Workshop on Adversarial Information Retrieval on the Web, 2006.
[14] H.-T. Lee, D. Leonard, X. Wang, and D. Loguinov, “IRLbot: Scaling to 6 billion pages and beyond,” in Proceedings of the 17th International World Wide Web Conference, 2008.
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。