从lucene的文件结构看它的性能(转)

从lucene的文件结构看它的性能

作者：冲出宇宙（lotusroots）

时间：2007-2-6

注：转载请注明作者。

        Lucene是一个apache项目，完全使用java语言编写（废话，谁都知道apache主要是做java项目的，不过，已经有人对Lucene进行了迁移，比如CLucene），它提供了一个基本的索引文档后进行搜索的功能。目前版本是2.0，具体信息可以直接看http://lucene.apache.org/官方网站。同时，http://www.lucene.com.cn/about.htm提供了一个很不错的介绍（同时介绍了CLucene项目）。

    本文不打算介绍它的使用，因为它的使用实在是过于简单，而且，太多的人写了关于它的使用方法。本文试图从一个更高的层次来分析一下lucene的文件结构及其性能，所以，需要读者已经对搜索引擎的工作原理有较深入的了解（推荐学习MIT的开放课程中的Information Extraction）。

    本文的内容主要参考了http://lucene.apache.org/java/docs/fileformats.html，这是lucene的文件结构页面。

一 lucene文件的基本构架

       lucene文件结构的最大特点是其结构十分紧凑。从文件开始的第一个字节直到最后一个字节都是有效数据，中间没有任何空闲的字节。这样有优点也有缺点，优点是读取迅速，缺点是修改复杂。因为lucene的作者说lucene并不是为修改频繁的应用设计的，所以，文件结构这么做是无可厚非的。在修改频繁的环境下，lucene的性能注定会很差。如果是那样的话，您或许需要考虑使用更好的技术，因为增加一个文档到索引其实可以做到十分迅速。

       在压缩方面，lucene也采用了一些基本的方法。比如，它对int类型就进行了所谓的byte压缩方法（最初级的方法）。不过，它在String上面采用的utf-8的编码显然会比utf-16编码占用更多的空间。其它地方还能够看到压缩的是Field Data（域值，.fdt）文件，这个文件保存的是文档包含的域的具体文本（一个文档可以划分为多个域，每个域都是一个字符串），显然这是很大的数据（zlib好像在这里比较常用，google据说也这样压缩，不过，文本压缩的最好办法显然不是zip，更好的办法还有ppmd）。

二 lucene构建索引的性能

       索引，专业点说，包含2种：前向索引和反向索引（倒排索引，inverted index）。前者表示的是某个文档里面的所有词语，后者表示的是包含某个词语的所有文档。对应到Lucene上面，它的前向索引可以认为是Term Vectors（词语向量）相关文件，包含.tvx、.tvd和.tvf这3种文件。前向索引没有什么好评论的，它一般只是做为重组原始数据时候的依据，其构建十分简单明了。反向索引对应到Lucene上就是index（索引）。Lucene把索引划分成一个一个的segment（块，其实是一个小索引），直观的说，当有一批新数据到达的时候，我们一般给其构建成一个新的segment，这是因为修改原来的segment的代价很高（并不是说一定很高，只是lucene采用的文件结构无法简单的加入新的文档）。当一个index包含的segment太多的时候，查找性能就很差了（因为一次查询需要查询多个segment），需要进行segment的合并。

       下面是index和segment的基本结构：

1.         index:

index包含4类文件：1）记录segment信息的文件；2）指示索引是否正在更改的标记文件；3）简单组合了若干个文件的复杂文件；4）segment文件及其附属文件。

2.         segment:

segment其实是一个小型index，它包含了词汇表、域表、反向索引表、域权重表、词语向量（即前向索引）和已经删除文档表。词汇表包括了本segment里面出现的所有词汇（记得词汇不见得是真的词语，它其实就是索引的字符串）。

三 lucene修改和删除索引的性能

       严格的说，lucene底层并不支持对某个文档的修改。因为它的紧密结构抗拒了对文档的直接修改。当需要修改某些文档的时候，可以是这样的：

1.         删除这些文档。这样会使得这些文档ID加入到已经删除的文档表里面。

2.         构建新的索引。这样会生成一个新的segment。

3.         合并索引的所有segment。这样会把所有的segment都合并到一起，构成唯一的一个segment。

大家可以看到，如果仅仅从以上3步来看，lucene的修改索引的性能极差。好在可以利用缓冲，分批的懒惰的进行上面的第2步和第3步。

四 lucene的查询性能

       我们从几个方面来分析它的查询性能：

1.         文件个数。文件个数越多，查询的时候需要访问的文件就越多，从而开销也会越大。这是因为要读取的类似数据处在不连续的位置。当你把所有segment都合并成一个之后，这种问题就不存在了。可是，合并segment的花销很大，需要谨慎考虑。

2.       索引词汇。lucene的词汇其实并不是简单的词汇，而是“域+词汇”的保存形式。当域比较多的时候，这种方式的索引词汇构建方式显然会大大降低查找的效率。不过，值得一提的是，为了降低空间占用，lucene在排序词汇之后，按照如下的形式进行保存： <PrefixLength, Suffix, FieldNum>，这里，PrefixLength表示本词汇借用了前面一个词汇的前面PrefixLength个字符，Suffix表示本词汇余下的字符串，FieldNum表示本字符串属于的域。

3.         布尔表达式计算。布尔表达式查找的时候，涉及到几条词汇倒排索引的合并的问题。未压缩的索引合并是一个十分容易（不过，算法需要很精细才能优化各种情况）的事情，可是，lucene的索引经过压缩了（包括前面提到的和相邻数据相减的压缩方法）以及String长度的不确定性，所以，我们无法根据词汇直接定位到它对应的TermInfo（做为一个变型，你可以在内存中为它做个索引）。于是lucene就使用了SkipInterval/SkipData（桩，即定位标记）这类结构来加快比较速度，通过和它们的比较，可以简单的跳过多个字节，从而加快了查找速度。当然了，这种策略比起直接的排序后2分查找显然是慢了许多。

4.         权重计算。权重的计算显然和文件结构没有太大关系。但是，已知的是，lucene保存了每个词汇的出现频率和每个域的权重值，这样就可以通过一些简单的公式计算满足要求的文档对本次查询的匹配度了。

五 Nutch对lucene的改进

       Nutch据说还是lucene的作者写的，不过，这次这个高手打算直接和商业搜索引擎进行抗衡，他引入了分布式的构架。Nutch一开始就是分布式的，它本来就是定位在百以上量级的集群系统（或者网格）上的。对于搜索引擎来说，除了抓取（或者还包含一些前期的数据处理）外，其余的工作都是信息保存、索引构建和索引查找。Nutch使用的分布式构架，它利用了多台机器的性能来同时构建索引（这一点的可行性在讲MapReduce的google论文里面已经做了详细的描述），这显然能够提高做索引的速度。在索引查找上面，因为索引查找显然不同于做索引，它要求极高的速度和不高的精度。简单的基于MapReduce的方法的最大缺点就是速度慢（因为它简单嘛），所以，这位高手强烈建议不要使用分布式的查找方法，因为速度比单机查找还要慢很多（考虑一下，对于google来说，它的数据量据说达到上百个T，即10万G，没有机器可以挂上这么大的硬盘吧？所以，他们肯定是分布式查询的）。可以肯定的是，Nutch在搜索方面对lucene的改进就是分布式的做索引。当然了，Nutch比lucene好的地方在于它有了抓取程序（虽然十分的原始）。

后记

       大家都在热捧这些开源软件，但是，我提醒大家一下：它们距离真正的商业应用还是有一定差距的。或许你会说Nutch不是很好么？它的作者都加入yahoo了。可是，你想过没有？yahoo本来就是做搜索的，它根本就不需要那么简单的技术，它可能基于其它方面的考虑，比如影响度或者创新度。虽然开源软件速度比较慢，但是，你可以通过十分优秀的缓冲算法来弥补它的不足。简单的说，缓冲才是一个追求速度的搜索引擎最需要关心的地方。作者在有空的时候将专门撰文讨论搜索引擎的缓冲处理。

       这么多年以来，搜索引擎的构架几乎没有发生任何改变（google使用的构架可以在15年前看到同样的），所以，想在这个方面有所突破几乎不可能了。现在人们的研究热点都集中在信息抓取（抽取，获取）和信息处理上。这些方面的技术还很不成熟，也是能够出现突破的地方。