基于P2P分布式的网络爬虫设计

1、基于P2P分布式的网络爬虫设计基于P2P分布式的网络爬虫设计摘要：未解决传统网络爬虫的在扩展性、容错性和低效性，提出一种基于P2P的分布式网络爬虫。分布式网络爬虫通过爬虫协调节点提高网络爬虫的爬取数 据的效率和扩展性。本文首先介绍了传统的网络爬虫的原理，在此原理的基础 上对其进行了改进，分析了分布式网络爬虫的结构设计，均衡负载策略和通信 策略，从而提高网络爬虫的容错性。关键字网络爬虫P2P 分布式负载策略通信策略1 .引言We流源是当今社会中获取资源重要途径之一，随着信息爆炸性增长，人们 对信息资源的需求也越来越大，如何使用网络爬虫技术高效的爬取Web中的数据成为了一个严峻的问题？由于传统的网

2、络爬虫的扩展性和容错性比较差，因 此在很多方面已经无法胜任高效爬取的任务。由于WebB息具有分布式的特性，因此将网络爬虫采取分布式的方式进行设 计可以大大提高爬取数据的效率。分布式的网络爬虫可以借助普通PC用户提供的空闲资源来获取网络，可以降低爬取数据的成本，减少对网络造成的负担。 设计一个分布式的网络爬虫首要了解传统的网络爬虫爬取数据的原理，在其基 础上进行改进和优化。本文详细介绍了分布式系统中常见的几种结构，并以P2P结构为例，说明了如何对资源的分配策略已达到每个节点的公平性，同时介绍了节点间的通信协 议如何保证分布式网络爬虫的良好容错性和扩展性。2 .传统网络爬虫2.1 工作原理网络爬虫

3、是一个 WebS序，按照某种规则自动爬取万维网中的WebM面，将爬取到的网页中的关键字存入关键字数据库中，用户通过搜索引擎或许相关信息的页面。传统的网络爬虫由带爬取的 URL库、未爬取的URLJ$、爬虫主题线程模块和内容提取模块组成。其工作原理 如图1,网络爬虫从一个或若干个初始网页的URl开始，通过爬虫主题线程模块从万维网中获得初始网页上的URL和网页信息，将新获取的URL存放在待爬取的URL队列中，将获取到的网页信息传给 内容提取模块，内容提取模块将访问过的 URL存入已爬行URL库中，将网页信 息存入页面信息库中，直到满足一定停止条件。通过一定的网页过滤算法过滤 掉与主题无关URL遵循一

4、定的调度策略从带爬取队列中选择下一次要抓取的URLInternet图i：商第磬url2.2 网页抓取策略网页抓取策略可以分为三类抓取策略， 分别是深度优先，广度优先和最佳优 先，深度优先策略容易使网络爬虫陷入问题，因此较为常用的是广度优先和最佳优先策略。1 .深度优先深度优先从初始的URL页面开始，通过一定的规则从初始 URL库中选 择一个URL ,分析这个网页中的其他 URL ,选择一个再进入。如此一个链 接一个链接地抓取下去，直到处理完一条线路为止然后再处理下一个URL。深度优先策略设计比较简单，但是一个门户网站中提供的连接的重要性随着 层次的深入逐级降低，从而使过度深入抓取的网页的价值过

5、低，因此深度优先策略直接影响了抓取效率与抓取命中率。2 .广度优先广度优先是先对初始的所有 URL网页进行抓取，然后通过网页过滤策 略选取其中一个链接的网页，继续抓取这个网页中的所有 URL链接网页， 这样逐层进行抓取。由于初始 URL在一定链接距离内的网页是具有主题相 关性的概率很大，但是随着抓取网页的增多，大量的无关网页将被下载并过 滤，算法的效率将变低。3 .最佳优先策略根据机器学习的一些算法提供一种网页分析算法，对初始的URL进行与要获取主题的相关性评估，选取评估最好的一个或几个URL进行抓取。它只访问进过网页分析算法预测为“有用”的网页。这种算法的优点在于可 以提高网页的爬取效率，但

6、是却容易忽略被过滤到的URL网页路径中与主题相关的页面，因此最佳优先策略是一种局部的抓取算法， 在使用的过程要 通过一定的优化使其能跳出局部最优点。3 .分布式网络爬虫由于传统的网络爬虫是使用集中方式来实现的，由于其扩展性和容错性较 差，在这个以大数据为背景的时代已经不能满足用户对数据的需求，分布式技 术能够最快的搜索大量网页，因此分布式的网络爬虫已经逐渐成为了网络爬虫 的一个发展方向。3.1 现状分析分布式网络爬虫在当今社会已经有了比较广泛的应用3,例如Google和百度所使用的网络爬虫就采用了分布式系统，但是由于涉及商业机密，因此很少 的想关信息进行交流，目前国外使用较多的分布式爬虫有Me

7、rcator、GoogleCrawler > UbiCrwaler > Internet Archive Crawler 等，国内比较著名的是 Web Gather。Google的分布式网络爬虫系统是一台中央主机和三台负责爬虫的机器，并 且这三台机器只与中央主机通信。中央主机从一个文件系统中读取 URL并把它们分给其它机器的爬虫进程中。爬虫采用异步I/O同时从三百个网站上获取数据。所有爬虫将下载下来的页面压缩并存储在磁盘上。然后索引进程从这些HTML页面中将URL®取出来存放在另外一个磁盘文件中。URLResolver进程读取这个 存放链接的文件，将其中的相对链接转换（通

8、过浏览文件夹按钮进行链接的方式 即本地链接）为绝对链接（一个指向摸个文件的精确位置的超级链接，该文件可 以存储在某个文件服务器、万维网或某家公司的内联网上），继而提供给主机。不足之处在于，一旦中央主机崩溃失效，则整个系统都会停止工作，而且中央 主机的URL分配模块常常成为整个系统的性能瓶颈。Mercator是Alta Vista搜索引擎的网络爬虫，它完全由JAVA编写。Mercator 的扩展性非常好，可以通过增减或替换模块来实现不同的功能。Mercator采用的数据结构可以使无论爬行的规模有多大，只占用有限的内存，数据结构的大 部分都在硬盘中存取。Mercator为最近访问的URL建立了缓存

9、，该缓存的命中 率达到了 85% Mercator证明了使用JAVA语言也可以达到较高的性能。Internet Achieve（也叫“网络时光倒流机器”）采用多个机器共同搜集页面。 每个Crawler进程负责收集64个WetR站的网页。Crawler从初始的URM中 读取，采用异步I/O并行爬行网页。网页下载后，提取出超链接。如果超链接 属于本Crawler负责收集的Web站点，则加入未访问URl集合，否则存储到交 叉的URL文件中。批处理模块定期分配这些交叉 URL文件到相应的搜集模块， 再次过程中要过滤到重复的 URL3.2 分布式网络爬虫特点分布式网络爬虫是在传统网络爬虫的基础上实现的，

10、分布式网络爬虫的每个 节点可以看成一个传统的网络爬虫，通过一个中心管理节点对所有节点进行管 理。因此分布式网络爬虫相比较传统网络爬虫具有以下优点：1 .可靠性：当某个节点崩溃后，通过中心管理节点进行广播使其他节点仍能 正常工作。2 .可扩展性：因为分布式的网络爬虫是由多个节点组成，由一个中心管理节点进行管理，因此当有新的节点加入后，可以不影响整个系统的工作，从而增 强系统的工作效率3 .高效率：相比较集中式的系统，分布式系统由于多节点协调工作，使其工 作效率要远远高于集中式的系统。同时，作为分布式系统有其固有的缺陷，其中最重要的是其通信问题，由于 分布式系统的每个节点都处于网络当中，网络中可能

11、出现数据丢失的可能，需 要特出的软件处理，其次，分布式系统的网络数据共享会导致安全性问题。3.3 工作原理分布式网络爬虫单个节点的工作原理与传统的网络爬虫的工作原理相似，多个节点之间通过协作完成对网页的爬取，从而使得分布式网络爬虫的效率远远 高于传统的网络爬虫。对于典型的分布式网络爬虫，每个节点不仅要从自身的 未访问URLJID WetM面中获取UR垃要从其他节点接受URL在分布式网络爬虫系统中4节点从未访问URL库中获取URL从万维网中下载对应的网页，从网页中获取出新的URL通过Hash函数计算出Hash®,将属于本节点的URLB入 未访问URLJ$队列中，将不属于本节点的 URL

12、>送到其属于的节点中。分布式 网络爬虫系统节点间协作的工作原理如图二。<2 Internet£J网络爬虫节点1URL URL网络爬虫节点2图2:节点间协作的工作原理4 .分布式网络爬虫设计4.1 体系结构该网络采用全分布式非结构化的拓扑结构也就是 P2P结构，节点间是对 等关系，每个节点既是客户端又是服务器，这种结构网的优点在于整体稳定 性较好，系统中某个节点发生故障不会对系统性能产生大的影响， 因此容错 性较好。但是一旦网络规模变大，节点间的通信的效率较低。基于 P2P的分 布式网络爬虫结构如图3,分布式系统由多个节点组成，每个节点都自己唯一的ID号，所有节点当中有一个

13、控制节点，用于为每个节点分配ID号，对系统进行动态监控管理等，剩余的节点都为爬虫节点，爬虫节点中有一个特 殊的中心协调节点，负责协调节点间的通信，一旦中心节点退出或者崩溃， 其他节点就会选取剩余节点中ID号最大的为中心节点。4.2 爬行节点结构设计分布式爬行节点可以划分为3'7如图4的四个部分：网络爬虫模块、节点信 息维护模块、任务分配模块、节点通信模块，其中节点信息维护模块、任务分 配模块、节点通信模块实现了网络爬虫的分布式处理，因此统称为分布式模块图4:爬行节点结构1 .网络爬虫模块网络爬虫模块有DNSW析器模块、下载模块和进程控制模块组成，是网 络爬虫节点的核心部分，它直接与We

14、b服务器进行通信。通过向线程控制模 块发送URL®彳TWebM面的下载，由于本文中的重点在于分布式模块， 该模 块不是讨论的重点。2 .节点通信模块节点通信模块由系统节点表，节点参数和日志记录组成，其中系统节点 表中记录了所有爬虫节点的信息，包含了所有节点的ID号，IP地址，端口号，是否为中心节点，为保证分布式环境中的视图一致性，每个节点的系统 节点表信息必须相同，当系统中有节点进入、退出或者崩溃时需要更新每个 节点中的系统节点表，当中心节点崩溃或者退出时，所有节点可以通过系统 节点表达成共识按照一定的选举规则选举新的中心节点表节点参数负责维护和改变节点运行的参数，当控制节点发出控制

15、命令， 由通信模块将控制命令发到该部分对节点当前的运行参数进行修改。日志记录，负责维护日志，使管理中心节点可以监控爬虫节点的运行速 度、爬行深度等参数。3 .任务分配模块分布式网络爬虫在工作时由于是所有节点协同工作，因此很容易出现访问到重复的URLM面5,同时将庞大的爬行任务分配给爬虫系统需要保证每个节点的负载平衡。任务分配模块的作用就是保证这些问题的解决而设计 的，具体的分配算法在后面的内容中具体说明。4 .节点通信模块节点间的通信包括URL勺传输和接受以及消息的传递，因此节点通信模 块包括消息通信子模块和URL传输子模块。4.3 控制节点的设计控制节点在爬行系统中不参与爬行过程，负责对整个

16、系统管理监控作用，该 节点主要实现以下功能1 .添加删除节点：动态的添加删除节点使得系统具有良好的可扩展性2 .监控运行节点：可以监控分布式系统中任何几点的运行状态，包括运行时 问、下载网页数量等。3 .动态调整爬虫节点的运行参数：通过动态调整爬虫节点的运行参数使得爬 虫节点具有更好的可管理性和可配置性，运行参数包括爬行速度、爬行深度、 爬虫线程数等。4.4 分配策略由于广域网的网络爬虫设计以及实现比较复杂，因此本文设计的网络爬虫建 立在局域网上的爬虫系统。局域网的网络爬虫是指所有的爬虫节点都分布在同 一个局域网中，节点间的通讯是依靠高速内连接进行。为避免在搜索网页出现重复爬虫并且使每个节点的

17、负载平衡，必须要选择合理的分配策略，常见的分配策略有以下三种 3：1 .集中方式：将初始URLM应的WetM面按照一定规则划分任务子集， 将特 定的任务子集通过中心节点划分给其对应的节点。在采集过程中如果有节点发 现采集信息不属于自己的范围，将信息反馈给中心节点，有中心节点重新分配 给其对应的节点。集中方式是通过中心节点完成合理分配的任务。这种方式往 往需要向中心节点转发较多的 URL容易造成性能瓶颈。2 .独立方式：每个节点都从自己初始的URL开始采集信息，节点间没有通信。 这种方式容易实现，但是会出现冗余的信息采集，不能达到节点的协作爬取任 务，效率较低。3 .动态哈希方式：将URLK哈希

18、函数划分，分配给各个节点。对于这种分配 方式，存在一种跨区链接（指一个采集节点在提取连接时发现不属于自己节点的 链接）。这就出现了一个难题，就是这种跨区链接不一定被它所属于的节点所发 现，如果本爬行节点采集可能会出现重复采取，如果不采集则可能出现漏采。 因此对于这个问题往往根据不同情况选择一下不同的处理方式：丢弃模式、交 叉模式或交换模式。使用动态哈希方式虽然会遇到跨区链接的问题，但是这种 方式对于中央节点的较低，只要能够根据情况选择合理的方式去处理跨区链接 问题就能对采集重复问题给予良好的处理，因此选择了动态哈希方式进行任务 分配。4.4.1 动态哈希分配算法对于分配算法可以通过增加或减少节

19、点对系统的影响的大小来分析其好坏。 在这里我通过增加一个或者删除一个节点来分析两种哈希分配算法的好坏。假设Wet®务器为M个，初始爬虫节点为N个，其中N<M4.4.1.1 一级哈希映射算法一级哈希映射算法是一中简单的哈希映射4,它采用全局哈希函数在所有节 点中动态分配新解析出来的 URL经过哈希函数得到的值对应相应节点的ID号, 其计算方式为：URL.length Hash(URL)Ascii (URL .charAt (i) mod Ni 1Ascii函数去URL中每个字符的ASCII值，N为爬虫节点数。系统初始化时，对节点数去模可以保证每个节点的负载平衡，在增加一个节点后对

20、N=N+1取模，同样可以保证每个节点的负载平衡，但是由于模数发生改 变导致每个节点所分配的 URL发生变化，这就会导致 URL的重复采集，同样在 减少一个节点时同样会产生这样的问题。为了解决这样的问题提出了其优化的 算法二级哈希算法。4.4.1.2二级哈希映射算法二级哈希映射4如图5所以，假设允许分布式网络爬虫系统中爬虫节点最 多为S个，当前运行的爬虫节点为 N个(N&M),相应的每个爬虫节点中有两张 表：一张是逻辑表，存储 S个逻辑节点的信息，每个逻辑节点的物理节点存在 则赋值为true ,否则赋值为false ,通过对逻辑节点个数取模获得逻辑表；另 一张表是物理表，用来存储物理存在

21、的节点的信息，赋值为每个节点对应的ID号，通过对物理节点个数取模得到物理表，无论是求逻辑表还是物理表都是根 据一级哈希映射算法的公式求得只是模数稍有改变。URLtrueltrueNHash。falsefalseN图5:二级哈希映射对一个URL®行任务分配时，通过标准化的URL®过第一次哈希映射到相应 的逻辑表中如果对应的元素值是 true ,则该ID号就是物理节点ID号，该URL 分类到该物理节点上，如果对应的元素值为false ,则说明该逻辑节点没有对应 的物理节点，这时候对 URL进行二次哈希映射，将 URL分类到对应的物理节点 上。文献4通过实验证明该算法可以保证各节

22、点负载平衡。通过增加或者减少节点来对该算进行进一步的分析。 当增加一个节点时，更 新表信息，将逻辑表中对应的元素值改为 true ,在物理表中添加该节点ID号。 为了提高系统性能，每个节点都有自己的数据库来存储已访问过的 URL当有新 节点加入后，必然产生 URL的重复采取，如果将原有节点以访问过的 URL迁移 到新的节点中会造成很大的系统开销，因此可以采取丢弃模式处理。当系统中有节点退出时一般分为两种情况，一种是控制节点要求节点退出 时，该节点通知其他节点自己要离开，其他节点收到消息后，修改逻辑表和物 理表。这样，任务不会再分配给已经退出的节点。而原先已分配给其他节点的 任务不会因为有节点退

23、出而被重新映射。另一种是节点崩溃非自愿的退出，系 统为每个节点设置一个响应时间，当节点超过响应时间仍没有响应则判定该节 点崩溃，此时系统通知其他节点崩溃节点的信息，其他节点将物理表中对应的 元素删除，将逻辑表中对应元素值更新为 false 。虽然二级映射解决了均匀分配的问题，但是没有考虑URL优先级的影响和子节点负载情况10主题爬虫的任务分割应该兼顾 URL优先级的影响和子节点负 载的均衡调度。4.5通信模块的设计通信模块包括消息通信模块和 URL传输模块，是系统的核心模块4.5.1 消息通信模块设计节点间的消息传递是节点间协作的基础，每个节点在消息同喜模块中都一个 线程监听的接口，该接口负责

24、接受其他节点发送的消息或控制模块发送的消息， 通过接受不同的消息使节点进行不同的处理动作。4.5.1.1 有新节点进入当有新节点进入时，会要求管理者输入当前正在运行的任何一个节点的IP,然后新加入的节点会向该节点发送加入请求，该节点接到请求会先判断自己是 不是中心节点，如果不是该节点将消息转发给中心节点，中心节点接到请求消 息后，向请求节点回复带有当前正在运行的所有节点的信息的应答信息。然后 中心节点把请求消息中请求节点的信息取出，为其分配一个ID,将请求节点加入自己的系统节点表中，最后向系统节点表中的所有节点发送新节点加入通知， 通知其他节点加入新节点的信息，其他节点收到通知消息后更新自己的

25、系统节 点表，此时，新节点可以爬取网页。这种通信方式保证了系统视图的一致性。4.5.1.2 节点要求退出系统有节点要求退出节点分为两种情况，一种是普通节点要求退出：控制模块向 节点发送退出消息，退出节点向中心协调节点发送退去请求消息。中心协调节 点收到该消息后，退出节点可以安全退出系统。中心协调节点在自己的系统节 点表中将退出节点的信息删除，并向其它所有正在运行的节点发送节点退出通 知消息，该消息中包括退出节点的信息。其它节点收到节点退出通知消息后， 也各自将系统节点表中退出节点的信息删除。另一种为中心节点要求退出：当中心节点要求退出时，先通过自己的系统节 点表中选出除自己以外ID号最大的节点

26、作为下一个中心节点，此时将退出请求 消息发给新选出的中心节点，当新中心节点接到消息后发现退出的是中心节点， 在系统表中删除节点的信息并选出新的协调的节点最后的结果是自己，然后向 其它所有正在运行的节点发送节点退出通知，当其他节点收到通知进行相同的 操作最后选取出共同的中心节点。4.5.1.3 有节点崩溃有节点崩溃也分为两种情况，一种情况是崩溃的节点为普通节点，最先发现 崩溃节点的节点先判断自己是不是中心节点，如果不是中心节点，该节点会向 中心节点发送崩溃节点的信息的消息，另一种情况是当崩溃的节点为中心节点 时，最先发现崩溃节点的节点先重新选出一个中心节点，再将崩溃节点的信息 的请求消息发送给新选出的中心节点。中心节点接受到请求消息后，现将自己 系统表中该中崩溃节点的信息删除，然后将节点崩溃退出通知消息发送给所有 正在运行的节点，其他节点接到消息后将自己的系统表中的崩溃信息的信息删 除掉。在这里需要注意由于发现崩溃节点的节点不止一个，因此发现崩溃节点 发送崩溃节点信息中要带上发现崩溃节点的时间戳，中心节点只处理最早发现 崩溃节点的节点的请求消息，对其它的请求消息忽略。4.5.2 节点间URL传输模块设计当节点发现URL不属于自己的采集范围，就会把该URL®送给其他节点，节 点问URL传输协议有很多种：1.使