前两篇文章主要围绕Lucene的底层索引文件结构方面介绍了倒排索引原理:

http://www.6aiq.com/article/1564413040138

http://www.6aiq.com/article/1564413209435

在Lucene中,写数据的基本单元称之为Document,本文将介绍一个Document写入Lucene后的索引全流程。

基础概念

** **

如下几个概念,Lucene的Document中给出了明确的定义,在这里先强调一下:

1. Document(文档)由Field(字段)构成。

2. Field是Term的集合。

3. Segment是最小的独立索引单元,由多个Documents构成。

在每一个Segment范畴内,每一个Document都被分配了一个唯一的数字ID,称之为DocID,同时根据每个Field的名字定一个唯一的FieldNaming,对于索引字段进到Postings之前也会被分配一个唯一的TermID。Field除了FieldNaming之外也有一个FieldNumber,与DocID和TermID一样都是一个自增的数值。

整体流程

一个Document写到Lucene中,大致涉及如下六大处理过程:

1. 处理需要存储的Fields

2. 构建正向索引

3. 对Field进行分词,构建倒排索引和TermVectors

4. 处理Points类型字段(6.0以后的版本)

5. 保存分词字段的Norms信息

6. Flush生成Segment,完成数据持久化存储

这并不是意味着每一个Document必然会经历这六大过程,有一些过程是互斥的,如步骤2与3、3与4、4与5都只能二选其一,同时,每一个步骤也都可以通过配置跳过。

下面将详细展开每一个处理所关联的细节。

Field存储

Field数据的存储与否,是可选的。Lucene关于Field存储的文件格式,与MySQL的frm文件格式类似。关于Field的处理,主要是由 StoredFieldsConsumer 完成。

Lucene为了保证写入的性能,文档一旦提交后便不可改写,这点跟MySQL的_ frm文件 是不一样的。字段存储是唯一一个按文档存储的文件,此外都是打破文档的边界按字段存储的。_

另外,因为Lucene作为搜索引擎,它读取文档的操作往往是以随机访问的方式。为此Lucene将文档数据写到.fdt文件的同时,还需要为DocID对应的文档所在.tdt文件上位置构建索引,并将索引存储到.fdx文件中,以提供快速随机访问的能力。

DocID是Lucene的内部ID,它被用来快速获取Document,但使用者并不能直接获取。需要注意区分DocID与用户定义的有业务意义的文档ID,它们并不是一回事。

索引构建及存储

在Lucene中,索引可以分成两类, 正向索引倒排索引 。在索引过程中,通常需要指定在哪个Field中进行检索的,也就是TermID在所有具有相同FieldName的Field中是唯一的。

Lucene通常为所有相同FieldName的字段分配一个 PerField 对象,由PerField实现所有字段级别所有操作。相同FieldName的所有Field在处理逻辑是可以认为是连续的,在这个过程中,DocID仅作为Term的属性存在。Field是Terms的集合,因此可以认为索引阶段Field就是所有同名Field的所有Terms的集合。

正向索引

正向索引 记录了DocId到FieldValue的映射关系,提供了通过DocID就能直接获取字段值的能力。 DocValuesWriter 将DocIdSet与FieldValue分别存储在类似数组的结构中,他们的存储顺序的是一致的。然后,DocValuesConsumer将FieldValues和DocIdSet一并写到.dvd文件中。每个需要存储DocValues的Field都有一对这样的结构,且DocValues是按字段连续存储在.dvd文件中。每个Field的DocIdSet和FieldValues在dvd文件中的索引信息(起始位置),被存储在.dvm文件中。

这实现上是一种 列式存储 的结构。这种列式存储结构,给Lucene带来很多二次计算的可能,比如Hive On Solr/ElasticSearch,Solr的高级特性Streaming Expression等。Streaming Expression是Solr提供基于Lucene索引实现的计算框架,以及在Streaming Expression上实现SQL的能力。

_存储DocID的内存是用DocsWithFieldSet(底层实际上是BitSet),在磁盘上的组织则要复杂一些。在Lucene7.0之后,Lucene针对BitSet的稠稀性,采用不同的存储方式:当BitSet比较稀疏时,直接存储DocID;当BitSet稠密时,则直接存储BitSet的Bits数据。根据数据的分布情况不同,采用适当的结构不仅可以提高空间的利用率,还能提高遍历的效率。唯一的缺点估计就是实现起来比较复杂。_ 当前版本DocValues还不支持分词。

_

_

Lucene定义多种DocValues类型,每种类型的存储方式有区别,但有一点是相同的:DocIDSet和DocValues均为分开存储的。关于DocValues部分其实是一个大话题,这里不再过多展开。

倒排索引

与Field存储相较而言,倒排索引的构建则要复杂很多,因为涉及到整个Segment级别的信息处理,比如Term在哪些文档出现了,在每个文档分别出现几次,每次出现在什么位置等等,这些信息都是需要站到Segment这个视角上才能够收集。

Lucene中的倒排索引实现分成两类:一种是传统的,按Segment构建的Postings,这是我们通常理解的倒排索引结构;另一种方式是在每个上文档构建的TermVectors,又叫词向量或者文档向量。

Postings

Posting是大家所熟悉的结构:左边是Terms列表,记录Field中出现的所有的Terms,也是叫TermsDictionary;右边是Postings,记录Term所对应的所出现哪些文档的文档号,出现次数,位置信息等。示意图如下:

在构建Posting过程中需要考虑如何收集Terms的位置信息和统计信息,还要考虑在大规模的数据量级下如何去重和排序。这些都是实现倒排索引需要考虑的关键问题,一些不合理的细节所导致的额外性能开销,就会直接影响全局索引性能。

现在我们来看一下Lucene构建Posting的过程: 在实时索引时,Postings先在内存中临时构建。Field被分词后变成一系列Terms的集合,而后遍历这个Terms的集合,为每个Term分配一个ID,叫TermID。Lucene用一个类HashMap的数据结构来存储Term与TermID的映射关系,同时实现去重的目的。分配完TermID之后,后续就可以使用TermID来表示Term。

在Postings构建过程中,会在PostingsArrays存储上个文档的DocID和TermFreq,还有Term上次出现的位置和位移信息。PostingsArrays由几个int[]组成,其下标即为TermID(TermID是连续分配的整型数,所以PostingsArrays是紧凑的),对应的值便是记录TermID上一次出现的相关信息。就是说,Lucene用多个int[]存储Term的各种信息,一个int[]存放TermID的一种信息。

Lucene为了能够直接使用基本数据类型(基本类型有两大好处:减少内存开销和提升性能),所以才有了PostingsArrays结构。为了便于理解,PostingsArrays可以表示为Postings[],每个Postings对象含有docFreq,intStart,lastPos等属性。

_

_

PostingsArrays这个结构只保留每个TermID最后出现的情况,对于TermID每次出现的具体信息则需要存在其它的结构之中。它们就是 IntBlockPool& ByteBlockPool,它能有效的避免Java堆中由于分配小对象而引发内存碎片化从而导致Full GC的问题,同时还解决数组长度增长所需要的数据拷贝问题,最后是不再需要申请超大且连续的内存。

限于篇幅,关于这两个结构的细节设计将在下一篇文章中分享。这里我们暂且将其看成两个连续的int[]和byte[],Postings的数据实际只存储在BytesBlockPool(byte[])一个地方,IntBlockPool(int[])中存储的是索引。

需要注意的是,Postings是在byte[]存储的结构是一个表尾增加的链表结构,在构建索引的时候用IntBlockPool来记录Term下一次要写的位置。也就是说,PostingsArrays的intStarts[]是Term的byte[]的表尾,而表头是记录在PostingsArrays的byteStart上,这也是一个int数组,记录每个Term的在BytesBlockPool的起始位置。有了表头和表尾之后,我们就可以ByteBlockPool里拿到整个链表了。

_

_

为什么不能直接写磁盘? 这是因为在构建过程中无法知道Postings有多长,不能确定要预留多少空间;另外构建过程中Term是随机出现的而非有序的;最后是Term难以再排序,只能按TermID的顺序处理。

为什么需要postingsArrays? 因为写到byte[]的只是增量,那么就需要找到上次的Term出现情况才能计算。如果总是在byte[]上查找则显得过重,因为Postings存储在byte[]时,它的结构是一个单向链表。有了PostingsArrays中记录的上条信息,则便于计算增量。

这里多提一点,Lucene在Segment提交之前,实现上不是在写Buffer,而是先在内存上构建了。当Segment提交之后,将内存上的索引重新编码之后再刷磁盘。 也就是说,索引在构建时写在内存的数据结构和编码与最终写在磁盘上的结构完全不一样。 基于以上,且不仅限以上原因,需要先收集posting的信息。知道这点之后,至于它叫什么,是缓冲,预构建,还是收集都是一样的。

_

_

收集完,也就是已经把整个Segment的文档全部遍历了,此时触发Flush的操作。然后,将Term排序之后编排成TermEnum格式,此处进入索引写磁盘的步骤了。

关于倒排索引更多信息,在前两篇文章中已经详细披露了。

TermVectors

上面已经用了比较长的篇幅来介绍Posting。接下来简单介绍第二种结构,需要存储的数据跟第一种实际上一样的,都是Term和Term的统计信息、位置信息。只不过,TermVectors在Postings的基础又将Terms按文档做了重新排序。同一个文档中,如果一个Field中出现了一个同名的Term出现了两次,则会被分开记录两次。

回顾一下Postings中记录的几种信息:

TermFreq :在一个文档中出现的次数,通过与DocID成对出现。

Position :Term出现的位置,相当于DocID。

Offset :在文档内的位移,与Position一起才能确定一个位置。

Payload :附加信息,如词性等,可用于自定义评分等。

__

这些信息也是TermVectors需要记录的。显然这些信息实际上与是否在文档内并无影响,所以TermVectors记录信息实际上Postings并无太大差别。只不过对于TermVectors是已经知道DocID的,所以并不会在所有Term上记录DocID。当然,Freq、Position和Offset也不会记录在其它Documnet出现的情况了。 此外还有一点需要注意的,TermVectors把Term所有信息都记录在同一个文件上(.tvd),这与Postings的记录方式是一样的。Postings将它们拆分成三个文件分别存储DocID和TermFreq、Position和Offset、Payload。

Lucene在存储TermVectors的时候,默认将4096个文档打包成一个chunk来存储。在一个chuck的结构如上图,这里想强调的是,TermFreq/Position/Offset/Payload的存储格式基本一样,这里以TermFreq为例。

假设有个 Term="Solr" 出�