Board 版 (精华区)

发信人: WeskitKeeper (马甲守护神), 信区: Board
标  题: [范文]基于Web的百万级FTP搜索引擎的设计与实现
发信站: 哈工大紫丁香 (Sat Nov 12 10:24:13 2005), 转信

基于Web的百万级FTP搜索引擎的设计与实现

陈华  罗昶  段晖  薛明  王建勇

北京大学计算机系网络与分布式系统研究室

  摘要

在因特网上对众多FTP站点进行快速的文件查找，是网络信息搜索的重要组成部分。本文以“天网”FTP搜索引擎为例，介绍了百万级FTP搜索引擎的设计与实现，并重点分析了系统所采用的关键技术和方法。

关键词 FTP, 搜索引擎，WWW

Design and Implementation of Web-based FTP Search Engine

Chen Hua, Luo Chang, Duan Hui, Xue Ming, and Wang Jianyong

Computer Networks and Distributed Systems Laboratory

Department of Computer Science and Technology, Peking University

Abstract

    FTP Search Engine is a powerful tool to search useful files for users from various resourceful FTP sites. In this paper, mainly described are the design and implementation of our FTP search engine, as well as the key technologies and methods we adopt.

Keyword FTP, Search Engine, World Wide Web

1.      引言

根据中国互联网络信息中心(CNNIC)有关中国Internet发展状况统计报告（截止到1999年底），中国上网用户数是890万。每年网民的增长率超过300%。而搜索引擎则是除电子邮件以外网民使用最多的服务。与相对众多的WWW搜索引擎相比，功能强大的FTP搜索器并不常见，由此限制了人们对具有大量信息与资源的FTP站点的访问。实现一个高速、海量、功能强大而又基于WEB的FTP搜索引擎将为网络用户提供极大方便。为此，北京大学计算机系网络与分布式系统研究室最新开发出了“天网”FTP搜索引擎，并已作为“天网”中、英文搜索引擎[1,2]的一个子系统在网上提供服务,获得了广大用户的一致好评。本文将从“天网”FTP搜索引擎的系统结构与算法出发阐述一种百万级FTP搜索引擎的设计与实现的方案。

2.      FTP搜索引擎的系统结构设计

FTP搜索器与WWW搜索器都是对字符串进行匹配与查找，以找出网络文档的链接，但FTP搜索器与WWW搜索器有很大不同。比如FTP搜索引擎不要求显示结果的内容摘要，对FTP站点各目录的数据刷新要求有不同的刷新速率，查询时需要文件信息、站点信息过滤等。因而设计FTP搜索器时应从网络用户对FTP搜索的实际需要出发，重点实现数据的实时性、搜索的快速性和功能的强大性。

 

2.1 系统结构

系统结构的好坏决定了开发周期的长短、系统的稳定性和高效性，甚至决定了系统最终是否能够成功实现。从使用分布式计算和系统模块化的角度出发，我们设计了以下这种方案并在“天网”FTP搜索引擎上成功实现。

[图1]  FTP搜索引擎的系统结构

 

在这个方案里，搜索服务器作为Client/Server机制的Server端提供服务，作为Client端的CGI程序可用远程连接的方法与之传递信息，同时搜集建库程序也可和服务器分离并行运算。因而CGI程序与网页、服务器和搜集建库程序是三个相对独立的模块。我们可以把CGI程序和网页放在Web服务器上，搜索服务器运行在具有大量硬盘空间和充足内存的高速机器上，而搜集建库程序运行在网络带宽大的机器上。它们同处于一个局域网内，用TCP/IP协议互相通讯。分布运算使Web服务、搜索服务与搜集建库可以并行执行，从而减轻了单机的负载，避免了单一服务器瓶颈问题。

2.2 数据库结构

    在上述方案中，数据库分为原始数据库和目标数据库，分别由搜集程序和建库程序生成。设立原始数据库的好处有几个方面，如可优化目标数据库，多线程同时对多个站点搜集数据而互不干扰，对优先目录进行更高频率的独立搜集，以及对所有数据统一编号使输出结果具有顺序性等等。在原始数据库中， FTP站点的优先根目录下的所有文件信息（如文件名、路径、大小、上次更改时间等）以独立文件存储，如ftp.pku.edu.cn的Incoming目录下的文件信息保存为ftp.pku.edu.cn_incoming文件，该站点其它根目录下所有文件信息保存在ftp.pku.edu.cn文件里。

目标数据库是直接用于搜索的数据库，它关系到搜索服务的速度与效率。它由索引文件、信息文件（用于过滤结果）和保存文件名和路径的显示文件（用于输出显示）组成。我们采用单字母倒排表的方式组织索引表。目标数据库中包含256个单字母索引文件，一个字母对应一个索引。其中信息文件和所有索引文件常驻内存，显示文件在输出结果时才被打开读取。对每一个FTP站点的文件，将其文件信息如创建时间，大小，文件类型等非字符串定长数据以及一个指向显示文件中对应的文件名和路径字串起始位置的偏移指针（Offset）记录在信息文件里，由数据在信息文件的位置获得该文件的唯一编号（ID）。同时在文件名的每个字母对应的单字母索引里生成以ID为高24位，该字母在文件名内的偏移为低8位的32位索引项。目标数据库结构如图2所示：

 

[图2 ]  FTP搜索引擎的目标数据库组织

 

3.      FTP搜索引擎的实现技术

3.1 搜集建库程序

    搜集建库运行的时机与频率是保证数据实时性的重要因素。由于搜集时要访问众多的FTP站点、进行大量的网络数据传输，因而搜集应在网络速率比较快的时候进行，一般来说凌晨3、4点是最佳时机。根据FTP站点内每个目录内容更新快慢的不同我们指定了一些优先目录。搜集程序以较高的频率刷新优先目录的原始数据库，并定时刷新所有的原始数据库。为了加快搜集的速度，我们采用多线程方式同时搜集多个站点的文件信息，并指定一个超时时间，以结束所有搜集，并转入建库程序。

    建库程序将原始数据库转化为临时的目标数据库。完成后通知服务器暂停搜索服务，用更改名称的方法将临时的目标数据库迅速切换为最终目标数据库，服务器重新读入目标数据库的索引文件和信息文件，开放对外搜索服务。

3.2 服务器的实现

    服务器是系统的核心，必须保证稳定性和高效性。实现高效性的关键在于使用线程，即一个用户请求使用一个线程处理。由于用户的搜索请求具有随机性和并发性，因而线程互斥、死锁预防、资源的管理等是服务器必须解决的重要问题。另外，对于由于某种原因（如内存不足、I/O错误等）不能正常完成搜索任务的线程，必须正确而完整的释放它申请的资源（如申请的内存、打开的文件、打开的Socket以及线程本身），并向用户显示不能完成任务的原因。安全性也是服务器要考虑的一个方面。服务器采用了TCP/IP作为与CGI通讯的协议，因而可能存在其它程序乃至网络黑客的非法连接。我们可以采用一种简单的身份验证机制保证安全，即CGI与服务器连接时先输入一个约定口令，若口令错误，则服务器直接关闭这个非法连接，从而确保了服务器的安全性。

在上述方案中，服务器会接收到来自CGI的搜索请求或搜集建库程序的更新数据库请求。接到更新数据库请求后，服务器暂停接收CGI的搜索请求，读入新的数据库，然后继续对外服务。接到搜索请求时，由CGI发送来的请求信息确定要匹配的串和过滤信息。由搜索串检查Cache是否命中（Cache是以搜索串为文件名，以匹配结果的所有ID为内容的文件），若命中，读入Cache，进行信息过滤，输出结果。否则，重新在数据库里查找，将结果过滤输出，然后将没过滤的结果ID串写入以搜索串为文件名的Cache文件中。输出结果给CGI时，由ID找到对应的文件信息记录，并由文件信息记录找到文件名与路径，最后以字符串格式发给CGI。服务器响应流程如图3：

[图3] 服务器响应流程 

查找是基于数据库里单子母倒排表的操作，通过提取两条索引中高24位（ID值）相等、低8位（字母在文件名中的偏移）有确定差值的索引项获得结果。具体而言，对连续的两字母串（如 ab ），取后一字母索引（b）与前一字母索引(a) 中ID相等的项，若后一索引（b）中的偏移大1，则为所求结果的一项。而对于 a?b、a??b等，则取偏移大于2、大于3即为所求结果。对于a*b, 则要求字母在后一索引（b）中的偏移大于它在前一字母索引(a) 中的偏移。

3.3 网页设计与CGI程序

    网页是FTP搜索引擎的用户界面。美观大方、使用方便以及兼容不同操作系统下不同浏览器是网页设计的标准。用户的输入页面有两种：简单查询与复杂查询页面。简单查询只有一个输入框用以输入要搜索的字串，其它限制信息由CGI缺省给出。简单查询可以和WWW查询集成，由用户选定使用WWW搜索器还是FTP搜索器查找。复杂查询由一个复杂表单供用户选定各种过滤，如时间，大小，站点，类型过滤等。

CGI程序从网页表单的提交或直接由URL得到搜索要求，进行错误检查。发往服务器，服务器将过滤后的结果信息返回，CGI程序按此生成网页。由于大部分情况下搜索结果在一页内显示不了，因而要采用换页机制。即CGI程序向服务器提供起始显示项号和最大显示项数，由服务器过滤，将可显示的结果信息返回给CGI程序。CGI程序由服务器给出的结果总数和起始显示项号生成换页链接。在北大“天网”FTP搜索引擎里，我们采用了一种智能的换页方案：将当前的起始显示项号对应的链接放在链接表的中间，以最大显示项数为间距生成有限个向后和向前的链接。这样用户可以保持鼠标不动的情况下，以相同的间距向前或向后翻页。如图4所示为最大显示数为20时的一种情况：

 

 0  20   50   70   90   110  130  150  170  190  210  230  250  270  290  310

50  70   90   110  130  150  170  190  210  230  250  270  290  310  330  350

90  110  130  150  170  190  210  230  250  270  290  310  330  350  370  390

                                                       ▲鼠标不动,每次跳过40个

[图4 ]一种智能的换页方案

 

4. FTP搜索引擎的特色功能

由上文可知，ID用24位Bit保存，远大于100万，要增大数据总量，只需增大内存，扩大搜集规模即可。搜索引擎的大小、时间过滤比较简单，我们主要讨论一下一些新的功能及其实现。

（1）结果中再搜索功能。基本上所有WWW搜索器均具有此功能，在FTP搜索引擎中也是必不可少的。首先，用要再搜的匹配串得到新结果；其次，由于在Cache中，必定保存了原先的搜索结果，将它读入内存。将新结果与原来的结果作“与”操作，即得结果中再搜索结果。

（2）多站点选择过滤。指定一个或多个站点搜索，将给用户带来极大方便，例如用户可以只搜对他（她）而言比较快的FTP站点，或他（她）比较喜欢的站点。指定一个最大站点数，如128，用4个32位数放在文件信息中，每个搜集到的文件其所在站点号对应位为1，其余位为0。在CGI端，用户选定的多个站点转变为4个32位数，传给服务器。在结果过滤时，若文件信息里的4个32位数与用户提交的4个32位数“与”不为零，即文件过滤为真，这样就可同时过滤多个站点。

（3）类型过滤。有时用户希望得到一类的文件，而不是一种文件。如用户希望查找所有图象文件，让用户输入一大堆图象文件的扩展名并不方便。我们可以在服务端对文件进行分类，如分为图象、视频、音乐、文档、程序、目录等，将文件类型存在文件信息记录里，结果过滤时将CGI提交的类型限制与文件信息里的类型进行比较即可。

5. “天网”FTP搜索引擎的系统现状及展望

    目前，“天网”FTP搜索引擎采用了上述结构与算法并成功发布，对“天网”用户提供了海量级的文件查询服务。它所搜索的最大文件数已达到150万，数据来自30多个FTP站点（可添加），每天凌晨自动更新优先目录，每三天自动跟新所有站点。在130万的数据量下，查无*、?的多个字串，可在0.5秒内显示结果；在Cache命中的情况下，任意字串的搜索都能在0.3秒内显示结果。最新的数据表明，“天网”FTP搜索引擎的日访问量持续上升，已接近一万。展望未来，我们还可在此搜索引擎的基础上提供更多服务，如对用户点击下载的软件以及软件所在的站点计数，实现热门软件下载排名与FTP酷站排名等。

6.      结束语

本文从北大“天网”FTP搜索引擎的结构与算法出发，分析了基于web的百万级文件查询系统的设计与实现，提供了一种高效、海量、功能强大的FTP搜索引擎方案。在系统的设计和实现过程中得到了北京大学计算机系网络与分布式系统研究室陈葆珏教授以及其他老师和同学的关心和支持，在此一并表示感谢。

 

主要作者简介：

陈华  1978年出生，籍贯广东，正在北京大学计算机科学技术系攻读学士学位

罗昶  1978年出生，籍贯广东，正在北京大学计算机科学技术系攻读学士学位
王建勇 工作于北大计算机系，讲师，博士，研究方向：分布式系统与算法、搜索引擎技术

参考文献：

[1]  雷鸣，刘建国，王建勇，陈葆珏。一种基于词典的搜索引擎系统动态更新模型。已被《计算机研究与发展》录用。

[2]  Jianguo Liu, Ming Lei, Jianyong Wang, and Baojue Chen. Digging for gold on the Web: Experience with the WebGather. Accepted by the HPC/Asia 2000 Conference., IEEE Computer Society Press, May 2000, Beijing, P.R.China

 

--

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.236.206]