基于web的百万级ftp搜索引擎的设计与实现

基于web的百万级ftp搜索引擎的设计与实现

第!"卷第%期!"""年%月

文章编号：（!"""）)""),%"+)"%,""*+,"’

计算机应用

6=>IJ:/;5IIEFC?:F=9KL=E-!"M7=-%G/I-M!"""

基于./0的百万级123搜索引擎的设计与实现

陈华，罗昶，王建勇，段晖，薛明

（北京大学计算机系网络与分布式系统研究室，北京)""+&)）

介绍了百万级123搜索引擎的设计与摘要：本文以“天网”123搜索引擎为例，

实现，并重点分析了系统所采用的关键技术和方法。

搜索引擎；关键词：123；...

中图分类号：23’%’-4文献标识码：5

)引言

根据中国互联网络信息中心（67786）有关中国

（截止到)%%%年底），中国89:/;9/:发展状况统计报告

上网用户数是+%"万。每年网民的增长率超过’""<。而搜索引擎则是除电子邮件以外网民使用最多的服务。与相对众多的...搜索引擎相比，

由此限制了人们功能强大的123搜索器并不常见，

对具有大量信息与资源的123站点的访问。实现一个高速、海量、功能强大而又基于./0的123搜索引擎将为网络用户提供极大方便。为此，北京大学计算机系网络与分布式系统研究室最新开发出了

并已作为“天网”中、英文搜索“天网”123搜索引擎，

［)］

引擎的一个子系统在网上提供服务，获得了广大用户的一致好评。本文将从“天网”123搜索引擎的系统结构与算法出发阐述一种百万级123搜索引擎的设计与实现的方案。

系统在用户端以...网页的形式供浏览器浏

程序进览，通过调用6(8（6=>>/9:(?:/@?A89:/;B?C/）

因而在服务端行搜索。6(8是个短生命周期进程，

需要有专用的搜索服务器以提高效率。6(8程序使用263D83协议与服务器连接。服务器将主要数据库读入内存，由6(8程序提供的搜索请求提供快速搜索服务。同时，数据库的生成需要一个搜集建库程序。考虑优先目录的搜集频率不同以及用并行搜集建库以解决网络传输速度问题，将数据库分为原始数据库与目标数据库。搜集程序将搜集的原始结果直接写入原始数据库，建库程序依靠原始数据库生成最终使用的目标数据库。整个系统结构如图)

所示：

!123搜索引擎的系统结构设计

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

重点实现数网络用户对123搜索的实际需要出发，

据的实时性、搜索的快速性和功能的强大性。!-)系统结构

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

图)123搜索引擎的系统结构

在这个方案里，搜索服务器作为6EF/9:DG/;H/;机

作为6EF/9:端的6(8程序可制的G/;H/;端提供服务，

用远程连接的方法与之传递信息，同时搜集建库程序也可和服务器分离并行运算。因而6(8程序与网页、服务器和搜集建库程序是三个相对独立的模块。

搜我们可以把6(8程序和网页放在./0服务器上，

索服务器运行在具有大量硬盘空间和充足内存的高速机器上，而搜集建库程序运行在网络带宽大的机器上。它们同处于一个局域网内，用263D83协议互

收稿日期：（修改稿）基金项目：国家%&’重大基础研究基金资助（()%%%"’!&"*）!"""#"$#!$

作者简介：陈华（)%&+,），男，广东人，在读本科学生；罗昶（)%&+,），男，广东人，在读本科学生；王建勇（)%*%,），男，山东人，讲师，博士，研究方向：分布式系统与算法、搜索引擎技术-万方数据

基于web的百万级ftp搜索引擎的设计与实现

第E期陈华等：基于!"#的百万级&’(搜索引擎的设计与实现7E

相通讯。分布运算使!"#服务、搜索服务与搜集建

库可以并行执行，从而减轻了单机的负载，避免了单一服务器瓶颈问题。$%$数据库结构

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

目标数据库是直接用于搜索的数据库，它关系到搜索服务的速度与效率。它由索引文件、信息文件（用于过滤结果）和保存文件名和路径的显示文件（用于输出显示）组成。我们采用单字母倒排表的方式组织索引表。目标数据库中包含$67个单字母索引文件，一个字母对应一个索引。其中信息文件和所有索引文件常驻内存，显示文件在输出结果时才

将其文件被打开读取。对每一个&’(站点的文件，

信息如创建时间，大小，文件类型等非字符串定长数据以及一个指向显示文件中对应的文件名和路径字

记录在信息文件里，串起始位置的偏移指针（8))9"*）

由数据在信息文件的位置获得该文件的唯一编号

。同时在文件名的每个字母对应的单字母索引（1:）

该字母在文件名内的偏移里生成以1:为高$;位，

为低<位的=$位索引项。目标数据库结构如图$

所示：

图$&’(搜索引擎的目标数据库组织

机。根据&’(站点内每个目录内容更新快慢的不同我们指定了一些优先目录。搜集程序以较高的频率刷新优先目录的原始数据库，并定时刷新所有的原始数据库。为了加快搜集的速度，我们采用多线程方式同时搜集多个站点的文件信息，并指定一个超时时间，以结束所有搜集，并转入建库程序。

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

服务器是系统的核心，必须保证稳定性和高效性。实现高效性的关键在于使用线程，即一个用户请求使用一个线程处理。由于用户的搜索请求具有随机性和并发性，因而线程互斥、死锁预防、资源的管理等是服务器必须解决的重要问题。另外，对于

不能正常由于某种原因（如内存不足、1?8错误等）

完成搜索任务的线程，必须正确而完整的释放它申请的资源（如申请的内存、打开的文件、打开的

，并向用户显示不能完成任务@2/,"*以及线程本身）

的原因。安全性也是服务器要考虑的一个方面。服

因而可务器采用了’A(?1(作为与AB1通讯的协议，

能存在其它程序乃至网络黑客的非法连接。我们可以采用一种简单的身份验证机制保证安全，即AB1与服务器连接时先输入一个约定口令，若口令错误，则服务器直接关闭这个非法连接，从而确保了服务器的安全性。

在上述方案中，服务器会接收到来自AB1的搜索请求或搜集建库程序的更新数据库请求。接到更新数据库请求后，服务器暂停接收AB1的搜索请求，读入新的数据库，然后继续对外服务。接到搜索请求时，由AB1发送来的请求信息确定要匹配的串和过滤信息。由搜索串检查AC/D"是否命中（AC/D"是以搜索串为文件名，以匹配结果的所有1:为内容的

进行信息过滤，输出结文件），若命中，读入AC/D"，

果。否则，重新在数据库里查找，将结果过滤输出，然后将没过滤的结果1:串写入以搜索串为文件名的AC/D"文件中。输出结果给AB1时，由1:找到对应的文件信息记录，并由文件信息记录找到文件名与路径，最后以字符串格式发给AB1。服务器响应流程如图=

：

=

=%>

&’(搜索引擎的实现技术

搜集建库程序

搜集建库运行的时机与频率是保证数据实时性的重要因素。由于搜集时要访问众多的&’(站点、进行大量的网络数据传输，因而搜集应在网络速率

万方数据比较快的时候进行，一般来说凌晨=、;点是最佳时

图=服务器响应流程

基于web的百万级ftp搜索引擎的设计与实现

V4计算机应用!444年

查找是基于数据库里单子母倒排表的操作，通

（#$值）相等、低%位（字过提取两条索引中高!"位

母在文件名中的偏移）有确定差值的索引项获得结

，取后一果。具体而言，对连续的两字母串（如&’）

与前一字母索引（&）中#$相等的项，若字母索引（’）

中的偏移大(，则为所求结果的一项。后一索引（’）

而对于&？’、？’等，则取偏移大于!、大于)即为&？

所求结果。对于&!’，则要求字母在后一索引（’）中的偏移大于它在前一字母索引（&）中的偏移。)*)网页设计与+,#程序

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

+,#程序从网页表单的提交或直接由123得到搜索要求，进行错误检查，发往服务器。服务器将过滤后的结果信息返回，+,#程序按此生成网页。由于大部分情况下搜索结果在一页内显示不了，因而要采用换页机制。即+,#程序向服务器提供起始显示项号和最大显示项数，由服务器过滤，将可显示的结果信息返回给+,#程序。+,#程序由服务器给出的结果总数和起始显示项号生成换页链接。在北大

我们采用了一种智能的换“天网”-./搜索引擎里，

页方案：将当前的起始显示项号对应的链接放在链接表的中间，以最大显示项数为间距生成有限个向后和向前的链接。这样用户可以保持鼠标不动的情况下，以相同的间距向前或向后翻页。如图"所示为最大显示数为!4

时的一种情况：

读入内存。将新结果与原来的结果作“与”操作，即得结果中再搜索结果。

（!）多站点选择过滤。指定一个或多个站点搜索，将给用户带来极大方便，例如用户可以只搜对他

或他（她）比较喜欢的（她）而言比较快的-./站点，

用"个)!位数站点。指定一个最大站点数，如(!%，

放在文件信息中，每个搜集到的文件其所在站点号对应位为(，其余位为4。在+,#端，用户选定的多

传给服务器。在结果过个站点转变为"个)!位数，

滤时，若文件信息里的"个)!位数与用户提交的"个)!位数“与”不为零，即文件过滤为真，这样就可同时过滤多个站点。

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

;系统现状及展望

图"一种智能的换页方案

"-./搜索引擎的特色功能

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

（(）结果中再搜索功能。基本上所有000搜索器均具有此功能，在-./搜索引擎中也是必不可少的。首先，用要再搜的匹配串得到新结果；其次，

万方数据必定保存了原先的搜索结果，将它由于在+&89:中，

目前，“天网”-./搜索引擎采用了上述结构与

算法并成功发布，对“天网”用户提供了海量级的文件查询服务。它所搜索的最大文件数已达到(;4万，数据来自)4多个-./站点（可添加），每天凌晨自动更新优先目录，每三天自动跟新所有站点。在

查无!、？的多个字串，可在4*;()4万的数据量下，

秒内显示结果；在+&89:命中的情况下，任意字串的搜索都能在4*)秒内显示结果。最新的数据表明，

已接近“天网”-./搜索引擎的日访问量持续上升，

一万。展望未来，我们还可在此搜索引擎的基础上提供更多服务，如对用户点击下载的软件以及软件所在的站点计数，实现热门软件下载排名与-./酷站排名等。

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

参考文献

<(=

>6&?@AB36ACD6?@3:6C>6&?EB?@0&?@C5&BFA:+9:?*$6@@6?@GBH@BIJB?79:0:’KLMN:H6:?8:O67979:0:’,&79:H<P=*/HB8::J6?@QBG79:-BAH79#?7:H?&76B?&I+B?G:H:?8:RLM96’676B?B?S6@9/:HGBHT&?8:+BTNA76?@6?79:PQ6&U/&86G682:@6B?<+=C5:6F6?@C/*2*+96?&CD&E("U(VC!444*#LLL+BTNA7:HWB86:7E/H:QQ*//KV;(UV;;*

本文来源：https://www.bwwdw.com/article/bliq.html