[搜索] 华中大在线FTP搜索引擎剖析

HonestQiao

[搜索]　华中大在线FTP搜索引擎剖析

转载自：http://blog.sina.com.cn/s/blog_4921e53d01000ak2.html

1. 历史
第一阶段：2005年7月~2005年8月
项目主要参与人员： nid, martin, idoloveyou(顾问)
主要贡献：完成华中大在线1.0版本。并成功推出了http://so.hustonline.net。这是我们网站第一次尝试做FTP搜索引擎，也算是圆了martin长久以来的一个梦想：）教育网内960万数据采集，1个星期到15天的更新速度，在当时可以算是比较强大了。整套代码用C++完成，数据存储使用的是SQLServer2000。搭配SQLServer2000的全文检索。
主要问题：因为使用的是C++的API，所以我们不能够灵活的对FTP文件的类别和其他一些信息进行采集。另外，SQLServer2000的全文检索也是有局限性的。搜索mp3,txt这种结果很多的关键词就会造成效率低下。

第二阶段：2006年1月~2006年7月
项目主要参与人员：nid, martin, hjr, lrl
主要贡献：针对第一个版本遇到的问题，完全摒弃使用原先的C++。重新使用C#。重写了Crawler部分。大大提高了采集FTP数据的灵活性。为了提高效率首次尝试使用了基于.net remoting的分布式搜索技术。数据存储换成了SQLserver2005。在索引速度和效率上都有极大的提升。这个版本在两个客户端搜集的情况下一个星期可以搜集数据大概2000万左右。
主要问题：过于复杂的结构造成了操作的不方便。SQLServer2005的全文检索仍然没有能够根本的解决上一个版本中检索遗留下的问题。

第三阶段：2006年12月~2007年7月
项目主要参与人员：hjr, liulei, nid, lrl
可以算是华中大在线FTP搜索具有很大意义的一版搜索。因为从这个版本开始，就已经实现了独立的文件系统，彻底摒弃了数据库系统。抛弃了原先的分布式搜索的想法，改成在Crawler中开启更多的线程。

2.FTP搜索的架构

我们将讨论如上图所示的FTP搜索的总体架构。更多关于数据结构和应用程序的讨论将在后续的章节给出。

2.1 FTP抓取器(FTPCrawler)
在我们的系统中，FTP文档抓取 (Web Crawling)(下载Web页面)是通过抓取器的多个线程完成的，每个客户端叫作一个FTP客户(FTPClient). 通常线程的个数是15。 DataHandler从数据库里面把可用的FTP站点的信息读出来。FTP客户端(FTPClient)则负责建立与FTP服务器的联系，并递归的获取每个目录的内容。将文件内容转化成一个FTP文档(FTPDocuments)的对象。我们并不直接把FTP文档存入到数据文件中，而是放入到一个容器中，并写入到临时的xml文件中。这样，我们就不会因为一些突发状况（停电）而使得数据丢失了。我们另外有个线程专门负责读xml临时文件获取FTP文档，并递交给索引模块。

2.2 存储(Store)

2.2.1 存储文件格式

2.2.1.1 定长数据文件(StaticFile)
StaticFile(.sd)->
DataInfos->DataCount
DataCount, DocumentID, Size, Date, Type, SiteID->Int
Document Identifier->long
说明：这一部分文件存储FTP数据中的定长的部分，所谓定长的部分就是数字非字符串的部分。
DocumentID, 用于标示每一个FTP文档的ID号。
Document Identifier, 用于记录该FTP文档在变长数据文件中的起始位置。
Size, 标示FTP文档的大小。
Date,记录FTP文件的时间
Type, 文档的类型，总共类型分为7类。其中低位作为该文档是否为目录的判断。
SiteID, 记录文档所属站点的ID号码。

2.2.1.2 变长数据文件(Repository)
DynamicFile(.dd) ->
DataInfos->DataCount
DataInfo->
DataCount->Int
Dir, FileName->String
说明：DataCount是记录文件数量的整型，
Dir记录的是文件的路径名称，
FileName记录的是文件文件名。

2.2.1.3. 索引文件
InvertedFile (.if)-> TermData
TermData ->(TermInfos) TermCount;
TermInfos->;
TermInfo->dataCount;
SkipData->dataCount/SkipIntervals
DocID,Score,NextDocPosition->Int
说明：SkipIntervals代表遍历倒排表时，一次跳过的记录个数，默认设置为16（暂定）。
DataCount是对应每个关键词的文档数量
TermInfos包含两个部分：
TermInfo:按照文档ID的升序排列，后面是该关键字在该文档中的得分，对于每个关键词应该有DataCount个
SkipData:记录的是跳跃遍历时的文档ID，和该文档在先前TermInfo中的位置
比如说，对应于某个关键字文档个数为35，SkipIntervals的值为16，那么在SkipData中应该有两个记录，分别对应于TermInfo中第16个和第32个文档的ID和位置。

2.2.1.4. 关键字信息文件（也叫作正向索引文件）
Lexicon(ls)文件：
Lexicon (.ls)->
TermInfos->TermCount
TermCode, TermFrequency, TermOffset, SkipDataOffset ->Int：
TermCode:每一个关键词都在分词的时候转换成为了数字签名的形式，也就是每一个关键词对应于一个唯一的TermCode。
SkipInverval, 跨越的TermCode数目。
TermCount,总共的关键词数目。
TermFrequency,该关键词在索引文件中个数。
TermOffset, 该关键词对应的倒排表在索引文件中的起始位置。
SkipDataOffset, 跳跃部分的起始位置。

2.2.2. 主要存储结构

2.2.2.1 输入输出流
优化了的FTP搜索数据结构可以以最小的消耗来处理海量文档的抓取，索引和搜索。虽然CPU和大数据块的输入输出这些年来已经有很大改善，磁盘的定位仍然需要大概10MS的时间才能完成。我们的FTP搜索被设计为无论何时总是避免不必要的磁盘定位，这种思想对我们数据结构的设计起了极大的作用。
输出流(OutputStream)
FTP文档的输出流是通过二进制的格式输出的，每一个输出都是以byte为单位进行输出。Int为4个byte, long为8个byte。String类型是这样的：首先输出一个int型确定这个string的长度，然后把string中每个char按照byte形式输出。这样做的好处在于可以尽可能的节约空间并且在文档中将字节长度统一。
输入流(InputStream)
为了避免不必要的磁盘定位，我们给输入流增加了一个缓存功能。就像操作系统中的虚拟内存一样。一次读文件操作读入65536个字节到内存中，下次读操作将先检查是否要读取的模块在缓存中，如果存在于缓存中，则直接从缓存中获取数据。避免了频繁的磁盘读取。

2.2.2.2. 文档索引
文档索引用来保存每一个文档的信息。包含两个部分：
定长的文件：这是一个固定宽度按照DocID排序的索引。每一条记录中存储的信息包括当前文档的ID，指向变长文件的指针和一些统计数据。这种设计是希望得到紧凑数据结构使得查询请求可以仅仅在一次磁盘定位时便可以得到相关记录。

2.2.2.3 词典(Lexicon)
词典通常有多种形式。一个与之前系统中词典最大的不同是我们设计的词典可以在地消耗的前提下放入到内存中。在目前的实现中，我们可以在一台256主存的机器上把词典文件整个的放入到内存中去。目前的词典包含大约1千4万个关键词。词典中的每一项都有固定的长度，

2.2.2.4. 倒排索引(Inverted Index)
倒排索引除了是由排序器来进行处理以外，桶的结构和正向索引是相同的。对于每一个有效的WordID，词典包含一个指向包含WordID的倒排索引的指针。这个指针指向一个包括对应DocID的链表。这个文档链表表示所有包含该关键词的文档集合。

一个重要的问题是，在文档链表中，DocID究竟应以一种什么样的顺序进行存储？一个简单的解决方案是按照DocID的顺序进行排序。这在多关键词进行求交集的时候有利于对文档链表快速地合并。另外一个选择是根据该关键词在每个文档中的得分来进行排序。这种方法对于处理单关键词查询时显得非常有用但是在多关键词的文档链表的合并过程中就显得异常困难。同样，这种排序方式使系统的进一步发展变得更加困难。因为一旦我们对排序的算法进行修改，我们就必须得重新生成整个倒排索引。尽管如此，我们还是选择了后者，我们将Score和DocID作为一个整体来进行排序。实际上对于不同的关键词在不同的文档中是完全不同的，这就保证了其唯一性。根据目前FTP搜索提供的三种排序方式，我们分别生成了三个不同的倒排表Inverted.if, Inverted_Size.if, Inverted_Date.if. 其中的Score分别是按照默认的排序，时间排序和大小排序的。

2.3 索引FTP网络
索引文档入桶—文档解析完成以后，被编码进入不同的桶中。每一个词都通过驻留内存的词典的哈希表被转换为一个WordID。新增的词典哈希项被记录到相关文件上。Word转换为WordID以后，他们在每个文档中的值被转换成为响应的关键词信息项（也叫作桶），被写入到正向索引中。同步索引状态的主要难题在于词典文件需要共享。我们通过采用为所有的不在词典中的关键词写入日志到日志文件中来代替词典的共享。这样一来，多个索引器可以并行工作，小的日志文件可以在最后阶段被索引器合并成一个大的索引文件。

2.3.1. 排序
为了产生倒排索引，排序器将所有的正向桶按照WordID进行排序来为关键词创建倒排桶。排序器每次对一个关键词信息项进行操作，因此对临时存储空间的需求就很少。同时我们使用多个排序器在排序阶段并行的工作。这些排序器可以在同一时间对不同的桶进行操作。由于桶的大小不能够全部载入内存，排序器根据WordID和DocID将其拆分成多个可以载入到内存中的篮(Basket)。然后排序器装载这些篮排序，比逆光把结果写入到短的和完整的倒排桶中。

2.3.2.合并索引
因为索引文件本身不可能全部缓存于内存中(大概有2GB左右)。我们必须不断地把排好序的索引写入到磁盘中，在FTP搜索设计中，我们是按照每4000个FTP文档建立一个索引来设计的。这样对于1400万左右的数据，第一次将会生成超过3500个的索引和词典文件。当索引生成以后，系统将会进行合并操作。系统一次性读取5个词典文件，然后根据词典文件中的Termcode排序。其实就是简单的5个数组的合并操作。然后根据Termcode从小到大在索引文件中读取相对应的倒排表。并写入到新的索引文件中。这里有一点需要注意的是，如果在5个数组中存在TermCode相同的项，系统将会分别读取其在各自倒排索引中的倒排表然后合并倒排表。更新词典项中Frequency和Offset。

2.4 搜索(Searching)

2.4.1 步骤

1. 解析查询

2. 通过词典将关键词转换成为WordID.

3. 在正向索引中根据wordID找到每个关键词在倒排桶的起始位置和倒排项的个数。

4. 在倒排索引中找出相对应的倒排表(inverted List)

5. 根据DocID在定长数据文件中找到对应的FTP文档的基本信息

6. 根据定长数据文件中

2.4.2. 多关键词查询

在这里我们就要使用到倒排索引中的SkipData结构了。

下面来列举一个例子：
假设我们有A,B关键词和他们的倒排索引表：
A 1 3 5 7 11 55 66 109...
B 55 110 135 150...
找两者的匹配值，我们通常的做法是发现A中第一个比B小，于是我们移动A中的指针。发现A中的下一个元素3还是比B中第一个元素55要小。于是我们依次移动直到找到55和B中的第一个元素匹配为止，总共要进行6次操作
现在，在lucene中，我们可以设置一个skipinterval的值，这个数值用来告诉我们，一次比较失败以后往后跳动的条目数量，比如说，我设置Skipinterval的值为3，那么在A中第一个元素比较失败以后，就会直接向后跳到7的位置进行继续比较，发现7还是比55要小，于是我们继续向前跳动3格，这时候发现数值大了，于是我们回溯到前一步(7的位置)，进行逐个比较，这样只要进行4次操作便可以比对成功。
后面的SkipData记录的是每次应该跳到的文档ID号，比如说，在a中，总共记录了8个文档，Skipinterval的值是3，那么DocSkip中的值就应该依次是7,66,下次检验是直接先从SkipData中查找数据，如果不匹配再按上述办法到倒排索引中去找相关数据

2.6 反馈(Feedback)

排序函数有许多参数，比如说类型权值和类型相近度权值，精确的计算这些权值的确切值在某种程度上几乎是不可能的。我们通过在搜索引擎中引入用户反馈机制来达到这个目标。一个值得信赖的用户可能会对所有返回的结果进行评价，这种反馈被储存起来，在我们对排序函数进行修改的时候，我们可以通过反馈得到一些有关因子在先前查询中起到的影响。虽然说这些方式远非理想，但确实给了我们如何改进排序算法可以影响搜索结果

3．我们走到哪了？
大规模FTP搜索引擎是一个复杂的系统，还有许许多多的工作需要去做。我们当前的目标是改进搜索时的性能并且将数据量进一步扩大，目前的数据保有量为1400万左右。一些简单的改进性能方法包括查询缓存，智能磁盘分配，子索引等等。
我们做了的：
1．我们实现了按照时间，大小和默认规则的排序，默认规则的排序方案已经能够初步在第一页就返回用户最为感兴趣的内容。
2．我们实现了站点快照功能。通过目录可以返回该目录下的所有结果。
3．我们实现了对FTP站点的初步估算，通过文件数量，成功连接次数和失败连接次数来给站点一个分数。
我们还没有做的：
1．对于用户查询的统计，包括对于用户使用偏好的统计。对于一段时间以内用户搜索热词的统计等等。
2．分学校查找功能，很多时候，用户只对他们一个区域内的资源感兴趣。
3．对关键词求并集。