“天网”中的并行与分布处理

《“天网”中的并行与分布处理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、“天网”中的并行与分布处理摘要本文介绍了“天网”搜索引擎系统2.0版本中所采用的分布并行处理系统结构和关键技术，主要包括搜集子系统和查询子系统两个部分。通过对设计、模拟、实现和实际运行评测等相关过程的描述，展现了系统在性能、负载平衡和扩展性等方面的性质和特点。关键词WWW，搜索引擎，信息检索，分布式系统，并行处理ParallelandDistributedProcessinginWebGatherAbstractThispaperpresentsparallelanddistributedarchitecturesandkeytechnologiesemployedin

2、crawlingsubsystemandretrievingsubsystemofWebGathersearchengineversion2.0.Characteristicsofthesystem,intermsofperformance,loadbalanceandscalability,areshownthroughdesign,simulation,implementation,andactualrunningmeasurement.KeywordsWWW,searchengine,informationretrieving,distributedsystem,

3、parallelprocessing1引言随着因特网上信息的爆炸性增长，搜索引擎已成为人们用得最多的网络应用程序之一。有报道称[5]，搜索引擎是除电子邮件系统外用户最多的网上应用程序（不过我们认为浏览器的用户应该更多些）。提供良好的搜索引擎服务，不仅是各类大型门户网站的一个基本配置，也是和WWW发展相关的学术界关注的一个热点。例如在2001年5月召开的第10届WorldWideWeb学术会议上，一共有24个学术分组报告会，其中4个就是直接和搜索引擎技术相关；78篇论文中有15篇讲的是搜索引擎技术[6]。搜索引擎，作为一个网络软件系统，主要追求三个方面的指标。一是规模，即

4、要能够维护足够多的网页信息。目前，中国因特网上的公开网页估计约有5000万个（根据[7]和“天网”最近一次收集的估计），每个网页纯文本信息大约13KB，要收集并维护这样一个量级的数据，并提供相应的查询服务，对系统是一个基本的挑战。二是性能，这是本文下面主要讨论的。三是质量，即要提供用户满意的查询结果。这方面本身是一个很复杂的问题，本文不做讨论，有兴趣的读者可参见[8，9]。性能大致上可归结为两个方面。一是搜索引擎的网页搜集子系统要能够在不太长的一个时间段里（例如20天）完成网页的搜集过程（目前是5000万左右，想象今后会是1亿、2亿、10亿等），否则搜索引擎维护的信息的

5、“新鲜度”就不高了。二是搜索引擎的查询服务子系统要能在“秒”量级的时间里返回对一个用户查询的结果，否则用户会很不耐烦了（如果信息量小，这会很简单；但我们现在讲的是从上亿的网页信息中挑出和用户查询相关的东西）。有多种计算机技术有助于来解决上述性能问题，例如设计用户查询cache对提高查询性能就很有好处[10]。然而，我们认为并行和分布处理是解决上述问题最重要的技术途径。“天网”是我们研制的中英文搜索引擎，1997年10月推出1.0版本[1]，正式在CERNET上提供查询服务。该版本采用的是单机结构，维护百万数量级的网页信息，全部网页更新周期为10天。这对于当时网上信息不够

6、丰富的情形来讲，是基本够用的。但是，我们注意到网页数量在爆炸性增长，全世界的网页数量达到十多亿，很多商业的搜索引擎索引网页的规模都是上亿的数量级（例如Google[2]），要达到这个量级，网页的更新是集中式系统在短时间内所不能胜任的。如果以“天网”1.0的速度，要达到1000万量级需要100天，100天中由于网页的更新，将使搜集到的部分网页失去意义。同时，单机系统也无法满足系统对磁盘容量的需求。统计显示，网页的平均长度是13K，一亿个网页的存储需求达到1.3TB，对其建索引会需要更多的磁盘。索引网页的数量增大后，单机的检索系统也无法完成。在100万数量级，天网的查询响应

7、时间在1秒以下。数据规模增大后，单机系统在线提供服务的性能将令用户无法忍受。因此，我们从2000年开始研制“天网”2.0版本，其基本要点是并行化天网的搜集子系统和查询子系统，使新系统可以支持上亿量级的网页，并且有很好的系统可扩展性。该系统已于2001年5月完成并投入使用(http://e.pku.edu.cn)。本文中，我们没有特别仔细地区别术语“并行处理”和“分布处理”的用法。这主要由于在系统实现中的确体现了两种技术的交融：宏观上讲，是因为并行处理提高了性能，由于多台机器的参与使得收集性能和查询性能得到了提高；微观上讲，在实现中也采用了