论文：分布式网络爬虫的设计与实现应用

本 科 毕 业 论 文院 系 专 业 题 目 分布式网络爬虫的设计与实现应用 年 级 学 号 学生姓名 指导老师 职 称 论文提交日期 20xx年x月x日 Xx 大 学本科生毕业论文（设计、作品）指导情况记录开题简况题目：分布式网络爬虫的设计与实现应用1、选题质量（简述选题与专业培养目标、专业要求关系、题目难度、工作量、创新性、理论性、实用性） 分布式网络爬虫的设计与实现应用在对分布式网络爬虫进行了一定的研究的基础上，结合实际背景，分析与设计爬虫运行策略，并通过实验证明其系统的高效性和可扩展性。本选题从理论出发，充分积累网络爬虫设计经验，将理论运用于实践，在系统设计与实现的过程中，加深了对理论的认识。具体而言，本选题在理论的指导下从整体结构、逻辑设计、通信设计等角度深入探讨，对选取的算法进行介绍与解释，在系统实现的过程中，又丰富了数据结构设计、线程控制、数据库连接等多方面的知识，锻炼系统编程的能力，让学生熟悉和掌握系统设计与实现应用的一般流程和分布式网络爬虫的具体实现方法，培养了学生分析问题、系统设计、技术应用等多种能力，并让其有了一定的项目意识和实践经验。本选题难度和工作量适中，适合本科生的知识结构和能力水平，创新性在于分布式网络爬虫控制策略的研究与选择，理论性在于对爬虫爬行原理的研究，实用性在于可以为苏州贷后风险平台及其他项目提供高效有用的信息采集结果。2、开题意见：本选题实用性较高，难度和工作量适中，具有一定的创新性，适合本科生开展研究，能很好地培养本科生的科学研究思维和项目组织与实现的能力。 指导教师签名： 年 月 日中期检查指导教师检查论文的进展情况：（指导和培养学生查阅文献资料、综合运用知识、研究方案设计、研究方法和手段运用和外文应用等能力简况） 该学生的论文严格按照开题时制定的论文计划进行，很好地完成了预定目标，在了解项目背景知识的基础上，目前已经完成对系统架构的设计，并开始进行分布式网络爬虫的代码编写工作。在项目已完成内容的基础上，进行了绪论、相关技术基础和爬虫逻辑设计部分的论文撰写，论文结构紧凑，文字通顺流畅，具有较强的逻辑性。指导教师签名： 年 月 日 - 1 -xx 大 学本科生毕业论文（设计、作品）指导教师评阅意见指导教师评语： 指导教师签名： 年 月 日- 2 -Xx 大 学本科生毕业论文（设计、作品）评阅教师评阅意见评阅教师评语： 评阅教师签名： 年 月 日- 3 -xx 大 学本科生毕业论文（设计、作品）答辩记录、成绩评定答辩记录：1、项目工作中的难点所在。 难点在于选定项目题目之前，对项目所研究的分布式网络爬虫了解并不多。因此，在选定题目后，以Nutch搜索引擎为例，对搜索引擎及其中的爬虫进行了深入的研究，了解和分析爬虫运行过程，通过对比认真选择和设计该系统中需要使用到的算法及策略，最终在编码实现各项功能的时候，控制节点和爬虫节点不同的多线程的管理也给项目带来了难度。 2、与Nutch相比，开发系统的意义是什么？ Nutch是优秀的开源搜索引擎，可以对海量的URL进行爬行与管理，但是其中的爬虫是为搜索引擎而专门设计的，不适用于精准数据爬取，因此，Nutch运行的过程中，会浪费很多的时间在不必要的计算上，即使对Nutch进行二次开发，也会破坏Nutch的框架，失去原本的优势。而且Nutch依赖Hadoop运行，Hadoop本身会消耗很多的时间，如果集群机器数量较少，爬取速度反而不如单机爬虫快。 本文所研究的分布式网络爬虫从实际项目背景出发，在保证爬行效率的基础上，强化系统可扩展性，使其能够适应多种类型数据。答辩记录人签名：答辩小组评语：答辩小组成员：_成绩_ 组长签名： 答辩时间： 年 月 日- 4 -Xx大学本科生毕业论文（设计、作品）中文摘要题目： 分布式网络爬虫的设计与实现应用 院系 专业 级本科生姓名： 指导教师（姓名、职称）： 摘要：随着互联网网络规模和用户数量的爆炸性增长，相关的服务和信息量也随之快速增长，单纯依赖计算机单机处理能力的集中式网络爬虫信息采集的速度已经无法满足快速获取大量数据的需求。分布式网络爬虫由可并行获取资源的多个节点爬虫组成，具有良好的可扩展性,它们在数据检索方面的优秀表现受到人们的欢迎。因此，本文将根据风险平台的需求，设计出一个高效的分布式网络爬虫。本文在对当前流行的分布式网络爬虫的相关技术进行了一定研究的基础上，根据需求分析将其应用于系统设计中，结合代码介绍爬虫的设计细节，通过对比实验体现分布式爬虫的优势，对全文进行总结，并提出展望。本文所研究设计的分布式网络爬虫系统，最大限度地利用了爬虫和网络带宽，不仅提高了计算机信息采集的速度，降低了系统损耗，而且加强了系统的可扩展性，能够适应更多类型的数据。关键词：分布式网络爬虫；Bloom过滤器；搜索引擎；Nutchxx大学本科生毕业论文（设计、作品）英文摘要THESIS：Design and Application of Distributed Web Crawler DEPARTMENT：Department of Computer Science and TechnologySPECIALIZATION: Computer Science and TechnologyUNDERGRADUATE: Qin YuMENTOR: Chongjun WangABSTRACT：With the scope and complexity of Internet growing explosively, related service and information is exploding as well. Information collection using centralized network crawlers cannot meet the need of accumulating large quantity of information in a short time. Distributed web crawlers are well scalable because they are made up of several crawler nodes which can get data synchronously. Their excellent performance on data retrieval is welcome. Therefore, it is worth studying the project by choosing a suitable algorithm and optimization technology accordingly. This paper is based on enough research on popular technologies related to distributed web crawlers. Then it analyzes design point ideas according to the demand and introduces design details of the crawler by codes. At last, the paper carries out an comparative experiment to reflect advantages of distributed crawlers and puts forward improvements.The distributed web crawler of this paper makes the most of the crawlers and the network. This system not only speeds up collecting information and decreases system loss, but also enhances the systems extensibility, which can deal with data of more types.KEY WORDS: Distributed Web Crawler; Bloom Filter; Search Engine; NutchVI目录第一章 绪论11.1 引言11.2 国内外研究现状11.3 主要研究内容41.4 论文组织结构4第二章 相关技术基础62.1 引言62.2 Nutch分布式搜索系统62.3 增量式爬取策略82.4 Bloom过滤器92.5 连接池与线程池112.6 本章小结12第三章 爬虫逻辑设计133.1 引言133.2 整体结构133.3 逻辑控制143.4 异常处理163.5 本章小结16第四章 系统实现174.1 引言174.2 数据结构174.3 报文设计194.4 报文传输204.5 本章小结21第五章 对比实验225.1 引言225.2 运行环境225.3 实验步骤225.4 运行结果225.5 实验小结25第六章 总结与展望266.1 本文工作总结266.2 未来工作展望26参考文献27致谢29第一章 绪论第一章 绪论1.1 引言近年来，互联网正处于越来越快的发展阶段，全面渗透于我们的日常生活和工作中，在诸多方面改变和改善我们的生活和工作形态。当前互联网已经成为影响我国经济社会发展、改变人们生活形态的关键行业，根据中国互联网络信息中心（CNNIC）在第35次中国互联网络发展现状统计报告中公布的数据指出：“截至2014年12月，我国网民规模大约6.49亿，全年共计新增网民3117万人。互联网普及率为47.9%，较2013年底提升了2.1个百分点”1。急剧膨胀的网民数量给搜索引擎的发展带来了极大的挑战。为了有效地解决这个问题，怎样从越来越大的数据资料源中以更快的速度、极高的效率、很高的安全性寻找到对网络使用者有价值的数据成为了搜索引擎的主要目标。在海量数据的现状下,想要解决网络搜索问题，单纯地依赖计算机单机处理能力是几乎完成不了的，即使是提升计算机硬件方面的功能，也不可能赶上信息增长的速度。经过研究者的潜心钻研，他们提出了分布式信息检索技术2。该技术一经发布，便得到了极大的关注，目前几乎所有的大型搜索系统都使用了分布式的体系构造，众所周知的Google和百度，它们的搜索引擎系统便是采用这一体系，利用分布式网络爬虫提高数据检索的效率。分布式搜索系统采用分布式信息检索技术，以分布式网络爬虫为基础，联结互联网中的多个机器，协调解决大规模数据的处理、索引和检索问题。其中，分布式搜索引擎的核心功能是由分布式网络爬虫实现的。本文研究内容依托苏州贷后风险平台，该项目通过采集互联网金融数据，对数据进行清洗、过滤和分析，为风险评估提供数据基础，其中，在采集数据时便需要分布式网络爬虫来提高搜索的效率。应用高效的分布式网络爬虫系统，可以准确而高效地采集互联网金融数据，减少搜索时间，为后续工作提供便利，提高贷后风险平台的整体效率。1.2 国内外研究现状网络爬虫，又称自动检索工具，是一种“自动化浏览网络”的程序，被互联网搜索引擎和某些类似网站用来获取或更新互联网中网站内容和检索方式。它们可以自动采集所有其能够访问到的页面内容，以供搜索引擎做进一步处理，而使得用户能更快的检索到他们需要的信息3。第一个实现网络爬行功能的网络爬虫World Wide Web Wanderer诞生于1993年，由麻省理工学院的学生Matthew Gray在MIT博士期间用Perl语言实现，本意是用来度量当时的互联网大小，并不是用来为搜索引擎服务的，也未公开发布。这是最早实现的爬虫，由于当时互联网的规模较小，需要检索的网页数量也较少，爬虫的实现比较简单。Repository-Based Software Engineering（RBSE）Crawler完成于1994年，是第一个公开发布的爬虫，由两部分组成，一部分是负责抓取网页的spider，将待爬网页队列中的内容放入一个数据库中，另一部分是文本浏览器mite，负责从网页上下载页面4。World-Wide Web Worm（WWWW）据称是第一个为万维网而设计的搜索引擎，由科罗拉多大学的Oliver McBryan于1993年实现，1994年正式发布，支持三十万多媒体对象的搜索，与如今的搜索引擎不同的是，WWWW支持Perl正则表达式搜索。早期爬虫在网络发展的过程中，早已无法适应爬行，人们开始认真思考这个问题。从1994年开始出现网络爬行器，也有几篇相关的论文，但是它们并没有介绍或解释是怎样解决海量网络信息的问题的。当时的网络爬行器大多被各大搜索引擎作为后台使用着，由于相互竞争的关系，这些网络爬行器的设计并没有公开，除了Google Crawler、Internet Archive Crawler以及Mercator5。这些爬虫都采用了分布式爬虫，分布式技术使得搜索引擎能够最快的搜索到大量网页。早期Google Crawler分布式爬虫采用主从式架构，主要由一个中心节点和三个负责网页爬行的设备构成，三台设备之间不直接相连，但分别与中心节点进行通讯6。中央主机负责从文件中将URL读取出来，并把URL发送给多个分设备的Crawler进程。Crawler进程会采用异步I/O的方式从三百多个互联网网站中获取搜索的数据，并将页面进行压缩存盘。之后再将URL从HTML页面中提取出来，并放置在页面存储以外的另一个磁盘文件中，Resolver进程会将存放在这一磁盘中的文件读取出来，将相对链接转变为绝对链接，继而提供给主机。这种做法确实可以提高爬行速度，但是缺陷也十分明显，若是中央主机出现故障，那么整个系统都会受到影响，并且系统存在瓶颈，即中央主机用于分发URL的模块。Internet Archive诞生于1997年，它采用了多线程以及异步I/O的技术，每个爬虫进程启动64个爬行站点同时爬行，每个爬行站点在爬行过程中维护一个爬行队列，并且采用异步I/O的方式读取URL，从网页中下载需要的信息。该爬行器为了提高爬行效率，将网页中的URL抽取出来的时候，若指向了同一个网站，就会将这个URL加入该站点的队列中，否则，就将其存放在磁盘中。此外，还有一个进程会周期性地去除重复链接，将不同的链接加入不同网站对应的队列中去7。康柏系统研究中心的Mercator是在1999年完成的。该系统是一个分布式、模块化地使用Java语言编写的网络爬虫系统，因为该爬虫系统具备高扩展性和强伸缩性，一经发布，就受到很多人的青睐。该系统除了使用多线程的技术，还同时加入了模块化的思想提高系统扩展性。它的模块化源自于使用可互换的“协议模块”和“处理模块”。协议模块负责怎样获取网页，处理模块负责怎样处理页面。标准处理模块仅仅包括了解析页面和抽取URL，其他处理模块可以用来检索文本页面或者搜集网络数据。此外，Mercator巧妙运用了LRU的缓存机制，优化存储空间，进一步提高了爬行的效率。随着互联网的进一步飞速发展，人们对分布式爬虫海量数据的计算能力的要求又达到了新的高度。在云计算的背景下，谷歌推出了一篇文章叫Web Search For A PlanetThe Google Cluster Architecture，在论文中较为详细地描述了云计算最基本的设施模型，该模型包括以下四个方面：一是分布式文件系统GFS，二是Map/Reduce代码编写框架，三是分布式锁机制，四是大的分布式数据库Big Table8。Nutch是一个基于Lucene的优秀开源搜索引擎，它提供了我们运行自己的搜索引擎所需的全部工具，具有很强的可扩展性9。Nutch在借鉴了GFS的经验后，结合Map/Reduce计算模型，推出了自己的分布式文件系统NDFS，并将该项目中分布式计算的框架独立出来，提出了Hadoop的设计框架，为海量数据的处理和计算带来了便利。如何利用框架实现更高性能的爬行系统也成为了目前分布式网络爬虫的主要发展方向。本文借鉴分布式网络爬虫发展的历史经验，在Nutch搜索引擎的框架启示下，采用Google Crawler的主从式结构，使用Java语言编写出一个分布式网络爬虫系统。该系统引入去重思想和模块化的思想，基本实现了信息采集模块的核心功能，能够稳定而高效地完成爬行任务。1.3 主要研究内容本文结合实际平台需求，基于分布式搜索引擎的框架，设计并实现了一个分布式网络爬虫。研究内容主要包括以下四个方面：（1）查阅当前流行的分布式模型的相关资料，积累分布式网络爬虫相关的开发经验和理论基础。（2）着重掌握分布式网络爬虫相关知识，根据苏州贷后风险平台的实际需要，分析爬虫设计要点，例如爬虫整体结构、逻辑运行方式、异常处理等。（3）细化设计要点，编码实现一个分布式网络爬虫系统，从数据结构、报文设计以及报文的解析三个方面简单介绍系统实现的细节，该系统完成基本功能，能够正常高效运行。（4）将本文实现的爬虫运用于模拟的分布式系统环境下，测试其爬行效率和系统的稳定性，并进行对比实验，分析实验效果，提出改进建议。1.4 论文组织结构第一章 引言，首先简单介绍了该课题的社会背景，分析其研究意义，论述选择该课题的原因。然后通过介绍国内外爬虫研究发展的过程，体现研究实现分布式爬虫的必要性。该部分还详细列举了该课题的主要研究内容以及本文的组织结构。第二章 相关技术基础，具体讲解了本文系统相关的理论技术。首先简单介绍了当前流行的Nutch分布式搜索系统，分析Nutch分布式爬虫值得借鉴的部分。接着，对增量式爬取策略进行一定的介绍和说明。然后，针对系统中使用到的Bloom过滤器进行详细介绍，结合实际背景，分析其必要性。同时，简单介绍系统中使用到的数据库连接池和线程池的概念。最后对技术基础进行总结。第三章 分布式网络爬虫逻辑设计要点，在开始系统编码前，需要根据单位提出的需求，分析本系统的实现方案，并对总体架构进行了设计。值得注意的设计要点有以下三个方面：整体结构、逻辑控制以及异常处理。对这三个方面进行具体的介绍后，最终对系统逻辑设计进行总结。第四章 系统实现。在第三章逻辑设计的指导下，在完成系统代码前仍需要对实现细节进行规定，这样系统代码才能够比较高效地完成。该部分对分布式网络爬虫实现过程中使用到的重要的数据结构进行了简单的介绍，然后，从报文的设计和解析的角度分析通信过程中的注意点，最后，在详细设计的辅助下，完成系统代码的编写，对本章进行小结。第四章 对比实验，部署本分布式网络爬虫，采用苏州贷后风险平台项目提供的数据，在不同运行组合下运行该系统，对比运行结果，展示和分析分布式网络爬虫的优势，对实验的过程及结果进行总结。第五章 总结与展望，结合研究的过程，对本文的编写过程以及本文所研究的分布式爬虫系统进行了具体的归纳和总结，分析研究过程中的优点及不足，最后总结本文系统研究的意义并提出展望。6第二章 相关技术基础第二章 相关技术基础2.1 引言本章针对系统实现过程中使用的优秀的思想和技术的原理进行了较为详细地介绍，为下文的系统设计说明作铺垫。本章的结构安排如下：第2节对Nutch分布式搜索系统进行了介绍，了解分布式网络爬虫在搜索引擎中的作用和位置，明确分布式网络爬虫需要实现的功能；第3节对增量式爬取策略进行了介绍，结合爬行节点的运行逻辑解释增量式爬取策略；第4节的Bloom过滤器解决了增量式爬取策略中的去重问题，应用于URL的增量过程中；第5节简单介绍了系统中运用的“池”的概念，从数据连接池和线程池两个方面进行了简单的介绍；第5节对本章进行了小结。2.2 Nutch分布式搜索系统如今的互联网犹如浩瀚的海洋，想在互联网中搜寻需要的信息，就如大海捞针，没有一定的工具几乎是无法实现的。因此网络搜索是互联网发展中一项必不可少的功能，然而,现有Web搜索引擎的数目不增反降，其中缘由则是某些公司为了谋取商业利益而垄断Web搜索市场，这对于互联网的长远发展和互联网用户的利益是极其不利的。作为开放源代码的搜索引擎,Nutch的目标是让每个开发者能很容易,同时花费很少的费用就可以配置世界一流的Web搜索引擎,尽自己最大的努力为用户提供最好的搜索结果10。Nutch是Apache的一个开源搜索引擎项目，于2002年8月发布，而如今的Nutch也已经从搜索引擎渐渐演化为了网络爬虫。为了能够完成最初的开发目标，Nutch必须能够做到每个月抓取几十亿的网页，并为这些网页维护一个索引，而对这些索引文件能够执行每秒上千次的搜索，以最小的成本，提供高质量的搜索结果11。Nutch作为一个开源的搜索引擎，具有很强的可扩展性，研究工作者可以在Nutch的基础上，根据自己的研究需要，设计开发自己的搜索引擎，把搜索结果以自己想要的方式呈现出来，因此，Nutch需要具备低耦合度和高可扩展性。Nutch模块化的设计为用户提供了很多的便利。Nutch搜索引擎具体可以分为三个主要的模块：采集模块，索引模块和搜索模块。采集模块即是Nutch搜索引擎的爬虫模块，是本文所研究的分布式网络爬虫所处的模块。采集模块的主要任务是通过初始URL，不断抓取获得新的URL，并对这些信息进行相关的处理。CrawlDB还会生成一个待抓取的网页URL集合Fetchlist，而Fetcher进程则会对抓取到的网页中相关的信息进行下载。Fetchlist不断更新，则会下载到更多的网页，而从更多的网页中又会抓取到更多新的网页URL加入Fetchlist，这样构成了一个循环过程，其“产生/抓取/更新”的循环步骤一直进行下去12。Nutch将网页中的相关链接抓取下来后，为了提高搜索效率，可以提前建立索引，索引模块完成的就是这样的工作。Nutch中的索引采用倒排索引，此索引是建立在Lucene框架之上，因此采用倒排索引可以提供更为高效的搜索服务。查询模块则是为用户提供查询界面的，用户在该界面键入搜索请求，当它到达搜索引擎的服务器时，查询模块就会通过索引模块中索引库的程序来进行处理，检索完成之后，根据一定的排序算法，生成搜索结果，将其在Web页面中呈现给使用的用户。Hadoop最开始是作为Apache Nutch的一个网络搜索引擎的一个基础设施，是一个稳定的且具有较好扩展性的架构。其主要设计思路和谷歌的Map/Reduce以及分布式文件系统一样13。其中的分布式文件系统HDFS不仅仅用于Nutch中的存储，同时也是大型搜索系统中的应用框架，基于Hadoop分布式搜索引擎系统的整体层次结构如图2-1所示14。图2-1 基于Hadoop分布式搜索引擎系统的整体层次结构Nutch是优秀的开源搜索引擎，可以对海量的URL进行爬行与管理，但是其中的爬虫是为搜索引擎而专门设计的，不适用于精准数据爬取，因此，Nutch运行的过程中，会浪费很多的时间在不必要的计算上，即使对Nutch进行二次开发，也会破坏Nutch的框架，失去原本的优势。而且Nutch依赖Hadoop运行，Hadoop本身也会消耗很多的时间，如果集群机器数量较少，爬取速度反而不如单机爬虫快。本文所研究的分布式网络爬虫从实际项目背景出发，在保证爬行效率的基础上，还强化系统可扩展性，使其能够适应多种类型数据。在对Nutch搜索引擎的结构有了一定的研究后，本文所研究的分布式网络爬虫的主要工作变得更加明晰。结合Nutch的模块分配，分布式爬虫在解析初始URL集合的基础上，不断深入爬取网页中的链接，下载网页信息，并对相关的信息进行处理和保存。建立索引、提供查询等功能会在后面的模块中完成，爬虫部分不需涉及。2.3 增量式爬取策略在对Nutch分布式搜索引擎有所了解后，我们明确了分布式网络爬虫的主要功能，从这一部分开始将深入介绍一下分布式网络爬虫中所使用的关键技术，首先从增量式爬取方式开始说明。在互联网中，爬虫主要功能就是将需要的网页数据从网页上下载下来，并将数据信息提供给搜索引擎，便于搜索引擎的搜索。通常，我们所说的网页数据不仅包含了大量的文字及图片数据，还包括很多网页链接。网络爬虫就是利用这些链接来爬取更多的网页，从更多的网页中获取更多的链接，这一数据采集的过程就和爬虫或蜘蛛在网上爬行一样，所以我们将其称为网络爬虫。我们在使用网络爬虫爬取网页时，一般都会选择链接数比较多的网站作为种子URL，在网络爬虫系统中被称为初始URL，通过初始URL集合开始在互联网中进行爬行。初始URL中的链接数越多，就可以爬取到越多新的网页链接。网络爬虫一般会根据一定遍历算法遍历网页，通常包括广度优先算法和深度优先算法。如果使用深度优先搜索算法，不断地深入搜索，在网络结构复杂的情况下，就很可能导致爬虫陷入网站的内部，无法获取其他网站的信息，所以更多的时候会使用广度优先搜索算法。网络爬虫的工作策略一般可以分为累积式抓取和增量式抓取两种。累积式抓取是指从某一个时间点开始，通过遍历的方式抓取系统所能允许存储和处理的所有网页。在理想的软硬件环境下，经过足够的运行时间，累积式抓取的策略可以保证抓取到相当规模的网页集合。但由于Web数据的动态特性，集合中网页的被抓取时间点是不同的，页面被更新的情况也不同，因此累积式抓取到的网页集合事实上并无法与真实环境中的网络数据保持一致。增量式抓取是指在具有一定量规模的网络页面集合的基础上，采用更新数据的方式选取已有集合中的过时网页进行抓取，以保证所抓取到的数据与真实网络数据足够接近。进行增量式抓取的前提是，系统已经抓去了足够数量的网络页面，并具有这些页面被抓取的时间信息。本文所研究的分布式网络爬虫采用增量式爬取的方式，网络爬虫在爬行网页的过程中，先把初始URL推送至下载队列首部，然后依次出队列，下载链接对应网页信息，获取的新链接，判断该链接是否已经爬取或过时，如果已爬取且不过时，则不再爬取，若未爬取过或已过时，则推进下载队列中，如此循环，直到下载队列为空。2.4 Bloom过滤器在互联网的日常应用中，我们可以发现，想要进入某一网页，可以从众多不同的网站上点击链接，该网页的链接会多次出现在不同网页中。当我们用爬虫爬取网页时，必定也会爬取到很多相同的网页链接，如果对这些网页都进行下载并继续爬取，又会产生更多相同的网页链接，这样得到的爬虫会受到巨大的影响，效率大大降低。因此，我们需要想办法把这些重复的网页URL去除。针对数据量比较小的情况，我们可以将访问过的URL保存到数据库中，每爬取一个新的URL，就与数据库中URL进行对比，丢弃重复的URL。也可以使用HashSet将访问过的URL保存起来，同样对比去重。但是随着URL的增多，占用的内存会越来越多。为了解决内存的问题，我们可以使用Bit-Map方法，将每一个链接地址通过一个哈希函数映射到BitSet中的某一位，这样内存的压力是相对较少了，但是只是使用单一的哈希函数发生冲突的概率还是太高了，若想要把冲突发生的概率降低到1%，就要将BitSet的长度设置为链接地址个数的100倍，这样就又得不偿失了。因此，为了解决上面的问题，本文的分布式网络爬虫需要对URL进行去重。在新的URL加入爬行等待序列前，需要将其与已爬行的URL进行对比。本文采用一种较为高效的过滤器Bloom过滤器，在URL的增量过程中，对URL进行去重。Bloom过滤器于1970年提出，是一种应用于快速判断某个元素是否输入集合的快速查找算法。这种算法采用了多哈希函数映射的方式，运算结果适用于不完全精确的场合15。Bloom过滤器在BitSet的基础上进行了改进，为了降低冲突的概率，使用了多个哈希函数。在应用过滤器前，我们需要设置一个m位的BitSet，每一位都初始化为0，然后选择k个不同的哈希函数，用第i个哈希函数对字符串str进行映射，其结果记为h(i,str)。当我们爬取到一个新的URL时，将该URL的信息包装成一个字符串的形式，将该字符串加入到BitSet中。对于字符串str，分别计算h(1,str)，h(2,str)，.，h(k,str)位设为1。如图2-2所示：图2-2 Bloom Filter加入字符串过程如图2-2所示，字符串str就成功地映射为BitSet的k个二进制位了，大大降低了内存的压力。字符串能够被成功加入后，若有新的字符串出现时，我们就需要对这个字符串进行检验，是否与之前的字符串重复，是否应该加入待爬URL列表。对于新的字符串newstr，我们需要将newstr代入MD5哈希算法中，分别计算h(1,newstr),h(2,newstr),.,h(k,newstr),然后检查BitSet的第h(1,newstr),h(2,newstr),.,h(k,newstr)位是否为1，若其中任何一位不为1，则说明这个新的字符串一定没有被记录过，若全部位都是1，则可以暂且认为字符串存在。不过，我们也不能说这个字符串一定存在，因为有时也会出现该字符串的所有位刚好都被其他字符串映射过的现象，这种现象也被称为false positive。加入过滤器的字符串最好就不要再删除了，无论哪一个字符串被删除都有可能对结果带来影响。如果确实需要删除字符串时，可以使用Counting Bloom Filter（CBF），这是一种基本Bloom Filter的变体，它将位改成一个计数器，通过计数器的加减实现字符串的删除。过滤器的性能很大程度上取决于其中的哈希算法的选择，一个优秀的哈希函数要能近似等概率的将链接地址映射到各个位。本文在使用Bloom过滤器时，选择MD5哈希函数，然后选择k个不同的参数，从而针对每个字符串可以计算出k个哈希结果，映射BitSet。根据本文需求，k值设置为8，BitSet设为URL总数n的20倍，false positive的值降低为0.00014，基本符合本项目分布式网络爬虫的需要了。2.5 连接池与线程池本分布式网络爬虫由一个中央爬虫和多个节点爬虫组成，每个节点爬虫中又使用多线程的方式，同时开启5个线程对网络数据进行爬取。这么多的线程同时抓取网络中的数据，得到的数据必然是庞大的，如果要将这些数据全都加入数据库，对数据库会产生极大的压力。因此，研究者提出了“池”的概念，具体的解决方案是当多个应用程序向数据库提出请求时，为这些应用程序同时建立足够多个数据库连接，并且让这些连接形成一个连接池，这样应用程序就可以对连接池中的连接进行动态的申请、使用和释放。当应用并发请求数多于连接池中连接数时，应用程序应该排队等待16。本文所使用的数据库是MySQL，采用JDBC数据库连接池，通过Connection函数从连接池中获取connection，对数据库的进行操作，不需要使用时，用close函数将connection放回数据库连接池，当connection不足时，数据库连接池也会自动增加connection个数。获取数据库连接的代码如图2-3所示：图2-3 获取数据库连接同样，由于多线程的形式，在爬虫节点采用线程池的方式管理线程。线程池的作用就是限制系统中执行线程的数量，当有一个新的任务需要完成时，若此时线程池处于空闲状态，则调用线程池中等待的线程开始运行；若线程池处于部分运作的状态，则完成队列中的第一个任务；若线程池处于满负荷的状态，该任务就先进入等待队列。这样，不仅可以最大限度的重复利用工作线程，还可以防止占用过多的内存，造成服务器过高负载而停机。2.6 本章小结这一章节主要介绍了本文系统相关的技术背景，通过对系统中需要运用到的技术及背景进行了比较详细的介绍，借鉴当前优秀的爬虫系统Nutch的设计经验，为之后的系统设计与实现打下了良好的基础。本章介绍的内容包括Nutch分布式搜索系统的基本知识、增量式爬取策略、Bloom过滤器、数据库连接池及线程池的相关知识，从多个角度由浅入深地介绍了分布式网络爬虫的背景及原理，为下文的系统框架的搭建提供了很好的经验，为整个项目的研究打下了良好的理论基础。36第三章 爬虫逻辑设计第三章 爬虫逻辑设计3.1 引言本章对分布式网络爬虫的设计展开研究，在实现系统前，对系统的整体框架及其中的逻辑控制进行详细的设计，意义在于搭建较为合理的爬行框架，从整体上提高爬虫的效率，也为后文的系统详细设计做好铺垫。本章的结构安排如下：第2节阐述了本系统采用主从式爬行结构和基于TCP/IP的Socket通信的原因；第3节从中心节点和爬行节点两种节点的角度分别设计逻辑运行策略，阐述运行过程并解释设计缘由；第4节介绍了系统在不同状况下发生异常时的处理方式；第5节对本章进行了小结。3.2 整体结构分布式网络爬虫主要分为两种系统架构，一个是主从式，整个系统中包含两种类型的节点，分别为中心节点和爬行节点。中心节点主要负责对爬行节点的管理和对爬行任务调度,爬行节点则负责抓取网络信息，为中心节点提供新的URL；另一种是并列式，在这个系统中，所有的节点功能相似，不仅要爬取网络信息，获取新的链接，而且每个节点都维护着一个其他节点地址的列表,当爬取到任务时，要通过这个列表中将爬行任务分配给其他合适的爬行节点17。本文分布式网络爬虫运行的网络环境使用校园网络，网速并不是特别理想，因此网络带宽是极其重要的资源，直接影响到爬虫系统的运行效率,并列式网络爬虫需要维护其他节点地址的列表，当节点产生或断开时，将会产生大量的系统损耗，降低了网络带宽的利用率，但是主从式网络爬虫系统与之不同，它的任务分配集中在中心节点上，中心节点可以随时根据爬行节点的爬行情况进行爬行任务的分配，避免了并列式网络爬虫各个爬行节点之间的任务不均现象。因此，本文选择使用主从式系统架构进行总体设计，其结构如图3-1所示：图3-1主从式结构本文使用Java语言编写，通过Socket通信方式进行中央节点与爬虫节点的联系。另外，TCP协议是一种面向连接的可靠传输协议，UDP是面向非连接的，考虑到本系统对信息传输的要求，本文选择基于TCP/IP的Socket通信建立可靠的传输链接18。在本文中，中央节点即Socket通信中的服务器端的角色，爬行节点即Socket通信中的客户端的角色，由于一个中央节点对应多个爬行节点，因此我们还要使用多线程的机制，中心节点通过多线程控制多个爬行节点，爬行节点通过多线程控制多个爬虫并行爬取网络。3.3 逻辑控制中心节点的线程主要负责管理爬虫节点，可以随时查询爬虫的状态，确认爬虫完成的任务以及管理爬行出错的URL。因此，对于中心节点来说，主要分为三个线程控制任务：（1）反馈确认当爬虫节点完成中心节点安排的URL任务，返回完成结果时，如果中心节点只是将URL列表中完成的部分删除，而不返回爬虫节点任何信息时，爬虫节点就无法确定中心节点是否已经收到确定。假如爬虫节点返回完成结果时，传输出现错误，中心节点并没有收到确认，而爬虫节点已经将该部分URL删除，那么超出一定时间后，中心节点就会误以为这部分URL没有完成爬取任务，加入出错URL的队列，浪费资源，降低爬取效率。因此，中心节点在收到爬虫节点发过来的完成任务的URL信息时，需要对完成的内容进行确认，不仅要从中心节点的待确认URL列表中将该部分URL出队，而且要返回给爬虫节点一个确认信息，供爬虫节点操作。（2）轮询检测在爬虫运行过程中，爬虫节点可能因为多种原因发生异常，与中心节点断开连接，因此，中心节点需要随时了解爬虫节点的运行状态，通过遍历的方式，询问各个爬虫节点的状况，当检测到某个爬虫节点出现故障时，应停止对其发送任务，完善后续任务。（3）URL丢弃首先将ErrorURL在所有没有被爬取过的爬虫节点上进行爬取，如果都没有爬取到结果，就说明是这个URL有问题，应将其丢弃。在这个过程中，我们也要注意线程的控制，不能为了爬取出错URL而影响正常URL的爬取，因此，应设置线程等待，控制处理出错URL的速度。与中心节点不同，对于爬虫节点来说，它的任务主要是完成爬行任务，并将爬行结果反馈给中心节点。本文所研究爬虫系统采用增量式爬取策略，爬虫节点运行逻辑如图3-2所示：图3-2 增量式爬取策略运行逻辑由图3-2可以看出，该分布式网络爬虫并不是对于所有爬取到的URL都进行深入爬行，只要该URL在最近一段时间内被爬取过，就不必再次进行爬行，这样的做法可以有效避免爬行资源的浪费。其中，在判断新URL是否已爬取时，我们采用第二章中介绍的Bloom过滤器，将各个URL映射为多维空间中的一个点，若点重合，则可认为该URL已爬取，进入下一个判断流程。3.4 异常处理该分布式爬虫系统采用主从式架构，将节点分为控制节点和爬虫节点，因此在考虑异常处理时也要分别针对控制节点和爬虫节点进行崩溃处理。（1）控制节点控制节点位于系统的中心，因此控制节点的崩溃处理十分重要。如果无法正确处理控制节点崩溃的状况，有可能导致之前所取得的结果全都白费，甚至整个系统停顿，无法继续支持。当面临控制节点发生异常时，我们需要做好日志恢复的工作。这里所说的日志恢复，不仅包括控制节点的日志恢复，还包括爬虫节点的日志恢复。当系统重新恢复正常时，存储的日志需要能够提供已爬取和未爬取URL的信息。（2）爬虫节点爬虫节点的崩溃有两种可能的原因：一是控制节点的崩溃或整个系统的崩溃，还有一个是该爬虫的崩溃。当控制节点或整个系统崩溃时，爬虫节点应该将未爬取的URL在本地完整保存；当只是该爬虫发生崩溃时，为了保证爬行结果的完整性，爬虫节点应该将未爬取的URL回送给控制节点，由控制节点分配给其他正常的爬虫对这些URL继续进行爬取。3.5 本章小结本章根据研究的需求分析分布式爬虫的逻辑设计要点。首先，从整体结构上简单介绍了该分布式爬虫，选择了主从式的架构进行研究，采取基于TCP/IP的Socket通信建立可靠的通信连接。然后，根据分布式网络爬虫的功能，分别介绍了中心节点和爬行节点在逻辑上的运行方式。接着，具体地介绍了在不同情况下系统出现异常时的处理方式。最后，对本章进行了小结。总的来说，本章对分布式网络爬虫的逻辑设计进行了详细的分析，选择合适的运行方式，从整体上提高了爬虫的效率，对实验的详细设计也带来了极大的便利，为本文的完成奠定了坚实的基础，是系统高效实现的前提。第四章 系统实现第四章 系统实现4.1 引言本章在第三章逻辑设计的基础上，对系统进行了更为详细的设计，从系统实现的角度对系统的细节进行介绍，在系统代码编写前，统一变量、对象，有助于模块化地实现分布式网络爬虫系统。本章的结构安排如下：第2节介绍了与本系统相关性最高的四种URL对象，从数据结构的角度，分析和解释URL的在系统运行时的流动过程；第3节对通信过程中使用的报文进行了简单的介绍，分析各个域的设计意义；第4节以爬虫节点向中心节点发送爬取到的URL的任务时的报文解析过程为例解释了报文的传输过程；第5节对本章进行了小结。4.2 数据结构根据项目需要，本项目共涉及四种URL相关的对象，分别为RawData，InterfaceURL，PackagedURL和ErrorURL。下面依次对这四类对象进行讲解：（1）RawData这个对象是在最终网页页面上抓取到URL时创建的，主要属性如表4-1：表4-1 RawData属性表其中，id是key值，唯一确定RawData，listId为取到该链接的网页编号，siteName为取到该链接的网站的地址，url即为链接地址，title和hrefText主要记录该链接的标题内容，inputTime为抓取到该URL的时间。（2）InterfaceURLInterfaceURL是原始URL的抽象类，根据URL类型的不同，又分为两种不同的URL形式，分别命名为URL1_Impl和URL2_Impl。URL1_Impl为第一种类别的原始URL，是三级爬取中的第一级，其主要属性如表4-2：表4-2 URL1_Impl属性表其中大部分跟RawData的相同的属性不再赘述，channel可以记录代理或网关的服务器相关信息，由于某些网页可以翻页，因此pageUrl此处也需要记录，URL2_Impl是第二种类别的原始URL，是三级爬取的第二级，其主要如表4-3所示：表4-3 URL2_Impl属性表（3）PackagedURL上面介绍了两种基本的URL类型，接下来的两种类型都是在前两种的基础上形成的。PackagedURL在原始URLInterfaceURL上包装了一些信息，更方便程序快速解析，是在该系