Lucene倒排索引实现原理探秘(2)

上篇文章详细介绍了Lucene索引表的实现,内容涉及关于Terms Index以及Term Dictionary的剖析:

Lucene倒排索引实现原理探秘(1)

此文将继续剖析Lucene倒排索引实现的另一部分核心内容: 倒排表(Postings)。Lucene的官方文档关于该部分内容的描述非常丰富,所以学习起来也相对轻松。

Postings编码

开始之前先介解Lucene在Postings采用了两个关键的编码格式,PackedBlock和VIntBlock。PackedBlock是在Lucene 4.0引入,带来向量化优化。

VIntBlock

VIntBlock是能够存储复合数据类型的数据结构,主要通过变长整型(Variable Integer)编码达到压缩的目的。此外VIntBlock还能够存储byte[],比如.pay用VIntBlock存储了payloads数据等。

值得一提的是,VIntBlock可以存储变长数据结构,如.doc用它存储DocID和TermFreq时,由于在特定条件下(TermFreq=1),Lucene会省略TermFreq以提高空间占用率。Lucene用一个VInt来表示DocID,VInt则用每个Byte左边第一个Bit来表示是否需要读取顺续到下个Byte。也就是说一个VInt有效位是28bit,这就说明VInt头部是有特殊含义的,因此Lucene只能在VInt最右边的一个bit下功夫。让VInt的右边第一Bit来表示是否有下个数据。

具体用法会在介绍.doc文件格式时介绍。

PackedBlock

PackedBlock只能存储单一整数(Integer/Long)数组结构。这里主要介绍PackedInts:它将一个int[]打包成一个Block。PackedBlock只能存储固定长度的数组(Lucene规定其长度为128个元素),它的压缩方式是将每个元素截断为一个预算的长度(length,单位是bit),以达到压缩的目的。所以当长度length不是8的倍数时,会出现一个byte被多个元素占用的情形。

PackedBlock需要把整个int[]的所有条目指定长度编码,所以PackedBlock只能选择int[]最大的数来计算长度,否则会让大数失真。反过来,PackedBlock都选择64位,则会浪费空间,不能达到压缩的目的。

Lucene预先编译了64个PackedFormat编码器和解码器,即针对Long以内的每种长度都数据都有自己的解码和编码器,以提高编解码的性能。

PackedPosDeltaBlock、PackedDocDeltaBlock以及PackedFreqBlock都采用了PackedInts结构,它能存储的信息实际上是很有限的,只能存储Int的数组。所以在PackedPosDeltaBlock的时候,只能存储position信息,在VIntBlock则会存储更多必要信息,减少搜索时的IO操作。

这也是为什么需要将DocId和TermFreq拆分成PackedDocDeltaBlock和PackedFreqBlock两个Block存储的原因了。

定长是指PackedBlock限定了一个Block仅允许存储长度128的整型数组,而不是限定Block用多少个Bytes来存储编码后的结果。另外Block存储占用的大小,是按数组中最大那个数的有效bits长度来计算整个Block需要占用多大的Bytes数组的。也就是Block的每个数据的长度都是一样,都按最长bits来计算。

比如:(我们定义一个函数,bit(num)用来计算num占用多少个bits)

  1. 数组中最大的是1,那么PackedBlock的长度仅是16Bytes。bit(1) * 128 / 8 = 16
  2. 数组中最大的是128,PackedBlock长度则是144个Bytes。bit(128) * 128 / 8 = 144
  3. 数组中最大的是520,PackedBlock则需要160Bytes。bit(520) * 128 / 8 = 160

简单总结一下,PackedBlock相当于实现了向量化优化,Lucene通常会将整个PackedBlock加载到内存,既可以减少IO操作数,又能提高解码的性能。相对而言VIntBlock则能够更丰富数据类型,比较适合存储少量数据。

Postings文件格式说明

进入正题,我们知道整个Postings被拆成三个文件存储,实际上它们之间也是相对独立的。基本所有的查询都会用.doc,且一般的Query仅需要用到.doc文件就足够了;近似查询则需要用.pox;.pay则是用于Payloads搜索(关于这个之前写一篇博客《Solr 迟到的Payloads》,介绍了Payloads用法和场景)。

Frequencies And Skip Data(.doc文件)

在Lucene倒排索引中,只有.doc是Postings必要文件,即它是不能被省略的。除此之外的两个文件通过配置都是可以省略的。那么.doc到底存储了哪些关键信息呢?直接上图:

这里画得不够清晰,每个Term都有成对的TermFreqs和SkipData的。换言之,SkipData是为TermFreqs构建的跳表结构,所以它们是成对出现的。

TermFreqs — Frequencies

TermFreqs存储了Postings最核心的内容,DocID和TermFreqs,分别表示文档号和对应的词频,它们是一一对应的,Term出现在文档上,就会有Term在文档中出现次数(TermFreqs)。

Lucene早期的版本还没有PackedBlock结构,所以DocID与TermFreq是以一个二元组的方式存储的。这个结构简单,有助于理解,但却并不准确。既然是想深入剖析,还是有必要还原真相的。

TermFreqs采用的是混合存储,由Packed Blocks和VInt Blocks两种结构组成。由于PackedBlock是定长的,当前Lucene默认是128个Integers。所以在不满128个值的时候,Lucene采用VIntBlocks结构存储。需要注意的是当用Packed Blocks结构时,DocID和TermFreq是分开存储的,各自将128个值写入到一个Block。

当用VIntBlocks结构时,还是沿用旧版本的存储方式,即上面描述的二元组的方式存储。所以说,将DocID和TermFreq当成一条数据的说法是不完全准确的。

在Lucene4.0之前的版本,还没有引入PackedBlock时,DocID和TermFreq确定完全是成对出现,当时只有VIntBlock一种结构。

Lucene尽可能优先采用PackedBlocks,剩余部分(不足128部分)则用VIntBlocks存储。引入PackedBlock之后,PackedDocDeltaBlock跟PackedFreqBlock是成对的,所以它的写出来的示意图应该是如下:

每个PackedBlock由一个PackedDocDeltaBlock和一个PackedFreqBlock构成,它们都采用PackedInts格式。

例如,在同一个Segment里,某一个Term A在259个文档同一个字段出现,那么Term A就需要把这259个文档的文档编号和Term A在每个文档出现的频率一同记下来存储在.doc。此时,Lucene需要用到2个PackedBlocks和3个VIntBlocks来存储它们。

VIntBlock结构相对复杂一些,它以一种巧妙的方式存储复杂的多元组结构。在.doc文件中,用VIntBlock存储DocID和TermFreqs二元组。后面将介绍的Positions则用VIntBlock存储了Postition、Payload和Offset多元组, byte[]和VInt多种数据类型。

这里每一个PackedBlock结构都包含了一个PackedDocDeltaBlock和一个PackedFreqBlock,如果没有省略Frequencies(TermFreq);如果用户配置了不存储词频(TermFreq),此时一个PackedBlock仅包含一个PackedDocDeltaBlock。PackedFreqBlock(TermFreq)的存储方式跟PackedDocDeltaBlock(DocID)完全一致,包括后面要讲的pos/pay也都一样的,都使用Packed Block这种编码方式。

在VIntBlock上如何存储DocDelta和TermFreq?如果设置了不存储TermFreq时,Lucene将所有DocDelta以Variable Integer的编码方式直接写到文件里。当设置为存储TermFreq信息时,实际上,TermFreq信息会被按需存储。Lucene做了一个小优化,即当TermFreq=1时,TermFreq将不被存储。那么原本DocDelta(DocID的增量)后面紧跟一个Frequencies的情况变得不再确定,因为压根无法知道DocDelta后面还有没有TermFreq信息。那应该如何识别TermFreq信息是否存在?Lucene先把数值向左移动一位,然后用最右的一个Bit的标记是否存储TermFreq。最后右边的一个bit1表示没有存储,0作为有存储TermFreq。实际上这是Lucene的惯用手段。

左移一位,实际上等同于X2,当最后一个bit是0,此时是一定是偶数,表示后面还存 储了TermFreq;左移一位再+1,相当于偶数+1,那就是奇数,此时最后一个bit是1,表示TermFreq=1,所以后面没有存储TermFreq。

DocFreq=1时,Lucene做一个叫Singletion(仅出现在一个文档中)的优化,此时就没有TermFreq和SkipData。因为TermFreq等同于TotalTermFreq(上篇文章介绍过,存储在.tim的FieldMetadata上)。

Multi-level SkipList — SkipData

SkipData是.doc文件核心部件之一,Lucene采用的是多层次跳表结构,首先我们先预热一下SkipList的逻辑结构图,最后剖析Lucene存储SkipList的物理结构图。下图(源自网图)很好的描述了SkipList的结构:

跳表的原理非常简单,跳表其实就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置,然后再跳到次高级索引继续查找,直到跳到最底层为止,这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素,所以跳查找的查找速度也就变快了。 ——— 百度百科

将搜索时耗时转嫁给索引时,这就是Lucene索引的“空间换时间”的基本思想。为此Lucene为Postings构建SkipList ,并把按层级将它系列化存储。第一个SkipLevel是最高,拥有最少的索引数。

Lucene在索引时构建了SkipList,在Segment中每个Term都有自己唯一的Postings,每个Postings都有需要构建一个SkipList,这三者是一一对应的。所以画出来结构图如下:

除了第0层之外所有SkipLevel的每个跳表数据块(SkipDatum)会存储了指向下一个SkipLevel的指针。图中SkipChildLevelFPg带?的原因是在Level 0时,SkipDatum没有下一级可以记录。如果Postings有存储positions、payloads和offsets的话,在跳表数据块中也会记录它们的Block所有文件指针。

通过SkipList可以找到DocID和TermFreq之外,还能找到Positions、Payloads和Offsets这三部分信息。因此,在搜索时通过SkipList可以快速定位Postings的所有相关信息。

关于Lucene构建SkipList的几点细节(Lucene规定SkipList的层级不超过10层):

  1. 第0层,SkipList为每个Block增加索引,所以VIntBlock不在SkipList上。
  2. 第9层,SkipList的第一个节点是在第89 (227)Block。(这个数确实有点大)
  3. 第n层,SkipList的第m个节点的位置是第8^n * m个Block。

跳表的第一层是最密的,越高层越稀疏。按层级从低到高依次系列化为写入.doc的SkipData部分。换言之,SkipDatum个数越多,SkipLevelLength则会越大。

SkipLevelLength说明当前层次Skip系列化之后的长度,SkipLevel是包含该层的所有节点的数据SkipDatum。SkipDatum包含四部分信息,doc_id和term_freq、positions、payloads、以及下一层开始的位置(是第N层指向第N-1层的前一个索引)。

SkipList主要是搜索时的优化,主要是减少集合间取交集时需要比较的次数,比如在Query被分词器分成多个关键词时,搜索结果需要同时满足这些关键词的,此时需要将每个Term对应的DocId集合进行析取操作,通过跳表能够有效有减少比较的次数。

Postitions(.pos文件)

.pos文件存储所有Terms出现文档中的位置信息。为了更好的搜索性能,Lucene还在VIntBlock上存储了部分payloads和offsets信息。实际上只有VIntBlock才有能力来存储复杂的数据结构,PackedBlock是不具备这样的能力的。具体请参考下面的示意图:

Lucene把同一个Term的所有position信息存储在同一个TermPositions上,并没有逻辑或者物理上的划分。将在一个文档里出现的所有位置信息,按出现的先后顺序依次写入。 关键在于,position与TermFreq并不是在一维度上,TermFreq的数值就是position的个数。也就是说,通过.pos文件无法知道每个position的具体含义,PostingsReader通过.doc文件的DocID和TermFreq信息才能算出Postition的是在哪个文档上的哪个位置。

Payloads and Offsets(.pay文件)

Payloads,可以理解为Term的附加信息,它是与Term成对出现的,类似于Map。在用法上也是如此,Payloads的信息需要用byte数组存储,所以在TermPayloads并不能用PackedBlock结构来存储。TermOffsets由2个int来表示Offset的开始位置和长度,可以将它们拆成两个等size的int[],因此可以用PackedBlock存储。如下图:

总结

开篇先学习了Lucene用于存储Postings的两种结构,PackedBlock和VIntBlock。PackedBlock是Lucene4.0引用的,它的核心就是一个int[],为Postings提供向量化优化,VIntBlock也是一种很巧妙且优雅的结构,能存储复杂的类型。

而后,在介绍.doc文件格式的同时,又对上面的两大结构深入剖析,了解这两个结构是理解postings的基础。接下来剖析了.doc文件上采用的SkipList数据结构,主要是搜索时集合间AND操作上的一个优化。至于postings中其它两个文件格式,仅做了简单介绍。

Lucene倒排索引部分内容到这里全部结束,包含很多优雅的设计和巧妙的结构,其中蕴含的Lucene设计之美,值得我们反复研读。

Leave a Reply

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