基于P2P分布式的网络爬虫设计.docx
《基于P2P分布式的网络爬虫设计.docx》由会员分享，可在线阅读，更多相关《基于P2P分布式的网络爬虫设计.docx（15页珍藏版）》请在冰点文库上搜索。
基于P2P分布式的网络爬虫设计
基于P2P分布式的网络爬虫设计
基于P2P分布式的网络爬虫设计
摘要：
未解决传统网络爬虫的在扩展性、容错性和低效性，提出一种基于P2P的分布式网络爬虫。
分布式网络爬虫通过爬虫协调节点提高网络爬虫的爬取数据的效率和扩展性。
本文首先介绍了传统的网络爬虫的原理，在此原理的基础上对其进行了改进，分析了分布式网络爬虫的结构设计，均衡负载策略和通信策略，从而提高网络爬虫的容错性。
关键字网络爬虫P2P分布式负载策略通信策略
1.引言
Web资源是当今社会中获取资源重要途径之一，随着信息爆炸性增长，人们对信息资源的需求也越来越大，如何使用网络爬虫技术高效的爬取Web中的数据成为了一个严峻的问题？
由于传统的网络爬虫的扩展性和容错性比较差，因此在很多方面已经无法胜任高效爬取的任务。
由于Web信息具有分布式的特性，因此将网络爬虫采取分布式的方式进行设计可以大大提高爬取数据的效率。
分布式的网络爬虫可以借助普通PC用户提供的空闲资源来获取网络，可以降低爬取数据的成本，减少对网络造成的负担。
设计一个分布式的网络爬虫首要了解传统的网络爬虫爬取数据的原理，在其基础上进行改进和优化。
本文详细介绍了分布式系统中常见的几种结构，并以P2P结构为例，说明了如何对资源的分配策略已达到每个节点的公平性，同时介绍了节点间的通信协议如何保证分布式网络爬虫的良好容错性和扩展性。
2.传统网络爬虫
2.1工作原理
网络爬虫是一个Web程序，按照某种规则自动爬取万
维网中的Web页面，将爬取到的网页中的关键字存入关键字数据库中，用户通过搜索引擎或许相关信息的页面。
传统的网络爬虫由带爬取的URL库、未爬取的URL库、爬虫主题线程模块和内容提取模块组成。
其工作原理
如图1，网络爬虫从一个或若干个初始网页的URl开始，通过爬虫主题线程模块从万维网中获得初始网页上的URL和网页信息，将新获取的URL存放在待爬取的URL队列中，将获取到的网页信息传给内容提取模块，内容提取模块将访问过的URL存入已爬行URL库中，将网页信息存入页面信息库中，直到满足一定停止条件。
通过一定的网页过滤算法过滤掉与主题无关URL，遵循一定的调度策略从带爬取队列中选择下一次要抓取的URL。
图1：
传统网络爬虫原理
2.2网页抓取策略
网页抓取策略可以分为三类抓取策略，分别是深度优先，广度优先和最佳优先，深度优先策略容易使网络爬虫陷入问题，因此较为常用的是广度优先和最佳优先策略
。
1.深度优先
深度优先从初始的URL页面开始，通过一定的规则从初始URL库中选择一个URL，分析这个网页中的其他URL，选择一个再进入。
如此一个链接一个链接地抓取下去，直到处理完一条线路为止然后再处理下一个URL。
深度优先策略设计比较简单，但是一个门户网站中提供的连接的重要性随着层次的深入逐级降低，从而使过度深入抓取的网页的价值过低，因此深度优先策略直接影响了抓取效率与抓取命中率。
2.广度优先
广度优先是先对初始的所有URL网页进行抓取，然后通过网页过滤策略选取其中一个链接的网页，继续抓取这个网页中的所有URL链接网页，这样逐层进行抓取。
由于初始URL在一定链接距离内的网页是具有主题相关性的概率很大，但是随着抓取网页的增多，大量的无关网页将被下载并过滤，算法的效率将变低。
3.最佳优先策略
根据机器学习的一些算法提供一种网页分析算法，对初始的URL进行与要获取主题的相关性评估，选取评估最好的一个或几个URL进行抓取。
它只访问进过网页分析算法预测为“有用”的网页。
这种算法的优点在于可以提高网页的爬取效率，但是却容易忽略被过滤到的URL网页路径中与主
可扩展性：
因为分布式的网络爬虫是由多个节点组成，由一个中心管理节点进行管理，因此当有新的节点加入后，可以不影响整个系统的工作，从而增强系统的工作效率
1.高效率：
相比较集中式的系统，分布式系统由于多节点协调工作，使其工作效率要远远高于集中式的系统。
同时，作为分布式系统有其固有的缺陷，其中最重要的是其通信问题，由于分布式系统的每个节点都处于网络当中，网络中可能出现数据丢失的可能，需要特出的软件处理，其次，分布式系统的网络数据共享会导致安全性问题。
3.3工作原理
分布式网络爬虫单个节点的工作原理与传统的网络爬虫的工作原理相似，多个节点之间通过协作完成对网页的爬取，从而使得分布式网络爬虫的效率远远高于传统的网络爬虫。
对于典型的分布式网络爬虫，每个节点不仅要从自身的未访问URL库和Web页面中获取URL还要从其他节点接受URL。
在分布式网络爬虫系统中
节点从未访问URL库中获取URL从万维网中下载对应的网页，从网页中获取出新的URL，通过Hash函数计算出Hash值，将属于本节点的URL插入未访问URL库队列中，将不属于本节点的URL发送到其属于的节点中。
分布式网络爬虫系统节点间协作的工作原理如图二。
图2：
节点间协作的工作原理
4.分布式网络爬虫设计
4.1体系结构
该网络采用全分布式非结构化的拓扑结构也就是P2P结构，节点间是对等关系，每个节点既是客户端又是服务器，这种结构
的优点在于整体稳定性较好，系统中某个节点发生故障不会对系统性能产生大的影响，因此容错性较好。
但是一旦网络规模变大，节点间的通信的效率较低。
基于P2P的分布式网络爬虫结构如图3，分布式系统由多个节点组成，每个节点都自己唯一的ID号，所有节点当中有一个控制节点，用于为每个节点分配ID号，对系统进行动态监控管理等，剩余的节点都为爬虫节点，爬虫节点中有一个特殊的中心协调节点，负责协调节点间的通信，一旦中心节点退出或者崩溃，其他节点就会选取剩余节点中ID号最大的为中心节点。
图3：
P2P分布式爬虫结构图
4.2爬行节点结构设计
分布式爬行节点可以划分为
如图4的四个部分：
网络爬虫模块、节点信息维护模块、任务分配模块、节点通信模块，其中节点信息维护模块、任务分配模块、节点通信模块实现了网络爬虫的分布式处理，因此统称为分布式模块。
分布式模块
图4：
爬行节点结构
1.网络爬虫模块
网络爬虫模块有DNS解析器模块、下载模块和进程控制模块组成，是网络爬虫节点的核心部分，它直接与Web服务器进行通信。
通过向线程控制模块发送URL进行Web页面的下载，由于本文中的重点在于分布式模块，该模块不是讨论的重点。
2.节点通信模块
节点通信模块由系统节点表，节点参数和日志记录组成，其中系统节点表中记录了所有爬虫节点的信息，包含了所有节点的ID号，IP地址，端口号，是否为中心节点，为保证分布式环境中的视图一致性，每个节点的系统节点表信息必须相同，当系统中有节点进入、退出或者崩溃时需要更新每个节点中的系统节点表，当中心节点崩溃或者退出时，所有节点可以通过系统节点表达成共识按照一定的选举规则选举新的中心节点表
节点参数负责维护和改变节点运行的参数，当控制节点发出控制命令，由通信模块将控制命令发到该部分对节点当前的运行参数进行修改。
日志记录，负责维护日志，使管理中心节点可以监控爬虫节点的运行速度、爬行深度等参数。
3.任务分配模块
分布式网络爬虫在工作时由于是所有节点协同工作，因此很容易出现访问到重复的URL页面
，同时将庞大的爬行任务分配给爬虫系统需要保证每个节点的负载平衡。
任务分配模块的作用就是保证这些问题的解决而设计的，具体的分配算法在后面的内容中具体说明。
4.节点通信模块
节点间的通信包括URL的传输和接受以及消息的传递，因此节点通信模块包括消息通信子模块和URL传输子模块。
4.3控制节点的设计
控制节点在爬行系统中不参与爬行过程，负责对整个系统管理监控作用，该节点主要实现以下功能
1.添加删除节点：
动态的添加删除节点使得系统具有良好的可扩展性
2.监控运行节点：
可以监控分布式系统中任何几点的运行状态，包括运行时间、下载网页数量等。
3.动态调整爬虫节点的运行参数：
通过动态调整爬虫节点的运行参数使得爬虫节点具有更好的可管理性和可配置性，运行参数包括爬行速度、爬行深度、爬虫线程数等。
4.4分配策略
由于广域网的网络爬虫设计以及实现比较复杂，因此本文设计的网络爬虫建立在局域网上的爬虫系统。
局域网的网络爬虫是指所有的爬虫节点都分布在同一个局域网中，节点间的通讯是依靠高速内连接进行。
为避免在搜索网页出现重复爬虫并且使每个节点的负载平衡，必须要选择合理的分配策略，常见的分配策略有以下三种
：
1.集中方式：
将初始URL对应的Web页面按照一定规则划分任务子集，将特定的任务子集通过中心节点划分给其对应的节点。
在采集过程中如果有节点发现采集信息不属于自己的范围，将信息反馈给中心节点，有中心节点重新分配给其对应的节点。
集中方式是通过中心节点完成合理分配的任务。
这种方式往往需要向中心节点转发较多的URL，容易造成性能瓶颈。
2.独立方式：
每个节点都从自己初始的URL开始采集信息，节点间没有通信。
这种方式容易实现，但是会出现冗余的信息采集，不能达到节点的协作爬取任务，效率较低。
3.动态哈希方式：
将URL按哈希函数划分，分配给各个节点。
对于这种分配方式，存在一种跨区链接（指一个采集节点在提取连接时发现不属于自己节点的链接）。
这就出现了一个难题，就是这种跨区链接不一定被它所属于的节点所发现，如果本爬行节点采集可能会出现重复采取，如果不采集则可能出现漏采。
因此对于这个问题往往根据不同情况选择一下不同的处理方式：
丢弃模式、交叉模式或交换模式。
使用动态哈希方式虽然会遇到跨区链接的问题，但是这种方式对于中央节点的较低，只要能够根据情况选择合理的方式去处理跨区链接问题就能对采集重复问题给予良好的处理，因此选择了动态哈希方式进行任务分配。
4.4.1动态哈希分配算法
对于分配算法可以通过增加或减少节点对系统的影响的大小来分析其好坏。
在这里我通过增加一个或者删除一个节点来分析两种哈希分配算法的好坏。
假设Web服务器为M个，初始爬虫节点为N个，其中N4.4.1.1一级哈希映射算法
一级哈希映射算法是一中简单的哈希映射
，它采用全局哈希函数在所有节点中动态分配新解析出来的URL，经过哈希函数得到的值对应相应节点的ID号，其计算方式为
：
Ascii函数去URL中每个字符的ASCII值，N为爬虫节点数。
系统初始化时，对节点数去模可以保证每个节点的负载平衡，在增加一个节点后对N=N+1取模，同样可以保证每个节点的负载平衡，但是由于模数发生改变导致每个节点所分配的URL发生变化，这就会导致URL的重复采集，同样在减少一个节点时同样会产生这样的问题。
为了解决这样的问题提出了其优化的算法二级哈希算法。
4.4.1.2二级哈希映射算法
二级哈希映射
如图5所以，假设允许分布式网络爬虫系统中爬虫节点最多为S个，当前运行的爬虫节点为N个（N≤M），相应的每个爬虫节点中有两张表：
一张是逻辑表，存储S个逻辑节点的信息，每个逻辑节点的物理节点存在则赋值为true，否则赋值为false，通过对逻辑节点个数取模获得逻辑表；另一张表是物理表，用来存储物理存在的节点的信息，赋值为每个节点对应的ID号，通过对物理节点个数取模得到物理表，无论是求逻辑表还是物理表都是根据一级哈希映射算法的公式求得只是模数稍有改变。
图5：
二级哈希映射
对一个URL进行任务分配时，通过标准化的URL进过第一次哈希映射到相应的逻辑表中如果对应的元素值是true，则该ID号就是物理节点ID号，该URL分类到该物理节点上，如果对应的元素值为false，则说明该逻辑节点没有对应的物理节点，这时候对URL进行二次哈希映射，将URL分类到对应的物理节点上。
文献[4]通过实验证明该算法可以保证各节点负载平衡。
通过增加或者减少节点来对该算进行进一步的分析。
当增加一个节点时，更新表信息，将逻辑表中对应的元素值改为true，在物理表中添加该节点ID号。
为了提高系统性能，每个节点都有自己的数据库来存储已访问过的URL，当有新节点加入后，必然产生URL的重复采取，如果将原有节点以访问过的URL迁移到新的节点中会造成很大的系统开销，因此可以采取丢弃模式处理。
当系统中有节点退出时一般分为两种情况，一种是控制节点要求节点退出时，该节点通知其他节点自己要离开，其他节点收到消息后，修改逻辑表和物理表。
这样，任务不会再分配给已经退出的节点。
而原先已分配给其他节点的任务不会因为有节点退出而被重新映射。
另一种是节点崩溃非自愿的退出，系统为每个节点设置一个响应时间，当节点超过响应时间仍没有响应则判定该节点崩溃，此时系统通知其他节点崩溃节点的信息，其他节点将物理表中对应的元素删除，将逻辑表中对应元素值更新为false。
虽然二级映射解决了均匀分配的问题，但是没有考虑URL优先级的影响和子节点负载情况
。
主题爬虫的任务分割应该兼顾URL优先级的影响和子节点负载的均衡调度。
4.5通信模块的设计
通信模块包括消息通信模块和URL传输模块，是系统的核心模块
4.5.1消息通信模块设计
节点间的消息传递是节点间协作的基础，每个节点在消息同喜模块中都一个线程监听的接口，该接口负责接受其他节点发送的消息或控制模块发送的消息，通过接受不同的消息使节点进行不同的处理动作。
4.5.1.1有新节点进入
当有新节点进入时，会要求管理者输入当前正在运行的任何一个节点的IP，然后新加入的节点会向该节点发送加入请求，该节点接到请求会先判断自己是不是中心节点，如果不是该节点将消息转发给中心节点，中心节点接到请求消息后，向请求节点回复带有当前正在运行的所有节点的信息的应答信息。
然后中心节点把请求消息中请求节点的信息取出，为其分配一个ID，将请求节点加入自己的系统节点表中，最后向系统节点表中的所有节点发送新节点加入通知，通知其他节点加入新节点的信息，其他节点收到通知消息后更新自己的系统节点表，此时，新节点可以爬取网页。
这种通信方式保证了系统视图的一致性。
4.5.1.2节点要求退出系统
有节点要求退出节点分为两种情况，一种是普通节点要求退出：
控制模块向节点发送退出消息，退出节点向中心协调节点发送退去请求消息。
中心协调节点收到该消息后，退出节点可以安全退出系统。
中心协调节点在自己的系统节点表中将退出节点的信息删除，并向其它所有正在运行的节点发送节点退出通知消息，该消息中包括退出节点的信息。
其它节点收到节点退出通知消息后，也各自将系统节点表中退出节点的信息删除。
另一种为中心节点要求退出：
当中心节点要求退出时，先通过自己的系统节点表中选出除自己以外ID号最大的节点作为下一个中心节点，此时将退出请求消息发给新选出的中心节点，当新中心节点接到消息后发现退出的是中心节点，在系统表中删除节点的信息并选出新的协调的节点最后的结果是自己，然后向其它所有正在运行的节点发送节点退出通知，当其他节点收到通知进行相同的操作最后选取出共同的中心节点。
4.5.1.3有节点崩溃
有节点崩溃也分为两种情况，一种情况是崩溃的节点为普通节点，最先发现崩溃节点的节点先判断自己是不是中心节点，如果不是中心节点，该节点会向中心节点发送崩溃节点的信息的消息，另一种情况是当崩溃的节点为中心节点时，最先发现崩溃节点的节点先重新选出一个中心节点，再将崩溃节点的信息的请求消息发送给新选出的中心节点。
中心节点接受到请求消息后，现将自己系统表中该中崩溃节点的信息删除，然后将节点崩溃退出通知消息发送给所有正在运行的节点，其他节点接到消息后将自己的系统表中的崩溃信息的信息删除掉。
在这里需要注意由于发现崩溃节点的节点不止一个，因此发现崩溃节点发送崩溃节点信息中要带上发现崩溃节点的时间戳，中心节点只处理最早发现崩溃节点的节点的请求消息，对其它的请求消息忽略。
4.5.2节点间URL传输模块设计
当节点发现URL不属于自己的采集范围，就会把该URL发送给其他节点，节点间URL传输协议有很多种：
1.使用单个TCP线程，采用阻塞套接字监听传送端口：
TCP是面向连接的协议，当其中一个节点与其他节点进行URL传输时先要先建立连接，通过循环方式一次接受每个节点发送过来的URL如图6。
这是以一种常见的方式，但是这种方式存在一个严重的问题，当其中一个节点出现故障时，会使整个系统的传输处于阻塞等待，这种阻塞会降低系统的传输效率。
图6：
TCP单线程连接
2.
使用多个TCP线程：
一个节点需要与其他每个节点都有一个TCP线程如图7。
这是一个多线程的处理方式，由于多线程处理因此可以实现并行传输，即便某个节点出现故障也不会影响到与其他节点之间的传输，但是维护和建立TCP会消耗大量的网络资源。
图7：
TCP多线程连接
3.用UDP进行URL传输：
这是一种消耗最少的方式，因为只需要一个线程监听端口来接受来自其他节点URL数据包，但是UDP是面向无连接，是一种不可靠的传输，容易产生丢包的现象，这就需要设置一个UDP包超时，如果在一定时间内没有接收到来自接受节点的确认消息就将URL包重新发送。
4.使用非阻塞套接字传输：
这种方法也是采用但线程的TCP连接，与第一种方法类似，但是当有节点故障时不会是整个系统处于阻塞状态，可以使节点的间的通信持续进行下去，对于故障的的节点等待修复后重新传输。
5.参考文献
[1]白鹤，王劲林等.分布式多主题网络爬虫系统的研究与实现[D].北京：
中国科学院研究生院，中国科学院声学研究所国家网络新媒体工程技术研究中心，2009.
[2]搜狗百科网站
[3]李小正等.分布式爬虫系统的设计与实现.中国科技信息2014年第15期.
[4]叶允明等.分布式WebCrawler的研究：
结构、算法和策略.电子学报.2003
[5]吴黎兵，刘楠等.分布式网络爬虫的设计和实现[A].湖北：
武汉大学计算机学院，上海：
信息网络安全公安部重点实验室,2011.
[6]金岳富，等.分布式Web信息采集系统的设计与实现[A].黑龙江：
哈尔滨理工大学测控技术与通信工程学院，2010.
[7]朱学芳，等.基于P2P的分布式主题爬虫系统的设计与实现.南京：
南京大学信息管理系、多媒体信息处理研究所，2010.
升级会员 