（计算机系统结构专业论文）基于面向领域搜索引擎的分布式共享存储解决方案.pdf

中文摘要分布式共享存储技术是当今计算机并行技术的主要发展方向之一，在服务器集群、人工智能以及搜索引擎等技术中都有很广阔的应用前景，特别是在搜索引擎方向，近年来有很多理论和技术的新突破。近期研究的面向领域的智能中文搜索引擎课题，其核心算法需要处理高维矩阵。但是单一服务器的存储空间有限而无法对其进行有效地读写。于是，本文结合分布式共享存储技术与智能中文搜索引擎的技术特点，提出了基于面向领域的智能中文搜索引擎的分布式共享存储方案1 d s m 系统( n u t c hd i s t r i b u t e ds h a r e dm e m o r ys y s t e m ) ，为搜索引擎提供一个大容量的和高效的虚拟存储空间和安全可靠的存储服务。本文重点介绍了n d s m 系统的设计思想和体系结构。着眼于业务需求，n d s m系统的设计理念是实现一个易操作的和易扩充的分布式共享存储系统，具体说就是将搜索引擎针对网页相关矩阵的多线程读写操作建立在统一的共享虚拟内存中，这个共享虚拟内存是由n d s m 的接口服务器和次服务器组，在满足c a c h e一致性、存储一致性和服务器负载平衡策略的基础上共同实现的。从功能上看n d s m 系统相对于搜索引擎其它部分是透明的，并且由于具备一定的本地管理功能而和搜索引擎其它模块之间呈现一定的松耦合性。通过对面向领域的智能中文搜索引擎的分布存储系统的功能评估和性能分析，表明该系统理论上具有稳定的性能，可以满足搜索引擎的核心算法对高维矩阵的运算需求。关键词：搜索引擎，高维矩阵，分布式共享存储，虚拟存储空间，一致性，负载平衡a bs t r a c td i s t r i b u t e ds h a r e dm e m o r yt e c h n o l o g y , w h i c hi so n eo ft h em a i nd i r e c t i o n so fc o m p u t e rp a r a l l e lt e c h n o l o g yn o w a d a y s ，h a sv e r ye x p a n s i v ea p p l i c a t i o nf o r e g r o u n di ns e r v e rc l u s t e r , a r t i f i c i a li n t e l l i g e n ta n ds e a r c he n g i n e e s p e c i a l l yi nt h ed i r e c t i o no fs e a r c he n g i n e ，t h e r ea l ep l e n t yo fn e wb r e a k t h r o u g h si nb o t ht h e o r ya n dt e c h n o l o g yi nr e c e n ty e a r s t h ep r o j e c tc a l l e dd o m a i no r i e n t e dc h i n e s ea is e a r c he n g i n ei sr e s e a r c h e dr e c e n t l y , w h o s ek e r n e la l g o r i t h mn e e d st oc o m p u t et h eh i g hd i m e n s i o nm e t r i c e s ，w h i c ha r en o ta b l et ob er e a da n dw r i t t e ni ns o l os e r v e rf o rt h er e a s o no fl i m i t e dm e m o r y f o rs o l v i n gt h ep r o b l e m ，c o m b i n i n gt h et e c h n i c a lf e a t u r e so fd i s t r i b u t e ds h a r e dm e m o r yt e c h n o l o g ya n dt h ep r a c t i c eo fi n t e l l i g e n tc h i n e s es e a r c he n g i n e ，t h i sp a p e rp r o p o s e st h es o l u t i o no fd i s t r i b u t e ds h a r e dm e m o r yb a s e do nd o m a i no r i e n t e dc h i n e s ea is e a r c he n g i n ec a l l e dn d s m ( n u t c hd i s t r i b u t e ds h a r e dm e m o r ys y s t e m ) ，w h i c hp r o v i d e sh i g hc a p a b i l i t ya n dh i g he f f i c i e n c yv i r t u a lm e m o r ys p a c ea n ds a f es t o r a g es e r v i c e t h i sp a p e re m p h a s i z e st h ed e s i g nt h i n k i n ga n ds y s t e mf r a m e w o r ko fn d s ms y s t e m b a s e do nt h eb u s i n e s sr e q u i r e m e n t ，t h ed e s i g ni d e ai st or e a l i z ead i s t r i b u t e ds h a r e dm e m o r ys y s t e mo fe a s yt oo p e r a t ea n de x t e n d s p e c i f i c a l l yt h es y s t e mm a n a g e st h eo p e r a t i o no fm u l t i t h r e a d i n gr e a da n dw r i t t e no i lp a g er e l a t i v em a t r i c e s ，a n de s t a b l i s h e so nt h eu n i t e ds h a r e dv i r t u a lm e m o r y , w h i c hi sa c h i e v e db o t hb yi n t e r f a c es e r v e ra n ds u b s e r v e rg r o u p ，w h e nt h ec a c h ec o n s i s t e n c y , m e m o r yc o n s i s t e n c ya n ds e r v e rl o a db a l a n c es t r a t e g ya l er e a c h e d a c c o r d i n gt ot h ed e s i g nt h i n k i n g ，t h en d s ms y s t e mi st r a n s p a r e n tt oo t h e rp a r t so ft h es e a r c he n g i n e ，a n ds h o w sc e r t a i nl o o s e l yc o u p l e df r o mo t h e ra s p e c t so ft h em a i ns y s t e mf o rt h er e a s o no fa u t o n o m yf u n c t i o no fn d s ms y s t e m b ya n a l y z i n gt h ef u n c t i o n so ft h ed o m a i no r i e n t e dc h i n e s ea is e a r c he n g i n e ，t h i sp a p e rc o n c l u d e st h a tt h i ss y s t e mh 4 sat h e o r e t i c a ls t a b l ee f f i c i e n c y , a n dc o u l ds a t i s f yt h er e q u i r e m e n tf r o mt h ek e r n e la l g o r i t h m sf o rh i g hd i m e n s i o nm a t r i c e s k e yw o r d s ：s e a r c he n g i n e ，h i g hd i m e n s i o nm a r x ，d i s t r i b u t e ds h a r e dm e m o r y ，v i t u a ls t o r a g es p a c e ，c o n s i s t e n c y ；l o a db a l a n c e独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得墨鲞盘鲎或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：赫之杰签字日期：2 口。7 年2 _ 月2 一日学位论文版权使用授权书本学位论文作者完全了解基鲞盘堂有关保留、使用学位论文的规定。特授权鑫盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：孙走莛导师签名名刁丕廓签字日期：沙7年乙月乙日签字日期：沙7 年五月2 - 日第一章绪论1 1 选题背景和研究意义第一章绪论在互联网飞速发展的今天，开放和共享为千万用户提供了不计其数的信息资源，极大地满足了人们工作和生活的各种需要。而能否从浩如烟海的网络世界中，及时找到所需的网络资源，就离不开搜索引擎技术【l 】。这里需要指出的是，当前著名的搜索引擎包括g o o g l e 和百度等在内，都是全方位的通用的搜索引擎，一方面在高效地满足广大用户普通需求的同时，却在某些特定专业领域例如偏僻学科等方面，无法达到该领域用户的实际工作标准。因此，为特定领域量身定做面向领域的搜索引擎，已经成为当前搜索引擎技术发展的一个新亮点。本课题组近年来从事上述面向领域搜索引擎的研究与开发，并承担天津市科技发展计划：面向领域的智能中文搜索引擎( 0 4 3 1 0 9 4 1 r ) 。该搜索引擎主要面向专利查询和股票搜索，当前进展顺利。近期本课题组在该搜索引擎核心算法方面，又取得了一定的理论进展。简单描述即是就是通过用户反馈不断提高排序准确性，其原理是一个用户对同一个搜索词组点击的多个链接必然是相关的，并定义对同一搜索词查询结果的若干链接的点击为同时点击，搜索引擎通过获取这些同时点击的链接，对描述网页相关性的矩阵系进行的更新排列，从而在下一次的相关搜索词查询中，可以获得更加精确的查询结果。对于特定的用户群，这样一个也许只可以获得几百个和领域密切相关的反馈结果的引擎，在搜索效率以及查询结果的友好性上，有望在一定程度上接近g o o g l e 和百度数以万计的松散的查询效果。在该理论的实现步骤中，需要针对点击数据构建网页相关性矩阵，用来评价网页之间的相关程度，并随着新网页的抓取而不断增加维数，这直接关系到查询的精度与速度，可以说对网页相关矩阵的操作是面向领域的智能中文搜索引擎的核心算法所在。需要注意的是，当搜索引擎经历了一定时期的运行进入平稳期时，由于实时处理海量网页数据而需要维护的高维网页相关性矩阵，是无法在单个服务器上进行有效处理与保存的，因此必须考虑对该矩阵进行分布式共享存储。上面提到的网页相关性矩阵从数学角度分析是稀疏矩阵，因此使用三元组的数据结构形式来表示该矩阵，可以在一定程度上减少网页相关信息的存储容量，但是对于单台服务器的存储能力而言仍然是较大的负担，特别是考虑到搜索引擎第一章绪论的数据容量将来可能的扩展，以及用户对查询精度和时间的更高要求，对网页相关信息进行分布式共享存储他3 是唯一可行的选择。事实上对于企业级的搜索引擎而言，想要立足于市场，除了核心算法和市场开发环节，比拼的就是如何利用分布式共享存储的巨大效率，从而使核心算法获得计算能力上的进一步提高。因此，如何开发分布式共享存储系统的更高效能，已经成为提高搜索引擎品质的核心课题。1 2 分布式共享存储系统的研究概况网络技术的飞速发展极大地推动了分布式共享存储技术的进步，同时也给分布式共享存储技术不断提出新的需求。先进的分布式共享存储系统，需要具备如下几个特征：高处理性能、高可靠性、高可扩展性、高度透明性和高度自治性。目前分布式共享存储技术的发展趋势和主要的研究热点如下。1 高处理性能。对分布式共享存储系统的每一个用户，系统都应该能够提供始终如一的高性能存储服务。不考虑硬件和网络设施的因素，系统应该尽可能地克服或缓解网络环境的动态性和不可预知性，对服务性能造成的影响。另外，为了提高数据的访问效率，减少文件传输的网络延迟，系统必须设计合理高效的文件c a c h e 机制、负载平衡算法以及并行传输机制以减小网络延迟，让用户没有远程感觉，为用户提供高品质的存储服务。，2 高可靠性。作为分布式共享存储系统的突出优点之一，高可靠性是大多数分布式系统设计时重点考虑的问题，分布式环境通常都有高可靠性的需求，用户将文件保存到分布式共享存储系统的基本要求是数据可靠。保证数据的高可靠性是分布式共享存储的基本目标，系统应该采用有效的容错机制，使得一些常见故障( 服务器离线或失效、网络断开等) 对用户透明，用户访问文件时，文件不会因为网络故障或部分服务器不在线而不可得，使用户在动态变化的网络环境下获得高可靠的文件服务。分布式共享存储系统的每个组件的设计都必须考虑可靠性，总的指导原则是避免集中式的部件和算法。3 高可扩展性。分布式共享存储系统要能适应服务器规模和数据规模的增长。对于规模需要不断增长的系统，扩展能力非常重要。分布式共享存储系统的体系结构必须具有高可扩展性，系统的存储容量可以随着用户存储需求的增长而增长，以支持海量存储。分布式共享存储系统的可扩展性表现在存储规模、用户数以及系统的总体服务能力。存储容量的扩展不能孤立于系统总体服务能力的扩展，更不能以牺牲服务性能为代价。分布式共享存储系统的扩展能力目标是系统的存储容量和系统的总吞吐率第一章绪论能够随着系统规模的增大而同步增大，而文件访问性能始终较高。分布式共享存储系统必须采用易扩展的拓扑结构和数据组织方式来适应服务器和存储数据规模的动态增长。4 高度透明性脚。如果一个分布式共享存储系统让用户和应用程序感觉和本地存储空间一样，就可以认为它具有透明性。分布式共享存储系统通过内部实现机制和用户接口为用户提供透明的存储服务。在设计和实现分布式共享存储系统时，完全实现以上透明性将付出巨大代价，考虑到系统的性能、需求和实现的复杂度，往往只实现部分透明性。从上述对分布式共享存储技术的研究热点来分析当前的网络系统服务，在开放型的网络环境下，包括搜索引擎在内的各种服务应用已经涵盖了工作和生活的方方面面。而随着信息领域内技术的发展，人们更希望能够在较大范围乃至全球范围内真正意义上一致地共享各种资源，这就要求我们必须从分布式共享存储系统的高度来看待这一问题，以便真正管理好类型多样的数据资源。因此对分布式共享存储系统的进一步研究，已经成为当今世界性的科技热点。每一次分布式共享存储系统的革新与精进，都将给地球村带来更便利、更安全和更友好的全球化服务。就这一点而言，早已超越搜索引擎自身的意义了。1 3 本文的主要研究工作及组织结构本文首先根据当今搜索引擎的最新背景，系统描述了本课题组一直以来从事的搜索引擎技术方面的工作，包括核心算法、组织架构和性能分析。随后在此基础上，结合分布式共享存储的经典理论和最新技术动态，提出了一个专用于本课题组的面向领域的智能中文搜索引擎的分布式共享存储系统。最后对该系统的工程模式和处理效率进行了系统分析，表明该系统应用于面向领域的智能中文搜索引擎，可以较好地提高搜索效率和系统品质。本文的组织结构如下：第一章为绪论，介绍课题的研究背景、研究价值以及分布式共享存储相关的概述，然后列出本文的主要研究工作和组织结构。第二章深入分析和研究了面向领域的智能中文搜索引擎的关键技术，包括网页相关性的概念，评价网页相关性的标准，构建网页相关性矩阵以及用户查询的系统流程，并对面向领域的智能中文搜索引擎的性能进行了评估。第三章根据分布式共享存储技术的最新潮流，以及本课题组的面向领域的智能中文搜索引擎的实际需求，提出了一个实际应用于面向领域的智能中文搜索引擎的分布式共享存储系统n d s m ，并在规划n d s m 的组织体系、c a c h e 一致性协第一章绪论议和存储一致性协议的基础上，完成n d s m 系统的功能模块和管理模块的设计，并在介绍n d s m 的过程中，逐步实现了n d s m 系统的工程流程。第四章在前三章的基础上，从系统吞吐率、调用文件开销、设备利用率和通信开销等六个方面，全方位对该系统进行评估。第五章总结本文的研究工作，并展望根据最新的进展，对未来的研究工作进行规划。第二章面向领域的智能中文搜索引擎模型及相关技术第二章面向领域的智能中文搜索引擎模型及相关技术随着互联网在全球的飞速发展，网页文件总量也达到了惊人的数量。早在2 0 0 4 年2 月，g o o g l e 就宣布将其数据库索引的网页文件数量从原来的3 3 亿增加到4 2 8 亿。而同期y a h o o 则宣称其全文搜索引擎已索引了4 3 亿个网页文件，如果加上图片等多媒体文件，其数量更高达6 0 亿。可见用户要在如此浩瀚的信息海洋里寻找有用信息无疑是很困难的，而且可能会错过一些很有价值的信息却获得一些没有意义的冗余信息。因此驱使搜索引擎技术一直在飞速发展，以应对如此高速递增的网页量。自从1 9 9 4 年出现第一个搜索引擎诞生起，搜索引擎已经发展到了第三代。然而，最新的搜索引擎仍然没有很好地解决第一章所谈到的不足之处，因而需要实现基于用户点击数据优化的，面向领域的智能搜索引擎，以满足特定领域的实际需要。2 1 搜索引擎技术及趋势搜索引擎是用于帮助互联网用户查询信息的搜索工具。它以一定的策略在互联网中搜集发现信息，对信息进行组织和处理，并为用户提供检索服务。从而达到信息导航的目的。搜索技术从本质上解决了信息的关联性问题，通过输入查询关键宇，系统可以对杂乱无章的信息进行筛选，列出与关键字相关的信息，并且根据出现频率自动做出排列，不仅降低了查询时间，而且丰富了查询内容。当前搜索技术已成为网络上必不可少的应用。人们每天都在从因特网上源源不断地获取信息。通过使用搜索技术人们获取信息的强度大大提高。2 1 1 搜索引擎系统架构介绍当前搜索引擎已成为一个全新的研究开发领域，应用从信息检索、人工智能、计算机网络、数据库、数据挖掘、数字图书馆，到自然语言处理等多领域的理论和技术，从而具有综合性和挑战性。又因为搜索引擎有大量的用户，有很好的经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关注。就目前发展前景而言，为满足广大市场对搜索引擎的各种要求，界面友好、功能强大的企业级的搜索引擎应该具备下面两点要求h 1 ：1 十分注意提高信息查询结果的精度，进而提高检索的有效性。用户在搜索第二章面向领域的智能中文搜索引擎模型及相关技术引擎上进行信息查询时，并不十分关注返回结果的多少，而是看结果是否符合自己的需求。对于一个查询，传统的搜索引擎动辄返回几十万、几百万篇文档，用户不得不在结果中筛选，从而影响了查询效率。为了解决查询结果过多的现象，目前出现了几种方法：一是通过各种方法获得用户没有在查询语句中表达出来的真正用途，包括使用智能代理跟踪用户检索行为，分析用户模型；使用相关度反馈机制，使用户告诉搜索引擎哪些文档和自己的需求相关( 及其相关的程度) ，哪些不相关，通过多次交互逐步求精。二是用正文分类( t e x tc a t e g o r i z a t i o n ) 技术将结果分类，使用可视化技术显示分类结构，用户可以只浏览自己感兴趣的类别。三是进行站点类聚或内容类聚，减少信息的总量。2 基于智能代理的信息过滤和个性化服务。信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模型( 如w e b 知识、信息处理、与用户兴趣相关的信息资源、领域组织结构) 、用户模型( 如用户背景、兴趣、行为、风格) 知识进行信息搜集、索引。过滤( 包括兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、对用户有用的信息提交给用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而提供个性化的服务。智能代理可以在用户端进行，也可以在服务器端运行。图2 - 1 通用搜索引擎基本框架第二章面向领域的智能中文搜索引擎模型及相关技术从工作机理上分析，搜索引擎的工作原理大致可以分为如下三个阶段口1 ，这三个阶段通常是在服务器中高速地并行运行：1 搜集信息。搜索引擎的信息搜集基本都是自动的。搜索引擎利用称为网络爬虫( s p i d e r ) 的自动搜索机器人程序来连接每一个网页上的链接。机器人程序根据网页链到其它中的超链接，从少数几个网页开始，连到数据库上所有到其它网页的链接。理论上，若网页上有适当的超级链接，机器人便可以遍历绝大部分网页。2 整理信息。搜索引擎整理信息的过程称为“建立索引”。搜索引擎不仅要保存搜集起来的信息，还要将它们按照一定的规则进行编排。这样搜索引擎就可以不用重新翻查其所有保存的信息而迅速找到所要的资料。如果信息是不按任何规则地随意堆放在搜索引擎的数据库中，那么每次找资料都得把整个资料库完全翻查一遍，从而降低了高品质硬件所能提升的系统整体性能。3 接受查询。用户向搜索引擎发出查询，搜索引擎接受查询并向用户返回资料。搜索引擎每时每刻都要接到来自大量用户的几乎是同时发出的查询，它按照每个用户的要求检查自己的索引，在极短时间内找到用户需要的资料，并批量返回给用户。目前，搜索引擎返回主要是以网页链接的形式提供的，这些通过这些链接，用户便能到达含有自己所需资料的网页。通常搜索引擎会在这些链接下提供若干来自这些网页的摘要信息以帮助用户判断此网页是否含有自己需要的内容。由此可见，搜索引擎的技术基础是全文检索技术，从2 0 世纪6 0 年代，国外对全文检索技术就开始有研究。全文检索通常指文本全文检索，包括信息的存储、组织、表现、查询、存取等各个方面，其核心为文本信息的索引和检索，一般用于企事业单位。随着互联网信息的发展，搜索引擎在全文检索技术上逐渐发展起来，并得到广泛的应用，但搜索引擎还是不同于全文检索。搜索引擎和常规意义上的全文检索主要区别有以下几点哺1 ：1 数据量。传统全文检索系统面向的是企业本身的数据或者和企业相关的数据，其中较大型索引库的数据项数量一般在几百万条左右。但互联网网页搜索需要处理几十亿的网页，搜索引擎的策略都是采用服务器群集和分布式计算技术。2 内容相关性。由于需要处理信息太多，查询的准确性和搜索引擎的排序技术就显得特别重要，g o o g l e 等搜索引擎采用网页链接分析技术，根据互联网上网页被链接次数作为重要性评判的依据。但全文检索的数据源中相互链接的程度并不高，不能作为判别重要性的依据，只能基于内容的相关性排序。3 安全性。互联网搜索引擎的数据来源都是互联网上公开的信息，而且除了文本正文以外，其它信息都不太重要。但企业全文检索的数据源都是企业内部的第二章面向领域的智能中文搜索引擎模型及相关技术信息，有等级和权限等限制，对查询方式也有更严格的要求，因此其数据一般会在保证安全的基础上，集中存放在数据仓库中。4 个性化和智能化。搜索引擎面向的是互联网访问者，由于其数据量和客户数量的限制，自然语言处理技术、知识检索、知识挖掘等计算密集的智能计算技术很难应用，这也是目前搜索引擎技术努力的方向。全文检索由于处理数据量相对较小，检索需求相对更明确，从而有望在智能化和个性化方向得到更多的重视与支持。搜索引擎与全文检索除了以上的区别外，还结合互联网信息的特点形成了三个不同的类型：1 全文检索搜索引擎。全文检索是指计算机索引程序通过扫描文章中的每一个词，为每一个词建立一个索引，并指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表查字的过程。全文检索系统中最为关键的部分是全文检索引擎，各种应用程序都需要建立在这个引擎之上。一个全文检索应用的优异程度由全文检索引擎来决定。2 目录索引搜索引擎。目录索引虽然有搜索功能，但在严格意义上讲不属于真正的搜索引擎，而可以看作是按目录分类的网站链接列表。用户完全可以不用进行关键词查询，仅靠分类目录也可找到需要的信息。用户在查询信息时，可以选择关键词搜索，也可以按分类目录逐层查找。当用户对某关键词进行搜索，则返回的结果跟全文检索搜索引擎一样，也是根据信息关联程度排列网站。如果按分层目录查找，某一目录中网站的排名则是由标题字母的先后顺序决定。3 元搜索引擎。元搜索引擎在接受用户查询请求时，同时在其它多个引擎上进行搜索，并将结果返回给用户，查一个元搜索引擎就相当于查多个独立搜索引擎，可以收到事半功倍的效果。按照搜索机制划分，元搜索引擎包括并行式和串行式两类，并行式元搜索引擎运行时是将查询请求同时发向各个独立搜索引擎，然后将的结果按特定的顺序呈现给用户；串行式元搜索引擎运行时是将查询请求先发向某个独立搜索引擎，待其返回结果后再将请求发往另一个独立搜索引擎。整体来说，并行式元搜索引擎运行模式较好，搜索所需时间也相对较短。2 1 2 搜索引擎专业细化趋势随着搜索引擎市场空间越来越大，搜索引擎的具体分工也越来越细。一个搜索引擎如果要想在搜索市场上有一席之地，必须拥有自己的特色。同时数以亿计的用户会提出各式各样的搜索需求，不同类型的用户需要不同类型的搜索引擎，前面提到的网页搜索只是当前若干搜索需求中的一种，这就决定了搜索引擎需要第二章面向领域的智能中文搜索引擎模型及相关技术不断地细化，各种各具特色的搜索引擎也陆续出现。从技术上讲，各种搜索引擎都具有类似的系统架构，其不同在于搜索的数据源不同。下面列举几个典型的搜索引擎幛1 ：1 新闻搜索引擎。查阅新闻是许多用户上网的主要目的，新闻搜索已经成为查看新闻的重要工具。新闻搜索引擎实现的过程比较简单，一般是扫描国内外有名的新闻网站，抓取新闻网页，建立自己的新闻数据库，然后提供搜索。只是对新闻网页抓取的频率要求很高，需要做到几分钟扫描一次。现在许多大型网页搜索引擎都提供相应的新闻搜索功能，如g o o g l e 新闻搜索和百度新闻搜索等。2 音乐搜索引擎。音乐通过互联网得到了广泛的传播，音乐搜索引擎需要监控互联网上大型的音乐网站，抓取其音乐数据的信息形成自己的数据库，音乐下载和试听都会在其原来的音乐网站上进行。目前有搜刮网和百度m p 3 搜索等。3 图像搜索引擎。通过图像搜索引擎可以找到用户感兴趣的图片链接，各大搜索引擎也提供了图像搜索功能。图像文件本身不能够被搜索引擎索引，但搜索引擎可以通过链接文本分析和图片注解等得到图片的信息。目前有g o o g l e 图像搜索和百度图像搜索等。4 商务搜索引擎。电子商务一直是互联网的热点，商务搜索对电子商务的发展也起到了巨大的推动作用，并让互联网经济和传统经营紧密结合在一起，给传统类型企业提供了一个新的销售模式。商机搜索引擎，通过抓取电子商务网站的商品信息和其他商业信息，给访问者提供统一的搜索平台。目前有e b a y 购物搜索和阿里巴巴搜索等。然而随着w e b 信息的急速增加，专业搜索引擎也面临着海量信息和人们获取所需信息能力的矛盾。一个好的专业搜索引擎不再仅凭借数据库大小、更新频率、检索速度、对多语言的支持这几个基本特性来衡量，如何从庞大的资料库中精确地找到正确的资料，被公认为是下代搜索技术的竞争要点智能化和个性化特色的新型引擎成为未来搜索引擎的发展趋势，同时搜索技术越来越被人们所看好，如何利用搜索技术整合企业和组织内外部信息资源，提供专业和定向的搜索服务，建立企业级搜索引擎也已经成为信息化建设的热点。当前的搜索引擎即面临这样的问题。例如微软可以宣称自己的w i n d o w s2 0 0 3 服务器很易用和稳定，并且容易管理。但在搜索引擎上，拼的是巨大的计算能力和超强的分布式共享存储能力，这些其实都是w i n d o w s 操作系统天生的缺陷。要想依赖w i n d o w s 作为服务器，即便微软的技术再高，在同样的投入下，肯定无法产生出像g o o g l e 那样的计算能力。没有足够的计算能力，再好的技术也无法发挥其所长。总而言之，搜索引擎已经进入到新的竞争范畴，很多参数的第二章面向领域的智能中文搜索引擎模型及相关技术计算都需要大规模的分布式技术的深入应用。2 2 面向领域的智能中文搜索引擎模型2 2 1 设想与原理判断一个搜索引擎的优劣的关键，就是在于要尽可能地把与检索关键词相关性最好的结果排在前面，这也就是网民选择搜索引擎的最主要的依据根据最新的统计信息。目前的研究、开发十分活跃，出现了很多值得注意的动向，本课题组选择下面两点作为研究的重点：首先，即是采用分布式体系结构提高系统规模和性能。搜索引擎的实现可以采用集中式体系结构h 1 和分布式体系结构，两种方法各有千秋。但当系统规模到达一定程度时，必然要采用某种分布式方法，以提高系统性能。搜索引擎的各个组成部分，除了用户接口之外，都可以进行分布。其次，是通过用户反馈提高排序准确性。这是一种全新的方法正在被业内研究，就是通过用户反馈提高排序准确性。其原理是，+ 一个用户对同一个搜索词组点击的多个链接必然是相关的。搜索引擎通过获取这些数据智能的更高标准满足用户需求的排列。用p- l o -第二章面向领域的智能中文搜索引擎模型及相关技术图2 2 通用搜索引擎的整体架构图2 2 是通用搜索引擎的系统结构，而面向领域的智能中文搜索引擎的详细设计由于本文主题所限不会具体呈现。接下来本文将重点讲述网页相关矩阵的理论基础，以及其在面向领域的智能中文搜索引擎的算法体系中所处的核心地位，进而从另一个角度，体现出分布式共享存储技术对于面向领域的智能中文搜索引擎的进一步发展所能提供的结构化的支持，以及特别针对高维网页相关矩阵的稀疏特点进行优化的设计理念。根据本课题组的理论储备，关于自然语言处理嘲的统计学范式能否有效达致语义层面，在领域内仍有较多争议，就当前前沿技术水平而言，实现语义分析最可靠的方法仍是人工标注。但是大规模网页库的标注工作量极为浩繁，几乎不可能人工实现。因此对于在搜索引擎环境下的语义相关性分析任务，利用用户的c o c l i c k 数据判定网页之间的语义相关性是一种自然的思路。所谓c o c l i c k 数据，可以理解为用户在某关键字的查询结果集中，在较短时限内所点击的若干反馈项，而这些被同时点击的反馈项即可组成c o c l i c k 数据。可以比较直观的理解，就是用户在查询某关键字的结果集中，有目的有选择所点击条目，相对于其它条目，其与用户所查关键字的相关性是更为紧密的，也就是说c o c l i c k 数据可以更趋近于用户真实所需。这种方法的可行性在于：假设用户的查询有明确目标，且用户可根据网页的简单摘要判定网页与查询目标之间的中肯程度，则两个页面被同时打开得越频繁，说明它们的语义内容相关性越强。这里，用户的c o c l i c k 行为可看作是一种特殊的语义相关性的人工标注，虽然用户点击网页的目的并非是要实现人工标注任务。通过这种方式，可以在将统计自然语言处理范式较强的数学背景和语义模型范式直观自然的优势的有机地结合在一起。既然检索系统服务于用户查询，则利用用户的c o c l i c k 定义网页差异性具有直观的合理性：统计上说，如果两个网页被用户同时打开的频率越高，这两个网页的内容对用户而言就越相关。假设系统运行了足够长的时间，则由此建构的差异性矩阵即使不能充分近似网页之间的内在差异性，也可以有效改善搜索引擎所提供的查询结果的中肯性，这种中肯性的获得依赖于大量用户在真实情境下的实际判断。为了对搜索引擎做出优化，须利用用户点击数据优化搜索引擎，近期本课题组所做的事情即上述两点，简单说来就是首先拦截用户反馈，得到相关性数据，然后通过这些数据改进排序的准确性。本课题组前期采用修改一个成熟的、开源第二章面向领域的智能中文搜索引擎模型及相关技术的搜索引擎n u t c h 阳1 来实现这个全新的功能。2 2 2 核心算法描述在这一小节，本文将简要描述通过本课题组最新的网页相关性原理，对面向领域的智能中文搜索引擎的模型进行系统升级。一方面通过对数学模型的验证，得出可行性的结论；另一方面会讲述高维的网页相关矩阵的推导过程和调用方式，从而证明其作为本算法的核心组成部分的理论依据。在接下来的章节，会体现出对高维网页相关矩阵进行分布式共享存储，能够给系统的整体性能和搜索品质上的提高。首先对接下来的算法符号进行约定：n ：网页的数目d o ：n xr l 的初始网页差异性矩阵d ：1 3 x n 的网页差异性矩阵c ：n x n 的基于用户点击的差异性矩阵c ：n xd 的基于c 的压缩矩阵a ：同时访问计数矩阵b ：点击计数向量下面将对本搜索引擎的核心数据结构进行简要说明。在外存上维护一个两个n n 矩阵：差异性矩阵c 和相关计数矩阵h 。c 用来存储网页之间的定量化的差异性，a 用来存储网页在同一个用户查询事务中被同时访问的计数。算法简述入下：1 由某种方法( 例如人工分类或自动聚类) 获得初始网页差异性矩阵c 。2 对于每个用户查询事务，执行根据基于网页差异性的查询结果生成算法生成一组查询结果，并将其按一定的次序提交给用户。3 用户将会打开系统提交的若干网页，记录用户所打开的所有网页，并执行：对于任何两个被同时打开的网页i 和j ，a i 3 ：= a i j + l 。设t 为所有被打开的网页中提交次序最靠后的一个，则将t 之前所有未被打开的网页与被打开的网页之间的同时访问计数减1 。4 系统定期根据a 重新计算c ，并对c 做维数约减，获得其压缩几何表示，每个网页被表示为一个d 维空间中的点，d n ，网页之间的差异性由点到点欧氏距离反映。所有网页的几何表示形成了n x d 矩阵c 。数据结构说明：算法需利用上一节生成的矩阵c ，c 为一个n x d 矩阵，每个网页被表示为一个1x d 向量，d n ，网页之间的差异性由向量间的欧氏距第二章面向领域的智能中文搜索引擎模型及相关技术离反映。算法的输出为一组有序的查询结果。算法简述：对于一个用户查询事务1 根据常规方法获得一组基本查询结果。2 利用矩阵c ，计算基本查询结果的加权重心，权重简单设为查询关键词在该网页中的出现次数。3 利用矩阵c ，计算基本查询结果中各个网页与加权重心的距离大小，确定基本查询结果被提交给用户的次序。最新的面向领域的智能中文搜索引擎在磁盘中维护一个n x n 的差异性矩阵d ，其第i 行第j 列元素d 。，表示网页i 与网页j 之间定量化的差异性；同时，在内存中维护d 的压缩表示y ，y 是n x d 矩阵，d 取极值时，e 形 不一定能取到极值，而且e s 与搜索引擎业务服务时间的具体分布相关，根据上文所述符合系统性能的负载平衡优化要求。综上所述，当以n d s m 系统以访问业务的最小平均等待时间为目标时，越是较大的业务其等待时间越长，在最终平均等待时间中占有的比重最大，从而在搜索引擎的访问及修改操作在整个业务中，可能会造成小的任务有相对较大的延迟。相比之下相对延迟反映的是每个任务延迟的相对量，同样的相对延迟任务越小则延迟越短，而大任务具有较长的延迟时间d 羽。因此采用相对延迟来衡量系统的性能更为合理一些。可见采用基于请求长度的s i t e 算法有可能对多服务器的性能有一定的改进。而对于面向领域的智能中文搜索引擎技术而言，由于将来会涉及到大量数据的并行批量处理，因此，应当在早期建立系统架构的时候，为将来可能应用的功能准备好相应的优化策略。3 7 n d s m 系统的功能模块n d s m 系统的功能模块主要可以分为三大部分。( 1 ) 初始化模块( 2 ) 共享存储模块( 3 ) 通信模块在下文的几个小节里，本文将详细的讨论各个管理模块的结构和体系，以及工作流程。3 7 1 初始化模块n d s m 系统的初始化是在接口服务器进行的，通过接口服务器中的启动配置文件s t a r t u p n d s m i n f o 来获取当前系统整体的有关信息，如服务器名、用户名和口令等。另外每个次服务器根据自己在s t a r t u p n d s m i n f o 中的顺序就可以决定其编号和总的次服务器数量，并刷新接口服务器的c a c h e 。接下来通常由s t a r t u p n d s m i n f o 中的第一个服务器也就是接口服务器来负责启动次服务器组的初始化进程。n d s m 系统初始化要完成的工作主要如下列步骤。第三章基于面向领域的智能中文搜索引擎的分布式共享存储方案( 1 ) 在次服务器系统中分配所必须的核心存储空间，刷新本地c a c h e 。( 2 ) 根据日志文件将上次结束时c a c h e 中的数据单元重新装入c a c h e 。( 3 ) 为每台服务器建立通信机制。( 4 ) 在每台次服务器上启动n d s m 的系统服务线程。( 5 ) 等待搜索引擎对接口服务器的访问及修改操作。经过上述步骤，n d s m 系统就可以正常启动，一方面接受搜索引擎的查询和修改业务，另一方面通过自身的机制完成对系统内部的资源整合。3 7 2 共享存储模块n d s m 系统的地址空间结构采用共享存储单地址系统结构】，实现全局的虚拟地址空间。共享存储单元全局编址每个服务器维护一个虚拟的远程c a c h e ，用于缓存若干台次服务器上的共享数据单元。远程c a c h e 中远程数据单元的地址与它在源次服务器的地址是一致的。所以当发生远程访问时，不需要进行地址的转换。另外，由于共享空间分布在所有服务器上，其容量不受一台机器实际存储空间的限制，所以n d s m 系统理论上可以动态存储规模较大的矩阵映像。在n d s m 系统中目录不再用来保存所有共享数据单元的全部信息，而只记录本地共享存储单元以及c a c h e 中远程共享数据单元的相关信息。对于每一数据单元来说，需要记录其保护状态，即有效或无效。有效是指其本地服务器和远程服务器都可以对其进行操作，无效是指对其操作都会引起中断，通过源次服务器找到其最新备份所在的次服务器，从而获得最新的数据单元。i从以上分析可以看出，n d s m 存储空间组织方式有如下优点。( 1 ) 虚拟远程访问时，不再需要进行地址的转换，从而提高了平均访问速度。( 2 ) 共享存储空间分布在所有的服务器之上，其容量不受某台服务器的实际存储空间的限制，并且易于扩展。对于搜索引擎而言，数据量增长的速度往往是比较迅速的，因而n d s m 系统有望在可扩展性上较好地满足实际应用的需要。3 7 3 通信模块由于n d s m 系统在在面向领域的智能中文搜索引擎中处于比较封闭的环境，从而可以保证比较优质的网络传输质量和比较安全的网络传输环境，因此在1 1 d s m 中缺省使用) p 协议。u d p 协议是英文u s e rd a t a g r a mp r o t o c o l 的缩写，即用户数据报协议，主要用来支持那些需要在计算机之间传输数据的网络应用。包括网络视频会议系统在内的众多的客户服务器模式的网络应用都需要使用u d p 协议。u d p 协议从问世至今已经被使用了很多年，但是即使是在今天，u d p 仍然不失为一项非常实用和可行的第三章基于面向领域的智能中文搜索引擎的分布式共享存储方案网络传输层协议。u d p 协议使用端口号为不同的应用保留其各自的数据传输通道。u d p 和t c p协议正是采用这一机制实现对同一时刻内多项应用同时发送和接收数据的支持。数据发送一方将u d p 数据报通过源端口发送出去，而数据接收一方则通过目标端口接收数据。数据报的长度是指包括报头和数据部分在内的总的字节数。因为报头的长度是固定的，所以该域主要被用来计算可变长度的数据部分。数据报的最大长度根据操作环境的不同而各异。从理论上说，包含报头在内的数据报的最大长度为6 5 5 3 5 字节。u d p 协议使用报头中的校验值来保证数据的安全。校验值首先在数据发送方通过特殊的算法计算得出，在传递到接收方之后，还需要再重新计算。如果某个数据报在传输过程中被第三方篡改或者由于线路噪音等原因受到损坏，发送和接收方的校验计算值将不会相符，由此u d p 协议可以检测是否出错。这与t c p 协议是不同的，后者要求必须具有校验值。u d p 协议是建立在i p 协议基础之上的，用在传输层的协议u d p 和礤协议一样是不可靠的数据报服务。u d p 的头格式为：0】63 2u d p 结构在中的定义为：t y p e d e fs t r u c tu d p h d r u _ i n t l6 _ ts o u r c e ；u _ i n t ltd e s t ；u i n t l ql e n ；u _ i n t l6 jc h e c k ；) ；u d p 协议具有以下几个特性：( 1 ) u d p 是一个无连接协议，传输数据之前发送端和接收端不建立连接，当传送时就简单地去抓取来自应用程序的数据，并尽可能快地把其发布到网络上。在发送端，u d p 传送数据的速度仅仅是受应用程序生成数据的速度、计算机的能力和传输带宽的限制；在接收端，u d p 把每个消息段放在队列中，应用程序每次从队列中读一个消息段。第三章基于面向领域的智能中文搜索引擎的分布式共享存储方案( 2 ) 由于传输数据不建立连接，因此也就不需要维护连接状态，包括收发状态等，因此一台服务机可同时向多个客户机传输相同的消息。( 3 ) u d p 信息包的标题很短，只有8 个字节，相对于t c p 的2 0 个字节信息包的额外开销很小。( 4 ) 吞吐量不受拥挤控制算法的调节，只受应用软件生成数据的速率、传