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

前言

在全文检索领域, Lucene可谓是独领风骚数十年。倒排索引构成全文检索的根基,只有深入理解了倒排索引的实现原理,才能算是入门了全文检索领域。本文将对Lucene的倒排索引的实现原理和技术细节进行详细的剖析,这些内容适用于Lucene 5.x至7.x系列版本。文章整体内容组织如下:

  1. 倒排索引理论
  2. Lucene倒排索引实现
  3. Lucene索引文件构成
  4. 什么是Terms Index?
  5. 什么是Terms Dictionary?
  6. 结束语

理论

在学术上,倒排索引结构非常简明易懂,如下:

也许你已接触过倒排索引,下面这张图你或许已经看过很多次了。本文将从你熟悉的部分开始,一步步深入去挖掘这张图的一个个细节。这里先介绍两个重要概念:

  1. 索引,索引词表。倒排索引并不需要扫描整个文档集,而是对文档进行预处理,识别出文档集中每个词。

  2. 倒排表,倒排表中的每一个条目也可以包含词在文档中的位置信息(如词位置、句子、段落),这样的结构有利于实现邻近搜索。词频和权重信息,用于文档的相关性计算。

倒排索引由两部分组成,所有独立的词列表称为索引,词对应的一系列表统称为倒排表。 —— 来自《信息检索》

如图,整个倒排索引分两部分,左边是Term Dictionary(索引表,可简称为Dictionary),是由一系列的Terms组成的;右边为Postings List(倒排表),由所有的Term对应的Postings组成。

实际上Lucene所用的信息信息检索方面的术语基本跟Information Retrieval(《信息检索》原版)保持一致。比如Term、Dictionary、Postings等。

首先,有必要解释一下,每个Segment中的每个字段(Field)都有这么一个独立的结构。其次,它是不可改写的,即不能添加或更改。至于为何选择不可改写的设计,简单说有两个方面:一是更新对磁盘来说不够友好;另一方面是写性能的影响,可能会引发各种并发问题。

我们可以用一个HashMap来简单描述这个结构:Map<String, List<Integer>>,这个Map的Key的即是Term,那它的Value即是Postings。所以它的Key的集合即是Dictionary了,这与上图的描述太贴切了。由于HashMap的Key查找还是用了HashTable,所以它还解决Dictionary的快速查找的问题,一切显得太美好了。这可以说是一个hello world的倒排索引实现了。

Lucene的实现

全文搜索引擎通常是需要存储大量的文本,Postings可能会占据大量的存储空间,同样Dictionary也可能是非常大的,因此上面说的基于HashMap的实现方式几乎是不可行的。在海量数据背景下,倒排索引的实现都极其复杂,因为它直接关系到存储成本以及搜索性能。为此,Lucene引入了多种巧妙的数据结构和算法。

Lucene索引文件构成

我们知道Lucene将索引文件拆分为了多个文件,这里我们仅讨论倒排索引部分。Lucene把用于存储Term的索引文件叫Terms Index,它的后缀是.tip;把Postings信息分别存储在.doc.pay.pox,分别记录Postings的DocId信息和Term的词频、Payload信息、pox是记录位置信息。Terms Dictionary的文件后缀称为.tim,它是Term与Postings的关系纽带,存储了Term和其对应的Postings文件指针。

总体来说,通过Terms Index(.tip)能够快速地在Terms Dictionary(.tim)中找到你的想要的Term,以及它对应的Postings文件指针与Term在Segment作用域上的统计信息。

postings: 实际上Postings包含的东西并不仅仅是DocIDs(我们通常把这一个有序文档编号系列叫DocIDs),它还包括文档编号、以及词频、Term在文档中的位置信息、还有Payload数据。

所以关于倒排索引至少涉及5类文件,本文不会全面展开。

什么是Terms Index

下面引用了一张来自网络上的图,非常直观:

Terms Index即为上图中.tip部分,它实际上是由一个或多个FST组成的,Segment上每个字段都有自己的一个FST(FSTIndex)记录在.tip上,所以图中FSTIndex的个数即是Segment拥有字段的个数。另外图中为了方便我们理解把FST画成Trie结构,然后其叶子节点又指向了tim的Block的,这实际上是用了一种叫Burst-Trie的数据结构。

Burst-Trie

.tip看起来是像一棵Trie,所以整张图表现出来就是论文上的Burst-Trie结构了。上面一棵Trie,Trie的叶子节点是Container(即是Lucene中的Block)。下图就是Paper上描述的Burst-Trie的结构:

来自Burst-Trie论文上的一张图

Burst-Trie,关于Burst-Trie,网上有很多专业资料,这里只做简单介绍。Burst-Trie可以认为是Trie的一种变种,它主要是将后缀进行了压缩,降低了Trie的高度,从而获取更好查询性能。

Lucene工程上的实现方式

Burst-Trie在Lucene是如何应用的?

前面提到了Lucene是采用Burst-Trie的思想,但在实现上存在一定的出入,Lucene的Burst-Trie被拆成两部分。如果一定把它们对应起来的话,我认为Burst-Trie的AccessTree的实现是FST,存在.tip文件中;Container的实现是Block,存在.tim文件里。Burst-Trie的Container内部是开放性结构,可能是Binary-Tree,可以也List。Lucene的block是数组,准确的说,就是把一系列的Block系列化写到文件上,这里好像并没有做特殊的处理。

FST

在Lucene,Terms Dictionary被存储在.tim文件上。当一个Segment的文档数量越来越多的时候Dictionary的词汇也会越来越多,那查询效率必然也会逐渐变低。因此需要一个很好的数据结构为Dictionary建构一个索引,将Dictionary的索引进一步压缩,这就是后来的Terms Index(.tii)。这是在早期的版本中使用的,到Lucene 4.0之后做一次重构和升级,同时改名为.tip。

FST:Finite-State-Transducer,结构上是。我们知道把一堆字符串放一堆,把它们的共同前缀进行压缩就会变成Burst-Trie。如果把后缀变成一个一个节点,那么它就是Trie结构了。如果将后缀也进行压缩的话,那你就能发现他更变成一张图结构了。 那么我们易知FST是压缩字典树后缀的图结构,她拥有Trie高效搜索能力,同时还非常小。这样的话我们的搜索时,能把整个FST加载到内存。

实际上,FST的结构非常复杂,我们可以简单的将其理解为一个高效的K-V结构,而且空间占用率更高。这里想简单强调一下:Lucene到底在FST里存了什么数据? 如果你已经了解FST在Lucene中充当的角色和作用的话,我想你可能会误认为FST中存了Dictionary中所有的Terms数据,这样可以通过FST是找到具体的Term的位置,或者通过FST可以切实获知一个Term是否存在。

然而,事实并非如此。 FST即不能知道某个Term在Dictionary(.tim)文件上具体的位置,也不能仅通过FST就能确切的知道Term是否真实存在。它只能告诉你,查询的Term可能在这些Blocks上,到底存不存在FST并不能给出确切的答案,因为FST是通过Dictionary的每个Block的前缀构成,所以通过FST只可以直接找到这个Block在.tim文件上具体的File Pointer,并无法直接找到Terms。关于FST的详细细节,后面将以一篇独立的文章来讲解,这里暂时不展开过多细节。

下面会详细的介绍Dictionary的文件结构,这里先提一下。每个Block都有前缀的,Block的每个Term实际不记录共同前缀的。只有通过Block的共同的前缀,这是整个Block的每个Term共同的,所以每个Term仅需要记录后缀可以通过计算得到,这可以减少在Block内查找Term时的字符串比较的长度。

简单理解的话,你可以把它当成一个高级的BloomFilter,我们BloomFilter是有一定的错误率的;同时BloomFilter是通过HashCode实现的,只能用它来测试是否存在,并无法快速定位。在FST中,并无错误率且能快速定位。但是BloomFilter有更高的性能。

说了这么多,Terms Index到底带来哪些实质性的功能呢? Terms Index是Dictionary的索引,它采用 了FST结构。上面已经提及了,FST提供两个基本功能分别是:

  1. 快速试错,即是在FST上找不到可以直接跳出不需要遍历整个Dictionary。类似于BloomFilter的作用。

  2. 快速定位Block的位置,通过FST是可以直接计算出Block的在文件中位置(offset,FP)。

上面已经介绍了FST的一种功能,此外,FST还有别的功能,因为FST也是一个Automation(自动状态机)。这是正则表达式的一种实现方式,所以FST能提供正则表达式的能力。通过FST能够极大的提高近似查询的性能,包括通配符查询、SpanQuery、PrefixQuery等,甚至包括近期社区正在做的基于正则表达式的查询。

什么是Terms Dictionary?

前面我们已经介绍了Terms Dictionary的索引,Terms Index。已经频频提到的Terms Dictionary到底是什么东东?Terms Dictionary是Segment的字典,索引表。它能够让你知道你的查询的这个Term的统计信息,如tf-idfdf(doc_freq)Total Term Frequence(Term在整个Segment出现频率);还能让你知道Postings的元数据,这里是指Term的docids、tf以及offset等信息在Postings各个文件的文件指针FP。

Block并不记录这个Block的起始和结束的范围,所以当FST最终指向多个Block时,就会退化为线性搜索。那什么时候会出现FST最终指向多个Block呢?最简单的一种情况是,超过48个的Term,且出现首字母相同的term的个数不超过25个。这种情况下由于没有每个Block都没有共同前缀,所以构建出来的FST只有一个结束节点记录每个Block的文件寻址的偏移增量。

Lucene规定,每个Block的大小在25-48范围内

说这么多,还是觉得太抽象了,我们来看一下.tim文件结构示意图:

主要是大两部分信息,1. Block信息,包含所有Term的详情;2. Field的自有属性和统计信息。接下来我们将展开来介绍这两部分内容。

Block信息 — NodeBlock

在整个.tim文件上,我觉得比较复杂且值得拎出来讲的只有NodeBlock。那么,Block又是什么东东?它是如何被构建的?这部分代码,还是比较晦涩难懂得,我每次读时也都会产生一些新的疑问。

我们前面所有说的Block即是NodeBlock的一个Entry。 由上图可以知道,Block中有两种OuterNode和InnerNode。这里我想引用代码上两个类名来辅助我们接下来的剖析:PendingTerm/PendingBlock,我们暂且把它们叫作待写的Term子Block的指针吧。

NodeBlock从构建逻辑上来讲是它是树型结构,所以它由叶子节点和非叶子节点两种节点组成。叶子节点就叫OutterNode,非叶子节点就叫InnerNode。一个Block可能含有一堆的Term(PendingTerm)和PendingBlock(当它是非叶子节点时),实际上PendingBlock也是不可能出现在叶子节点上的。如果是PendingBlock,那么这个Entry只记录两个信息:后缀(这个Block的共同后缀)以及子Block的文件指针,此时就不必再记上所说的统计信息和postings信息了。

如图所示,一个Block记录的信息非常多,首先是Block的类型和Entry的条数等元数据信息,而后是该Block拥有的所有Entry。

这里每个Entry含有后缀、统计信息(对应为前面据说的权重,它含有ttf和df)、Postings的位置信息(这就是反复提及postings相关的文件指针,postings是拆分多文件存储的)。 关于Postings更多细节,放到下个章节来讨论。

Field信息 — FieldMetadata

相对来说FieldMetadata组织结构就简单多了,纯粹的线性写入即可。但Field信息记录的内容还是挺多的,包括字段本身的属性,如字段编号、Terms的个数、最大和最小的Terms;此外还记录了Segment级别的一些统计信息,包括tdf、拥有该字段的文档总数(如果文档没有该字段,或者该字段为空就不计了)。

  1. RootCode实际上指向该字段第一个Block的文件指针。

  2. LongsSize这个名字有点隐晦,它是说该字段的字段存储哪些Postings信息。因为我们是可以指定Postings存储或者不存储诸如位置信息和Payload信息的,存与不存将被表现在这里了。

从搜索流程来看,Lucene先读到FieldMetadata的信息,然后判断Query上Terms是否落在这里字段的MinTerm和MaxTerm之间。如果不在的话,完全不需要去读NodeBlock的。MinTerm和MaxTerm可以有效的避免读取不必要的.tip文件。

结束语

到这里,关于倒排索引结构中第一部分内容已经介绍完了,限于篇幅的原因,还有更多有趣的小细节没有呈现出来。简单总结一下:我们先从Information Retrieve开始了解学术上倒排索引结构,接着我们又对Luecne的实现做了深入剖析。Lucene对索引词表也做了索引(叫Terms Index,文件后缀是.tip),索引词表的索引采用Finite-State Transducer这种数据结构。由于这种结构占用空间极小,所以它完成可以被加载到内存加速Terms Dictionary的查找过程。而后又介绍了Terms Dictionary,Terms Dictionary以Terms Index共同构成与Burst-Trie类似的数据结构,Terms Dictionary含两部分信息:1. NodeBlock记录Dictionary的所有Terms;2. FieldMetadata存储了FieldInfos信息和Segment的统计信息。

关于倒排索引还有Postings List,这部分内容将在下篇文章中介绍。

Leave a Reply

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