《天网增量搜集子系统的设计与实现.doc》由会员分享，可在线阅读，更多相关《天网增量搜集子系统的设计与实现.doc（55页珍藏版）》请在金锄头文库上搜索。
1、北京大学 网络实验室硕士学位论文硕士研究生学位论文题目：天网增量搜集子系统的设计与实现姓 名：王东海学 号：10308155院 系：信息科技学院专 业：计算机软件与理论研究方向：计算机网络与分布式系统导 师：严伟 副教授，韩华二六 年 五 月版权声明任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。北京大学硕士学位论文摘 要互联网中的网页呈几何级数的增长。对搜索引擎而言，及时搜集互联网中新出现和变化的网页是核心工作之一。本文首先总结了当前有关搜集系统主要问题的解决方
2、法。其后主要介绍天网增量搜集子系统中结点协作、URL调度、网页指纹、网页变化预测、URL缓冲等算法设计实现以及相关算法的性能测试。在系统设计实现章节中较为详细说明了系统的体系结构和各主要模块的设计实现。通过良好设计，我们保证了系统具有良好的扩展性，并对内存和其它硬件资源利用等做了较好的优化。为检测算法的有效性，我们跟踪了近50万的网页在一个月内的变化，并以此为测试集。在此测试集上对比了我们系统中实现的算法与其它算法，结论表明系统实现的动态选择算法在预测效果上要优于其它三个独立的算法。论文最后总结了增量搜集子系统的运行情况：天网增量搜集子系统从2005年10月开始在单结点运行，平均每天提供约10
3、0万左右的新出现网页，有效地保证了天网搜索引擎的时新性。关键字：天网，搜索引擎，增量搜集， 网页变化预测-I-Masters Thesis of Peking UniversityThe Design and Implementation of Tiwang incremental crawlerDonghai Wang (Computer Software and Theory) Directed by Wei Yan, Hua Han AbstractThe number of web pages, which follows power-law distribution, in Inte
4、rnet always increases sharply, and it is crucial for a modern search engine to collect new web pages as soon as possible. In this article well first introduce the related work about crawling and incremental crawling technology, and then well state the design and realization of several key algorithms
5、, namely node-collaboration algorithm, URL scheduling algorithm, web page fingerpoint generation algorithm, URL caching alrogirhm, web page change forcast algortithm ,etc. Besides, we evaluate the performance of the above algorithms.Well also describe the main architecture of Tianwang incremental su
6、b-system and the design and implementation of chief components.In order to verify the efficiency of our web page change forcast algorithm, weve traced about 500,000 URLs to record the history of their changing within one month as a test-set. Based on this test-set ,we have made a comprison between o
7、ur algothm and other three algorithms.We draw a conclusion that the algorithm proposed in this article is more effective than the other three.At last, well summarize the running condition of this sub-system, which has been running on a single computer since Oct. , 2005. We find that the sub-system h
8、as greatly enhanced the preforcement of original Tianwang search engine.Keywords: Tianwang, search engine, incremental crawler, web page change forecast-47-北京大学硕士学位论文目 录摘 要IABSTRACT II第 1 章引言 11.1 课题背景11.1.1搜索引擎介绍11.1.2搜集系统工作方式11.1.3天网搜集的工作方式及不足21.2 研究内容31.3 本文贡献31.4 论文组织3第 2 章搜集系统的相关研究42.1 通用搜集42.1
9、.1多结点协作52.1.2URL选择62.1.3URL重复性判断72.1.4DNS解析82.1.5网页搜集92.1.6其它与搜集相关内容102.2 增量式搜集112.2.1更新策略112.2.2网页存储122.3 其它相关的搜集系统12第 3 章系统主要算法设计133.1 网页更新时间的预测算法143.1.1邻近法143.1.2等间隔153.1.3及时返回法153.1.4动态选择153.2 网页指纹算法183.3 URL调度算法203.4 URL缓存算法22第 4 章 系统设计实现254.1 天网增量系统结构和流程254.1.1天网搜索引擎系统结构254.1.2增量搜集子系统体系结构264.2
10、 增量搜集的模块结构284.2.1调度模块294.2.2站点列表模块304.2.3URL cache模块304.2.4搜集模块324.2.5网页更新预测模块334.3 系统实现中的一些问题及解决方法364.3.1网页初始变化时间、最小/大访问间隔的选择364.3.2更新列表文件读写双缓冲39第 5 章应用与评测405.1 测试集的建立405.2 评测项415.3 评测结果415.4 当前运行情况42第 6 章结论与展望436.1 结论436.2 展望43参考文献44致谢47第 1 章 引言1.1 课题背景1.1.1 搜索引擎介绍搜索引擎是一种在Web上应用的软件系统，它以一定的策略在Web上搜
11、集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。搜索引擎通常由三部分组成：搜集、预处理、检索李晓明 等, 2004。其体系结构大致如下图Arvind Arasu, 2004所示：图 1-1 搜索引擎通用结构搜集端搜集互联网上的网页数据。预处理部分对搜集提供的网页进行净化、消重、切词、建索引。检索端接收用户提交的查询，首先分析用户查询串，然后分别将查询请求广播到索引和广告服务结点，索引和广告结点经过本地查询后把结果返回给检索端，检索端把返回的结果进行分析后返回给用户。1.1.2 搜集系统工作方式就搜索引擎而言，高效的搜集端能够及时地为系统提供数据，较为快速地感知互联网上发生
12、的主要事件，并反馈给用户，从而提高用户感受，并增加搜索引擎的吸引力和提高用户的忠诚度。搜集的工作方式可以分为两种：集中式搜集、增量搜集。所谓集中式搜集，即在一个工作周期内，搜索引擎对互联网中的网页进行全网搜集，然后建索引和提供服务。这种方式的优点是易于实现，数据全，不过有明显的滞后性。增量搜集即在以前搜集网页的基础上，采用某种更新策略，在适当的时间再去获取网页信息，并把变化及新出现的网页保存到本地。这种方式通常需要记录网页的历史变化信息，而且不同的算法效果也不尽相同。增量的另一种工作方式为先集中搜集网页，然后在此基础上进行增量搜集。等一个周期结束后（如三个月或半年）再次搜集全互联网中的网页，然
13、后在这个数据集上进行增量式搜集；在一个周期内其包括两个阶段：集中式搜集和增量搜集。1.1.3 天网搜集的工作方式及不足网络实验室曾分别为天网实现了多个搜集系统，每次均有较大的性能提高。当前天网使用的搜集系统由北大网络实验室谢正茂老师等人开发。该搜集系统的单结点平均每天可以搜集500万左右的网页，搜集能力和其它商用的搜索引擎基本上处于同一层次，较好的满足了天网搜索引擎的需要。不过该系统在运行时只是用来进行周期性搜集。考虑到天网现有系统的负载能力，搜集一轮通常需要10天，而后的预处理工作包括对网页分析、消重、分词、建索引工作，这些工作通常需要20天左右。这样，用户在使用天网检索时最快也有近30天的
14、延迟。即使采用流水线工作方式，让搜集和预处理并行，这种延迟也有20天左右。因此系统并不能及时对互联网中的变化做出反应。而通常来说，用户在使用搜集引擎时，很多时候和时间有较大的相关性，如高考前后对高考相关的信息会有比较多的关注。我们曾对天网2006年1-3月的日志进行过统计，发现1月份对春运/春节方面的关注远比平时高，而3月份对研究生复试方面的关注也高于其它两个月。为了提高天网网页的时新度，需要搜集系统提供增量功能：即能够有一个补充系统和当前的搜集系统有比较好的结合，这个补充系统能及时提供互联网上的新网页。1.2 研究内容本文围绕增量搜集网页工作展开，主要内容包括：网页变化的预测算法的设计原理及
15、实现，网页指纹算法的实现，更新URL的调度策略，更新信息的表示等。最后针对系统效率进行评估并给出相关实验数据。1.3 本文贡献本文首先介绍搜集系统实现中的一些通用问题及针对这些问题的主要解决方法，并对这些解决方法进行了简单的对比。其后说明了增量过程中需要解决的问题和前人对这些问题的解决方法。在此基础上阐述了文中相关设计实现的思路和方法。该系统当前运行在天网中，通过特定的调度方法，较好的保证了天网中网页的时新性，有效的提高了用户体验。1.4 论文组织本文第一章介绍了增量研究的背景。第二章总结了搜集增量系统需要解决的主要问题及当前对这些问题的不同解决方法。在第三章，在对搜集能力分析的基础上，主要从工程的角度给出相关算法的设计思路和方案。第四章较为详细描述了系统的设计和实现，并介绍了系统的可扩展性。第五章对系统性能及增
