分布式网络机器人的设计与实现

1、李广丽，张红斌，刘觉夫：分布式网络机器人的设计与实现2010,31（3 5910引言网络机器人是搜索引擎系统的核心部件，负责从 Web上爬行网页1。网络机 器人的架构可选择单机爬行或分布式并行爬行，单机爬行适合小型或垂直搜索引擎 系统，爬行速度有限。分布式并行爬行则适合大型通用搜索引擎系统，可以充分利 用多台计算机资源，爬行速度快。传统的搜索引擎一般采用C/S模式来驱动分布在多台计算机上的网络机器人，完成网页爬行，并最终建立索引库，面向Web提供搜索服务。近年，随着 Web 2.0的风靡，尤其是 Web Service技术在各种分布式系 统中的成功应用，也使得网络机器人的设计在体系架构上由C/

2、S模式迁移到B/S模式变为可能，同时其技术实现上也可由底层Socket编程迁移到高层的Web Service编程。所以，本文着重探索如何在 B/S模式下，借助 Web Service完成一个分布式 网络机器人原型，最终的实验结果证明其爬行性能明显优于单机爬行。1分布式网络机器人体系架构设计Web Service的核心思想：任何一个 Web应用系统都可由多个Web Service集成2。服务请求者可根据需要从服务提供者处获取相应的 服务（Service 3-4。而服务生产者则可在较高的应用层封装多个 Web Service，然 后将服务的发布权交给服务提供者（有时服务生产者同时也是服务提供者发布

3、4。 此种思想也可应用到分布式网络机器人的体系架构设计中，图1就给出了分布式网络机器人的体系架构设计结果。图中综合应用了Web Service、数据库、索引等相关技术。包含在网络机器人客户结点中的所有公共数据操作被抽取出，并被设计为Web Method ，然后封装在 Web Service 中。如某公共数据操作的功能描述如下： 爬行客户结点 （服务请求者向爬行服务器 （服务提供者 传递它的实时爬行性能参数，并需收稿日期： 2009-02-20；修订日期： 2009-04-07。人工智能5922010,31(3计算机工程与设计 Computer Engineering and Design要保存

4、到爬行服务器的数据库中。爬行服务器向所有客户结点提供统一的调用 接口，爬行客户端结点就可以突破网络环境限制完成网页爬行，即在 Web 环境下构建一个 Web Server，然后发布这些 Web Service，由爬行客户结点通过访问Web Ser-ver来调用已部署好的 Web Service，完成公共数据操作或数据通信 （如网页分析与爬行、 URL 转发及网页数据保存等 。在系统实现过程中，为了缓解爬行服务器的访问负担、改进系统的性能，将爬 行服务器和 Web Server彼此独立。Web Service被部署于 Web Server上，它负责接 受爬行客户结点对其发出的 Web Servi

5、ce 服务请求。而爬行服务器则提供管理页面 对爬行客户结点进行统一管理：记录客户结点的爬行速度、爬行线程数、连接超时长度、 URL 分析时间长度、计算机资源使用率等，服务器还可发送“启动”、“停止”、“重启 ”等控制命令给客户结点，调度其网页爬行动作。此外，爬行服务器还 需根据客户结点的爬行速度来协调 URL 在各客户结点之间的分配，或是发现新的 域名后将其指派给合适的爬行客户结点，即完成均衡负载，具体算法见2.1小节。作为完整的搜索系统，图 1 中还给出了索引服务器，索引服务是在每个客户结点爬 行得到大量网页数据的基础之上建立的，由于索引服务是一种非实时任务，故也将 其部署在 Web Ser

6、ver上。Web Service中的关键 Web Method设计如表1所示。2分布式网络机器人关键算法设计2.1均衡负载算法设计算法 1：在每个网络机器人客户结点上都建立了一份域名分表，保存该结点应该爬行的域名信息。在服务器上则建立了一份域名总表，该表由每个客户结点上的域名分表汇总而成。当客户结点爬 行到一个 URL 后，首先判断该 URL 对应的域名是否属于它的爬行范围，如果属于 则继续爬行其指定内容。如果不属于它的爬行范围，则把这个 URL 发送给服务 器，然后服务器通过下面的算法 2 判断哪个爬行客户结点最空闲，获取最空闲的爬 行客户结点，并把这个新域名分别添加到客户结点的域名分表和服

7、务器的域名总表 中，然后启动该爬行结点接受该 URL ，开始网页爬行工作。算法 2：当网络机器人客户结点爬行到一个 URL 后，不管其是否有效，也不 管其是否属于其爬行范围，均先利用 MSMQ （Microsoft message queue给爬行服务 器发送一个通知信号，告诉服务器它刚获取了一个 URL 。服务器接受到该通知信 号后，分析网络中的每个爬行客户结点最近 n 次爬行到一个 URL的平均消耗时间，从而计算出哪个客户结点相对最为空闲，这是一种自动的均 衡负载策略。此外，服务器还可手动控制均衡负载：在每个客户结点都设有一个守 护进程 5 ，该进程定时获取客户结点所在计算机的各种性能指标

8、 （如 CPU 使用率、内存使用率等 ， 然后把这些数据发送给爬行服务器，爬行服务器依据这些数据来决定如何调度客户 结点的吞吐。爬行服务器还记录了每个客户结点最近一次爬行到 URL 的时间，如 果爬行客户结点在 M 秒（默认值 30秒 内可以爬行到一个新的 URL ，则认为该客户 结点仍在进行爬行活动。反之，超出这段时间则认为该爬行客户结点已经停止爬 行，需要进一步检查其状态，以决定是否继续控制其完成网页爬行。2.2URL 队列操纵算法设计算法 3：分布式网络机器人中爬行客户结点在网页爬行过程里需要维护大量的 URL 队列 6 ，URL 队列分为待爬行 URL 队列、已经下 载 URL 队列、

9、正下载 URL 队列、噪声 URL 队列和域名列表队列。队列的操纵算 法将决定整个系统的性能以及搜索网页的质量 7 。在本系统中对 URL 队列实行 3 种方式的队列操作，第 1 种方式遵循数据表中数据记录的顺序，即按照数据表中记 录的物理记录的顺序来处理 URL ，此方法实现起来最简单，但在一段时间内其操 作的 URL 可能会集中在某一个 Web 服务器上。网络机器人的此种爬行行为很容易 被误认为是恶意的网络攻击，很多 Web 服务器就会拒绝其继续爬行 8，故此队列 操作策略较适合对中小型主题网站进行爬行；第 2 种方式是随机顺序，即随机从URL 队列中选择 URL 进行处理，此方法可以较大

10、概率地避免第 1种方法的 Dot 攻 击，但需要编写随机函数进行 URL 选取，算法速度稍慢于第一种方表1封装在 Web Service 中的关键 Web Method序号方法名说明服务对象 1234567891011GetSpiderInfo ConnectToServer UploadAllSpider SendKnownURLSendUnkownURL SendDomainName InsertDomainName InsertURLToUnCrawlListInsertURLToCrawledList SelURLFromUncrawlList DelURLFromUnCrawlLis

11、t获取所有爬行客户结点的基本信息连接协调爬行服务器上传给爬行器的统计数据客户结点爬行到一条已知域名的 URL 客户结点爬行 到一条未知域名的 URL发送域名到服务器在域名总表中插入一条新的域名插入一条新的 URL 到未爬 行 URL 队列插入一条新的 URL 到已爬行 URL 队列从未爬行 URL 列表中选择一条 新的 URL 从未爬行 URL 列表中插入一条 URL服务器客户结点客户结点客户结点客户结点服务器服务器客户结点客户结点客 户结点客户结点李广丽，张红斌，刘觉夫：分布式网络机器人的设计与实现2010,31(3593法，比较适合广域网范围内的网络爬行；第 3种方法是根据URL的MD5运

12、算结果的首字符进行 URL 选择，即按照 URL 对应的 MD5 码的第一个字符依次轮 询多个 URL 队列（从 0到 F ，然后循环 。此种方法结合了前两种方法的优点，可 作为更一般的队列操作算法。2.3网页消重算法设计算法 4：由于 URL 的惟一性，故其 MD5 码也具有惟一性，引入MD5对URL进行散列不但可以消除网页爬行过程中的 URL重复现象,而且其存储字节远小于 URL 平均字符串长度，存储起来更经济。算法操作过程： 在获取 URL 后，首先对其进行 MD5 运算，转换为 MD5 码表示，然后根据 MD5码的首字符在爬行数据库中查询对应的 URL 数据表，若该 MD5 码已存在则

13、将该URL 抛弃，否则将该 URL 存储到对应数据表中。图 2是 URL 的散列方法， MD5码作为每个表的主码，所以，每个表中均不会存在相同的 URL 。同时，图 2的URL 散列算法还避免了在不同的表之间存在相同 URL 的可能，因此，理论上该网 页消重算法可以完全消除重复 URL 爬行的情况。3实验实验软件环境如下：操作系统选择 Win dows XP P rofes-sio nal，开发工具选择Microsoft Visual Studio 2005，数据库工具选择 SQL Server 2000 Web 服务器选择IIS 5.1;实验硬件环境如下:(1 服务器：CPU 是 Intel

14、 Pentium Processor 1.73GHz,内存 2GB，硬盘 80GB ；(2网络环境：2M ADSL (1个外部接口 +100M的LAN ； (3客户结点：CPU是In tel Pen tium P rocessor 1.5GHz，内存 1.2GB，硬盘 40GB ；实验描述：分别进行单机模式和分布式模式下的爬行测试。在单机模式下分别进行1个、5个、10个和20个爬行线程的4组实验，每组实验做10次，每次实验运行12个小时以获取更稳定、更准确的实验数据。在分布式模式下，将网络机器人客户端分布在两台计算机结点上，每个结点均进行5个、10个和20个爬行线程的3组实验，每组实验做6次，

15、每次实验运行12个小时。此外，为了表明完整的 网页爬行过程，在实验中同时启动了相等数量的网页下载线程，以获取更加真实的URL处理速度。定义1URL处理速度指一个爬行线程从开始获取一个待爬行 URL 到是否把 URL 交给网页下载线程结束这段过程所耗费的时间。3.1系统的性能对比测试图 3 是单机爬行模式下不同线程数的 URL 处理速度对比。图中可以看出： 1个爬行线程的运行较稳定，但 URL处理速度很慢，大约是1Url/s。当线程数达到5 个后，系统性能快速提升，说明多线程是提高系统性能的重要手段。而当线程数达 到 10 或 20 个后，系统性能提升，但对比 5 个线程的折线图却发现：在某几次

16、实验 中 5 个线程的 URL 处理速度比 10 个或 20个线程还要快。分析原因：线程之间的并发调度、网络环境的不稳定以及过多的下载线程均可能占用了较多的系统资源， 从而导致 URL 处理速度变慢。此外， 20个线程的折线始终位于 10个线程的折线 之上，说明 20 个线程的系统性能优于 10 个线程，分析原因： 20个爬行线程与 20 个网页下载线程并行工作，下载线程数量增加了，加快了网页下载的速度，同时降 低了下载线程对系统资源的占用，爬行线程之间的并发度降低了，从而加快了URL 处理速度。图 4 是分布式模式下不同线程数量的 URL 处理速度的对比。图 4 中的 URL 处 理速度是来

17、自两个分布式客户结点上的 URL 处理速度之和。图中可以发现： 20 个 爬行线程的折线基本处于 10 个和 5 个爬行线程之上，说明多线程也是改善分布式 网络机器人爬行性能的关键手段。此外，分析图 4 还可发现：分布式环境下 10个 线程及 20个线程的折线图基本位于图 3 中 10个和 20 个线程的折线图之上。主要 原因：分布式网络机器人系统通过占用分布式环境下更多的计算机资源，并行地爬 行网页，大大提升了 URL 的处理速度。从图中还可发现：这种速度的提升并不是 线性成倍增加的，因为，在分布式爬行过程中，客户结点需要与服务器进行必要的 数据通信，这势必会占用网络带宽，造成 URL 处理

18、速度的损失。在实验过程中还发现：分布式爬行时其中一个结点的 URL 处理速度明显低于 另一个结点。分析可能原因： 计算机软硬件条件的制约。可通过改善计算机的软硬件配置来提升 URL 处理速度； 目前的爬行测试仅通过一个外部端口连接Web ，故有限的网络带宽制约了两个结点的 URL 处理速度图 2URL 散列算法URL 链接32位的MD5 码取 MD5 码的第一个字母TCrawled_0TCrawled_1TCrawled_2TCrawled_F图 3 单机爬行模式下 URL 处理速度对比次数 123456789101线程；765432105 线程； 10 线程；20线程U R L s /s图

19、4 分布式模式下 URL 处理速度对比次数2361210864205线程；10线程；20线程U R L s /s5942010,31(3计算机工程与设计 Computer Engineering and Design之和，从而导致一个结点的 URL 处理速度会明显低于另一个结点。因此，需 要设计更好的均衡负载算法对爬行过程进行优化，使两个结点的 URL 处理速度趋 于接近。对于这两个可能的原因，笔者将继续通过实验加以验证。3.2网页消重测试网页消重测试主要是面向 SQL Server 数据库，利用查询分析器工具或编写测试代码进行测试。如已下载 URL 队列共包含 16 个数据 表，其表名为固定

20、格式 “TCrawled_X”，X 代表 0F 中的任一字符，需要测试这 16个表中是否存在重复URL。2.3节从理论角度分析了网页消重算法的可行性，现通 过实验对其进行确认。如需验证 TCrawled_0和TCrawled_1表中是否存在相同的URL，可设计查询语句：Select count (* from TCrawled_0,TCrawled_1where TCrawled_0.MD5=TCrawled_1.MD5。若结果为 0，则 不存在任何重复URL，网页消重的目的实现。把问题一般化，需要讨论所有16个URL网页消重验证算法类似，不再赘述。表两两之间是否存在相同的URL，则可根据图5

21、选择数据表，然后用下面的伪代 码1实现，至于其它URL队列的伪代码1：For (i nt i=0;iv16;i+For (i nt j=i+1;j<16;j+If (i>=10&&i<=15 / 转换其为AF之间的任意一个字符，作为表名后缀Co nvert i to 'A' 'F'字符，作为表名后缀Convert j to 'A' 'F'/对两个表进行联接查询，返回查询出记录的数量S ="Select count (* From TCrawled_"+i.ToString (+

22、",TCrawled_"+j.ToString(+"WhereTCrawled_"+i.ToString (+".MD5" ="TCrawled_"+j.ToString (+".MD5".Execute S and get the int value offered to sameURLRe-cord执行 SQL 语句If (sameURLRecord=0 /返回查询结果为 0，则未发现重复的 URLThere is no same URL records Else /发/ 现了重复的 URL

23、 ，并进行累加 Found same URL records and add records 根据上述测试思想，对单机爬行模式中的 URL 队列数据库进行了测试，结果 未发现任何重复的 URL 。此外，还对分布式爬行模式下两个客户结点的 URL 队列 数据库进行了联合测试，结果也未发现任何重复的 URL ，故本系统的网页消重算 法是可行的。4结束语综合上述实验得出如下结论：本系统的成功运行基本验证了系统架构设计的正确性。此外，系统已经具备较好的鲁棒性：线程数量的 增加对系统性能的改善有着积极的影响，且在网络带宽有限的情况下，分布式爬行 的性能明显优于单机模式爬行，并且网页重复现象也通过网页消重

24、算法得以抑制。 故本系统已经具有一定的实际应用价值，但由于硬件环境的限制，目前还仅能在中小型搜索引擎中应用。下一步，笔者还会着重在如下几个方面展开深入的研究和实 验工作：(1 通过实验找出两个客户结点 URL 处理速度相差较大的真正原因及解决办 法；(2 部署更多的分布式网络机器人客户结点，测试其 URL 处理速度，并进行对 比分析得出本系统爬行性能与客户结点数之间的定性关系；(3 把分布式网络机器人部署到包含多个外部网络连接的测试环境中进行分布 式爬行测试，获取 URL 处理速度的实验数据，进一步验证其面向 B/S 模式进行网 页爬行的架构设计的正确性；(4 分布式的索引集成、更新，进一步完善系统，设计一个面向计算机教育资 源的垂直搜索引擎系统，使之可以基于 Web 向从事计算机教学工作的人员或学生 提供免费的垂直搜索服务，真正实现从研究到应用的转变。参考文献 :1李晓明, 闫宏飞, 王继民. 搜索引擎 -原理、技术与系统 M . 北京:科学出版 社,2005:40-45.2Foster H