需求
让我们设计一个网络爬虫，它将系统地浏览和下载万维网。网状物爬虫也被称为网络蜘蛛、机器人、蠕虫、步行者和机器人。
难度等级：难
1.什么是网络爬虫？
网络爬虫是一种软件程序，它以一种有条不紊的自动浏览万维网。它通过递归地从一组起始页获取链接来收集文档。
许多网站，特别是搜索引擎，使用网络爬网作为提供最新数据的手段。搜索引擎下载所有页面，在其上创建索引，以执行更快的搜索。网络爬虫的其他一些用途包括：
•测试网页和链接的有效语法和结构。
•监控网站，查看其结构或内容何时发生变化。
•维护流行网站的镜像站点。
•搜索侵犯版权的行为。
•建立专用索引，例如，对存储在中的内容有一定了解的索引
网络上的多媒体文件。
2.系统的要求和目标
让我们假设我们需要抓取所有的网页。
可伸缩性：
我们的服务需要具有可伸缩性，以便它可以爬网整个Web并用于获取数亿个Web文档。
可扩展性：
我们的服务应该以模块化的方式设计，并期望新的将向其添加功能。可能需要下载更新的文档类型
并在将来进行处理。
3.一些设计考虑
在网络上爬行是一项复杂的任务，有很多方法可以完成。我们应该考虑如下几个方面：
它是一个仅用于HTML页面的爬虫程序吗？或者我们应该获取和存储其他类型的媒体，例如声音文件、图像、视频等？
如果我们正在编写一个通用的爬虫程序来下载不同的媒体类型，我们可能需要进行分解将解析模块分为不同的模块集：一个用于HTML，另一个用于图像，或者另一个用于视频，其中每个模块提取该媒体类型的有趣内容。
现在让我们假设我们的爬虫程序将只处理HTML，但它应该是可扩展的和可扩展的轻松添加对新媒体类型的支持。
我们需要关注什么协议？HTTP？FTP？还有什么其他的协议？爬虫是否应该处理？
为了简单，我们现在假设只有HTTP（但是实际上不应该这样，因为很难将设计扩展到以后使用FTP和其他协议）
我们将爬网的预期页数是多少？URL数据库将变得多大？
假设我们需要抓取10亿个网站。因为一个网站可以包含很多很多URL，我们假设爬虫将访问150亿个不同网页的上限。
什么是“机器人结论”，我们应该如何处理？礼貌的网络爬虫实现
Robots排除协议，允许网站管理员将其网站的部分内容声明为禁止访问爬虫。机器人排除协议要求网络爬虫获取一个名为机器人从网站下载任何真实内容之前，包含这些声明的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列表作为其输入和输出
重复执行以下步骤。
1.从未访问的URL列表中选择URL。
2.确定其主机名的IP地址。
3.建立与主机的连接以下载相应的文档。
4.解析文档内容以查找新URL。
5.将新URL添加到未访问的URL列表中。
6.处理下载的文档，例如存储或索引其内容等。
7.返回到步骤1
如何爬行？
广度优先还是深度优先？
通常使用广度优先搜索（BFS）。然而，深度优先搜索（DFS）也可用于某些情况，例如，如果爬虫程序已建立连接对于该网站，它可能只需要删除该网站中的所有URL，以节省一些握手开销
路径提升爬网：
路径提升爬网可以帮助发现大量孤立的资源或资源，在特定Web的常规爬网中找不到入站链接的资源，在这个方案中，爬虫将上升到它打算爬网的每个URL中的每个路径。例如，当给定的种子URL为http://foo.com/a/b/page.html，它将尝试爬网/a/b/，/a/，和/.
实现高效网络爬虫的难点
Web的两个重要特性使Web爬行成为一项非常困难的任务：
1.大量网页：
大量网页意味着网络爬虫只能在任何时候下载一小部分的网页，所以使用网络爬虫是至关重要的足够智能，可以优先下载。
2.网页上的变化率。当今动态世界的另一个问题是
互联网变化非常频繁。因此，当从站点爬虫下载最后一页时，页面可能会更改，或者可能会向站点添加新页面。
最低限度的爬虫程序至少需要以下组件：
1.URL frontier：存储要下载的URL列表，并确定应该下载哪些URL的优先级先爬。
2.HTTP抓取器：从服务器检索网页。
3.提取器：从HTML文档中提取链接。
4.重复消除：确保相同内容不会被无意中提取两次。
5.数据存储：存储检索到的页面、URL和其他元数据。
6.详细部件设计
让我们假设我们的爬虫程序运行在一台服务器上，所有爬虫都是由多个工作组完成的线程，其中每个工作线程执行下载和处理文档所需的所有步骤
在一个循环中。此循环的第一步是从共享URL边界中删除绝对URL以供下载。URL以一个方案（如“HTTP”）开始，该方案标识了所使用的网络协议，应该用来下载它。我们可以以模块化的方式实现这些协议以实现可扩展性，因此
如果我们的爬虫程序需要支持更多的协议，那么它可以很容易地完成。
- 基于URL的方案中，工作者调用相应的协议模块来下载文档。
- 之后下载时，文档被放入文档输入流（DIS）。将文件放入DIS将使其他模块能够多次重新读取文档。
- 将文档写入DIS后，工作线程将调用重复数据消除测试以确定以前是否见过此文档（与其他URL关联）。如果是，则该文件为未进一步处理，工作线程将从frontier中删除下一个URL。
- 接下来，我们的爬虫程序需要处理下载的文档。每个文档可以有不同的MIME类型，如HTML页面、图像、视频等。我们可以在模块中实现这些MIME方案。
这样，以后如果我们的爬虫程序需要支持更多类型，我们就可以轻松地实现它们。基于对于下载的文档的MIME类型，工作者调用每个处理的处理方法与该MIME类型关联的模块。
此外，我们的HTML处理模块将从页面中提取所有链接。每个链接都被转换并根据用户提供的URL筛选器进行测试，以确定是否应该下载。如果URL通过了过滤器，工作人员将执行URL seen测试，该测试将检查URL以前见过，也就是说，它是否位于URL边界或已下载。如果URL是新的，它被添加到边界。
让我们逐一讨论这些组件，看看如何将它们分布到多个组件上机器：
1.URL边界：
URL边界是包含所有剩余URL的数据结构可下载。我们可以通过执行广度优先的Web遍历来爬行，从种子集中的页面。这种遍历可以通过使用FIFO队列轻松实现。因为我们将有一个庞大的URL列表需要抓取，所以我们可以将URL边界分布到多个站点服务器。让我们假设在每台服务器上都有多个工作线程执行爬网任务。我们还假设我们的散列函数将每个URL映射到负责爬行它。
设计分布式URL边界时，有以下要求：
1.我们的爬虫程序不应该通过从服务器下载大量页面而使服务器过载。
2.我们不应该让多台机器连接一个web服务器。
为了实现这种约束，我们的爬虫程序可以有一组不同的FIFO子队列，在每台服务器上。每个工作线程都将有其单独的子队列，从中删除每个工作线程的URL爬行。当需要添加一个新的URL时，它所在的FIFO子队列将被删除。由URL的标准主机名确定。我们的散列函数可以将每个主机名映射到一个线程号。这两点合在一起意味着，最多一个工作线程将下载文档。通过使用FIFO队列，它不会使Web服务器过载。
我们的URL边界有多大？
其大小将达到数亿个URL。因此我们需要将URL存储在磁盘上。我们可以以这样一种方式实现队列，即用于排队和退队的单独缓冲区。队列缓冲区一旦填满，将转储到磁盘，而出列缓冲区将保留需要访问的URL缓存；它可以定期读取磁盘以填充缓冲区。
2.取数器模块：
取数器模块的作用是下载对应的文档，使用适当的网络协议（如HTTP）连接到给定的URL。如上所述，网站管理员创建机器人。txt使其网站的某些部分禁止爬虫进入，避免下载。对于每个请求，我们的爬虫程序的HTTP协议模块都可以维护一个固定大小的缓存将主机名映射到其机器人的排除规则。
3.文档输入流：
我们的爬虫设计使相同的文档可以由多个处理模块。为了避免多次下载文档，我们缓存使用称为文档输入流（DIS）的抽象在本地创建文档。DIS是一种输入流，用于缓存从internet读取的文档的全部内容。它也提供重新读取文档的方法。DIS可以缓存小文档（64KB或更小）完全在内存中，而较大的文档可以临时写入备份文件。每个工作线程都有一个关联的DIS，可以在不同的文档中重用。之后从frontier提取URL时，工作人员将该URL传递给相关的协议模块，该模块从网络连接初始化DIS以包含文档内容。那工人呢将DIS传递给所有相关的处理模块。
4.文档重复数据消除测试：
Web上的许多文档都有多个不同的URL。还有许多情况下，文档会镜像到不同的服务器上。这两种效应将导致任何Web爬虫多次下载同一文档。阻止处理我们对每个文档执行重复数据消除测试，以消除重复。要执行此测试，我们可以计算每个已处理文档的64位校验和，并将其存储在数据库对于每个新文档，我们都可以将其校验和与以前计算的所有校验和进行比较查看文档的校验和以前见过。我们可以使用MD5或SHA来计算这些校验和。
校验和存储有多大？
如果校验和存储的全部目的都是进行重复数据消除，然后我们只需要保留一个唯一的集合，其中包含所有以前处理过的文档的校验和。考虑到150亿个不同的网页，我们需要15B*8字节=>120GB。
虽然这可以放入现代服务器的内存中，但如果我们没有足够的可用内存，我们可以在每台服务器上保留更小的基于LRU的缓存，所有内容都由持久性存储支持。
重复数据消除测试首先检查缓存中是否存在校验和。如果没有，则必须检查
校验和驻留在后台存储器中。如果找到校验和，我们将忽略该文档。否则，它将被添加到缓存和后台存储中。
5.URL过滤器：
URL过滤机制提供了一种可定制的方式来控制URL集下载的。这是用来黑名单的网站，以便我们的爬虫可以忽略它们。之前
将每个URL添加到frontier时，工作线程会参考用户提供的URL筛选器。我们可以定义按域、前缀或协议类型限制URL的筛选器。
6.域名解析：
在联系网络服务器之前，网络爬虫必须使用该域名称服务（DNS）将Web服务器的主机名映射到IP地址。DNS名称解析将
考虑到我们将使用的URL数量，这将是我们的爬虫程序的一大瓶颈。避重复请求后，我们可以通过构建本地DNS服务器来开始缓存DNS结果。
7.URL重复数据消除测试：
在提取链接时，任何网络爬虫都会遇到指向同一链接的多个链接文件为了避免多次下载和处理文档，必须执行URL重复数据消除测试
在将每个提取的链接添加到URL之前，必须对其执行。要执行URL重复数据消除测试，我们可以将爬虫看到的所有URL以规范形式存储在数据库为了节省空间，我们不在URL集中存储每个URL的文本表示，而是而是一个固定大小的校验和。
为了减少数据库存储上的操作数量，我们可以保留一个流行的内存缓存所有线程共享的每个主机上的URL。使用此缓存的原因是指向某些URL的链接是非常常见，因此在内存中缓存流行的内存将导致较高的内存命中率。
URL的存储区需要多少存储空间？
如果校验和的全部目的是URL重复数据消除，然后我们只需要保留一个唯一的集合，其中包含以前看到的所有URL重复数据的校验和网址。考虑到150亿个不同的URL和4个字节的校验和，我们需要：15B * 4 bytes => 60 GB
我们可以使用bloom过滤器进行重复数据消除吗？Bloom过滤器是集合的概率数据结构可能产生误报的成员资格测试。一个大位向量表示集合。一个元素是通过计算元素的“n”散列函数并设置相应的位添加到集合中。如果元素散列位置的所有“n”位都已设置，则元素被视为在集合中。因此，一个文件可能被错误地视为在集合中。对URL seen测试使用bloom过滤器的缺点是，每个误报都会导致错误URL不会添加到frontier，因此，文档将永远不会被下载。机会通过增大位向量，可以减少误报的概率。
8.检查点：
整个网络的爬网需要数周时间才能完成。为了防止失败，我们的爬虫程序可以将其状态的常规快照写入磁盘。中断或中止的爬网很容易恢复，从最新的检查点重新启动。
7.容错
我们应该使用一致的散列在爬行服务器之间进行分发。一致性散列将不起作用。这不仅有助于更换死机主机，而且有助于在爬行服务器之间分配负载。我们所有的爬网服务器都将执行常规检查点并将其FIFO队列存储到磁盘。如果服务器出现故障，我们可以更换它。同时，一致散列应该将负载转移到其他服务器。
8.数据分区
我们的爬虫程序将处理三种数据：
1）访问URL的URL
2）重复数据消除的URL校验和
3）记录重复数据消除的校验和。
因为我们是基于主机名分发URL，所以我们可以将这些数据存储在同一台主机上。所以每个主机将存储其需要访问的URL集，以及之前访问的所有URL的校验和所有下载文档的URL和校验和。因为我们将使用一致性哈希，所以可以假定URL将从过载的主机重新分发。每个主机将定期执行检查点，并转储它所持有的所有数据的快照安装到远程服务器上。这将确保如果一台服务器死机，另一台服务器可以通过它的数据来自上一个快照。
9.履带式陷阱
有许多爬虫陷阱、垃圾邮件站点和隐藏内容。爬虫陷阱是一个URL或一组URL，这会导致爬虫无限期地爬行。有些爬虫陷阱是无意的。例如，一个文件系统中的符号链接可以创建一个循环。有意引入其他爬虫陷阱。
例如，人们编写了动态生成无限文档网的陷阱。这些陷阱背后的动机各不相同。反垃圾邮件陷阱旨在捕获垃圾邮件发送者使用的爬虫寻找电子邮件地址，而其他网站则使用陷阱捕捉搜索引擎爬虫，以提高搜索效率搜索评级。
参考资料
grok_system_design_interview.pdf
