分布式网络爬虫的设计与实现——分布式算法研究和系统架构设计---毕业论文

本本 科科 毕毕 业业 论论 文文 分布式网络爬虫的设计与实现分布式网络爬虫的设计与实现 分布式算法研究和系统架构设计分布式算法研究和系统架构设计 The Design and Implementation of Distributed Web Crawler Distributed Algorithm Research and System Architecture Design 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年年 月月 摘摘 要要 随着网络技术的发展，Web上的信息海量增加，人们对信息的需求也不断加 大，使得专门负责Web信息采集的网络爬虫技术面临着巨大的挑战。集中式的单 机网络爬虫由于运行效率低、搜索时间长等缺点在很多情况下已经难当重任， 分布式网络爬虫以其单机网络爬虫无法比拟的信息采集速度和规模，满足了人 们日益增长的对Web信息的需求。 本文通过对分布式网络爬虫相关知识和技术的研究，设计了一个以中心化 拓扑结构为基础的分布式网络爬虫架构，其中一台主机作为控制中心节点，多 台主机作为爬行节点，在局域网中连接，由控制中心节点进行任务分配，协调 调度多个爬行节点并行爬取网页信息。通过对任务分配策略和分配粒度的研究， 系统采用二级哈希映射的任务分配算法实现了分布式系统的协调机制，在控制 中心节点的协调下，多个爬行节点避免重复爬行，均衡全面地采集网页信息。 最终开发实现了一个容错能力强、负载均衡，爬行性能良好的分布式网络 爬虫系统原型程序。并对其进行了详细的测试评估，实验结果验证了分布式网 络爬虫的可行性和高效性。 关键词：关键词：分布式系统；网络爬虫；任务分配 Abstract With the development of network technology, Web information increase rapidly,at the same time peoples information needs have also increased, so the network technology of Web Crawler is faced with enormous challenges.because of A single Web Crawler has some disadvantage ,such as low operating efficiency, long search time etc.It is difficult to crawl the whole Web as comprehensive as possible for a single Crawler.Distributed Crawler can run more than one Crawler to crawl the Web information concurrently,so Distributed Crawler sovle the problem of the increasing Web information on demand. Based on the knowledge and technology of distributed crawler research,this paper design the architecture of Distributed Crawler with center of a topology-based including one PC as the control center, more than one PC as crawling nodes with the LAN connected. Nodes from the control center for distribution of tasks, coordination of scheduling a number of parallel crawling node information from the page. This paper also study the strategy of task allocation and distribution of particle size, achieve a distributed system coordination mechanisms with two-level hash task distributed algorithm. Ultimately,this paper introduce how to develop a balanced,comprehensive,strong and efficient Distributed Crawler to collect Web pages from the Internet . Key words: Distributed System; Web Crawler; Task Allocation 目目 录录 第一章第一章 引言引言1 1.11.1 课题研究背景及意义课题研究背景及意义.1 1.21.2 本文主要工作内容本文主要工作内容.2 1.31.3 论文组织结构论文组织结构.3 第二章第二章 分布式网络爬虫相关知识分布式网络爬虫相关知识4 2.12.1 搜索引擎工作原理搜索引擎工作原理.4 2.22.2 分布式与集中式网络爬虫分布式与集中式网络爬虫.6 2.2.1 集中式网络爬虫.6 2.2.2 分布式网络爬虫.7 2.2.3 分布式系统的优缺点.8 2.32.3 分布式网络爬虫研究现状分布式网络爬虫研究现状.9 第三章第三章 分布式网络爬虫系统架构设计分布式网络爬虫系统架构设计11 3.13.1 分布式拓扑结构的选取分布式拓扑结构的选取.11 3.1.1 中心化拓扑结构11 3.1.2 全分布式非结构化拓扑结构12 3.1.3 全分布式结构化拓扑结构.13 3.1.4 半分布式拓扑结构.13 3.1.5 拓扑结构的选取14 3.23.2 系统功能分析与设计目标系统功能分析与设计目标.15 3.33.3 系统的基本结构设计系统的基本结构设计16 3.3.1 系统总体结构设计.16 3.3.2 控制中心结构设计.17 3.3.3 爬行节点结构设计.19 第四章第四章 分布式协调机制的实现分布式协调机制的实现.23 4.14.1 分布式任务分配分布式任务分配23 4.1.1 分配策略23 4.1.2 分配粒度25 4.1.3 任务分配函数26 4.1.4 任务分配算法27 4.24.2 节点管理与通信节点管理与通信29 4.2.1 控制中心对爬行节点的管理.29 4.2.2 控制中心与爬行节点的信息传输30 第五章第五章 系统实现与测试分析系统实现与测试分析.32 5.15.1 系统实现系统实现.32 5.1.1 开发环境与类组织结构.32 5.1.2 系统架构实现33 5.1.3 控制中心类详细设计35 5.25.2 运行结果运行结果.37 5.35.3 测试分析测试分析.40 5.3.1 分布式爬行与单机爬行比较测试.40 5.3.2 分布式爬行性能测试.43 第六章第六章 结束语结束语45 参考参考文文献献 .46 致谢语致谢语48 Contents Chapter 1 Introduction.1 1.1 Background1 1.2 Contents.2 1.3 Structure3 Chapter 2 Knowledge of distributed web crawler4 2.1 Principles of search engine.4 2.2 Distributed and single crawler.6 2.2.1 Single web crawler.6 2.2.2 Distributed web crawler.7 2.2.3 The advantege of distrituted8 2.3 Research status of distributed crawler9 Chapter 3 Design of system structure11 3.1 Selection of Topology.11 3.1.1 Centralized Topology.11 3.1.2 Distributed non-structure Topology.12 3.1.3 Distributed structure Topology13 3.1.4 Partially Decentralized Topology.13 3.1.5 Selection14 3.2 Design Objectives.15 3.3 Structure Design16 3.3.1 Structure Design of System16 3.3.2 Structure Design of Control center.17 3.3.3 Structure Design of Crawling node19 Chapter 4 Implementation of coordination mechanism23 4.1Task Allocation23 4.1.1Strategy.23 4.1.2Mission size25 4.1.3Function26 4.1.4Algorithm.27 4.2Management and Communication29 4.2.1 Management.29 4.2.2 Communication.30 Chapter 5 Results and test.32 5.1Implementation32 5.1.1Development environment.32 5.1.2Implementation of Structure33 5.1.3Class of Control center .35 5.2Results.37 5.3Test and Analysis40 5.3.1 Test between Distributed and Single40 5.3.2 Performance testing.43 Chapter 6 Conclusions45 References.46 Acknowledgements48 第一章 引言 - 1 - 第一章第一章 引言引言 1.11.1 课题研究背景及意义课题研究背景及意义 随着国际互联网（internet）的迅速发展，网上的信息越来越多，全球目 前的网页超过 30 亿个，每天新增加上百万网页。要在如此浩瀚的信息海洋里寻 找信息，就像“大海捞针”一样困难。搜索引擎正是为了解决这个问题而出现 的技术。搜索引擎是通过互联网搜索信息的重要途径。它要用到信息检索、人 工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语 言处理等多领域的理论和技术，具有很高的综合性和很强的挑战性。而搜索引 擎的网页信息来源是由一种叫做网络爬虫的信息采集程序提供的。 网络爬虫是指可以在 Web 上漫游并按照一定规则自动从 Web 上采集网页的 计算机程序。它也经常被称为“蜘蛛” （Spider） ， “机器人” （Robot）或者“漫 游者” （Wanderer）等。通俗的讲，网络爬虫就是一种下载网页的信息采集程序。 通常，一个网络爬虫从一个初始的 URL 集合开始，首先把这些 URL 放进队列。 网络爬虫在运行时从队列中取出 URL，下载其指向的页面，从下载的页面中提 取出新的 URL，然后把新的 URL 放进队列。这个过程被网络爬虫反复执行，直 到其停止运行。可以清晰地看到，网络爬虫所执行的这个过程实际上就是对互 联网遍历的过程。网络爬虫下载的页面被保存在磁盘上，并建立索引，以供日 后分析其内容。 网络爬虫的应用领域十分广泛。目前主要的搜索引擎，如 Google，AltaVista，Excite，MSN 等，都各自拥有自己实现的网络爬虫。这些 综合性的搜索引擎要下载大量的 Web 页面，并建立索引，为用户搜索信息提供 资源。近年来兴起的主题搜索中也利用的网络爬虫技术。在主题搜索中，网络 爬虫也访问大量的 Web 页面，但是只下载特定内容的信息（例如邮件地址） 。网 络爬虫也可以用于桌面应用。爬行器可以为特定用户检索感兴趣的页面，并建 立页面缓冲，为用户快速浏览信息提供便利。对于搜索引擎来说，要采集到互 联网上所有的网页几乎是不可能的，从目前公布的数据来看，容量最大的搜索 引擎也不过只采集了整个网页数量的百分之四十左右1。这其中的原因一方面 第一章 引言 - 2 - 是网络爬虫技术的瓶颈，无法遍历所有的网页2，有许多网页无法从其它网页 的链接中找到；另一个原因是存储技术和处理技术的问题，如果按照每个页面 的平均大小为 20K 计算，100 亿网页的容量是 100*2000G 字节。即使能够存储， 下载也存在问题，按照一台机器平均每秒下载 20K 计算，需要 340 台机器不停 的下载一年时间，才能把所有网页下载完毕。而互联网上的页面数量又是在迅 速增大的，因此穷尽下载互联网的内容几乎不可能。同时，如果数据量太大， 搜索引擎在提供搜索时也会有效率方面的影响。因此，用于搜索引擎的网络爬 虫只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据可以是某 个网页的链接深度。 索引网页数量的大小和质量的好坏是评价一个搜索引擎的重要指标3。因 此，一个高效的网络爬虫系统是一个好的搜索引擎的重要基础。但是出于商业 机密的考虑，目前各个搜索引擎使用网络爬虫系统的技术内幕一般都不公开。 现有的文献也仅限于概要性的介绍456，如斯坦福大学的Google，康柏研究中 心的Mercator以及卡内基梅隆大学的WebSPHINX，对于分布式网络爬虫的详细设 计和实现很少涉及。3Mercator和WebSPHINX是在单机上运行的, 它们的信息搜 集速度比较有限,就目前互联网的规模来说, 已无法在一个有效的时间范围内完 成一次尽可能全面的搜集整个Web的任务，分布式网络爬虫系统采用多机并行工 作, 提高整个系统的工作效率, 并具有良好的可扩展性, 是必然的发展趋势。 1.21.2 本文主要工作内容本文主要工作内容 本文根据对分布式网络爬虫技术的研究，自主开发了一个容错能力强、负 载均衡，爬行性能良好的分布式网络爬虫系统原型程序。主要的工作内容为： 1.研究网络爬虫的工作原理和组成部分，分析了分布式网络爬虫相对于传 统集中式网络爬虫的优点。 2.调研了当前分布式网络爬虫的研究现状。 3.设计分布式系统体系结构，并详细设计了控制中心节点和爬行节点的各 个功能组成模块。 4.对分布式算法进行了研究，通过研究任务分配策略、任务分配粒度和任 务分配函数，设计了二级哈希映射的任务分配算法。通过任务分配和节点通信 第一章 引言 - 3 - 协作实现分布式协调机制。 5.实现全部控制中心节点程序和部分爬行节点程序的编写，实现控制节点 和爬行节点的交互，并使得控制中心可实时监控各个爬行节点。 1.31.3 论文组织结构论文组织结构 第一章:介绍了课题研究背景和意义，概述了本文主要工作内容和论文组织 结构。 第二章:介绍了分布式网络爬虫的相关知识，通过搜索引擎的工作原理引出 网络爬虫在搜索引擎中的作用，并对分布式和集中式爬虫做了分析比较，介绍 了分布式网络爬虫的研究现状。 第三章:介绍了爬虫系统的架构设计，包括分布式拓扑结构的选取，系统设 计目标和系统结构设计，着重介绍了控制节点和爬行节点的功能模块设计。 第四章:介绍了分布式协调机制的实现，包括任务分配策略，任务分配粒度， 任务分配算法以及节点管理和通信方法。 第五章:介绍了系统的实现和测试，包括系统实现的细节和运行结果，比较 测试和性能测试 第六章:结束语，总结概述全文。 第二章 分布式网络爬虫相关知识 - 4 - 第二章第二章 分布式网络爬虫相关知识分布式网络爬虫相关知识 2.12.1 搜索引擎工作原理搜索引擎工作原理 搜索引擎是指根据一定的策略、运用特定的计算机程序搜集互联网上的 信息，在对信息进行组织和处理后， 将信息显示给用户从而为用户提供检 索服务的系统。 总体来说搜索引擎可分为目录搜索引擎和全文搜索引擎，本 文讨论的是全文搜索引擎技术。 从使用者角度看，搜索引擎提供一个包含搜索框的页面，在搜索框输入 词语，通过浏览器提交给搜索引擎后，搜索引擎就会返回跟用户输入的内容 相关的信息列表。 从功能角度看，搜索引擎搜集互联网上成千上万的网页,并对网页中的内容 按照关键词进行索引，建立索引数据库供用户进行全文搜索。当用户需要查找 某一个关键词时，所有在页面内容中包含了该关键词的页面都会被搜索出来。 本文所研究的网络爬虫就是搜索引擎中负责信息采集的程序，是搜索引擎中的 数据来源，先来通过搜索引擎的工作原理来介绍网络爬虫在搜索引擎中的作用。 第二章 分布式网络爬虫相关知识 - 5 - 图图2-12-1 搜索引擎的基本构成搜索引擎的基本构成 上图描述了搜索引擎的基本构成，信息采集器从互联网上采集并存储信息， 经过网页分析处理之后由索引器进行处理建立索引数据库，用户通过查询接口 从索引数据库中查询信息，信息通过复杂的算法排序后将结果呈现给用户。因 此，当我们在百度或Google的搜索框键入一个单词进行搜索时，这个搜索需求 并不是实时去海量的互联网信息数据中去寻找与其相关的页面，而是搜索引擎 本身在此之前已经做了许多工作，搜索引擎的工作原理可以归纳为三步：从互 联网上抓取网页，建立索引数据库，在索引数据库中搜索排序查询。 网页内容库 索引数据库 索引程序 查询程序 网络爬虫 用户 因特网 图图2-22-2 搜索引擎工作原理简图搜索引擎工作原理简图 上图描述了搜索引擎的工作原理。依靠网络爬虫获取互联网上的大量的网 页信息，交给索引程序建立索引，最后提交给用户查询程序供用户使用。传统 搜索引擎的工作从功能结构上划分主要分三个部分：从互联网上获取信息的爬 虫模块；建立全文索引库的索引模块；用户查询模块。下面简要介绍一下各个 模块的作用。 1.网络爬虫模块 网络爬虫实际上是一个基于 web 的程序。它从一个初始的网页集出发，遍 第二章 分布式网络爬虫相关知识 - 6 - 历Internet自动的采集网络信息。当爬虫打开某个HTML 页面后，它会分析HTML 标记结构来获取信息，并获取指向其它页面的超级链接，然后通过既定的搜索 策略选择下一个要访问的站点。从理论上讲，如果为Spider 指定个适当的初始 文档集和个适当的网络搜索策略，它就可以遍历整个网络。它的性能在很大程 度上影响了搜索引擎站点的规模。 2.索引模块 网络爬虫爬取的网页上的信息以固定的格式获取到本地后，索引建立程序 对信息进行分析，针对页面中出现的关键词建立一种利于快速查找的数据结构， 即索引，以供搜索引擎使用。搜索引擎在选择索引数据结构时通常考虑两个因 素：紧凑的数据结构和高效的检索能力。由于搜索引擎在建立索引的时候是面 对海量的信息，因此在考虑记录大小时要具体到字节中的位，这样才能达到一 种比较合理科学性的空间膨胀比。合理的数据结构将使对关键词的检索更加迅 速。通常有三种索引的建立基本技术：倒排文件、后缀数组和签名文件。倒排 文件在当前大多数信息获取系统中得到应用，它对于关键词的搜索非常有效。 后缀数组在短语查询中具有较快的速度，但是该结构在维护上相对比较麻烦。 签名文档如今已被倒排索引技术替代。处理网页的过程主要包括这几部分:文档 特征向量提取、网页筛选、相关度分析、文档分类和入库操作。 3.用户查询模块 用户查询模块是搜索引擎和用户之间的接口。其首先获取用户查询条件并 加以分析，然后访问索引数据库进行匹配后获得检索结果，然后根据设定的相 关度进行降序排序处理后返回给用户。 2.22.2 分布式与集中式网络爬虫分布式与集中式网络爬虫 .1 集中式网络爬虫集中式网络爬虫 集中式网络爬虫指运行于单机的集中爬取网页的网络爬虫程序，其工作原 理是：给定一组初始 URL 种子集合，通过爬虫主体程序多个线程分别获取到种 子 URL 后，将 URL 对应的 html 页面获取到本地进行分析，页面内容提取模块 将页面中有用的可供搜索引擎建索引的信息获取到本地保存起来，种子提取模 第二章 分布式网络爬虫相关知识 - 7 - 块将 html 页面中新的指向其他页面的链接提取出来，经过一系列的处理保存 起来供以后继续爬行。 爬虫在网络中爬行的时候，将Web 上的网页集合看成是一个有向图，从给 定的起始URL 开始，沿着网页中的链接，按照一定的策略进行。通常用到以下 几种遍历算法： 1.深度优先算法 该算法是指网络爬虫会从选定的一个超链接开始，按照一条线路，一个一 个链接访问下去，直到达到这条线路的叶子节点，即不包含任何超链接的HTML 文件，处理完这条线路之后再转入下一个起始页，继续访问新的起始页面所包 含的链接中的一条，直到到达叶子结点。这个方法有个优点是网络爬虫在设计 的时候比较容易。 2.广度优先算法 广度优先算法是指网络爬虫会先抓取起始网页中包含链接的所有网页，然 后再选择其中的一个链接网页，继续抓取在这个网页中链接的所有网页。这种 搜索方法是实现通用网络爬虫的最佳方法，因为它的特点是易于实现，并且能 够避免陷进一个无穷尽的深层分支中去，可以让网络爬虫并行处理，从而提高 其抓取速度。 3.启发式搜索算法 启发式搜索算法源于人工智能，即先通过在线获得的领域知识评价待访问 链接的价值，借以推断信息资源的分布情况，然后按一定的原则选择价值最大 的链接进行下一步的搜索，找到到达目标节点的最佳路径，删除不好节点，保 留那些好的节点，该算法主要用于主题爬虫。 .2 分布式网络爬虫分布式网络爬虫 随着 WWW 信息的爆炸性增长，网络爬虫信息采集的速度越来越不能满足实 际应用的需要。即使大型的信息采集系统对Web 的覆盖率也只有 3040，刷 新一遍已经采集的页面常常需要数周到一个月的时间，致使集中式的搜索引擎 已经出现了效率瓶颈,网上庞大的数字化信息和人们获取所需信息能力之间的矛 盾日益突出。 第二章 分布式网络爬虫相关知识 - 8 - 解决这一问题的直接办法是升级信息采集器的硬件，采用处理能力更强的 计算机系统，然而这种方法的扩展性有限，性价比也不高。因而人们找了一个 更好的选择，用分布式方式来进行网页信息采集。分布式网络爬虫比集中式网 络爬虫往往有更高的性能，是今后大规模网络爬虫发展的一个重要方向。分布 式网络爬虫可以看做由多个集中式网络爬虫组合而成。分布式系统中的每个节 点都可以看作一个集中式网络爬虫。分布式爬虫与集中式爬虫工作原理基本相 同，但前者需要各个节点协作完成网页的爬行，从而使得分布式爬虫的效率远 远高于集中式爬虫。分布式爬虫的系统结构有很多种，工作方式也各不相同。 对于典型的分布式爬虫系统，它的每个节点不仅从web 页面获得URL，同时也从 其它节点接收URL。然后节点对URL 对应的网页进行解析，并将不属于自己爬行 范围的URL 转发给其它节点。 .3 分布式系统的优缺点分布式系统的优缺点 尽管分布式系统有自己的优势，它也有自身的缺点。首先是软件问题，大 部分分布式软件设计较为复杂。第二个问题与通信网络有关。网络可能丢失数 据，需要有特殊的软件处理。它也有可能过载，当网络饱和时，要么被替换掉， 要么增加一个新的网络。这两种选择都需要全部或部分地重新布线，更换网卡。 当系统过分依赖于网络时，网络中的数据丢失或过载会抵消分布式系统的优点。 第三，数据共享导致安全性问题，这也是一个不能忽视的问题。 尽管有上述潜在的问题，总的说来分布式的优点超过了它的缺点，见表2- 1。 表表2-12-1 分布式系统相对于集中式系统的优点分布式系统相对于集中式系统的优点 优点说明 经济性多机多个微处理器能提供比大型机更好的性能价格比 高效性分布式系统利用多机并行计算提高计算能力，大大增加 工作效率 分布性物理上分散的机器，可以充分利用每个机器的资源 可靠性当某台机器崩溃时，整个系统仍能正常工作 第二章 分布式网络爬虫相关知识 - 9 - 扩展性计算能力逐步增加 分布式系统的应用将越来越广泛，就搜索引擎系统而言，采用分布式系统 更是利大于弊。Internet 本身就是分布式的，适合于采用分布式方案搜集信息。 搜索引擎系统采用分布式，可以继承分布式系统本身的优点，同时，通过精心 设计，可以避免分布式系统本身的缺点。 2.32.3 分布式网络爬虫研究现状分布式网络爬虫研究现状 要在搜索引擎中尽可能地找到用户所需信息，就要求搜索引擎索引尽可能 多的网页，索引网页数量是评价一个搜索引擎好坏的关键因素之一。采用分布 式技术在尽可能短的时间内搜集尽可能多的网页，是研制高效搜索引擎的关键 技术。 到目前为止，分布式网络爬虫系统已经有了不少应用，例如现在著名的 Google 和Alta Vista 搜索引擎所采用的网络爬虫系统。但由于商业机密等因 素的影响，较详细的介绍分布式网络爬虫系统的文章并不多，并且基于 Web 信 息采集的分布式理论也还不完善，仍然有待研究。目前，较著名的分布式爬虫 有Google Crawler、Mercator、Internet Archive Crawler、UbiCrawler 等7 8，国内的有北大天网的Web Gather 爬虫系统9。 Google 的分布式爬虫系统由四台机器组成，其中一台机器是中央主机，其 它三台机器只负责爬行网页，并且只与中央主机通信。中央主机从一个文件里 读取URL，并把它们分发给其它机器的Crawler 进程。爬虫采用异步I/O 同时从 300 个网站上获取数据。所有的Crawler 将下载来的页面压缩并存放在磁盘上。 然后Indexer 进程从这些HTML页面中将URL 提取出来，并存放在另一个磁盘文 件中。URL Resolver 进程读取这个存放链接的文件，将其中的相对链接转化为 绝对链接，然后存入一个文件供中央主机读取。不足之处在于如果中央主机失 效，则整个系统都会停止工作，而且中央主机的URL 分发模块常常成为整个系 统的瓶颈。 Mercator 是Alta Vista 搜索引擎的网络爬虫，它完全由JAVA 写成。 Mercator 的可扩展性非常好，可以通过增减或替换模块来实现不同的功能。 第二章 分布式网络爬虫相关知识 - 10 - Mercator 采用的数据结构可以使无论爬行的规模有多大，只占用有限的内存， 数据结构的大部分都在硬盘中存放。并且Mercator 只存放URL 的checksum 值， 这样可以节省大量的内存和磁盘空间。Mercator 为最近访问URL 建立了缓存， 该缓存的命中率达到85。在提高系统性能方面，Mercator 系统做了非常多的 工作，比如重写JAVA 核心库，建立缓存，采用高速硬盘系统。Mercator 证明 了使用JAVA 语言也可以达到较高的性能。 Internet Archive 爬虫系统采用多个机器共同搜集网页。每个Crawler 进 程负责搜集64 个Web 站点的网页10。Crawler 从起始URL 集合中读取，采用 异步I/O 并行爬取网页。网页下载后，提取出超链接。如果超链接属于本 Crawler 负责搜集的Web 站点，则加入未访问URL 集合，否则存储到交叉URL 文件中。批处理模块定期分配这些交叉URL文件到相应的搜集模块，在此过程中 要过滤掉重复的URL11。 表表2-22-2 几种著名分布式网络爬虫比较几种著名分布式网络爬虫比较 GoogleGoogleMercatorMercatorInternetInternet ArchiveArchive UbiCrawlerUbiCrawler URL存储结构 Hash Table 数据结构 Bloom Filter 数据 结构 使用的编程 语言和类库 C+/python Java，重写 Java类库 Java 并行度( (每个 节点) ) 异步I/O 300个连接 同步 I/O， 100个线程 异步 I/O 64个线程 同步 I/O 4个线程 第三章 分布式网络爬虫系统架构设计 - 11 - 第三章第三章 分布式网络爬虫系统架构设计分布式网络爬虫系统架构设计 3.13.1 分布式拓扑结构的选取分布式拓扑结构的选取 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系， 结点之间的拓扑结构一直是确定系统类型的重要依据1213。根据拓扑结构的关 系可以分为4 种结构:中心化拓扑结构(Centralized Topology)、全分布式非结 构化拓扑结构(Decentralized Unstructured Topology)、全分布式结构化拓扑 结构(Decentralized Structured Topology)和半分布式拓扑结构(Partially Decentralized Topology)。下面分别介绍一下各种结构的特点。 .1 中心化拓扑结构中心化拓扑结构 这种结构中有一个节点作为中心节点，其它节点只与中心节点通信13。当 爬行节点发现新URL 时，就将其提交给中心节点，然后中心节点负责将任务转 发给相应节点。结构如下图所示： 图图3-13-1 中心化拓扑结构图中心化拓扑结构图 第三章 分布式网络爬虫系统架构设计 - 12 - 这种结构的最大优点在于由于中心节点的存在，使分布式系统的管理和维 护比较简单。当有节点加入或退出时，只与中心节点通信即可，不会出现系统 视图不一致的情况。缺点主要有两个，可靠性低：如果中心节点崩溃，则整个 分布式系统都会崩溃。效率低：当爬行节点数量较多时，中心节点常常不堪重 负，成为系统的瓶颈。 .2 全分布式非结构化拓扑结构全分布式非结构化拓扑结构 在这种结构中，所有的节点都是对等的，每个节点既是客户机，又是服务 器。其结构如下图所示： 图图3-23-2 全分布式非结构化拓扑结构图全分布式非结构化拓扑结构图 这种结构对网络的动态变化有较好的容错能力，可靠性较高。14但缺点在 于当网络规模较大时，节点之间相互通信的效率较低，而且对带宽消耗较大。 第三章 分布式网络爬虫系统架构设计 - 13 - .3 全分布式结构化拓扑结构全分布式结构化拓扑结构 与全分布式非结构化拓扑结构不同之处，在于这种结构中每个节点只能与 系统中部分节点通信，而前者每个节点能与系统中所有节点进行通信。节点之 间的相互通信依赖于分布式哈希表(Distributed Hash Table，简称DHT)15。 DHT实际上是一个由广域范围大量结点共同维护的巨大Hash 表。Hash 表被分割 成不连续的块，每个节点被分配给一个属于自己的Hash 块，并成为这个Hash 块的管理者。Hash表中存储的是这个节点可以通信的其它节点的信息。这种结 构有着良好的可扩展性和健壮性，适用于大规模网络。其结构如下图所示： 图图3-33-3 全分布式结构化拓扑结构图全分布式结构化拓扑结构图 .4 半分布式拓扑结构半分布式拓扑结构 这种结构是一种层次性结构，它是中心化结构和全分布式非结构化拓扑结 构的结合体。选择性能较高(处理、存储、带宽等方面性能)的节点作为超级点 (Super Node )，在各个超级点上存储了系统中其他部分节点的信息。超级点之 间采用全分布式非结构化拓扑结构连接，超级点与子节点之间采用中心化拓扑 第三章 分布式网络爬虫系统架构设计 - 14 - 结构连接。其结构如下图所示： 图图3-43-4 半分布式拓扑结构图半分布式拓扑结构图 这种结构吸取了中心化结构和全分布式非结构化拓扑结构的优点。它的性 能和可扩展性较好，而且容易管理，适用于大规模网络。缺点在于系统对超级 点依赖性较大，容错性、健壮性受到影响。 .5 拓扑结构的选取拓扑结构的选取 前面所述的分布式系统拓扑结构中，半分布式拓扑结构和全分布式结构化 拓扑结构适用于大规模网络，节点间依赖关系较为复杂，在小规模网络中体现 不出其优势。对于全分布式非结构化拓扑结构，其中节点既做客户机又做服务 器，为了达到容错性每个节点都要与其余所有节点进行通信，占用了网络资源 且在节点数目逐渐增加时凸显冗余的缺点。 考虑到本课题运行环境在局域网中，且系统中节点数目规模有限，所以采 用中心化拓扑结构实现一个控制中心协调多个爬行节点并行爬行的分布式系统 结构。每个爬行节点只与控制中心进行通信，由控制中心统一协调各个爬行节 点的工作。 第三章 分布式网络爬虫系统架构设计 - 15 - 3.23.2 系统功能分析与设计目标系统功能分析与设计目标 本文所开发的分布式网络爬虫系统采用C/S架构，控制中心节点作为Server 端，爬行节点作为Client端，由Server协调控制多个Client进行并行爬取网页 的程序。主要功能需求为： 控制中心（Server端）： 1.可操作性和可配置性。即可对各个爬行节点的爬行参数可配置，包括爬 行的初始网页，爬行深度，开启的爬行线程数目等等。 2.可监控性。即可对各个爬行节点的爬行状态进行动态监控，在Server端 实时显示每个爬行节点的运行状态，包括爬行节点的ID号，爬行的起始时间， 运行时间，爬取有效网页数量，超时网页数量等等。 3.动态任务分配。任务分配是整个分布式爬虫系统的关键，合理高效的任 务分配是各个爬行节点避免重复爬取，达到负载平衡的前提。在Server端主要 做两件事：分配URL任务到相应的爬行节点，接收来自爬行节点的非己任务（非 己任务即为不属于本爬行节点的任务集合）。 4.负载平衡性。由控制中心分配给各个爬行节点的任务量应达到负载平衡。 5.容错性。考虑到实际应用中网络爬虫系统会运行很长时间，有可能会存 在某个爬行节点故障的可能，所以控制中心在爬行节点故障时做出相应调节， 包括任务分配器的调整。由于控制中心节点也有可能故障出错，但是考虑到本 文选取的中心拓扑结构暂不讨论此种情况，若考虑到中心节点故障可选用前面 讨论的全分布式拓扑结构，当Server端崩溃时由其它爬行节点接替Server端工 作。 爬行节点（Client端）： 1.接收来自控制中心分配的任务URL集，以此来进行爬取网页行为。 2.将不属于自身的URL集发送回控制中心。 3.将自身爬行信息发送给控制中心。 第三章 分布式网络爬虫系统架构设计 - 16 - 3.33.3 系统的基本结构设计系统的基本结构设计 .1 系统总体结构设计系统总体结构设计 如图 3-5 所示，分布式网络爬虫系统采用 C/S 架构，一个控制中心作为 Server 端，多个爬行节点作为 Client 端，由控制中心控制协调，多个爬行节 点并行爬取网页。此处并行包含两层含义，一是多个爬行节点并行爬取，二是 单个节点开启多个线程并行爬取。爬行节点将爬取结果存入统一数据库中，以 便为搜索引擎下一步建立索引数据库使用，每个爬行节点与控制中心交互，交 互信息为接收任务集合，发送非己任务集合，发送节点爬行信息（用于控制中 心监控） 。 Internet 控制中心 数据库 爬行节点 爬行节点爬行节点 爬行节点 URLs and NodeInfo Crawl Download Pages Download Pages URLs and NodeInfo URLs and NodeInfoURLs and NodeInfo Crawl CrawlCrawl 图图 3-53-5 系统总体结构图系统总体结构图 第三章 分布式网络爬虫系统架构设计 - 17 - .2 控制中心结构设计控制中心结构设计 控制中心节点详细划分为 5 个模块：任务分配模块，信息监控模块，URL 传输模块，节点信息传输模块以及爬行节点管理模块。控制中心的结构以及各 个模块间关系如图 3-6 所示。 -任务分配- -信息监控- Server Client 节点信息传输 模块 爬行节点管理 模块 任务分配模块 URL传输模块 任务URL 爬行参数 起始URL 爬行参数 节点爬行信息 任务URL 非己任务URL 信息监控模块 节点爬行信息 图图 3-63-6 控制中心工作流程图控制中心工作流程图 如上图所示控制中心的工作流程为： 1.将用户输入的爬行参数通过节点信息传输模块传递给每个爬行节点，作 为爬取网页行为的依据。 2.将用户输入的起始 URL 种子网址通过任务分配模块分配给相应的爬行节 点。 第三章 分布式网络爬虫系统架构设计 - 18 - 3.接收来自各个爬行节点的非己任务集合，然后通过任务分配模块和 URL 传输模块分配给相应的爬行节点。 4.每个爬行节点的爬行信息通过信息监控模块反馈给控制中心。 下面对各个功能模块具体分析如下： 1.任务分配模块 任务分配模块负责将 URL 分配到相应的爬行节点，所做工作就是将接收到 的 URL 集合通过任务分配算法确定到对应的节点，然后发送给相应的爬行节点。 其中任务分配算法涉及到任务分配的策略，URL 散列算法，任务分配粒度 等关键技术将会在下一章详细介绍。任务分配对应到爬行节点后要进行任务的 派发，此处涉及到对各个爬行节点的统一管理，Socket 通信与 Java I/O 技术 也将在下一章详细介绍。 2.信息监控模块 信息监控模块负责实时监控各个爬行节点的爬行状态，并在控制中心动态 显示，以此来观察各个爬行节点是否负载平衡，爬行效率及速度是否均衡，以 便实现可操作性，从而体现控制中心的协调调度作用。只要系统处于运行状态， 信息监控模块就实时的接收来自各个爬行节点发送来的节点状态信息（如每隔 1s 接收一次） 。这些状态信息包括节点 ID、爬行开始时间、爬行运行时间、爬 取有效网页数量、爬取超时网页数量等，然后将这些信息动态显示在控制中心 端可视化界面上，以起到对整个分布式系统的监控作用。 3.URL 传输模块 URL 传输模块负责在控制中心与爬行节点之间传输 URL，主要传输任务包括 接收来自爬行节点的非己任务和发送已经分配好的任务给对应的爬行节点。 4.节点信息传输模块 节点信息传输模块负责将爬行参数和起始 URL 发送给爬行节点，当各个爬 行节点稳定运行开始从互联网爬取网页信息后，实时将各个爬行节点的爬行状 态信息发回给控制中心。 5.爬行节点管理模块 爬行节点管理模块负责管理多个爬行节点，多个爬行节点以 ID 号递增的形 第三章 分布式网络爬虫系统架构设计 - 19 - 式在管理模块注册，管理模块建立爬行节点 ID 与其连接线程，输入输出流的映 射关系，当任务分配模块将 URL 分配到对应爬行节点时，调用爬行节点管理模 块找到对应的连接线程以及输入输出流并将任务分配到对应爬行节点。具体的 实现细节将在第五章详细介绍。 爬行节点管理模块还要考虑节点有效性监控，因为网络爬虫程序一般需要 运行较长时间，存在其中某一个或者多个爬行节点出现故障的可能性很大，爬 行节点的减少分为主动退出和被动故障，当爬行节点主动退出时需要向控制中 心发送退出消息，以便控制中心做出相应调整，当遇到故障出错时，控制中心 无从知晓。为解决这个问题，控制中心的爬行节点管理模块需要做两件事，一 是负责接收来自爬行节点的退出信息，二是间隔一段时间就向爬行节点发送有 效性判断消息，如果有回应说明爬行节点运行正常，如果无回应说明爬行节点 故障退出。 第三章 分布式网络爬虫系统架构设计 - 20 - .3 爬行节点结构设计爬行节点结构设计 -与Server交互- -爬取网页- Server 网页解析 模块 下载模块 任务URL 起始URL 爬行参数 数据存储 模块 优雅爬行 模块 URL传输 模块 节点信息 传输模块 任务定位 模块 非己任务URL起始URL Internet 网页内容 数据库 节点信息 图图 3-73-7 爬行节点工作流程图爬行节点工作流程图 爬行节点详细划分为 5 个模块：爬行模块（包含下载模块、网页解析模块、 优雅爬行模块三个子模块） ，数据存储模块，任务定位模块，URL 传输模块以及 节点信息传输模块。爬行节点的结构以及各个模块间关系如图 3-7 所示。 爬行节点的工作流程如下： 1.通过 URL 传输模块接收来自控制中心的任务 URL 开始进行爬取工作。爬 行参数通过节点信息传输模块接收。 2.通过下载模块对起始 URL 进行链接下载，期间调用优雅爬行模块访问网 站 Robot.txt 协议。 3.对下载到的网页内容进行网页解析，将有用内容存储到网页内容数据库， 第三章 分布式网络爬虫系统架构设计 - 21 - 同时抽取超链接传递给任务定位模块。 4.经过任务定位后，属于自身爬行范围的添加到待爬队列继续爬行，不属 于的添加到非己任务队列，待非己任务达到一定量（如 URL 数目达到 50）发送 回控制中心。 5.开始爬行后将自身爬行状态信息发送回控制中心。 下面对各个功能模块具体分析如下： 1.爬行模块 爬行模块负责具体从一个种子 URL 地址开始对互联网进行网页爬取。主要 分为三个子模块，包含下载模块、网页解析模块、优雅爬行模块。 下载模块的任务是由上级模块提供 URL，根据提供的 URL 地址与该地址指 向的 Web 服务器建立会话连接，读取该 URL 地址所指向的网页数据流，以提供 网页解析模块进行进一步的分析。在进行网页下载时，根据本结点的计算机硬 件的运行情况，需要把并行开设的线程数控制在一个最佳的数量上，这样才能 保证 web 服务器不会出现类似于拒绝服务攻击(DOS)的反应而使得一些页面的漏 取。最基本的 DOS 攻击就是利用合理的服务请求来占用过多的服务资源，致使 服务超载，无法响应其它的请求16,17。Web 服务器的管理人员为了防止这种恶 意或者非故意，对服务器造成故障的行为做了一些防范措施，比如从同一个 IP 发出的 TCP/IP 请求必须小于一定的数目，否则视为攻击，所以本文的系统在和 web 服务器通信的时候必须避免这种情况的出现。 网页解析模块主要根据下载模块获取的网页文档数据流，根据 HTML 的语法， 从数据流中解析出不同的标签内容，根据标签的不同而做出不同的处理。主要 通过 MetaData 解析获取网页编码，Title 解析获取网页标题，Contents 解析获 取摘要，Links 解析获取超链接，将有用内容存储到数据库，并对超链接进行 处理进一步爬行。 优雅爬行模块的任务是遵循网站 robots.txt 协议，避免对同一个 Web 网站 服务器在短时间内过于频繁的访问，而增加服务器的访问负担。在爬行过程中 爬虫节点会对获取的 URL 地址的 Host 进行抽取分析，然后去缓存的映射表中查 询是否已经读取过该网站的 robots.txt 文件。