Lucene倒排索引原理探秘(4)

在《Lucene倒排索引原理探秘(1)》和《Lucene倒排索引原理探秘(2)》两篇文章中详细介绍了Lucene的倒排索引文件组织结构,这为高效的搜索过程奠定了良好的基础。

我们已经知道,Lucene的倒排索引有两种格式:一种是用于搜索的Postings;另一种是TermsVectors。这两种索引的构建过程基本相同,只是写文件时在编排方式上有所差异,在《Lucene倒排索引原理探秘(3)》一文中已经做了详细介绍。

在构建倒排索引的过程中,Lucene需要收集每个Term在整个Segment中的相关信息(DocID、TermFreq、Position、Offset、Payload),并且将这些信息存储下来,如下图所示。因此,在索引阶段,如何高效的收集这些信息,显得至关重要,本文将以Postings索引格式为例,详细探讨Lucene索引过程中所采用的数据结构与技术手段。

数据结构

Lucene设计了一系列内存高效的数据结构,通过对象复用内存分页的思想,来优化Java GC问题。这部分内容将围绕ByteBlockPoolByteRefHashPostingsArray三个结构展开。

ByteBlockPool

ByteBlockPool是Lucene实现高效的可变长的基本类型数组,但实际上数组一旦初始化之后长度是固定的,因为数组申请的内存必须是连续分配的,以致能够提供快速随机访问的能力。那么ByteBlockPool是如何实现的?

Buffer结构

在JDK中,以数组为底层存储的数据结构,如ArrayList/HashMap,实现可增长时都需要花费一定的代价。数组增长的过程分两步,首先申请更大数组,然后将原数组复制到新数组中。即使JVM已经对数组拷贝做了很多优化,但随着数据量的不断增大,拷贝的性能开销问题也会越来越凸显,同时,数组的频繁创建也都会加大JVM的GC负担。

ByteBlockPool是一个可动态增长的结构,如下图所示:

ByteBlockPool是一个由多个Buffer构成的数组,如上图右侧所示,左侧的数字则代表了每一个Buffer在这个二维数组中的Index位置。Buffer的长度是固定的,当一个Buffer被写满以后,需要申请一个新的Buffer,如果这个Buffer数组要扩展,仅仅是将已有Buffer的引用拷贝了一次,而不需要拷贝数据本身。Buffer本质上是一个byte[],因此,ByteBlockPool其实是一个byte的二维数组,用Buffer数组来表达则更易理解。

Slice链表

索引构建过程需要为每个Term分配一块相对独立的空间来存储Posting信息。一个Term可能会出现在几个文档中,而且在每个文档出现的次数和位置都无法确定,所以Lucene无法预知Term需要多大的数组来存储Posting信息。

为此Lucene在ByteBlockPool之上设计了可变长的逻辑结构,这结构就是Slice链表。它的节点称之为Slice,Lucene将Slice分成十个级别,逐层递增,十层之后长度恒定。Slice的最后一个位置用于存储下个节点Offset,对于最后一个Slice,则存储了下个Slice的层级数。

Slice节点可以跨越多个Buffer,Slice链表为我们提供了一个逻辑上连续的内存块。如果将Slice链表理解成类分布式文件系统上的文件,每个Slice则是文件的数据块,不过文件系统的数据块的大小是固定的,而Slice的长度则是分层级的。

这种设计方案的一个好处:Buffer是相对比较紧凑的结构,能够更高效的利用Buffer内存。按Zipf定律可知一个单词出现的次数与它在频率表里的排名成反比,也就是说可能会有很多Term的频率是很低的,同样也有小部分Term的频率则非常高,Slice的设计正是考虑到了这一分布特点。

ByteBlockPool与IntBlockPool设计思想完全一样,IntBlockPool只能存储int,ByteBlockPool存储byte,这里我们不再赘述。Lucene仅实现这两种基础的数据类型,其它的类型可以通过编码之后用ByteBlockPool来存储。

BytesRefHash

Lucene在构建Postings的时候,采用一种类似HashMap结构,这个类HashMap的结构便是BytesRefHash,它是一个非通用的Map实现。 它的非通用性表现在BytesRefHash存储的键值对分别是Term和TermID,其次它并没有实现Map接口,也没有实现Map的相关操作。

Term在Lucene中通常会被表示为BytesRef,而BytesRef的内部是一个byte[],这是一个可以复用的对象。当通过TermID在BytesRefHash获取词元的时候,便将ByteBlockPool的byte[]拷贝到BytesRef的byte[],同时指定有效长度。整个BytesRefHash生存周期中仅持有一个BytsRef,所以该BytesRef的byte[]长度是词元的长度。

BytesRefHash用来存储Term和TermID之间的映射关系,如果Term已经存在,返回对应TermID;否则将Term存储并且生成TermID后返回。Term在存储过程BytesRefHash将BytesRef的有效数据拷贝在ByteBlockPool上,从而实现紧凑的key值存储。TermID是从0开始自增长的连续数值,存储在int[]上。BytesRefHash非散列哈希表,从而TermID的存储也是紧凑的。

因为BytesRefHash为了尽可能避免用到对象类型,所以直接采用int[]存储TermID,实际上也就很难直接采用散列表的数据结构来解决HashCode冲突的问题。

Lucene构建倒排索引的过程分了两步操作,构建Postings和TermVectors。它们俩过程共享一个ByteBlockPool,也就是在每个DocumentsWriter共用同一个ByteRefHash(因为BytesRefHash以ByteBlockPool都不是线程安全的)。它为Postings收集过程提供去重和Term与TermID对应关系的存储及检索等功能。

3. PostingsArrays

从PostingsArrays名字上容易被误以为是存储Postings数据的结构,实则不然。在Postings构建过程中,Lucene将各项信息写到ByteBlockPool的Slice链表上。链表是单向链表,它的表头和表尾存储到PostingsArrays,从而能够快速写入,并且可以从头开始遍历。这个结构曾在《番外篇:Lucene索引流程与倒排索引实现》一文中介绍过。

PostingsArrays除了记录了Slice链表的索引之外,它还存储上个文档的DocID和TermFreq,还有Term上次出现的位置和偏移信息。PostingsArrays由几个int[]组成,其下标都是TermID(TermID是连续分配的整数),对应的值便是记录TermID上一次出现的各种信息。

Lucene为了能够直接使用基本类型数据,所以才有了PostingsArrays结构。方便理解你可以理解成是Postings[],每个Postings对象含有DocId,TermFreq,intStarts,lastPosition等属性。

索引构建过程

在索引构过程中,Term由TextField经过TokenStream处理之后产生,它由一个可复用对象BytesRef表示。在建构索引的链路上,Lucene更多是用TermID来表示Term。

当Term第一次出现时,Lucene尝试在BytesRefHash取到TermID失败,此时Lucene将它的状态标记”新人"。新出现的Term作为”新人”,需要在BytesRefHash上为它分配一个”证件号码”(TermID)。在PostingsArrays中会登记他的”户籍信息”,包含他的名字(BytesRef的byte[])在哪个位置(前面提过,BytesRefHash直接把Term存储在ByteBlockPool上,所以需要把位置记下来);还会为他建立一个履历档案(第一Slice链表),记录他将来在每个年级(DocID)的考试次数(TermFreq)。

在每一个”地区”,还可以为Term建立另外一份档案(第二Slice链表)用于记录每次考试的情况,比如班级(Position),座位号(Offset),以及成绩(Payload)。这些数据是Term成长过程的产生,经历一次记一次。关于每次考试的情况,第一次考试Lucene直接把它写入ByteBlockPool的Slice链表上,同时会记录增量信息,为了节省内存空间,Position/Offset第二次及以后都用VInt来记录这个增量值。

这就是PostingsArrays需要记录lastPosition/lastOffset的原因,而lastDocID和lastTermFreq不仅可用计算增量,还可以用来计算Term每次出现后TermFreq的累加值。需要说明的一点:每个信息在Slice中没有索引,不方便回溯和修改。

构建索引的过程是ByteBlockPool(IntBlockPool)、BytesRefHash和PostingsArrays三者之间的协作,如下图所示:

这里为了简化流程,图中将IntBlockPool简化成为int[],也就是说它也是Slice的方式实现连续的链表。

PostingsArrays的byteStarts[TermID]记录Term的两个链表的表头在ByteBlockPool的绝对位置,intStarts[TermID]记录下次要写的位置,则textStarts[TermID]则记录BytesRefHash把Term存储在ByteBlockPool的哪个位置上。

为什么byteStart和intStart需要先指向IntBlockPool呢? 主要是因为TermID可能对应了两条Slice链表,以TermID为索引的数组不方便存储。通过IntBlockPool可以方便处理,仅需要IntBlockPool连续两个位置,下一个位置用于存储第两个Slice链表。IntBlockPool的引入虽然让这个过程变得更复杂了,但也更体现了Lucene的设计之精湛和巧妙。

在索引提交的时候,Lucene将这两个Slice链表的数据通过PostingsEnum遍历出来,交由BlockTreeTermsWriter完成索引文件的输出。至此,已经完成了一轮构建索引的流程。

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注