分布式爬虫系统中URL去重的设计与实现

陈宇伦 周奎

摘  要：目前全球URL总数在350亿以上，在满足时效性的前提下，越来越多地选择采用分布式爬虫技术，它可以快速高效地从Web中获取有价值的数据。基于Redis数据库设计一种相关去重协议，实现URL去重，有利于提高分布式系统的稳定性和高效性，以及保持整个系统对URL去重的一致性。

关键词：分布式爬虫系统;URL去重;URL去重协议

（School of Electrical and Information Engineering，Hubei University of Automotive Technology，Shiyan  442002，China）

Abstract：There are more than 35 billion URLs in the world nowadays. Under the premise of satisfying the timeliness，more and more people choose to adopt distributed crawler technology，which can quickly and efficiently obtain valuable data from Web. Based on Redis database，this paper designs a kind of related de-reduplication protocol to realize URL de-reduplication，which is helpful to improve the stability and efficiency of distributed system，and to maintain the consistency of the whole system to URL.

Keywords：distributed crawler system;URL de-duplication;URL de-duplication protocol

0  引  言

随着移动互联技术的日益成熟和Web的飞速发展，Web这张网也愈来愈壮大。每天在这张网中产生大量的数据，蕴藏在这张网中的数据的价值不言而喻。从Web中快速而高效地挖掘数据成为各大公司的核心竞争力，要想高效地从Web中挖掘数据，分布式系统必不可少[1]。在分布式爬虫系统中也面临着各种复杂的挑战，比如分布式任务的调度、分布式系统中负载均衡、分布式系统中URL去重等。分布式系统中URL去重算法影响着系统的效率，面对上百亿的URL设计一个优秀的去重算法能提高整个系统的性能[2]。

1  分布式系统URL去重关键技术

1.1  Redis

Redis是开源的且遵循BSD协议，基于Key-Value的数据库，同时有着极高的性能以及提供多种数据结构的存储。分布式调度协议基于Redis数据库作为数据存储技术，实现分布式系统中URL去重。

基于Redis数据库URL去重协议的设计，将分布式系统划分为两层，分布式系统架构如图1所示。本地主机和中心主机，将中心主机作为单个网络节点，通过单个节点实现与本地网络和其他网络通信对URL去重[3]。

本地主机Redis服务（local_Redis）拥有三大数据库：（1）已完成的URL池（finish_URL），用于保存已经爬取的URL以及去重查询;（2）爬虫的任务池（task_pool），用于保存爬虫将要爬取的任务;（3）新获取的URL数据池（URL_pool），用于保存最新獲取的URL。

中心主机Redis服务（center_Redis）拥有三大数据库：（1）去重后的URL数据池（task_URL），用于分配给本地网络其他主机的task_pool;（2）本地网络去重池（local_reduce_pool），用于本地网络其他主机间的去重;（3）其他网络去重池（dist_reduce_pool），用于发送至其他网络，由其他网络完成去重查询，如果没有其他网络此处可选用[4]。

1.2  分布式系统中URL去重协议

实现分布式爬虫系统需要解决分布在不同主机上URL的去重问题，由于URL分散在不同主机和不同网络，对URL去重存在一些困难。设计一种协议为解决URL去重时URL一致性，将一定量URL作为一个集合去重时的基本单位。在去重时每台主机上的爬虫获取的新URL首先在本地去重，然后将第一轮去重后的URL集合提交至中心节点，再由中心节点去重，中心节点将本地网络主机发来的URL分发至其他网络，再由其他网络去重，再将去重的结果上报。主机与中心节点和中心节点与其他网络的去重，按照设计的数据格式通信[5]。

2  URL去重协议的设计与实现

2.1  URL去重协议格式

URL去重协议格式如图2所示，URL set为不同主机间要去重的URL集合，每次以一定量的URL作为一次通信的数据，IP为当前主机IP地址，用于主机间的通信和身份标识，number为整个分布式系统中唯一的标识，用以区分哪个网络哪个主机的哪次请求，flag为每次通信时发送的何种请求[6]。

2.2  本地去重

运行在不同主机上的爬虫在抓取页面时，会从页面中获取新的URL，将新获取的URL存入本地URL_pool。在本地去重时，遍历URL_pool中的URL，并计算每个URL的哈希值，同时与finish_url中的哈希值比较，若URL_pool中存在相同的哈希值，将该URL从URL_pool中删除。在遍历时将不重复的URL以一定数量构成URL_set，URL_set数据格式为JSON格式，其中以URL字符串为键，以阿拉伯数字0为默认值进行表示，并生成分布式系统中唯一的number作为去重协议数据帧的标识，置flag=1，置IP为本机IP，构成基本去重协议数据帧，并将此数据帧发给中心节点[7]。

2.3  本地局域网去重

中心节点收到数据时，读取flag的值，并根据flag的值将URL_set存入对应的数据库中。若flag=1，表明接收到的数据为待去重URL的集合，并将整个数据帧存入local_reduce_pool。中心节点处理local_reduce_pool中的数据帧时，从local_reduce_pool中每获取一个数据帧，置其flag=2，并向本地局域网主机发起广播，等待局域网内主机的应答。

主机收到数据时，判断flag的值，若flag=2，表明接收的数据为去重请求，同时判断数据帧中的IP是否为本机IP，若是，则丢弃该数据帧;否则，该数据帧进入去重队列。去重队列处理数据帧时遍历URL_set中的URL，在遍历时计算该URL的哈希值，并在finish_URL中查找是否有相同的哈希值，若finish_URL中存在相同的哈希值，则令键为该URL字符串的值为1，否则保持原值不变。遍历完URL_set时，令flag=3，并将该数据帧中发给中心节点。

中心节点收到数据时，判断flag的值，若flag=3，表明接收的数据为去重应答，此时判断数据帧中的IP是否为本局域网中其他主机IP，若是本局域网中其他主机IP数据帧进入去重队列。去重队列处理数据帧时读取number，并從local_reduce_pool取出相同number的数据帧，获取的数据帧其flag=2。去重队列遍历flag=3的URL_set，根据flag=3中值不为0的项，删除flag=2中对应的键的项，直到URL_set中的URL遍历完。在限定的延时时间内，直到接收了相同number所有主机去重应答为止，该number下的URL_set去重结束，此时删除local_reduce_pool中该number对应的数据帧，并将此数据帧转入dis_reduce_pool中。

2.4  分布式系统去重

中心主机接收到数据帧时，判断flag的值，若flag=2，表明此数据帧为去重请求，同时判断IP是否为其他网络IP，若是，则此数据帧进入dis_reduce_pool，并由分布式去重查询队列处理，否则返回。分布式去重查询队列将dis_reduce_pool的数据帧广播到本局域网所有主机，等待本地主机的去重应答。

中心主机接收到数据帧时，判断flag的值，若flag=3，表明此数据帧为去重应答，同时判断IP是否为本机IP或其他网络IP。若IP为其他网络IP，此数据帧进入分布式去重队列。分布式去重队列处理数据帧时读取number，并从本机dis_reduce_pool获取相同number的数据帧，获取到的数据帧flag=2，分布式去重队列遍历flag=3的URL_set，判断flag=3中键的值是否为0，若是，则令flag=2中对应的键的值为1，否则保持原值不变。在限定的延时时间内，直到接收了相同number所有主机的去重应答为止，并将该数据帧发送给数据帧中IP对应的网络。若IP为本机IP，此数据帧进入分布式去重队列，分布式队列处理数据帧时读取number，并从本机dis_reduce_pool获取相同number的数据帧，获取到的数据帧flag=2，分布式去重队列遍历flag=3的URL_set，判断flag=3中键的值是否为0，若不是，则删除flag=2中对应的项，否则保持原值不变。在限定的延时时间内，直到接收了相同number所有主机的去重应答为止，分布式系统URL去重完成，并将该URL_set中的URL存入task_pool[8]。

3  结  论

本文设计了一个简单且易于实现的分布式去重协议，对去重协议算法进行了详细的介绍和说明。使用Redis数据库存储URL哈希信息，可以快速查询URL是否被爬取，分布在不同网络的主机将去重结果发送至中心主机，中心主机负责整个分布式系统中URL去重。

参考文献：

[1] 李婷.分布式爬虫任务调度与AJAX页面抓取研究 [D].成都：电子科技大学，2015.

[2] 吕阳.分布式网络爬虫系统的设计与实现 [D].成都：电子科技大学，2013.

[3] 吴昊.主题爬虫URL分析模型与高度技术研究 [D].哈尔滨：哈尔滨工程大学，2011.

[4] 邱祝文.基于redis的分布式缓存系统架构研究 [J].网络安全技术与应用，2014（10）：52+54.

[5] 陈亮，廖文和.分布式结构在企业信息管理系统中的应用 [J].机械制造与自动化，2002（5）：48-50.

[6] 程斌，金海，石柯.一种自适应的分布式调度策略 [J].小型微型计算机系统，2005，26（10）：1793-1798.

[7] 梁正友，张林才.基于Rabin指纹方法的URL去重算法 [J].计算机应用，2008，28（S2）：185-186+203.

[8] 袁志伟，杨鹏，刘旋.双结构网络中URL去重机制研究 [J].太原理工大学学报，2016，47（1）：68-74.

作者简介：陈宇伦（1995-），男，汉族，湖北孝感人，本科在读，研究方向：分布式爬虫系统、网络程序开发与设计;周奎（1980-），汉族，男，湖北荆州人，讲师，硕士研究生，研究方向：智能汽车、图像处理、嵌入式系统。