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

“天网”中的并行与分布处理
摘要 本文介绍了“天网”,主要包括搜集子系统和查询子系统两个部分。通过对设计、模拟、实现和实际运行评测等相关过程的描述,展现了系统在性能、负载平衡和扩展性等方面的性质和特点。
关键词 索,分布式系统,并行处理
Parallel and Distributed Processing in WebGather
Abstract This paper presents parallel and distributed architectures and key technologies employed in crawling subsystem and retrieving subsystem of WebGather search engine version . Characteristics of the system, in terms of performance, load balance and scalability, are shown through design, simulation, implementation, and actual running measurement.
Keywords WWW, search engine, information retrieving, distributed system, parallel processing
引言
随着因特网上信息的爆炸性增长,搜索引擎已成为人们用得最多的网络应用程序之一。有报道称[5],搜索引擎是除电子邮件系统外用户最多的网上应用程序(不过我们认为浏览器的用户应该更多些)。提供良好的搜索引擎服务,不仅是各类大型门户网站的一个基本配置,也是和年5月召开的第10届World Wide Web学术会议上,一共有24个学术分组报告会,其中4个就是直接和搜索引擎技术相关;78篇论文中有15篇讲的是搜索引擎技术[6]。
搜索引擎,作为一个网络软件系统,主要追求三个方面的指标。一是规模,即要能够维护足够多的网页信息。目前,中国因特网上的公开网页估计约有5000万个(根据[7]和“天网”最近一次收集的估计),每个网页纯文本信息大约13KB,要收集并维护这样一个量级的数据,并提供相应的查询服务,对系统是一个基本的挑战。二是性能,这是本文下面主要讨论的。三是质量,即要提供用户满意的查询结果。这方面本身是一个很复杂的问题,本文不做讨论,有兴趣的读者可参见[8,9]。
性能大致上可归结为两个方面。一是搜索引擎的网页搜集子系统要能够在不太长的一个时间段里(例如20天)完成网页的搜集过程(目前是5000万左右,想象今后会是1亿、2亿、10亿等),否则搜索引擎维护的信息的
“新鲜度”就不高了。二是搜索引擎的查询服务子系统要能在“秒”量级的时间里返回对一个用户查询的结果,否则用户会很不耐烦了(如果信息量小,这会很简单;但我们现在讲的是从上亿的网页信息中挑出和用户查询相关的东西)。有多种计算机技术有助于来解决上述性能问题,例如设计用户查询cache对提高查询性能就很有好处[10]。然而,我们认为并行和分布处理是解决上述问题最重要的技术途径。“天网”是我们研制的中英文搜索引擎,[1],上提供查询服务。该版本采用的是单机结构,维护百万数量级的网页信息,全部网页更新周期为10天。这对于当时网上信息不够丰富的情形来讲,是基本够用的。但是,我们注意到网页数量在爆炸性增长,全世界的网页数量达到十多亿,很多商业的搜索引擎索引网页的规模都是上亿的数量级(例如Google[2]),要达到这个量级,网页的更新是集中式系统在短时间内所不能胜任的。如果以“天网”,要达到1000万量级需要100天,100天中由于网页的更新,将使搜集到的部分网页失去意义。同时,单机系统也无法满足系统对磁盘容量的需求。统计显示,网页的平均长度是13K,,对其建索引会需要更多的磁盘。索引网页的数量增大后,单机的检索系统也无法完成。在100万数量级,天网的查询响应时间在1秒以下。数据规模增大后,单机系统在线提供服务的性能将令用户无法忍受。
因此,我们从2000年开始研制“天网”,其基本要点是并行化天网的搜集子系统和查询子系统,使新系统可以支持上亿量级的网页,并且有很好的系统可扩展性。该系统已于2001年5月完成并投入使用(.)。
本文中,我们没有特别仔细地区别术语“并行处理”和“分布处理”的用法。这主要由于在系统实现中的确体现了两种技术的交融:宏观上讲,是因为并行处理提高了性能,由于多台机器