基于优先级队列的分布式多主题爬虫

范珊珊，李石君

（武汉大学 计算机学院，湖北 武汉430072）

0 引 言

目前已有各种算法研究在分布式爬虫中分配资源和调度网页抓取的策略。其中，文献 ［3］提出基于动态反馈的负载均衡算法，使任务集在集群系统中各单节点中得到均匀分布；文献 ［10］提出一种改进的T－Spider分布式爬虫，其对页面切割一遍各节点能够并行地解析网页。然而，这些方法更为集中地研究分布式爬虫整体框架与单节点之间的资源分配和调度策略，未能将调度粒度细化到单节点中的各子任务，从而忽略了单节点中多样性任务之间的调度竞争和协同关系。

为了改善这一缺陷，本文以多主题任务为切入点，在研究如何使任务集均匀分布到各集群节点的基础上，提出了一种基于优先级队列的单节点任务调度算法，基于各主题的特点构建优先级队列，在单节点中各主题任务基于时间段轮询调度，使优先级较高的任务能够进行抢夺式调度，提高分布式环境中各处理节点资源的利用效率，克服传统分布式爬虫中各主题任务分配的处理资源差异性较大导致爬取结果不均的缺点。最后实验分析并比较引入优先级队列的分布式爬虫与传统分布式爬虫的性能差异。

1 爬虫调度算法PQ－MCSA

在PQ－MCSA 中采用静态分配和动态调度相结合的策略，在优先级和权重关系约束下，计算各节点的负载能力，使任务合理分配到各处理机上有序执行。首要的任务是将大量的爬行任务进行合理分割，然后按照一定策略分配到各处理节点上进行爬虫调度。

1.1 任务分割策略

任务分割是指将用户指定的Web Page集合合理划分，然后分布到多个爬行器中，分割过程中需要避免一个URL被分配到多个处理节点下，出现重复下载，以及漏掉某些网址，出现某些Web页面不能下载的情况。

传统的任务分割方法是通过协调器来实现的，将爬虫分成一个协调器 （coordinator）和多个爬行器 （crawler）。在分布式系统中，指定一台主机作为协调器，将用户指定的URL 通过Hash函数计算，按照计算结果将URL 分配到指定的计算节点中。协调器负责系统全局的URL 分布，而超过爬行范围的链接则通过计算节点反馈给协调器处理模块，由协调器通过一定策略转发给其余对应的Crawler。由于爬虫任务量随着爬虫的进行逐渐增多，在并行处理系统中协调器需要处理大量的URL，很容易出现超负荷运行的情况，从而影响系统性能，这成为垂直搜索引擎爬虫能力提升的瓶颈。

在改进的任务分割算法中，设定URLs＝ ｛URL1，URL2，URL3，…｝是爬虫系统运行过程中积累的网页地址集合，爬行器数目为M，待下载网页的集合为W，任务分割子集合为｛W1，W2，…，Wn｝，满足∪ni＝1Wi＝W 且Wi∩Wj＝，其中i≠j，1≤i＜j≤n，且满足：｜Wi｜≈｜Wj｜，即每个任务节点上的任务量是大致相等，达到各爬行器分配的任务均衡。

1.2 任务分配策略

哈希方法是信息查询和存储所用的一项基本技术，一些基于Hash函数的文件结构在大型的分布式文件系统中得到了广泛的应用。在静态负载分配的各种方案之中，我们选择是利用缓存与哈希算法相结合静态分配策略，这种算法能有效缓解一般哈希算法中由于输入的记录键值分布异常而出现大量内存浪费的情况，使负载能均匀分配到各计算节点之上。

1.2.1 基于缓存的扩展式哈希算法 （cache－based extendible hashing system）

哈希算法能实现对记录的随机快速访问，传统哈希算法中，设定被访问的记录键值为KEY，哈希函数为Hash（），N 为存储单元的总数，通过key＝Hash（KEY）计算出记录键值所对应的伪键值，其中记录键值KEY 所对应的存储单元编号ID 为key%N。这种直接映射哈希算法的不足之处是，对于存储单元总数N 随时间变化敏感的情形并不合适，因为N 如果易于随时间变化，记录键值KEY 数量较多，伪键值key 计算较频繁的情况下会消耗大量的内存资源，效率不高。与缓存相结合的哈希算法是通过引入一定大小的缓存，该缓存大小可以随系统的需求来制定，这部分缓存用于记录各文件的使用情况，提高内存利用率，使哈希函数将记录的键值 （KEY）均匀的映射到伪键域上。在提高伪键值查询效率的同时，避免每次因存储单元总数的变化而需要全部重新计算伪键值 （pseudo key）的缺陷。

算法过程为在文件结构中构造桶文件 （bucket file）、目录文件 （directory file）、缓 存 桶 （cache bucket）3 种 抽象的数据结构。桶文件由桶组成，它们是一些桶文件块，在桶中设置记录单元RU （record unit），局部长度LL （local length）两个因素，其中RU 用于记载桶中存放的记录数。全局长度为GL （global length），其中GL 的值为所有局部深度LL中的最大值，GL 和LL 随着RU 的数量及记录的分布的变化而变化。目录文件中维护一个有2GL个元素的数组NArray，NArray［x］为该数组的第x个索引项对应的目录，NArray［x］都存储有指向某个桶的指针，成为桶指针 （bucket pointer），对于一个桶，如果其局部深度LL为M，那么目录文件中总工有2GL－M个桶指针指向它。初始时只有一个桶，而且LD＝0，RU＝0，数组NArray有一个元素，NArray［0］都存储有指向该桶的指针。

缓存桶的目录文件的结构和普通桶文件结构基本是相同的，在桶文件的结构上，缓存桶增加了两个标志位，一个标志位为LG，用来表示桶的局部深度和全局长度之间的关系，具体是，LG＝0 表示该记录单元对应桶LL＜GL，而LG＝1表示该记录单元对应桶LL＝GL；另外一个标志位为BNP，为布尔型值，表示桶在其对应的缓存桶中是否存在相应记录，BNP＝0 为假，表示桶在缓存桶中没有记录，相反BNP＝1为真，表示桶在缓存桶中有记录。

为了使网址尽可能合理地按照计算节点的承载能力来分配到各个装载有Crawler的爬行器中，设计一个较好的网址Hash函数，其函数表达式如下

该函数中，ASCII用来取字符串中每个字符的ASCII码，第一次取值W ＝GL，第二次取值W ＝LL，其中GL 为全局长度，LL为桶的局部深度，实验表明，该哈希函数呈现的分布均匀，能够使爬行器获取的任务数量均匀增长。

记录单元R 的检索过程是，首先根据设定的哈希函数Hash（S）计算出R 的伪键值Pseudo Key，根据伪键值的GL位得到索引的目录，找到桶的指针，根据该桶的存储结构寻找该记录单元R。如果在该桶中查找不到记录单元R且该桶的标志位BNP＝1，则进入缓存桶中进行查找，在缓存桶中对记录单元的检索并不影响记录的检索效率，因为缓存桶常驻内存，避免了慢速的I／O 操作。将记录R 插入桶的过程如图1所示。

1.2.2 URL逻辑二级节点哈希映射法

图1 基于缓存的扩展式哈希算法

采用URL 逻辑二级节点哈希映射发来实现网页爬取URL的分布式分配，使URL 的分配不再交由传统方法中的协调器完成，这样可使系统规模灵活可扩展。这种新方法的显著特点是在爬虫任务和最终的分配的物理实况之间加入一层逻辑空间的概念，即首先将URL映射到一张一维的逻辑表上，这是第一级映射，对爬取任务集进行第一步划分，然后进行第二级映射，将逻辑表上的节点映射到各个物理节点中。作如下的定义：

定义1 任务集 （task set）。设URLSet＝ ｛URL1，URL2，URL3，…｝是爬虫的任务集合，该任务集是动态变化且未知的，因为此任务集会在爬虫处理网址的过程中发掘新的网址而处于不同的状态。

定义2 划分粒度 （partition granularity）。设定M 为爬虫系统的并行节点数量，［M］＝ ｛1，2，3，…，M｝表示集群系统中的所有节点的集合。N 为单个爬行节点上网页抓取线程的总数。在单机爬虫系统中为了有效地管理CPU，网络带框，IO 等资源，会将爬行的任务集合按照一定策略分配给各个线程。定义即所有的任务集URLSet 到M×N 个线程之间的映射为划分粒度。

定义3 host（URL）。定义host（URL）为一个URL 的主机部分，通常情况下可以根据某一网址得出其值。例如

URL1＝ “http：／／www.lib.gxu.edu.cn／content／detail.asp”，则host（URL）＝ “www.lib.gxu.edu.cn”。一个host（URL）一般对应物理领域的某一台Web Server。

URL逻辑二级节点哈希映射的步骤为，约定可利用的并行节点数目为T，当前正在运行的爬虫数目为N（N＜＝T），而系统初始节点数为n，在爬虫运行过程中n 不断变化，变现为集群节点不断发生变化。在第一级映射中，采用Hash（URL）mod M 的方法将URL 映射到节点数为M的逻辑表上，其中M＞＞N，在第二级映射中，同样采取Hash（URL）的方法，将M 个逻辑节点映射到n 个集群节点上，通过两级映射，将划分粒度成功细化到n，结合一个随机性较强的哈希函数，将可以达到各个爬行节点上的子任务集相对均匀的目的，如图2所示。

图2 二级URL哈希映射

1.3 任务调度策略

集群式系统中，通过分布式任务调度算法将整个任务集分配到了各个计算节点上。任务是多主题的，按照主题的时效性特点和其重要程度以合理的方式分成不同的优先度。例如时效性较强的Web页面类是需要优先爬取的，且爬取的频率要求较大，这样才能周期性的及时将内容爬取下来供搜索引擎处理，这种主题的URL优先度较高。而时效性要求较低而且更新周期较长的网页类别优先度较低。优先级分类原则是不同重要性的网页类别分成不同的优先级，对优先级不同的任务集采用抢占式调度的方式来进行爬取，优先级高的类别优先获得系统调度，从而提高重要性较高的主题任务被爬取的机会。而重要性类似或相同的网页类别则赋予同等的优先级，采用多线程和类似于分时操作系统中采用的时间片轮转的方式来分配调度空间，在调度时具有同等优先级的类别具有相同的几率。以此方式来减少有些URL类别始终都得不到爬取的现象，提高节点的利用率。

1.3.1 优先级队列设计

维护优先级队列PRIORITY＿QUEUE 这样一个数据结构来存储所有主题任务的优先级。队列中存储爬取任务和任务对应的优先级。任务可以是某一个爬取主题，也可以细化到粒度为URL的具体爬行目标。如果某一个主题下的所有网址的优先级都相同，则该任务在优先级队列中以爬取主题存储，否则细化到单一的URL存储，这样能够提高优先级划分的灵活性。任务控制块QUEUE＿MCB，优先级队列结点QUEUE＿NODE和指针数组QueueArray［］的相互关系见图X。

定义优先级队列PRIORITY＿QUEUE 表为一个五元组形式

其中IDtask是任务标识符，采用N 位无符号整型，具体设计由实际任务规模决定。IDtheame表示URLFORM 所属的主题，称作主题标识符，当任务的粒度G 为false时才有意义。P 表示队列中任务的优先度，采用M 位整型存储。G是任务的粒度，为true表示粒度为主题，为false表示粒度为主题下所包含的URL。TN 队列上的任务数，是动态可变化的。UMAP 与G 联合起来使用，采用Map数据结构存储，该Map中KEY 表示主题的任务标识符IDtask，VALUE 为CHARSEQUECE 类型，存储主题任务标识符为IDtask且优先级为P 的URL的SURT 格式，当G 为false时UMAP 才有意义。

定义队列控制块QUEUE＿MCB的数据结构为一个八元组形式

其中IDtask是任务标识符，它是任务的唯一标志。TN 是任务名称 （task name），TD 是任务的描述信息 （task description），ST 是分配给此任务的时间片长度 （slice total），SR是在一个时间段内此任务执行的剩余时间段长度 （slice remain），SI 是 任 务 执 行 的 状 态 信 息 （task state information），CP 是堆栈指针，用于保存任务上下文 （task context P）。TD 是任务延时 （task delay）。优先级队列的详细结构设计如图3所示。

图3 任务优先级队列

定义网址的格式为SURT 格式 （sort－friendly URI reordering transform），一般网址的格式采用URL 格式 （uniform resource locator，统一资源定位符），SURT 格式是对URL格式的一种改进，有利于URL 的排序和集合聚拢。SURT 格 式 将 “scheme：／／userinfo＠domain.tld：port／path？query＃fragment”形式的URL 转换成 “scheme：／／（tld，domai n，：port＠userinfo）／path？query＃fragment”的形式，例如 “http：／／www.baidu.com”对应的SURT格 式 是 “http：／／ （com，baidu，www，）”。同 时 引 入TaskID 作为每一个任务的标识符，TaskID 可以采用N 位的符号整数来表示，可存储的任务数目为2N。

1.3.2 任务调度算法描述

队列控制块中唯一表示任务标示符的是TaskID，Slice＿Total用来保存分配到TaskID 所表示的任务的时间区间大小，Slice＿Remain表示任务执行的剩余时间，这两项用来实现任务的时间片轮转调度。

算法1：任务初始化

输入：可调度任务task，预分配的爬取时间段time＿schedule

输出：任务执行队列scheduleTaskQueue

算法2：任务调度过程

输入：任务执行队列scheduleTaskQueue，优先级队列priorityQueue

输出：FOR each crawlSubTask∈scheduleTaskQueue

算法3：抢夺式调度

输入：待调度的任务task＿pending，正在运行任务task＿crawling，优先级队列priorityQueue

输出：启动后台线程并进行轮询监控

启动后台线程并进行轮询监控

任务调度过程中，首先将所有可调度的任务细分成各个爬行子任务，按照其优先级分配到不同的预备队列中，在预备队列中完一系列例如DNS解析等网页爬取的初始化工作。调度器不间断地调度任务，优先级高的有较高的几率获得系统运行资源并被调度进入爬取队列中，而优先级相同的任务分时地占用调度资源。预先给不同优先级的任务分配不同的爬行时间阈值，即一次爬取的最大时间，同一优先级的任务之间的爬行时间阈值相同。而不同优先级的任务根据调度策略的不同分配不同的爬行时间阈值，在任务开始时，维护一个计时器对每个开始运行的爬行任务进行计时，相同优先级的任务之间进行时间片轮转，如果有优先级更高的任务被调度进来，则当前运行的任务会被强制进入就绪队列，而将执行资源让给优先级高的任务。在任务调度的同时，维护一个Demon线程，统计各个主题下任务的爬取规律和爬取的网页数量。如果符合相应主题的爬取规律且在规定时间内爬取到了最低数量的相关性网页，则相应的爬行时间阈值减少一个额度，同时将在较短的时间内调换执行同类任务或者更高优先级的任务。这样在有限的调度周期内，该主题爬取的机会减少，留给其它主题的爬取机会将会增多，从而保证各个爬取的主题分配到的运行资源是相对均匀的。

2 系统实现与结果分析

该多主题的分布式爬虫系统采用一个功能节点，两个能力节点进行测试，需要一台架构服务器，和两台能力服务器。其中功能节点用于收集各能力节点的负载情况，来分发任务，维持分布式系统的负载均衡状况。两个能力节点采用不同的任务调度方式，进行多主题爬虫。表1是节点的规格型号和技术参数说明。

表1 系统测试环境参数说明

对于传统的分布式爬虫，系统运行时间是24小时，到次日凌晨时会重启爬虫，对于优先级队列的分布式爬虫，在一轮调度完成之后，会重启爬虫，给定测试时间为24小时，此次试验主要设计爬取税收领域的3个主题，税收经验，每日动态，重点税源，每一类主题在数据库中配置了相应的网址，可对网址进行更新修改。

表2中每个主题中有3个参数，下载URL 数量、发现URL数量、网页下载总数，分成A 组和B组，A 组表示传统的分布式多主题爬虫系统，B 组表示基于优先级队列的分布式多主题爬虫系统，运用相同的能力节点在规定的时间内测试，A 组即A1主题，A2主题，A3主题；相应地右边是B1主题、B2主题、B3主题。Ai和Bi均分出重点税源、税收经验、每日情报3个主题，然后对比左右两边的数据均匀情况。从测试结果中可以看出，该分布式爬虫系统各节点中任务爬取较均匀，具有较高的性能。

图4横坐标是时间，纵坐标是爬取的网页数目，每隔两个小时采集一次样本数据，展现的是A 组和B组的总体爬虫结果对比。能力节点1进行B 组的爬虫实验，能力节点2进行A 组的爬虫实验。能力节点2引入优先级队列的分布后调度的情况，表示优先级不同的主题之间是如何体现调度关系的。画中4条曲线表示的是A 组和B组并行节点的均值和总和，体现出了调度算法的实际运作过程，同时进行了新旧对比。是对分布式爬取节点的一个切片展示。从图中可以看出采用新算法的爬虫的所有主题比不采用新算法的爬虫结果分布的要均匀，且避免了旧的算法出现的没有数据的特殊情况。

表2 单个节点爬虫结果对比

图4 爬虫结果总体对比

3 结束语

在集群环境中，传统的分布式主题爬虫较为集中地关注分布式系统的架构和功能模块的划分和协同，忽略了各计算节点的子任务集的相关度计算因素，及爬取资源分配情况。本文提出了一种基于优先级队列的分布式主题爬虫调度算法PQ－MCSA。在对任务集进行分配模块中，引入基于缓存的可扩展哈斯算法检索记录，减少了I／O 操作数，避免了传统的可扩展哈希方法在伪键值分布不均匀上造成浪费内存的缺陷。在单处理节点中，针对多主题的子任务集，根据各主题的优先度和时效性不同的特点基于优先级队列进行优先级队列调度。实验结果表明，使用该算法能够在更短的时间内爬取相对较多的网页，使各主题爬取的结果相对均匀。确定各主题任务的优先级过程中，是根据以往经验和主题相关度因素进行设定的，还缺乏精确的方法生成与主题特点相对应的优先级。将在下一步工作中进行上述研究，以进一步提高调度的实用性和准确度。

［1］LIANG Gen，QIN Yong，GUO Xiaoxue，et al.Task scheduling in distributed system based on dynamic multi processing nodes［J］.Computer Engineering，2009，35 （9）：31－33 （in Chinese）.［梁根，秦勇，郭小雪，等.基于动态多处理节点的分布式系统任务调度 ［J］.计算机工程，2009，35 （9）：31－33.］

［2］LIU Shuang，JIANG Chunxiang，ZHANG Weizhe，et al.GNP－based scheduling strategy for distributed crawling ［J］.Application Research of Computers，2010，27 （2）：446－449（in Chinese）.［刘爽，姜春祥，张伟哲，等.基于GNP 算法的分布式爬虫调度策略 ［J］.计算机应用研究，2010，27（2）：446－449.］

［3］WANG Chunjuan，DONG Lili，JIA Li.Load balance algorithm for Web cluster system ［J］.Computer Engineering，2010，36 （2）：102－104 （in Chinese）. ［王春娟，董丽丽，贾丽.Web集群系统的负载均衡算法 ［J］.计算机工程，2010，36 （2）：102－104.］

［4］GENG Xiaozhong.Research on key techniques of task scheduling based on multi－core distributed environment ［D］.Jilin：Jilin University，2013：30－32 （in Chinese）.［耿晓中.基于多核分布式环境下的任务调度关键技术研究 ［D］.吉林：吉林大学，2013：30－32.］

［5］BAI He，TANG Dibin，WANG Jinsong.Research and implementation of distributed and multi－topic Web crawler system［J］.Computer Engineering，2009，35 （19）：13－16 （in Chinese）.［白鹤，汤迪斌，王劲松.分布式多主题网络爬虫系统的研究与实现 ［J］.计算机工程，2009，35 （19）：13－16.］

［6］MENG Xiangqian，YE Yunming，DENG Bin.Study on paral－lel crawler based on pipeline load balancing model［J］.Computer Engineering，2009，35 （2）：34－36 （in Chinese）.［孟祥乾，叶允明，登斌.基于流水线负载平衡模型的并行爬虫研究［J］.计算机工程，2009，35 （2）：34－36.］

［7］Cafarella M J，Madhavan J，Halevy A.Web－scale extraction of structured data ［J］.SIGMOD Record，2008，37 （4）：55－61.

［8］LIU Shaofeng，DONG Jian，WU Zhibo.A dynamic－feedback scheduling algorithm for cluster load balancing based on priority queue［J］.Intelligent Computer and Applications，2012，28（4）：78－80 （in Chinese）.［柳少峰，董剑，吴智博.一种基于优先级队列的集群动态反馈调度算法 ［J］.智能计算机与应用，2012，28 （4）：78－80.］

［9］XU Xiao.Research on key technology of distributed Web crawling ［D］.Harbin：Harbin Institute of Technology，20011：28－31 （in Chinese）.［许笑.分布式Web信息采集关键技术研究 ［D］.哈尔滨：哈尔滨工业大学，20011：28－31.］

［10］JIN Fan，GU Jinguang.An improved t－spider distributed crawler［J］.Microelectronics ＆Computer，2011，28 （8）：102－104 （in Chinese）.［金凡，顾进广.一种改进的T－Spider分布式爬虫 ［J］.微电子学与计算机，2011，28 （8）：102－104.］