11. 设计网络爬虫
难度等级：困难
让我们设计一个网络爬虫，网络爬虫可以系统地浏览和下载万维网内容。网路爬虫也称为网络蜘蛛、机器人、蠕虫、步行者等。
1. 什么是网络爬虫？
网络爬虫是一个有条理地自动浏览万维网的软件程序。网络爬虫通过从一系列开始页面出发递归地获取链接的方式收集文档。很多网站，特别是搜索引擎，使用网络爬虫作为提供实时数据的工具。搜索引擎下载所有的页面并创建这些页面的索引以实现更快的搜索。
网络爬虫的一些其他应用有：
测试网页和链接是否符合语法和结构规则。
监控网站，查看结构或内容是否改变。
为热门网站维护镜像网站。
搜索侵犯版权行为。
建立一个特殊目的的索引，例如索引包含对网络上的多媒体文件中的信息的理解。
2. 系统的要求和目标
我们假设需要爬取整个网络上的内容。
可测量性：我们的服务应该具备可测量性，可以爬取整个网络上的内容并可以用于获取数以亿计的网络文档。
可延伸性：我们的服务应该使用模块化的方式设计，预期到可能增加新的功能。将来可能有新的文档类型需要被下载和处理。
3. 设计需要考虑的方面
爬取网络是一个复杂的任务，有多种处理方法。在进一步设计之前，应该考虑若干问题：
爬虫是否只爬取 HTML 网页？还是也应该获取和存储其他类型的媒介，例如声音文件、图像、视频等？这个问题很重要，因为回答会改变设计。如果我们要实现的是多功能的爬虫，下载不同的媒介类型，我们可能将解析模块分成不同模块：一个模块用于 HTML，一个模块用于图像，或者一个模块用于视频，每个模块提取对应的媒体类型的内容。
我们假设目前我们的爬虫只处理 HTML，但是应该具有可扩展性，方便增加对新的媒体类型的支持。
我们使用哪种协议？HTTP？FTP 链接如何处理？我们的爬虫应该处理哪些不同的协议？从联系的角度，我们假设使用 HTTP。后续将设计延伸到使用 FTP 或者其他协议应该不是困难的事情。
我们预期爬取多少页面？URL 数据库将有多大？我们假设需要爬取 10 亿个网站。由于每个网站可能包含大量的 URL，我们假设爬虫将会访问的网页数量上限是 150 亿。
什么是「机器人排除」以及我们应该如何应对？合法的网络爬虫遵循机器人排除协议，该协议允许网站管理员声明网站的部分内容是禁止爬虫访问的。机器人排除协议要求网络爬虫在从网站下载任何真实内容之前首先获取一个称为 robot.txt 的特殊文档，该文档包含网站的这些声明。
4. 容量估算和限制条件
如果我们想要在四个星期内爬取 150 亿个页面，我们需要每秒获取多少页面？
15B / (4 weeks * 7 days * 86400 sec) ~= 6200 pages/sec
需要多少存储容量？页面大小相差很多，但是如我们上面所说，我们只处理 HTML 文本，我们假设平均每个页面的大小是 100KB。对于每个页面，如果我们存储 500 字节的元数据，我们需要的总存储是：
15B * (100KB + 500) ~= 1.5 petabytes
假设我们使用一个 70% 容量模型（使用的容量不超过总容量的 70%），我们需要的总容量是：
1.5 petabytes / 0.7 ~= 2.14 petabytes
5. 高阶设计
任何网络爬虫执行的基础算法是将一个种子 URL 列表作为输入然后重复执行以下步骤。
从未访问的 URL 列表中选择一个 URL。
决定该 URL 的主机名的 IP 地址。
建立与主机的链接以下载对应的文档。
解析文档内容以寻找新 URL。
将新 URL 添加到未访问的 URL 列表。
处理下载的文档，例如将其存储或者对其内容建立索引等。
回到第 1 步。
如何爬取？
广度优先还是深度优先？通常使用广度优先搜索。但是，在一些场合下也会使用深度优先搜索，例如当爬虫已经和网站建立链接时，就可能对网站中的所有 URL 做深度优先搜索，以节省握手的开销。
路径上升爬取：路径上升爬取有助于发现特定网站内部的很多独立的资源，或者内部链接无法发现的资源，这些资源使用常规爬虫可能不会被发现。该方案下，爬虫会在每个想要爬取的 URL 中上升到每个路径。例如，给定种子 URL 是 http://foo.com/a/b/page.html，爬虫将会尝试爬取 /a/b/，/a/ 以及 /。
实现高效网络爬虫的困难之处
网络有两个重要的特点，使得网络爬虫成为一项非常困难的任务：
1. 网页数量巨大：网页数量巨大，意味着网络爬虫在任何时候只能下载部分网页，因此至关重要的一点是网络爬虫应该足够智能到可以安排下载优先级。
2. 网页的变化比例：当今的动态世界的另一个问题是因特网上的网页非常频繁地变化。结果是，当爬虫正在从一个网站下载最后一个页面时，网页可能变化，或者网站可能增加了新页面。
最少量爬虫需要至少以下部件：
URL 边界：存储需要下载的 URL 列表，并安排优先级，决定哪些 URL 首先被爬取。
HTTP 获取器：从服务器上获取网页。
提取器：从 HTML 文档中提取链接。
去重器：确保相同的内容不会无意中被提取两次。
数据存储器：存储获取的页面、URL 以及其他元数据。
6. 部件设计细节
我们假设爬虫在一台服务器上运行，所有的爬取操作通过多线程完成，每个工作线程循环执行下载和处理文档所需要的操作。
循环的第一步是从共享的 URL 边界中移除一个绝对 URL。一个绝对 URL 以一个体系开头，该体系识别应该用于下载的网络协议。我们可以模块化地实现这些协议以支持可延伸性，当爬虫需要支持更多的协议时，就可以很容易地实现。基于 URL 的体系，工作者调用合适的协议模块以下载文档。下载之后，文档加入文档输入流（DIS）。将文档加入文档输入流可以允许其他模块多次重新读取文档。
一旦文档加入文档输入流，工作线程唤醒去重测试，判断这个文档（和一个不同的 URL 结合）是否在之前已经见过。如果已经见过，该文档不会被继续处理，工作线程从边界中移除下一个 URL。
然后，爬虫需要处理下载的文档。每个文档可能有不同的媒体类型，如 HTML 网页、图像、视频等。我们可以使用模块化的方式实现这些媒体类型，当爬虫后续需要支持更多的类型时，就可以很容易地实现。基于下载的文档的媒体类型，工作者调用该媒体类型对应的每个模块的处理方法。
除此之外，HTML 处理模块将提取页面中的所有链接。每个链接被转换成绝对 URL，并使用用户提供 URL 过滤器测试，决定是否应该被下载。如果 URL 通过了过滤器，工作者执行 URL 去重测试，检查 URL 是否在之前已经见过，即该 URL 是在边界内还是已经被下载。如果 URL 是新的，将被加入边界。
我们依次讨论这些部件，以及如何分布到多台机器上：
1. URL 边界：URL 边界是一个数据结构，包含所有剩余的需要被下载的 URL。我们可以通过从种子集合中的页面开始，在网络上执行广度优先遍历进行爬取。这样的遍历可以使用先进先出的队列方便地实现。
由于我们有一个很大的待爬取 URL 列表，我们可以将 URL 边界分布到多台服务器上。假设每台服务器上有多个工作线程执行爬取任务。同时假设哈希函数将每个 URL 映射到负责爬取该 URL 的服务器上。
当设计分布式 URL 边界时，必须记住以下规范性需求：
爬虫不能从一台服务器下载大量网页导致服务器过载。
不能有多台机器连接同一台网络服务器。
为了实现这样的规范性约束，爬虫可以在每台服务器上有若干不同的先进先出子队列。每个工作线程将有独立的子队列，从子队列中移除 URL 用于爬取。当一个新 URL 需要被添加时，应该加入的子队列将由 URL 的标准主机名决定。哈希函数可以将每个主机名映射到一个线程号。这两点结合可知，最坏情况下，工作线程将从一个给定网络服务器下载文档，通过使用先进先出队列，不会使网络服务器过载。
URL 边界有多大？大小将是数亿个 URL。因此，我们需要将 URL 存储在磁盘上。实现队列时，我们可以为队列的入队和出队操作分别增加独立的缓存区。当入队缓存区填满时，将被添加到磁盘。出队缓存区将保留需要被访问的 URL 的缓存，可以周期性地从磁盘读取已填满缓存区。
2. 获取模块：获取模块的目的是使用合适的网络协议如 HTTP 下载对应给定 URL 的文档。如上文讨论的，网站管理员创建 robot.txt 以将网站的特定部分内容禁止爬虫访问。为了避免每次请求时都下载这个文件，爬虫的 HTTP 协议模块可以维护一个固定大小的缓存，将主机名映射到对应的机器人排除规则。
3. 文档输入流：爬虫的设计允许同一个文档被多个处理模块处理。为了避免多次下载同一个文档，我们使用一个称为文档输入流的抽象概念本地缓存文档。
文档输入流是缓存从因特网下载的整个文档内容的输入流。文档输入流也提供重新读取文档的方法。文档输入流可以将小文档（64KB 或更小）完全在内存中缓存，更大的文档可以临时写入备份文件。
每个工作线程有一个对应的文档输入流，可以对不同文档复用。在从边界提取 URL 之后，工作者将 URL 传给相关的协议模块，协议模块使用网络连接将文档输入流初始化，使得文档输入流包含文档内容。工作者然后将文档输入流传给所有相关的处理模块。
4. 文档去重测试：网上的很多文档可能在多个不同的 URL 下都存在。也有很多情况是文档在不同服务器上存有镜像。这两种情况都会引起任何网络爬虫多次下载相同的文档。为了避免多次处理同一个文档，我们对每个文档执行去重测试以删除重复文档。
为了执行这个测试，我们可以给每个处理过的文档计算一个 64 位的校验和，并将其存入数据库。对于每个新文档，我们可以将其校验和与所有已经计算过的校验和做比较，判断该文档之前是否已经见过。我们可以使用 MD5 或 SHA 计算校验和。
存储校验和需要多少空间？如果存储校验和的全部目的是做去重，我们只需要维护一个无重复集合存储所有之前处理过的文档的校验和。考虑到有 150 亿个不同的网页，我们需要：
15B * 8 bytes => 120 GB
虽然这些空间可以存入一台现代服务器的内存，如果我们没有足够的内存，可以在每台服务器上维护较小的最近最少使用（LRU）缓存，使用永久存储备份所有数据。
去重测试首先检查校验和是否在缓存中。如果不存在，则必须检查校验和是否在备份存储中。如果找到校验和，则忽略该文档。否则，将校验和添加到缓存和备份存储中。
5. URL 过滤器：URL 过滤器机制提供一个可自定义的方式控制下载的 URL 集合。该机制用于排除一些网站，使得爬虫可以忽略这些网站。在将每个 URL 加入边界之前，工作线程询问用户提供的 URL 过滤器。我们可以定义过滤器根据域名、前缀或协议类型限制 URL。
6. 域名处理：在联系网络服务器之前，网络爬虫必须使用域名服务（DNS）将网络服务器的主机名映射到 IP 地址。考虑到我们需要处理的 URL 的数量，域名服务处理主机名将是爬虫的一个大的性能瓶颈。为了避免重复请求，我们可以通过建立本地域名服务的服务器将域名服务结果缓存。
7. URL 去重测试：当提取链接时，任何网络爬虫将遇到多个链接指向同一个文档。为了避免多次下载和处理同一个文件，必须对每个提取的链接执行 URL 去重测试，通过测试才能加入边界。
为了执行 URL 去重测试，我们可以在数据库中存储爬虫见过的所有 URL 的标准形式。为了节省空间，我们在 URL 集合中不存储每个 URL 的文本形式，而是一个固定大小的校验和。
为了降低数据库存储的操作次数，我们可以维护一个内存中的缓存用于存储每台服务器上由所有线程共享的热门 URL。维护这个缓存的理由是部分 URL 的链接非常流行，因此将流行的 URL 缓存在内存中可以有很高的内存命中率。
我们需要多少空间存储 URL？如果校验和的全部目的是做 URL 的去重，我们只需要维护一个无重复集合存储所有之前见过的 URL 的校验和。考虑到有 150 亿个不同的 URL 以及每个校验和有 4 个字节，我们需要：
15B * 4 bytes => 60 GB
我们是否可以使用布隆过滤器做去重？布隆过滤器是一个用于检查元素是否在集合中的概率型数据结构，可能会有假阳性。一个大型比特向量表示这个集合。当一个元素加入集合时，对该元素使用 n 个哈希函数计算结果并将相应的比特设为 1。如果对一个元素使用所有 n 个哈希函数计算的结果中相应的比特都是 1，则该元素被认为在集合中。因此，一个文档可能错误地被认为在集合中，但是假阴性是不可能的。
使用布隆过滤器测试 URL 是否出现过的缺点是每次假阳性都会导致 URL 不被加入边界，因此该文档将永远不会被下载。可以通过增加比特向量的方式降低假阳性的概率。
8. 定点检查：整个网络的爬取需要数周才能完成。为了预防失败，爬虫可以定期将其状态的快照写入磁盘。当爬取操作被中断或终止，则可以方便地从最后一个检查点开始重新启动爬取操作。
7. 容错
在爬虫服务器中分布时，我们应该使用一致性哈希。一致性哈希不仅有助于替换宕机的主机，也有助于在爬虫服务器之间分布负载。
所有的爬虫服务器将执行定期的定点检查，将先进先出队列存入磁盘。当一台服务器宕机时，即可将其替换。与此同时，一致性哈希应该将负载转移到其他服务器。
8. 数据分块
爬虫将处理三类数据：1. 访问的 URL；2. URL 去重的校验和；3. 文档去重的校验和。
由于我们基于主机名分布 URL，我们可以将这些数据存放在同一台主机上。因此，每台主机将存储各自的需要访问的 URL、所有已经访问过的 URL 的校验和以及所有下载过的文档的校验和。由于我们使用一致性哈希，我们可以假设 URL 将会从过载的主机重新分布。
每台主机将周期性地执行定点检查并将其获取的所有数据的快照存储在一台远端服务器上。这可以确保当一台服务器宕机时，另一台服务器可以从最后的快照中获取数据并替代宕机的服务器。
9. 爬虫陷阱
有很多爬虫陷阱、垃圾网站和被掩盖的内容。爬虫陷阱时导致爬虫无限爬取的一个 URL 或者一系列 URL。一些爬虫陷阱是无意的。例如，一个文件系统中的链接可能产生环。另一些爬虫陷阱是故意的。例如，人们写动态生成无线网络文档的陷阱。这些陷阱背后的动机各不相同。反垃圾陷阱的设计目的是抓获被垃圾邮件制造者用于寻找电子邮箱地址的爬虫，另一些网站使用陷阱抓获搜索引擎爬虫以提升它们的搜索排名。
Last updated
