一种网络爬虫的带缓存非阻塞异步
第8卷第11期软件导刊2009年11月Software GuideVol.8No.11Nov. 2009一种网络爬虫的带缓存非阻塞异步域名解析器模型及其性能分析陈言1，颜晨阳1（宁波大学职教学院，浙江
第8卷第11期
软件导刊
2009年11月Software Guide
Vol.8No.11Nov. 2009
一种网络爬虫的带缓存非阻塞异步域名解析器模型及其性能分析
陈
言1，颜晨阳1
（宁波大学职教学院，浙江宁波315100）
摘
要：网络爬虫是搜索引擎的一个基本组件，网络爬虫抓取页面的效率直接影响搜索引擎提供的服务质量。除了
可以通过改进网络爬虫的爬行策略来提高网络爬虫效率之外，也可以通过优化网络爬虫程序某方面的设计来消除特定的效率瓶颈。通过对网络爬虫结构和实际运行数据的分析，针对爬虫的DNS 解析瓶颈，设计了一种带缓存异步域名解析器模型，并通过实验和一般DNS 解析器模型进行了比较，实验结果证明这种模型对于减少程序等待解析域名的这一操作时间十分有效，显然也能够提高爬虫的整体效率。关键词：网络爬虫；域名解析；散列缓存；异步事件处理中图分类号：TP393.01
文献标识码：A
文章编号：1672-7800（2009）11－0143－04
网络爬虫的目标就是尽可能多地采集有效信息，并且消耗尽可能少的的系统资源和网络带宽。所以，网络爬虫的效率瓶颈主要和两方面爬虫程序设计相关：一方面是采集信息的价值，也即网络爬虫要尽可能地提高对包含有价值并且不重复的信息页面采集覆盖率；另一方面是爬行的效率，也即网络爬虫要使得采集一个页面的平均时间尽可能地短并且消耗尽可能少的网络资源和本地资源。所以，对于网络爬虫的性能的改进可以从两方面着手：一方面是提高爬虫的采集信息价值。这可以通过制定各种高效的爬行策略和相关算法来实现。简单爬虫往往采用广度优先或者深度优先爬行策略，无论是广度优先还是深度优先策略，其时间渐近复杂度都为O （e＋v），其中v ，e 分别为网络中的网页页面与链接的数量，这些爬行策略对各个页面的价值回报并不评估筛选，爬行速度快，但针对性较差，不能提高搜索的查准率。为了准确抓取与主题相关的网络资源，研究者提出了许多主题定制爬行策略和相关评价网页的方法，使得网络爬虫尽可能多地爬行价值高网页，尽可能少地爬行价值低网页。这些爬行策略包括：①基于文字内容的启发式方法，利
图1
0引言
网络爬虫是搜索引擎的重要组成部分。我们总是希望爬虫
对服务器不造成冲击的前提下，爬行速度尽可能快，信息覆盖高而且准确。通用网络爬虫爬行的基本策略是将Internet 视为一幅复杂的有向图。利用这样的模型，网络爬虫可以采用图的广度优先搜索算法或图的深度优先搜索算法爬行Internet 并下载数据。一个网页即为一个节点，网页中指向其他页面的URL 为该节点到其他节点的路径，整个Internet 由大量这样的节点构成一幅庞大的有向图G （E ，A ），如图1所示。其中矩形代表页面，箭头线为URL ，该图显示了网页间相互链接的关系
。
Internet 的有向图模型示意图
用了Web 网页文本内容、URL 字符串、锚文字等文字内容信上市。
参考文献：［1］
郭华. 基于ARM 的ZigBee 无线网络通信系统的研究与设计［D ］. 济南：山东科技大学硕士学位论文，2006.
（责任编辑：杜能钢）
开始读写，这样就可以有效地利用缓冲区。
4结束语
FS8610具有高性能的网络协议处理能力以及可编程控制
的GPIO 接口，搭配UZ2400这款ZigBee 网络芯片，可以轻松地实现ZigBee 到以太网的转换，有效缩短开发时间，加速产品
基金项目：宁波市自然科学基金资助项目（2008A610030）；浙江省大学生科技创新项目基金资助项目
作者简介：陈言（1985－），男，浙江宁波人，宁波大学职教学院本科生，研究方向为智能计算；颜晨阳（1982－），男，浙江常兴人，硕士，宁波大学职教
学院讲师，研究方向为智能计算。
,·144·软件导刊2009年
息。主要包括Best first search 方法、Fish search 方法、Shark Search 方法等；②基于Web 超链图评价的方法，基于Web 图的
启发策略的基本思想来自于文献计量学的引文分析理论。主要包括了BackLink 、PageRank 等方法；③基于分类器预测的方法，将文本分类技术应用于信息采集中。主要包括基于朴素贝叶斯分类模型引导主题Web 爬虫、基SVM 分类模型的爬虫等等。另一方面就是必须要消除制约爬虫自身爬行效率的瓶颈，使爬虫达到高效。这可以通过改进爬虫程序的设计结构来实现。为了高速地抓取尽量多的网页，许多爬虫程序都采用了一些程序设计方法和技巧，使得爬虫提高网络资源和本地资源利用效率，这些方法和技巧包括：①采用并发结构，主要是多进程／线程架构；②采用流水线结构，主要是采用异步事件处理技术；③采用缓存机制等等
。
图2
网络爬虫的瓶颈
1爬虫的DNS 查询瓶颈
通用爬虫能在指定应用层协议（一般为HTTP ）上通过指
定的端口与服务器进行通信。在爬行过程中，网络爬虫一般需要使用域名解析服务来解析域名，然后通过解析得到的IP 地址来抓取网页。在实际测试中，（Linux kernel version2. 6. 4，
gcc2. 7. 2）采用gethostbyname 系统调用，对3000个主机名进行
解析，花费9. 93×105ms，大部分域名的查询时间在10－100ms左右，少数域名的解析时间甚至达到数秒乃至数十秒。显然解析域名是造成爬虫爬行效率的重大瓶颈之一，事实上这个瓶颈是由于crawler 程序架构和网络资源本身造成的，和造成页面数据传输速率瓶颈的原因相同。但究其详细，主要有如下原因：
①一般操作系统（例如大部分Unix 、Linux 和Windows ）提供的DNS client 没有考虑cralwer 的需求，统提供DNS client 是阻塞
的，这带来两个问题：DNS 解析不能并发和DNS 解析不能在多个DNS server 之间均衡负载；②crawler 避免同时从一个服务器抓许多网页也使域名服务器cache 能力发挥不出来。
爬虫程序一般都采用多线程架构来提高网络资源利用率，这当然是可行而且有效的方法，但是由于上面提到的两个原因，仅仅采用多线程架构是不可能解决上面提到的DNS 解析瓶颈的。
在本文的下面一节中，针对爬虫程序需要频繁请求域名解析服务的DNS 瓶颈，架构了一种带缓存的异步非阻塞DNS 解析器模型。
2带缓存非阻塞异步域名解析器模型
本文中构造的域名解析器主要分为两个模块：①域名解析
结果散列缓存；②基于非阻塞socket 和事件处理异步DNS 客
户端。下面就详细给出这两个模块的构建方法：
2.1域名解析结果散列缓存
URL 中重复的域名使用频繁，DNS 本地缓存能大量减少
因重复的域名解析造成的网络占用及等待时间。为提高域名缓存模块的效率，本文设计了一个使用哈希表为表头、以双向链表保存域名－IP映射，用一个缓冲节点双向链表来存储可用缓冲节点，我们将这个DNS 缓存命名为“域名散列缓存（name
cache ）”，能够比较有效地写入域名、检索域名以及高效地按需
求替换域名。图3展示了域名缓冲的构造与关键环节，其中缓冲节点的数据结构如下所示：
struct nc_node｛
char*host_name；//主机名int host_addr；//IP地址
struct nc_node*next；//哈希表拉链后继节点指针sturct nc_node*prev；
//哈希表拉链前驱节点指针
struct nc_node*next_node；//可用链表后继节点指针sturct nc_node*prev_node；
//可用链表前驱节点指针
char in_use；//使用标志
time_tc_time；
//缓冲结点创建时间
}
图3域名缓冲的构造
本文中哈希表使采用如下散列函数进行散列，其中hot-
sname 为主机名字符串，hlen 为哈希表长。
表1
哈希函数
Pseudo-code of Hash function ：
unsigned long getHIndex （const char *hostname，int hlen ）｛unsigned long nHash=0；while （*hostname）
nHash=（nHash<<5） nHash *hostname ；return （nHashhlen）；｝
域名缓存过程大致如下：使用域名首字符ASCII 码值与域名长度散列域名到哈希头表。依照线性指针序列的下标索引，通过遍历双向链表检索已存在域名－IP映射缓冲结点，若域名－IP地址映射结点存在于该表中，则命中，并根据LRU 策略更新该节点在“可用缓冲节点双向链表”的位置，更新策略如下：如果前驱结点不是空闲节点，则当前结点和前驱节点交换位置。
若该域名－IP地址映射还未在表中，则将域名解析请求置入Send Queue ，请求DNS 客户端解析，解析失败则返回错误代码通知调用者，解析成功则向缓存的“可用缓冲节点双向链表”申请一个空缓冲节点，将域名域名－IP地址映射写入这个缓冲节点，并将节点链接到哈希头表相应的节点所指向的双链中。
如果缓存中没有空闲节点了，那么将“可用缓冲节点双向链表”中最后一个结点从缓冲中摘出，作为一个空闲节点使用，
,第11期陈言，颜晨阳：一种网络爬虫的带缓存非阻塞异步域名解析器模型及其性能分析
·145·
并将这个节点链接在“可用缓冲节点双向链表”头结点后面作为首结点。
特别要注意到，Internet 的DNS 系统会定期刷新，交换更新的域名和IP 的信息。普通的DNS cache 一般应该尊重上级
DNS 服务器带来的域名“过期”的信息，但用于爬取网页的DNS cache 不一定如此，以减小开销。在我们的模型中采用这样的策略：用定时器进行控制，在一定的周期内（TTL ）忽略缓存中域名的过期信息，一旦一个缓冲节点的TTL＜当前时间－c＿time，则在下次命中这个缓冲节点的时候，将或略这个缓冲结点的域名－IP映射信息，而将域名解析请求置入Send Queue ，解析结果成功返回时，刷新这个结点上的域名－IP映射信息，并根据LRU 策略更新该节点在“可用缓冲节点双向链
表”的位置。
2.2基于非阻塞socket 和事件处理异步DNS 客户端
在大多数操作系统中，系统提供的DNS 客户端均是阻塞的系统调用，也即不能够做到并发DNS 解析，也就是说不管你的爬虫的DNS 解析是不是多线程架构的，在同一时间只能够有一个线程，比如说线程A 的DNS 解析请求可以执行，其余线程的请求均被阻塞直到线程A 的DNS 解析请求得到了结果。这个特性是由于操作系统／语言本身造成的，因为在提供DNS 客户端的时候，根本就没有考虑到像cralwer 这样的，需要在很短时间里解析大量域名的应用，所以如果要创建一个有效实用的cralwer ，而非一个玩具，自己定制一个DNS 客户端是必需的，在本文中，我们构建了一个基于非阻塞socket 和事件处理异步DNS 客户端。这个客户端的构建大体如下：为了减少等待查找涉及新主机的地址的时间，也即尽早将主机名投给DNS 系统，cralwer 分析刚得到的网页，从提取主机名，向域名散列缓存服务器（name cache ）提交这些主机名的DNS 解析请求，如果域名散列缓存服务器无法回答，那么这些解析请求将被置入Send Queue ，如果这个Send Queue 非空，那么“发送请求”线程将一直从Send Queue 中取出解析请求，根据RFC 1035获取的DNS 协议的标准请求和回应数据格式，构建DNS 解析请求数据包，用UDP 协议，以异步非阻塞socket 向指定的DNS
Server 提出解析请求，线程不着等待解析的完成，发送解析请求后立刻返回（因此可以连续给出多个DNS 请求），随后DNS 客户端通过“轮询／接收”线程调用select 系统调用来检查完成的状态，select 可以同时监管多个socket 的状态，调用select 的“轮询／接收”线程将在select 调用上阻塞，直到数据可以通过socket 读，也即DNS Server 返回了至少一个主机名解析结果或者select 等待超时，如果DNS Server 返回了至少一个主机名解析结果。那么“轮询／接收”线程将读出结果，并根据RFC 1035获取的DNS 协议的回应数据格式解析数据，获取这个主机名对应的IP 地址
。
图4基于非阻塞Socket 和事件处理异步DNS 客户端
特别注意到，本文中构建的DNS 客户端是单线程结构，但是这样的架构足以应付一般中小型的crawler 的需求了，而且这样的架构避免了对发送队列和准备好的sockets 集合的并非访问，而用程序的方式协调这种并发访问的开销可能将会非常大（线程互斥，或者进程通信，都很复杂），可能会造成得不偿失的后果。
3性能测试与对比结果
综合以上论述，本文的在Linux 平台下用C 语言开发了一
个采用广度优先策略的通用爬虫，主要目的在于测试在选定爬行策略的前提下，爬虫DNS 客户端改进以及主要瓶颈的消除所带来的爬行效率提升。测试环境如下：Intel Core Dual （E2200），DDR4002GB （内存），7200rpm SCSI 硬盘，Fedora
Core 8（操作系统），校园网电信（带宽10Mbit ／s ）。该带缓存非
阻塞异步域名解析器模型结构如图5所示
。
图5带缓存的异步非阻塞DNS 客户端架构
程序采用主机名测试集合是用爬虫程序获取的随机主机名（显然，集合中必定有大量重复主机名），测试集合中共有
100万条主机名记录。程序运行设置如表2所示。
表2
程序运行主要参数设置
运行设置
缓存大小50000哈希表桶个数21911缓存策略LRU 缓存刷新周期1800s 发送队列大小
1024
图6显示了2对DNS 解析效率的影响，图7显示了DNS 缓存的引入对DNS 解析的效率的影响，图8显示了同时引入异步事件处理和缓存对DNS 解析效率的影响，其中横坐标表示DNS 客户端的运行时间，以小时为单位间隔，纵坐标为DNS
图6缓存对DNS
客户端性能的影响
,·146·软件导刊2009年
图7异步非阻塞架构对DNS 客户端性能的影响
图8异步非阻塞架构和缓存对DNS 客户端的影响
客户端的主机名解析量，以万次为单位。可以看到，引入DNS 缓存使DNS 解析效率提升了近2－3倍，而引入异步非阻塞程序架构也使DNS 解析效率提升了近1. 5倍左右，而带缓存的异步非阻塞组合更是大大提升了DNS 解析效率（3－5倍），显然，本文中提出带缓存非阻塞异步域名解析器模型达到了原本的设计初衷。
4结束语
网络爬虫自身结构设计不良，尤其是爬虫的DNS 解析和网页摄取的设计不良，会给爬虫工作效率造成极大影响。通过改进这些模块本身设计，可以消除爬虫部分系统工作效率的瓶颈，提高爬虫系统的爬行效率。本文提出的带缓存非阻塞异步域名解析器模型就是针对网络爬虫DNS 解析瓶颈的两个特性，引入了域名散列缓存（name cache ）和基于非阻塞socket 和事件处理异步架构这两种技术，并且用爬虫获取的大量主机名测试集合对这个模型进程了测试，测试表明本文提出的带缓存非阻塞异步域名解析器模型从一定程度上提高了DNS 域名解析的效率，也显然能够提高爬虫的整体效率。参考文献：［1］J.CHO ，H.GARCIA -MOLINA ，L.PAGE.Efficient crawling through URL ordering ［J ］.Computer Ne tworks and ISDN Systems ，1998，30（17）：161-172. ［2］P.DE BRA ，G -J.HOUBEN ，Y.KORNATZKY ，R.Post ，Informat ion retrieval in distributed hypertexts ，in ：Proceedings of RIAO'94，In -telligent Multimedia ，Information Retrieval Systems and Manage -ment ，New York ，NY ，1994. ［3］M.HERSCOVICI ，M.JACOVI ，Y.S.MAAREK ，ET AL.The shark -search algorithm ：an application ：tailored Web site mapping ［J ］. Computer Networks ，1998，30（17）：317-326. ［4］S.BRIN AND L.PAGE.The anatomy of a large-scale hypertextual W eb search engine ［J ］.Computer Networks and ISDN Systems. 1998，30（1-7）：107-117. ［5］S.CHAKRABARTI ，B.DOM ，AND P.INDYK.Enhanced hypertext ca tegorization using hyperlinks ［C ］.The ACM SIGMOD International Conference onManagement of Data.Seattle ，1998：3072318. ［6］J.JOHNSON ，K.TSIOUTSIOULIKLIS.Evolving strategies for focused Web crawling ［C ］.Int'l Conf Machine Learning.2003. ［7］A.HEYDON ，M.NAJORK.Mercator ：a scalable ，extensible web crawler ［J ］.World Wide Web ，2：219-229，1999. ［8］R.STEVENS ，S.A.RAGO.Advanced programming in the UNIX envir onment ［M ］.Addison Wesley ，1992. ［9］D.BOVET ，M.CESATI.Understanding the linux kernel ［M ］.O'Reilly ，2005. （责任编辑：杜能钢
）