一、Lucene源码实现分析的说明
通过以上对Lucene系统结构的分析,我们已经大致的清楚了Lucene 系统的组成,以及在Lucene系统之上的开发步骤。接下来,我们试图来分析Lucene项目(采用Lucene 1.2版本)的源码实现,考察其实现的细节。这不仅仅是我们尝试用C++语言重新实现Lucene的必须工作,也是进一步做Lucene开发工作的必要准备。因此,这一部分所涉及到的内容,对于Lucene上的应用开发也是有价值的,尤其是本部分所做的文件格式分析。
由于本文建立在我们的毕设项目之上,且同时我们需要实现cLucene项目,因此很遗憾的我们并没有完全的完成Lucene的所有源码实现的分析工作。接下来的部分,我们将涉及的部分为Lucene文件格式分析,Lucene中的存储抽象模块分析,以及Lucene中的索引构建逻辑模块分析。这一部分,我们主要涉及到的是文件格式分析与存储抽象模块分析。
二、Lucene索引文件格式
在Lucene的web站点上,有关于 Lucene的文件格式的规范,其规定了Lucene的文件格式采取的存储单位、组织结构、命名规范等等内容,但是它仅仅是一个规范说明,并没有从实现者角度来衡量这个规范的实现。因此,我们以下的内容,结合了我们自己的分析与文件格式的定义规范,以期望给出一个更加清晰的文件格式说明。具体的文档规范可以参考后面的文献2。
首先在Lucene的文件格式中,以字节为基础,定义了如下的数据类型:
表 3.1 Lucene文件格式中定义的数据类型
数据类型 |
所占字节长度(字节) |
说明 |
Byte |
1 |
基本数据类型,其他数据类型以此为基础定义 |
UInt32 |
4 |
32位无符号整数,高位优先 |
UInt64 |
8 |
64位无符号整数,高位优先 |
VInt |
不定,最少1字节 |
动态长度整数,每字节的最高位表明还剩多少字节,每字节的低七位表明整数的值,高位优先。可以认为值可以为无限大。其示例如下
值 |
字节1 |
字节2 |
字节3 |
0 |
00000000 |
|
|
1 |
00000001 |
|
|
2 |
00000010 |
|
|
127 |
01111111 |
|
|
128 |
10000000 |
00000001 |
|
129 |
10000001 |
00000001 |
|
130 |
10000010 |
00000001 |
|
16383 |
10000000 |
10000000 |
00000001 |
16384 |
10000001 |
10000000 |
00000001 |
16385 |
10000010 |
10000000 |
00000001 |
|
Chars |
不定,最少1字节 |
采用UTF-8编码[20]的Unicode字符序列 |
String |
不定,最少2字节 |
由VInt和Chars组成的字符串类型,VInt表示Chars的长度,Chars则表示了String的值 |
以上的数据类型就是Lucene索引文件格式中用到的全部数据类型,由于它们都以字节为基础定义而来,因此保证了是平台无关,这也是Lucene索引文件格式平台无关的主要原因。接下来我们看看Lucene索引文件的概念组成和结构组成。
![点击图片可在新窗口打开 Lucene索引文件格式分析](http://img.ddvip.com/2008_10_07/1223372781_ddvip_1148.gif)
以上就是Lucene的索引文件的概念结构。Lucene索引index由若干段(segment)组成,每
一段由若干的文档(document)组成,每一个文档由若干的域(field)组成,每一个域由若干的项(term)组成。项是最小的索引概念单位,它直接代表了一个字符串以及其在文件中的位置、出现次数等信息。域是一个关联的元组,由一个域名和一个域值组成,域名是一个字串,域值是一个项,比如将“标题”和实际标题的项组成的域。文档是提取了某个文件中的所有信息之后的结果,这些组成了段,或者称为一个子索引。子索引可以组合为索引,也可以合并为一个新的包含了所有合并项内部元素的子索引。我们可以清楚的看出,Lucene的索引结构在概念上即为传统的倒排索引结构[21]。
从概念上映射到结构中,索引被处理为一个目录(文件夹),其中含有的所有文件即为其内容,这些文件按照所属的段不同分组存放,同组的文件拥有相同的文件名,不同的扩展名。此外还有三个文件,分别用来保存所有的段的记录、保存已删除文件的记录和控制读写的同步,它们分别是segments, deletable和lock文件,都没有扩展名。每个段包含一组文件,它们的文件扩展名不同,但是文件名均为记录在文件segments中段的名字。让我们看如下的结构图3.2。
关于图3.2中的各个文件具体的内部格式,在参考文献3中,均可以找到详细的说明。接下来我们从宏观关系上说明一下这些文件组成。在这些宏观上的关系理清楚之后,仔细阅读参考文献3,即可清楚的明白具体的Lucene文件格式。
每个段的文件中,主要记录了两大类的信息:域集合与项集合。这两个集合中所含有的文件在图3.2中均有表明。由于索引信息是静态存储的,域集合与项集合中的文件组采用了一种类似的存储办法:一个小型的索引文件,运行时载入内存;一个对应于索引文件的实际信息文件,可以按照索引中指示的偏移量随机访问;索引文件与信息文件在记录的排列顺序上存在隐式的对应关系,即索引文件中按照“索引项1、索引项2…”排列,则信息文件则也按照“信息项1、信息项2…”排列。比如在图3.2所示文件中,segment1.fdx与segment1.fdt之间,segment1.tii与segment1.tis、 segment1.prx、segment1.frq之间,都存在这样的组织关系。而域集合与项集合之间则通过域的在域记录文件(比如 segment1.fnm)中所记录的域记录号维持对应关系,在图3.2中segment1.fdx与segment1.tii中就是通过这种方式保持联系。这样,域集合和项集合不仅仅联系起来,而且其中的文件之间也相互联系起来。此外,标准化因子文件和被删除文档文件则提供了一些程序内部的辅助设施(标准化因子用在评分排序机制中,被删除文档是一种伪删除手段)。这样,整个段的索引信息就通过这些文档有机的组成。
以上所阐述的,就是 Lucene所采用的索引文件格式。基本上而言,它是一个倒排索引,但是Lucene在文件的安排上做了一些努力,比如使用索引/信息文件的方式,从文件安排的形式上提高查找的效率。这是一种数据库之外的处理方法,其有其优点(格式平**立、速度快),也有其缺点(独立性带来的共享访问接口问题等等),具体如何衡量两种方法之间的利弊,本文这里就不讨论了。
三、一些公用的基础类
分析完索引文件格式,我们接下来应该着手对存储抽象也就是org.apache.lucenestore中的源码做一些分析。我们先不着急分析这部分,而是分析图2.1中基础结构封装那一部分,因为这是整个系统的基石,然后我们在下一部分再来分析存储抽象。
基础结构封装,或者基础类,由org.apache.lucene.util和org.apache.lucene.document两个包组成,前者定义了一些常量和优化过的常用的数据结构和算法,后者则是对于文档(document)和域(field)概念的一个类定义。以下我们用列表的方式来分析这些封装类,指出其要点。
表 3.2 基础类包org.apache.lucene.util
类 |
说明 |
Arrays |
一个关于数组的排序方法的静态类,提供了优化的基于快排序的排序方法sort |
BitVector |
C/C++语言中位域的java实现品,但是加入了序列化能力 |
Constants |
常量静态类,定义了一些常量 |
PriorityQueue |
一个优先队列的抽象类,用于后面实现各种具体的优先队列,提供常数时间内的最小元素访问能力,内部实现机制是哈析表和堆排序算法 |
表 3.3 基础类包org.apache.lucene.document
类 |
说明 |
Document |
是文档概念的一个实现类,每个文档包含了一个域表(fieldList),并提供了一些实用的方法,比如多种添加域的方法、返回域表的迭代器的方法 |
Field |
是域概念的一个实现类,每个域包含了一个域名和一个值,以及一些相关的属性 |
DateField |
提供了一些辅助方法的静态类,这些方法将java中Date和Time数据类型和String相互转化 |
总的来说,这两个基础类包中含有的类都比较简单,通过阅读源代码,可以很容易的理解,因此这里不作过多的展开。
四、存储抽象
有了上面的知识,我们接下来来分析存储抽象部分,也就是org.apache.lucene.store包。存储抽象是唯一能够直接对索引文件存取的包,因此其主要目的是抽象出和平台文件系统无关的存储抽象,提供诸如目录服务(增、删文件)、输入流和输出流。在分析其实现之前,首先我们看一下UML [22]图。
![点击图片可在新窗口打开 Lucene索引文件格式分析](http://img.ddvip.com/2008_10_07/1223372781_ddvip_2670.gif)
图 3.3 存储抽象实现UML图(一)
![点击图片可在新窗口打开 Lucene索引文件格式分析](http://img.ddvip.com/2008_10_07/1223372782_ddvip_9736.gif)
图 3.4 存储抽象实现UML图(二)
![点击图片可在新窗口打开 Lucene索引文件格式分析](http://img.ddvip.com/2008_10_07/1223372782_ddvip_4939.gif)
图 3.4 存储抽象实现UML图(三)
图3.2到3.4展示了整个org.apache.lucene.store中主要的继承体系。共有三个抽象类定义:Directory、 InputStream和OutputStrem,构成了一个完整的基于抽象文件系统的存取体系结构,在此基础上,实作出了两个实现品:(FSDirectory,FSInputStream,FSOutputStream)和(RAMDirectory,RAMInputStream和 RAMOutputStream)。前者是以实际的文件系统做为基础实现的,后者则是建立在内存中的虚拟文件系统。前者主要用来永久的保存索引文件,后者的作用则在于索引操作时是在内存中建立小的索引,然后一次性的输出合并到文件中去,这一点我们在后面的索引逻辑部分能够看到。此外,还定以了 org.apache.lucene.store.lock和org.apache.lucene.store.with两个辅助内部实现的类用在实现 Directory方法的makeLock的时候,以在锁定索引读写之前来让客户程序做一些准备工作。
(FSDirectory, FSInputStream,FSOutputStream)的内部实现依托于java语言中的io类库,只是简单的做了一个外部逻辑的包装。这当然要归功于java语言所提供的跨平台特性,同时也带了一些隐患:文件存取的效率提升需要依耐于文件类库的优化。如果需要继续优化文件存取的效率,应该还提供一个文件与目录的抽象,以根据各种文件系统或者文件类型来提供一个优化的机会。当然,这是应用开发者所不需要关系的问题。
(RAMDirectory,RAMInputStream和RAMOutputStream)的内部实现就比较直接了,直接采用了虚拟的文件 RAMFile类(定义于文件RAMDirectory.java中)来表示文件,目录则看作一个String与RAMFile对应的关联数组。 RAMFile中采用数组来表示文件的存储空间。在此的基础上,完成各项操作的实现,就形成了基于内存的虚拟文件系统。因为在实际使用时,并不会牵涉到很大字节数量的文件,因此这种设计是简单直接的,也是高效率的。
这部分的实现在理清楚继承体系后,相当的简单。因此接下来的部分,我们可以通过直接阅读源代码解决。接下来我们看看这个部分的源代码如何在实际中使用的。
一般来说,我们使用的是抽象类提供的接口而不是实际的实现类本身。在实现类中一般都含有几个静态函数,比如createFile,它能够返回一个 OutputStream接口,或者openFile,它能够返回一个InputStream接口,利用这些接口之中的方法,比如 writeString,writeByte等等,我们就能够在抽象的层次上处理Lucene定义的数据类型的读写。简单的说,Lucene中存储抽象这部分设计时采用了工厂模式(Factory parttern)[23]。我们利用静态类的方法也就是工厂来创建对象,返回接口,通过接口来执行操作。
五、关于cLucene项目
这一部分详细的说明了Lucene系统中所采用的索引文件格式、一些基础类和存储抽象。接下来我们来叙述一下我们在项目cLucene中重新实现这些结构时候的一些考虑。
cLucene彻底的遵守了Lucene所定义的索引文件格式,这是Lucene对于各个兼容系统的基本要求。在此基础上,cLucene系统和Lucene系统才能够共享索引文件数据。或者说,cLucene生成的索引文件和Lucene生成的索引文件完全等价。
在基础类问题上,cLucene同样封装了类似的结构。我们同样列表描述,请和前面的表3.2与3.3对照比较。
表 3.4 基础类包cLucene::util
类 |
说明 |
Arrays |
没有实现,直接利用了STL库中的快排序算法实现 |
BitVector |
C/C++语言版本的实现,与java实现版本类似 |
Constants |
常量静态类,定义了一些常量,但是与java版本不同的是,这里主要定义了一些宏 |
PriorityQueue |
这是一个类型定义,直接利用STL库中的std::priority_queue |
表 3.3 基础类包cLucene::document
类 |
说明 |
Document |
C/C++语言版本的实现,与java实现版本类似 |
Field |
C/C++语言版本的实现,与java实现版本类似 |
DateField |
没有实现,直接利用OpenTop库中的ot::StringUtil |
存储抽象的实现上,也同样是类似于java实现。由于我们采用了OpenTop库,因此同样得以借助其中对于文件系统抽象的ot::io包来解决文件系统问题。这部分问题与前面一样,存在优化的可能。在实现的类层次上、对外接口上,均与java版本的一样。