lucene查询原理

前言&＃xff1a;
  lucene 是一个基于java实现的全文信息检索工具包&＃xff0c;目前主流的搜索系统 Elasticsearch 和 solr 都是基于 lucene 检索功能实现的。想要理解搜索系统的实现原理&＃xff0c;就需要深入 lucene 这一层&＃xff0c;看看 lucene 是如何存储需要检索的数据&＃xff0c;以及如何完成高效的数据检索。

1. lucene 数据模型

  lucene 中包含四种基本的数据类型&＃xff1a;

• index&＃xff1a;索引&＃xff0c;由很多的 Document 组成。相当于 mysql 的数据库
• Document&＃xff1a;由很多的 Field 组成。相当于 mysql 的一行数据
• Field&＃xff1a;由 Field Name 和 Field Value 组成。相当于 mysql 的字段和字段值
• Term&＃xff1a;由很多的字节组成。一般将Text类型的 Field Value 分词之后的每个最小单元叫做 Term。

2. lucene 查询过程

  在 lucene 中查询是基于 segment。每个 segment 可以看做是一个独立的 subindex&＃xff0c;在建立索引的过程中&＃xff0c;lucene会不断的 flush 内存中的数据持久化形成新的 segment。多个 segment也会不断的被 merge 成一个大的 segment&＃xff0c;在老的 segment 还有查询在读取的时候&＃xff0c;不会被删除&＃xff0c;没有被读取且被 merge 的 segement 会被删除。这个过程类似于 LSM 数据库的 merge 过程。下面我们主要看在一个 segment 内部如何实现高效的查询。
  为了方便大家理解&＃xff0c;我们以人名字&＃xff0c;年龄&＃xff0c;学号为例&＃xff0c;如何实现查某个名字&＃xff08;有重名&＃xff09;的列表。

  每个 document 的 name value 经过分词形成多个 term&＃xff0c;多个 term 组成 term dictionary&＃xff0c;如下显示基于 name 创建倒排链如下&＃xff1a;

  在这里&＃xff0c;Alice、Alan 都是 term。所以倒排本质上就是基于 term 的反向列表&＃xff0c;方便通过属性反向查找 doc_id。
  到这里我们有个很自然的问题&＃xff0c;如何快速拿到这个倒排表呢&＃xff1f;在 lucene 里面就引入了 term dictonary 的概念&＃xff0c;也就是 term 的字典。term 字典里我们可以按照 term 进行排序&＃xff0c;那么用一个二分查找就可以找到这个 term 所对应的倒排表信息&＃xff0c;这样的复杂度是 logN。
  但在 term 很多&＃xff0c;内存放不下的时候&＃xff0c;效率还是需要进一步提升。 为解决这个问题&＃xff0c;lucene 引用 term dict index 来存放 term 的共享前缀&＃xff0c;后缀则放在 term dictonary 中。

• term dict index&＃xff1a;是采用 FST 数据结构&＃xff0c;存放在内存中。term dict index 查到对应的 term dict 的 block 位置之后&＃xff0c;再去磁盘上找 term&＃xff0c;大大减少了磁盘的 random access 次数
• Term dict&＃xff1a;在磁盘上是以分 block 的方式保存的&＃xff0c;一个 block 内部利用公共前缀压缩&＃xff0c;比如都是 Ab 开头的单词就可以把 Ab 省去
• SkipList&＃xff1a; 是以 docId 建立的数据结构

  如果所有的 term 都是英文字符的话&＃xff0c;可能这个 term index 就真的是 26 个英文字符表构成的了。但是实际的情况是&＃xff0c;term 未必都是英文字符&＃xff0c;term 可以是任意的 byte 数组。

  图示如下&＃xff1a;。

  在 term dict index 中需要保存的是 Term 的前面部分字段&＃xff0c;以及与 Term Dictionary 之间的映射关系&＃xff0c;这使得存储的信息量减少。再结合 FST&＃xff08;Finite State Transducer&＃xff09;压缩技术&＃xff0c;term dict index 可以被压缩到足够小&＃xff0c;以至于可以被缓存进服务器内存中&＃xff0c;而 Term 后缀则存放在 trem dict。
  整个检索过程如下&＃xff1a;

• 内存加载 term dict index&＃xff08;tip文件&＃xff09;&＃xff0c;通过 FST 匹配前缀找到后缀词块位置。
• 根据词块位置&＃xff0c;读取磁盘中 Term dict&＃xff08;tim 文件&＃xff09;&＃xff0c;匹配后缀&＃xff0c;读取倒排表信息。
• 根据倒排表位置去 doc文件 中加载文档数据。

  找到了倒排表&＃xff0c;怎么通过 docId 找到我们需要的文档呢&＃xff1f;

3. SkipList

  为了能够快速查找 docid 对应的 document&＃xff0c;lucene 采用了SkipList 这一数据结构。SkipList 有以下几个特征&＃xff1a;

• skipInterval&＃xff1a;该值描述了在 level&＃61;0 层&＃xff0c;每处理 N 篇 document 文档&＃xff0c;就生成一个 skipDatum&＃xff0c;该值默认为 128。
• skipMultiplier&＃xff1a;该值描述了所有层&＃xff0c;每处理 N 个skipDatum&＃xff0c;就在上一层生成一个新的 skipDatum&＃xff0c;该值默认为 8
• numberOfSkipLevels&＃xff1a;skipList中的层数

  直接给出一个生成后的跳表&＃xff1a;

  文档号0~3455的3456篇文档&＃xff0c;我们令 skipInterval 为128&＃xff0c;即每处理128篇文档生成一个 skipDatum 和对应的 PackedBlock&＃xff1b;令 skipMultiplier 为3&＃xff08;源码中默认值为8&＃xff09;&＃xff0c;即每生成3个 skipDatum 就在上一层生成一个新的 skipDatum 索引&＃xff0c;它是 3个 skipDatum 中的最后一个。对于 level > 0 的 skipDatum 都有一个索引值 SkipChildLevelPointer 字段来指向下一层对应的 skipDatum &＃xff0c;例如 level&＃61;1 的第一个 skipDatum&＃xff08;383&＃xff09;&＃xff0c;SkipChildLevelPointer 值就是 127、255、383。

哨兵数组 skipDoc

  哨兵数组skipDoc的定义如下所示&＃xff1a;

int[] skipDoc;


  该数组用来描述每一层中正在处理的 skipDatum &＃xff0c;skipDatum 对应的 PackedBlock 中的最后一篇文档的文档号作为哨兵值添加到哨兵数组中&＃xff0c;在初始化阶段&＃xff0c;skipDoc 数组中的数组元素如下所示&＃xff1a;

int[] skipDoc &＃61; {127, 383, 1151, 3455}


  初始化阶段将每一层的第一个 skipDatum 对应的 PackedBlock 中的最后一篇文档的文档号作为哨兵值。

docDeltaBuffer

  docDeltaBuffer 是一个int类型数组&＃xff0c;上文我知道一个 skipDatum 可以映射128篇文档&＃xff0c;而 docDeltaBuffer 记录了一个 skipDatum 中所有的文档号。

Lucene中使用读取跳表SkipList的过程

  读取过程分为下面三步&＃xff1a;

• 步骤一&＃xff1a;获得需要更新哨兵值的层数N
  • 从 skipDoc 数组的第一个哨兵值开始&＃xff0c;依次与待处理的文档号比较&＃xff0c;找出所有比待处理的文档号小的层
• 步骤二&＃xff1a;从 N 层开始依次更新每一层在 skipDoc 数组中的哨兵值
  • 如果待处理的文档号大于当前层的哨兵值&＃xff0c;那么令当前层的下一个 skipDatum 对应的 PackedBlock 中的最后一篇文档的文档号作为新的哨兵值&＃xff0c;直到待处理的文档号小于当前层的哨兵值
  • 在处理 level&＃61;0 时&＃xff0c;更新后的 skipDatum 对应的 PackedBlock 中的文档集合更新到 docDeltaBuffer 中
• 步骤三&＃xff1a;遍历 docDeltaBuffer 数组
  • 取出 PackedBlock 中的所有文档号到 docDeltaBuffer 数组中&＃xff0c;依次与待处理的文档号作比较&＃xff0c;判断 SkipList 中是否存在该文档号

跳表查询演示

  我们依次处理下面的文档号&＃xff0c;判断是否在跳表 SKipList 中来了解读取过程&＃xff1a;

文档号&＃xff1a;{23, 700}


文档号&＃xff1a;23

  更新前的skipDoc数组如下所示&＃xff1a;

int[] skipDoc &＃61; {127, 383, 1151, 3455}


  当前 skipDoc 数组对应的 SkipList 如下所示&＃xff1a;

  由于文档号 23 小于 skipDoc 数组中的所有哨兵值&＃xff0c;故不需要更新 skipDoc 数组中的哨兵值&＃xff0c;那么直接遍历 docDeltaBuffer&＃xff0c;判断文档号23 是否在该数组中即可。

文档号&＃xff1a;700

  更新前的skipDoc数组如下所示&＃xff1a;

int[] skipDoc &＃61; {127, 383, 1151, 3455}


  文档号700小于1151、3455&＃xff0c;执行了步骤一之后&＃xff0c;判断出需要更新哨兵值的层数N为2&＃xff08;两层&＃xff09;&＃xff0c;即只要从level&＃61;1开始更新level&＃61;1以及level&＃61;0对应的skipDoc数组中的哨兵值。

  对于 level&＃61;1 层&＃xff0c;在执行了步骤二后&＃xff0c;更新后的skipDoc数组如下所示&＃xff1a;

int[] skipDoc &＃61; {127, 767, 1151, 3455}


  随后更新 level&＃61;0 层&＃xff0c;在执行了步骤二后&＃xff0c;更新后的 skipDoc 数组如下所示&＃xff1a;

int[] skipDoc &＃61; {767, 767, 1151, 3455}


  这里要注意的是&＃xff0c;level&＃61;0 层的 skipDatum 更新过程如下所示&＃xff1a;

  在更新的过程中&＃xff0c;跳过了两个 skipDatum &＃xff0c;其原因是在图3中&＃xff0c;当更新完 level&＃61;1 的 skipDatum 之后&＃xff0c;该 skipDatum 通过它包含的SkipChildLevelPointer字段&＃xff0c;重新设置在 level&＃61;0 层的哨兵值为 511&＃xff0c;随后在处理 level&＃61;0 时&＃xff0c;继续往下遍历 skipDatum 找到 767 > 700&＃xff0c;并更新 skipDoc &＃xff0c;然后通过 skipDatum&＃xff08;767 &＃xff09;对应的 PackedBlock 遍历看里面是否有 doc_id &＃61; 700&＃xff0c;有的话返回读取 doc_id &＃61; 700 的文档数据。

为啥使用跳表而不是Hash&＃xff1f;

  通过区间来查找数据这个操作&＃xff0c;跳表天然有序的数据结构效率比 hash 高的多

4. 倒排合并

  到这里还有另一个问题&＃xff0c;那就是当我们查询中出现了 name&＃61;‘Alan’ and name&＃61;‘Alice’ limit 0,20 该如何处理&＃xff1f;

  它会拆分为 term &＃61; ‘Alan’ 和 term &＃61; &＃39;Alice’的查询。分别得到每个term的倒排链&＃xff08;docId列表&＃xff09;&＃xff0c;再对多个倒排表做交集。那么倒排表怎么做交集呢&＃xff1f;

水平分桶&＃xff0c;多线程并行

有序集合1{1,3,5,7,8,9, 10,30,50,70,80,90}和有序集合2{2,3,4,5,6,7, 20,30,40,50,60,70}&＃xff0c;先进行分桶拆分【桶1的范围为[1, 9]、桶2的范围为[10, 100]、桶3的范围为[101, max_int]】&＃xff0c;于是拆分成集合1【a&＃61;{1,3,5,7,8,9}、b&＃61;{10,30,50,70,80,90}、c&＃61;{}】和集合2【d&＃61;{2,3,4,5,6,7}、e&＃61;{20,30,40,50,60,70}、e&＃61;{}】&＃xff0c;利用多线程对桶1&＃xff08;a和d&＃xff09;、桶2&＃xff08;b和e&＃xff09;、桶3&＃xff08;c和e&＃xff09;分别求交集&＃xff0c;最后求并集。

bitmap&＃xff0c;大大提高运算并行度&＃xff0c;时间复杂度O(n)

假设set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的所有元素都在桶值[1, 16]的范围之内&＃xff0c;可以用16个bit来描述这两个集合&＃xff0c;原集合中的元素x&＃xff0c;在这个16bitmap中的第x个bit为1&＃xff0c;此时两个bitmap求交集&＃xff0c;只需要将两个bitmap进行“与”操作&＃xff0c;结果集bitmap的3&＃xff0c;5&＃xff0c;7位是1&＃xff0c;表明原集合的交集为{3,5,7}

水平分桶&＃xff08;每个桶内的数据一定处于一个范围之内&＃xff09;&＃xff0c;使用bitmap来表示集合&＃xff0c;能极大提高求交集的效率&＃xff0c;但时间复杂度仍旧是O(n)&＃xff0c;但bitmap需要大量连续空间&＃xff0c;占用内存较大。