网页设计与网站建设简答题,网站域名试用期,如何编写一个网页,网站内容建设和管理系统CHAPTER 9: 《DESIGN A WEB CRAWLER》第九章 设计一个web爬虫
在本章中#xff0c;我们将重点介绍网络爬虫设计#xff1a;一种有趣而经典的系统设计 面试问题。 网络爬虫被称为机器人或蜘蛛。它被搜索引擎广泛用于发现网络上的新内容或更新内容。内容可以是网页、图像、视频…CHAPTER 9: 《DESIGN A WEB CRAWLER》第九章 设计一个web爬虫
在本章中我们将重点介绍网络爬虫设计一种有趣而经典的系统设计 面试问题。 网络爬虫被称为机器人或蜘蛛。它被搜索引擎广泛用于发现网络上的新内容或更新内容。内容可以是网页、图像、视频、PDF文档等。网络爬虫首先收集一些网页然后跟踪这些网页上的链接页面以收集新内容。图 9-1 显示了爬网过程的直观示例。 爬虫有多种用途
搜索引擎索引这是最常见的用例。爬虫收集网络页面为搜索引擎创建本地索引。例如Googlebot 就是网络谷歌搜索引擎背后的爬虫。Web 存档这是从 Web 收集信息以保存的过程数据以备将来使用。例如许多国家图书馆运行爬虫来存档网络网站。值得注意的例子是美国国会图书馆[1]和欧盟网络档案馆[2]。网络挖矿网络的爆炸性增长为数据挖掘。网络挖掘有助于从互联网上发现有用的知识。为例如顶级金融公司使用爬虫下载股东大会和年度报告以了解公司的关键举措。网络监控。爬虫有助于监控版权和商标侵权行为通过互联网。例如Digimarc [3] 利用爬虫来发现盗版作品和报告。
开发网络爬虫的复杂性取决于我们打算支持的规模。它可以是一个只需要几个小时就能完成的小型学校项目也可以是一个巨大的项目需要专门的工程团队持续改进的项目。因此我们将在下面探讨要支持的规模和功能。
第 1 步 - 了解问题并确定设计范围
网络爬虫的基本算法很简单
给定一组 URL下载这些 URL 链接的所有网页。从这些网页中提取 URL将新 URL 添加到要下载的 URL 列表中。重复这 3 个步骤。
网络爬虫真的像这个基本算法一样简单吗不完全是。设计一个可扩展的网络爬虫是一项极其复杂的任务。任何人都不太可能设计面试期间的大型网络爬虫。在开始设计之前我们必须提出问题以了解需求并确定设计范围 应聘者爬虫的主要用途是什幺它是否用于搜索引擎索引数据挖掘还是别的什幺 面试官搜索引擎索引。 应聘者网络爬虫每月收集多少个网页 面试官10 亿页。 应聘者包括哪些内容类型仅限 HTML 或其他内容类型例如还有 PDF 和图像 面试官仅限 HTML。 应聘者我们可以考虑新添加或编辑的网页吗 面试官是的我们应该考虑新添加或编辑的网页。 应聘者我们需要存储从网络上抓取的 HTML 页面吗 面试官是的最长 5 年 应聘者如何处理重复内容的网页 面试官包含重复内容的页面应被忽略
以上是您可以向面试官提出的一些示例问题。重要的是了解要求并澄清歧义。即使你被要求设计一个 像网络爬虫这样的简单产品你和你的面试官也可能有不一样的想法。
除了与面试官澄清的功能外记下一个好的网络爬虫的以下特征
可测量性网络非常大。那里有数十亿个网页。使用并行化爬网应该非常有效。鲁棒性网络充满了陷阱。错误的 HTML、无响应的服务器、崩溃、恶意链接等都很常见。爬网进程必须处理所有这些边缘情况。人性爬虫不应在短时间内向网站发出太多请求时间间隔。可扩展性系统非常灵活因此只需进行最少的更改即可支持新的内容类型。例如如果我们将来想抓取图像文档我们不需要重新设计整个系统。
封底计算
以下估计基于许多假设重要的是与面试官沟通以达成共识。
假设每月下载10亿个网页。QPS1,000,000,000 / 30 天 / 24 小时 / 3600 秒 ~400 页/秒。峰值 QPS 2 * QPS 800假设平均网页大小为 500k。10 亿页 x 500k 每月 500 TB 存储。如果您不清楚数字存储单元请再次浏览第 2 章中的“2 的幂”部分。假设数据存储 5 年则 500 TB * 12 个月 * 5 年 30 PB。一个 30 PB需要存储来存储五年的内容。
第 2 步 - 提出高级设计并获得支持
一旦明确了需求我们就会继续进行高级设计。灵感来自以前的在对网络爬虫的研究[4] [5]中我们提出了一个如图9-2所示的高级设计。 首先我们探索每个设计组件以了解它们的功能。然后我们逐步检查爬虫工作流程。 种子网址 网络爬虫使用种子 URL 作为爬网过程的起点。例如要抓取大学网站上的所有网页选择种子 URL 的直观方法是使用大学的域名。要抓取整个网络我们需要创造性地选择种子 URL。一个好的种子网址作为一个很好的起点爬虫可以利用它来遍历尽可能多的链接。一般策略是将整个 URL 空间划分为更小的空间。第一个提出的该方法基于地点因为不同的国家可能有不同的流行网站。另一种方法是根据主题选择种子 URL例如我们可以划分 URL 空间购物、体育、医疗保健等。种子 URL 选择是一个开放式问题。你应该不会给出完美的答案。开放思考 网址前沿 大多数现代网络爬虫将爬行状态分为两种待下载和已下载。存储要下载的 URL 的组件称为 URL Frontier。您可以将其称为先进先出 (FIFO) 队列。有关详细信息URL Frontier请参阅深入研究。 HTML下载器 HTML 下载器从 Internet 下载网页。通过 URL 边界提供了这些 URL。 DNS解析器 要下载网页必须将 URL 转换为 IP 地址。超文本标记语言下载器调用DNS解析器来获取URL对应的IP地址。为了例如自 2019 年 3 月 5 日起URL www.wikipedia.org 已转换为 IP 地址198.35.26.96。 内容解析器 下载网页后必须对其进行解析和验证因为格式错误的网页页面可能会引发问题并浪费存储空间。在中实现内容解析器抓取服务器会减慢抓取过程。因此内容解析器是一个单独的成分。 内容已存在了 在线研究[6]显示29%的网页是重复内容这可能导致相同的内容被存储多次。我们介绍“看到的内容”数据结构消除数据冗余并缩短处理时间。它有助于检测新的之前存储在系统中的内容。要比较两个 HTML 文档我们可以一个接一个的比较他们。然而这种方法速度慢且耗时尤其是当涉及数十亿个网页时。完成这项任务的一个有效方法是比较两个网页的哈希值[7]。 内容存储 它是一个用于存储HTML内容的存储系统。存储系统的选择取决于磁盘和内存数据类型、数据大小、访问频率、寿命等因素。
大多数内容存储在磁盘上因为数据集太大无法放入内存。热门内容保留在内存中以减少延迟。
网址提取器 URL Extractor 从 HTML 页面中解析并提取链接。图 9-3 显示了一个示例链接提取过程。通过添加以下内容将相对路径转换为绝对 URL“https://en.wikipedia.org”前缀。 URL 过滤器 URL 筛选器排除了“列入黑名单”的网站。 URL Seen “URL Seen”是一种数据结构用于跟踪之前或已经访问过的 URL最尾端地址。“URL Seen”有助于避免多次添加相同的 URL增加服务器负载并导致潜在的无限循环。布隆过滤器和哈希表是实现“URL Seen”组件。我们不会详细介绍 bloom 过滤器和哈希表的实现这里。有关详细信息请参阅参考资料 [4] [8]。 URL 存储 URL 存储存储已访问的 URL。到目前为止我们已经讨论了每个系统组件。接下来我们把它们放在一起来解释工作流。 网络爬虫工作流程 为了更好地逐步解释工作流程在设计中添加了串行号如图9-4所示。 第 1 步将种子 URL 添加到 URL 边界 第 2 步HTML 下载器从 URL Frontier 获取 URL 列表。 第 3 步HTML 下载器从 DNS 解析器获取 URL 的 IP 地址并启动下载。 第 4 步内容解析器解析 HTML 页面并检查页面是否格式不正确。 第 5 步解析和验证内容后将其传递给“看到的内容”组件。 第 6 步“看到的内容”组件检查 HTML 页面是否已在存储中。
如果它在存储中这意味着不同 URL 中的相同内容已经处理。在这种情况下HTML 页面将被丢弃。如果它不在存储中则系统之前没有处理过相同的内容。这内容被传递给链接提取器。
第 7 步链接提取器从 HTML 页面中提取链接。 第 8 步提取的链接将传递到 URL 过滤器。 第 9 步过滤链接后它们被传递到“URL Seen”组件。 第 10 步“URL Seen”组件检查 URL 是否已经在存储中如果是则为之前处理过不需要做任何事情。 第 11 步如果之前未处理过 URL则会将其添加到 URL 边界。
第 3 步 - 深入探究设计
到目前为止我们已经讨论了高级设计。接下来我们将讨论最多的重要的建筑构件和技术深度
深度优先搜索 DFS 与广度优先搜索 BFSURL 边界HTML 下载器鲁棒性扩展检测并避免有问题的内容
DFS 与 BFS
您可以将 Web 视为有向图其中网页充当节点超链接URL 作为边。爬网过程可以看作是从一个 Web 遍历有向图页面给其他人。两种常见的图遍历算法是 DFS 和 BFS。但是DFS 是通常不是一个好的选择因为DFS的深度可能很深。BFS 通常由网络爬虫使用并由先进先出 FIFO 实现队列。 在 FIFO 队列中URL 按照其排队顺序取消排队。但是这实现有两个问题 来自同一网页的大多数链接都链接回同一主机。在图 9-5 中所有wikipedia.com 中的链接是内部链接使爬虫忙于处理 URL来自同一主机 wikipedia.com。当爬虫尝试下载同时维基百科服务器将充斥着请求。这被认为是“不礼貌”。 标准 BFS 不考虑 URL 的优先级。网络很大并非每个页面都具有相同的质量和重要性水平。因此我们可能想要根据URL的页面排名、网络流量、更新频率等确定URL的优先级。 URL 边界 URL 边界有助于解决这些问题。URL 边界是一种存储的数据结构要下载的 URL。URL 边界是确保合理的重要组成部分URL 优先级和新鲜度。书中提到了一些关于URL前沿的值得注意的论文在参考资料[5] [9]中。这些论文的发现如下 礼貌 通常网络爬虫应避免向同一托管服务器发送过多请求在短时间内。发送过多的请求被认为是“不礼貌”的甚至被对待作为拒绝服务 DOS 攻击。例如在没有任何约束的情况下爬虫可以发送每秒有数千个请求发送到同一个网站。这可能会使网络不堪重负服务器。强制礼貌的一般思路是一次从同一页面下载一页主机。可以在两个下载任务之间添加延迟。礼貌约束是通过维护从网站主机名到下载工作线程线程的映射来实现。每个下载器线程都有一个单独的 FIFO 队列并且仅下载从那个队列。图 9-6 显示了这个队列合理礼貌的设计。 队列路由器确保每个队列b1、b2、…bn 仅包含来自同一主机。 映射表它将每个主机映射到一个队列。 FIFO 队列 b1、b2 到 bn每个队列都包含来自同一主机的 URL。 队列选择器每个工作线程都映射到一个 FIFO 队列并且它只下载该队列中的 URL。队列选择逻辑由队列选择器完成。 工作线程 1 到 N。工作线程从同一个线程中一个接一个地下载网页主机。可以在两个下载任务之间添加延迟。
优先权 来自一个关于苹果产品的论坛的随机帖子具有非常不同的分量而不是 Apple 主页上的帖子。尽管它们都有“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 协议从 Internet 下载网页。 在讨论 HTML 下载器之前我们首先看一下机器人排除协议。 Robots.txt Robots.txt全称为机器人排除协议是网站用于通信的标准与爬虫。它指定允许爬虫下载哪些页面。在尝试之前爬虫抓取网站时首先要检查其对应的robots.txt并遵循其规则。
为了避免重复下载 robots.txt 文档我们缓存该文档的结果。该文档是定期下载并保存到缓存。这是一段 robots.txt 文档取自https://www.amazon.com/robots.txt。某些目录例如 Creatorhub是不允许的对于谷歌机器人。
用户代理Googlebot 禁止/creatorhub/* 禁止/rss/people//reviews 禁止/gp/pdp/rss//reviews 禁止/gp/cdp/member-reviews/ 禁止/gp/aw/cr/
除了 robots.txt 之外性能优化是我们将介绍的另一个重要概念 HTML 下载器。 性能优化 以下是 HTML 下载器的性能优化列表。 1.分布式抓取 为了获得高性能爬虫作业被分发到多台服务器上每台服务器运行多个线程。 URL空间被分割成更小的部分所以每个下载者负责 URL 的子集。图 9-9 显示了分布式爬网的示例。 2.缓存DNS解析器 DNS 解析器是爬虫的瓶颈因为 DNS 请求可能会由于以下原因而花费时间许多 DNS 接口的同步特性。 DNS 响应时间范围从 10 毫秒到200毫秒。一旦某个爬虫线程执行了对 DNS 的请求其他线程就会被阻塞直到第一个请求完成。 维护我们的 DNS 缓存以避免调用 DNS频繁是速度优化的有效技术。我们的 DNS 缓存保留域名名称到 IP 地址的映射并由 cron 作业定期更新。 3. 地点 按地理位置分布爬网服务器。当爬行服务器距离网站主机较近时爬虫体验更快的下载时间。设计局部性适用于系统的大部分组件爬取服务器、缓存、队列、存储等。 4、超时时间短 一些网络服务器响应缓慢或者可能根本不响应。为了避免长时间等待指定了最长等待时间。如果主机在预定时间内没有响应爬虫将停止该作业并爬取其他一些页面。 鲁棒性 除了性能优化之外鲁棒性也是一个重要的考虑因素。我们提出提高系统鲁棒性的几种方法
一致的散列这有助于在下载者之间分配负载。一个新的可以使用一致性哈希来添加或删除下载服务器。参见第五章设计一致的哈希以获取更多细节。保存爬网状态和数据为了防止失败爬网状态和数据被写入一个存储系统。通过加载保存的状态可以轻松重新启动中断的爬网数据。异常处理在大型系统中错误是不可避免且常见的。这爬虫必须优雅地处理异常而不导致系统崩溃。数据验证这是防止系统错误的重要措施。
可扩展性 随着几乎每个系统的发展设计目标之一就是使系统变得灵活足以支持新的内容类型。爬虫可以通过插入新的扩展模块。图9-10显示了如何添加新模块。
插入 PNG 下载器模块以下载 PNG 文档。添加Web监控模块监控网页防止版权和商标侵权。
检测并避免有问题的内容本节讨论如何检测和预防冗余、无意义或有害的内容。 1. 冗余内容 如前所述近 30% 的网页是重复的。哈希值或校验和帮助检测重复 [11]。 2. 蜘蛛陷阱 蜘蛛陷阱是导致爬虫无限循环的网页。例如无穷深层目录结构如下 www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/… 可以通过为 URL 设置最大长度来避免此类蜘蛛陷阱。然而没有人-存在适合所有尺寸的解决方案来检测蜘蛛陷阱。包含蜘蛛陷阱的网站很容易由于在此类网站上发现了异常大量的网页而进行识别。它是难以开发自动算法来避免蜘蛛陷阱;但是用户可以手动验证并识别蜘蛛陷阱然后从爬虫中排除这些网站或应用一些自定义的 URL 过滤器。 3.数据噪声 有些内容几乎没有价值例如广告、代码片段、垃圾邮件URL 等。这些内容对爬虫没有用处应尽可能排除。
第 4 步 - 结束
在本章中我们首先讨论了一个好的爬虫的特征可扩展性、人性礼貌、可扩展性和健壮性。然后我们提出了一个设计方案并讨论了关键组件。构建可扩展的网络爬虫并非易事因为网络非常庞大而且到处都是陷阱。尽管我们已经涵盖了许多话题但我们仍然错过了许多相关的谈话积分
服务器端渲染许多网站使用 JavaScript、AJAX 等脚本来即时生成链接。如果我们直接下载和解析网页我们将无法检索动态生成的链接。为了解决这个问题我们执行服务器端在解析页面之前先渲染也称为动态渲染[12]。过滤掉不需要的页面凭借有限的存储容量和抓取资源反垃圾邮件组件有助于过滤掉低质量和垃圾页面 [13] [14]。数据库复制和分片复制和分片等技术用于提高数据层的可用性、可扩展性和可靠性。水平扩展对于大规模爬虫数百甚至数千台服务器是需要执行下载任务。关键是保持服务器无状态。可用性、一致性和可靠性这些概念是任何大型系统的成功。我们在第 1 章中详细讨论了这些概念。刷新你的关于这些主题的记忆。分析收集和分析数据是任何系统的重要组成部分因为数据是微调的关键成分。
恭喜你走到这一步鼓励下自己。干得好
参考资料 [1] 美国国会图书馆https://www.loc.gov/websites/ [2] 欧盟网络档案馆http://data.europa.eu/webarchive [3] Digimarchttps://www.digimarc.com/products/digimarc-services/piracy-intelligence [4] Heydon A. Najork M. Mercator可扩展、可扩展的网络爬虫万维网24 1999第219-229页 [5] 作者Christopher Olston、Marc Najork网络爬虫http://infolab.stanford.edu/~olston/publications/crawling_survey.pdf [6] 29% 的网站面临重复内容问题https://tinyurl.com/y6tmh55y [7] Rabin M.O. 等人。随机多项式指纹识别 Center for Research in大学艾肯计算实验室计算技术1981 [8] B. H. Bloom“具有允许误差的哈希编码中的空间/时间权衡”《ACM通讯》第13卷第7期第422-426页1970年。 [9] 唐纳德·帕特森Donald J. Patterson网络爬虫https://www.ics.uci.edu/~lopes/teaching/cs221W12/slides/Lecture05.pdf [10] L. Page、S. Brin、R. Motwani 和 T. Winograd“PageRank 引文排名为网络带来秩序“技术报告斯坦福大学1998. [11] 伯顿·布鲁姆。哈希编码中的空间/时间权衡与允许的误差。ACM 通讯137第 422–426 页1970 年 7 月。 [12] 谷歌动态渲染 https://developers.google.com/search/docs/guides/dynamic-rendering [13] T. Urvoy、T. Lavergne 和 P. Filoche“使用隐藏样式跟踪网络垃圾邮件相似性“载于第二届对抗性信息国际研讨会论文集网络上检索2006 年。 [14] H.-T.Lee、D. Leonard、X. Wang 和 D. Loguinov“IRLbot扩展到 60 亿页及其他“第 17 届国际万维网会议论文集2008 年。
